search

MiniZinc / libminizinc

The MiniZinc compiler
http://www.minizinc.org
Other
514 stars 80 forks source link

Please consider providing Graph Reachability Matrix predicate #837

Open LebedevRI opened 2 months ago

LebedevRI commented 2 months ago

It would have been rather useful to me when i was trying to write a model, and i couldn't quite come up with anything good on a spot, and thus after much pain ended up with: https://github.com/LebedevRI/minizinc-graph-reachability-matrix-predicate.mzn

Unfortunately it ends up having O(n^3) complexity, as benchmark notes, but that is only because connected() is itself O(n^2). There may perhaps be a better formulation for all that, but i'm not seeing it currently. The results are already much better than i had hoped.

(There may be a standard set of inefficiencies in minizinc itself, not sure how much i want to look into that given how it's developed and tested...)

LebedevRI commented 2 months ago

FYI i'm looking at a non-cubic implementation, hang on.