Hello.The challenge is the visual presentation of information:

There is a graph that is formed randomly - information about the existence of a vertex of the graph and about who its parents and who is a child vertex is in relation to it.Oriented graph: Any vertex except a few initially specified has 1 or several parent vertices.( There may be no children).That is, any newly appeared vertex has a connection with 1 or several old ones.

Task: to represent this in the form of successive growth of the graph horizontally down from several original vertices(Initially, the vertices are not connected, but in the process of growth, the divided graphs are necessarily merged).
Its growth should be presented in such a way that the child vertices in the visual representation should be below their immediate parent.This condition does not apply to those peaks that have no direct connection.That is, figuratively speaking, the grandfather's brother may be lower than the grandson of this very grandfather for the sake visual presentation.

There is one more condition: at arbitrary moments of time a connection may appear between two randomly selected vertices.Let this be called an event A.When such a connection appears, one of the vertices becomes a parent and the other is a child.UPD(A link can only be oriented so that there is no closed loop between the peaks)

The condition of clarity is the following: as the graph grows, visually represent it so that it has the minimum number of intersections between the links(did not look confused).And when an A event occurs, redraw the visual representation of the graph so that the newly formed link is not too long, and the graph again had the minimum number of intersections of connections, and the above condition that all child vertices must be drawn below their immediate parents continued to work.

I ask you to suggest whether there are libraries for solving such problems in Python or javascript(I did not decide to implement the calculations of the coordinates of the vertices in the client’s browser or on the backend, but it’s preferable to count them in the browser).

Or a graph drawing algorithm, or at least articles and tutorials where similar tasks are covered.


1 Answers 1

Standard solution for static graphs: https://www.graphviz.org/maybe you can get the code from this library or logic for dynamics.

If you write yourself, you can start searching for logic here: alenacpp.blogspot.com/2006/03/blog-post_23.html

In general, the representation of arcs of a graph as springs with subsequent emulation of physics should suffice.

Also I recommend to google about topological sorting.
  • It seems that Sugiyama's method, mentioned in the article in the second link, is just what I need.
    The spring method is not interesting, but does not guarantee that the child elements will be below the parent
    – Bouncin'45 Jul 16 '18 at 18:19