The directed graph layout howto

Because there is a shortage on graph layout tools here is a howto to start programming it yourself and create a new program as opensource and make yourself and others happy.

This are the minimal steps:
1) parse the input into internal data structures
2) scan the data for cycles and reverse edges to break cycles
3) run dfs algorithm to put nodes in relative vertical levels
4) run sugiyama barycenter to put nodes in relative horizontal positions
5) run placement routine to set nodes at absolute (x,y) positions
6) runs drawing routines
7) additional routines

about 1:
The easiest parser is gml graph language or json graph languge
Then the xml based graph formats as gexf or graphml
The parsing of graphviz dot is very difficult and there are no opensource alternatives yet
parsing dot also needs parsing html and record labels data
The usual bison+flex can be used or a peg parser which can be easier
For testing a own simple graph language is recommended.

about 2:
just google for a yet-another algorithm how to find cycles and reverse needed edge directions

about 3:
google for dfs for a yet-another dfs routine and the new outgoing edges are placed at next level

about 4:
There is a nice GNU GPL barycenter with pdf's in C from prof. matthias stallman at:
https://github.com/mfms-ncsu/Crossing-Minimization
https://people.engr.ncsu.edu/mfms/

also C++ showgraph is GNU GPL and can be re-used
https://github.com/MIPT-ILab-Compilers/MIPT-Vis
https://code.google.com/archive/p/showgraph/
https://github.com/gml4gtk/miptgraph
or GNU GPL graphlet C++ source
https://github.com/GunterMueller/UNI_PASSAU_FMI_Graph_Drawing

also javascript dagre is recommended
https://github.com/dagrejs/dagre
or GNU GPL dgraph in javascript
https://github.com/speich/dGraph

about 5:
for placement the priority method is used or "brandes and koepf horizontal placement"
and example code is in graphlet and dagre see above links.

about 6:
Now for the drawing node (x,y) positions are available and edge coordinates,
so draw the boxes and lines using svg, postscript, gtk+ or qt5 or otherwise.

The whole graph layout in C is also in sfg.c at https://github.com/gml4gtk/singlefilegraph

about 7:
Much extra routines are added in all steps in many layout software for extra features.
The result can be a better drawing and much depends on the amount of drawing routines.

For C++ there is GNU GPL ogdf libary which is big and also creates many new problems.
For java are also few interesting graph layout libraries.

Note that real used dot graph data uses only a small part of graphviz features and
that means it is not too difficult to create a graphviz compatible program with a subset
of the dot languages supported that is actually usable with most used data.
One example is gml4gtk in C usable with gcc data supporting part of grapviz features
as GNU GPL Free software for Linux or windows at https://sourceforge.net/projects/gml4gtk/

Now start programming and reading the sources and few pdf's with good luck and happy coding!

Some problems with graphviz:

- use of graphviz does not improve know-how about graph topics for programmers or users

- graphviz cannot be combined with GNU GPL Free software and there is no guarantee it will not become closed software

- important information is not in the graphviz output which make it impossible to create own independant drawing routines or add own algorithms

- the parsing of dot is very difficult and there are no opensource alternative parsers then it does act as a vendor-lock-in

- graphviz acts as a black box for programmers and users

- graphviz is slow and barely usable with big gcc data files and that cannot be changed because dot is a kinof closed program, but gml4gtk can do it with newer ways to handle the data

- graphviz has undocumented and even hardcoded limitations, only known if you are really reading the difficult source code

- graphviz has many never used features and wasting cpu time on it which makes it easier to
make a replacement without all those nonsense features, and the real difficult problem is to
find and program what really makes sense in the algorithms. Almost all graph layout software
has far too many unneeded complicating features resulting in a slow and unreliable program.

- the fsf is not interested in gnu gpl graph layout solutions partly because the specialistic topic and graphviz just works for most users, but not for me

if you want to program solely GNU GPL Free graph layout solutions, you can contact me and there are more pointers to ways to get it programmed as GNU GPL Free software


The GNU GPL makes sure it does not end as closed source software which does not benefit the users.

ps:
Also using github copilot is not a copyright problem if the snippet is not uniq enough
to reach the treshold of originality see
https://juliareda.eu/2021/07/github-copilot-is-not-infringing-your-copyright/
or here in 
github-copilot.pdf