0

The problem: Looking for quite some time for a js graph library to create a directed graph (e.g. using dagre layout), with the constrain of non-overlapping edges.

Steps until now

  1. Started with cytoscape.js but as it seems, such a feature doesn't exist.
  2. Continued on with an svg based solution (considering that all elements are in the DOM), d3.js using the dagre-d3, but still the information in the DOM is the path route.

Objective

  1. Find a way to detect edge overlapping, either canvas or svg based.
  2. Create a custom layout to respect this constrain. Will use this as a metric for my convergence algorithm.

Graphical Representation

Below a graphical representation of the objective. I want to detect that edges 0>1 and 2>3 are overlapping.

Any ideas, thoughts are welcome. If there is something wrong with my logic, corrections/suggestions are more than welcome. enter image description here

Gr3at
  • 330
  • 6
  • 12

1 Answers1

3

Finding edge crossings (line intersections) is a fairly simple bit of geometry which is explained here --> https://stackoverflow.com/a/18234609/368214

But then minimising such edge crossings in a graph (zero edge crossings are only possible in planar graphs) is one of the great research challenges of graph layout - https://cs.stackexchange.com/questions/14901/how-to-reduce-the-number-of-crossing-edges-in-a-diagram

Some graph layouts for specific graph types like DAGS such as Sugiyama aim to reduce crossings and similar cytoscape layouts are available at yfiles if that helps (i.e. the hierarchic layout) --> http://apps.cytoscape.org/apps/yfileslayoutalgorithms

mgraham
  • 6,147
  • 1
  • 21
  • 20
  • Thanks for the resources. Cytoscape's app seems good but not applied in js (just for the desktop app if i get it right). The second url is rather informative. I got an idea from there, to evaluate each point but feels excessive. Do you know if i can manually render each pixel of a line in svg or canvas? – Gr3at Feb 19 '21 at 12:52
  • Probably the easiest way to do that is look at the stroke-array functions for each: https://developer.mozilla.org/en-US/docs/Web/SVG/Attribute/stroke-dasharray https://developer.mozilla.org/en-US/docs/Web/API/CanvasRenderingContext2D/setLineDash – mgraham Feb 19 '21 at 13:08
  • The answer is not exactly what i was hopping for, but as it seems there is not an out of the box solution to my problem and your answer provided useful information pointing to the right (in my opinion) direction. Thanks for the resources. – Gr3at Feb 22 '21 at 14:15