Improve crossing-aware port ordering algorithm #882
Description
Who would benefit from this feature?
Users
What is this feature about?
The new crossing-aware port ordering algorithm implemented in #759 is quite good at minimizing all crossings with a certain kind of datasets (small-ish datasets, medium datasets without too much cycles, etc...) but is also pretty bad at improving readability with other datasets (larger datasets, denser datasets...).
@louisgreiner kindly listed multiple documented cases, where the algorithm performs poorly here.
There are various ways we could explore to either improve the current algorithm, or design a new one. Here are some leads already:
- Try different roots - using different centrality scores, for instance
- Try to isolate sub-graphs by ignoring some edges, to reduce the complexity and improve local solutions
- Try some random-ish permutations maybe, when the algorithm converges too soon, to try to kickstart it again
- Add new heuristics to move unavoidable crossings from between nodes to inside a node, when it would improve readability
Why is this feature valuable?
This feature matters because it would:
- improve readability
- provide better visuals of the datasets