Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Please consider providing Graph Reachability Matrix predicate #837

Open
LebedevRI opened this issue Aug 27, 2024 · 1 comment
Open

Please consider providing Graph Reachability Matrix predicate #837

LebedevRI opened this issue Aug 27, 2024 · 1 comment

Comments

@LebedevRI
Copy link
Contributor

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
Copy link
Contributor Author

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants