Review the "Manhattan" layout algorithm

[tbouffard]

This is the way we are building the graph under the hood: The Manhattan distance function computes the distance that would be traveled to get from one data point to the other if a grid-like path is followed.

resources

• https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1039&context=ecetr
• https://stackoverflow.com/questions/1285623/manhattan-layout-algorithm
• https://en.wikipedia.org/wiki/Organizational_chart
• http://www.improvedoutcomes.com/docs/WebSiteDocs/Clustering/Clustering_Parameters/Manhattan_Distance_Metric.htm

mxgraph java implementation

• https://github.com/jgraph/mxgraph/tree/v4.2.2/java/src/com/mxgraph/layout

used by bpmn.io for autolayout (there are refs to this algorithm described in diagram-js)

• https://github.com/bpmn-io/diagram-js/blob/develop/lib/layout/ManhattanLayout.js#L197
• https://github.com/bpmn-io/bpmn-auto-layout/blob/fa13b219c470a46ea0d1044d04d19d9183c7ac40/lib/DiUtil.js#L48

[tbouffard]

I found this JS lib that manages the Manhattan layout greatly!

Manhattan layout

demo: https://x6.antv.vision/zh/docs/api/registry/router#manhattan

Metro layout

demo: https://x6.antv.vision/zh/docs/api/registry/router#metro