search

backtracking / ocamlgraph

OCaml graph library
http://backtracking.github.io/ocamlgraph/
Other
232 stars 60 forks source link

FASH algorithm for minimal feedback arc sets #121

Closed tbrk closed 2 years ago

tbrk commented 2 years ago

Implementation of a published heuristic (FASH of Eades, Linh, and Smyth) for calculating a minimal (not necessarily minimum) feedback arc set. Extended with support for obligatory arcs (not to be included in the feedback arc set) and weights (lighter is better).

backtracking commented 2 years ago

Thanks @tbrk for this contribution to OCamlGraph!

backtracking commented 2 years ago

@tbrk You are using Map.to_rev_seq which requires OCaml >= 4.12. (Currently, OCamlGraph compiles with OCaml >= 4.03.) Since the use of Seq is delimited to function max_from_deltas, is there any chance you can rewrite this function to avoid this dependency? (does not look obvious at first sight...)

tbrk commented 2 years ago

Ah... I had forgotten that detail. That function is indeed central to the current implementation. It's obviously not worth losing compatibility with OCaml 4.03 (2016-04-25) and requiring OCaml >= 4.12 (2021-02-24) for this single function. I'll see if I can rework things to avoid using it.