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

All other things being equal preserve vertex order #41

Open
oxinabox opened this issue May 14, 2024 · 0 comments
Open

All other things being equal preserve vertex order #41

oxinabox opened this issue May 14, 2024 · 0 comments
Labels
enhancement New feature or request

Comments

@oxinabox
Copy link
Owner

Right now we do not take into account the order of the vertices in the graph at all,
except through the force_order functions and the like, which add a hard constraint on them.

However, there is a good change that the order is semantically meaningful,
while being less crucial than minimizing crossing. And so we should try to preserve it.
E.g. they might be ordered alphabetically.
In cases where minimizing crossings is easy (like a tree) then this can dominate the layout.

We should be able to add a prerve order term to the objective, and give it a very small weight such that any crossing always dominates it. Weighting with 1/num_vertices^2 should do that.
The term for preserving order should be to go through and add a term for each layer summing how often something of lower index is before something of higher.

One significant effect of this change is that it will make the ordering_problem solution unique,
and so will mean that adding more solve time will never find a better arrangement by searching over the existing solutions.
So it is arguably breaking, though I think we can just deprecate the argument for max_time and not tag a breaking release and noone will care. It rarely found a better solution anyway -- by symmetry often the next best solution was to just invert the order which still has equal score on both optimization problems.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

1 participant