[Gammaray-interest] Graph library

[Christian Gagneraud]

On Thu, 23 May 2019 at 02:31, Kevin Funk <kevin.funk at kdab.com> wrote:
> Let me know what you think about KDSME, and (potentially) why it doesn't fit
> your use-case?

The code is interesting indeed: the _wrapping code, the quirk handling
("C" lang, DPI, const correctness, ...).
Unfortunately the approach and the goals are radically different.

I'm trying to "stick" to the graphviz API as much as possible, and
just be a convenient C++/Qt wrapper with no perf impact and no
limitation.

KDSME use graphviz in an ad-hoc way to layout state machines, what i'm
after is a "data visualisation" system, where one can
choose/experiment b/w different layout algorithm, extract/filter
connected components, find paths b/w nodes/clusters, change the
"central" node(s), do transitive reductions, use discriminating
clusters, ... Check [1] for a very simple example of looking at the
same data set using different algorithms.

I see a lot of potential, but my feeling is that the difficulties are
performance/scalability (layout/s), stability/predictability and
usability ([2] is a bit of a crazy zoo). I spent a fair bit of time
formalising/filtering all these parameters.

My goal is to display big graphs (thousands of node and edges, maybe
even more, the bigger the better), and give a bit of dynamic to the
view (quick answer to filtering).
I haven't made any measurement yet, and there are different areas of
interests here: construction, visiting, layout and rendering. The
biggest unknown is unfortunately the "layout" phase. There's hooks for
libcgraph, there's facilities for efficient traversal (flattening),
and you can use many tricks for QGV. But there's a big rotten cherry
on the cake: gvc_t in not thread safe. :(

Another difference with KDSME is the rendering, I let graphviz drive
the rendering by injecting a custom Render/Device plugin into
graphviz, i guess this is just a minor convenience (you only need to
implement drawEllipse/Polygon/Polyline/BezierCurve), the advantage is
that you get exactly the same rendering as when using the dot command
line, including fancy decorations, weird graphical artifact (!), which
means that when you hit "export as dot", you'll get the same rendering
as with the graphviz command line ("no regerts"  as they say [3]).

I haven't looked at KCacheGrind, HeapProfiler and the likes, they
might have another specialised usage of graphviz (or maybe another
framework). Have to check it out.
Their use case is squarified tree maps, which is what graphviz
"patchwork" provides. At this stage, that's not something i'm
interested in.

Thanks,
Chris

[1] https://rich-iannone.github.io/DiagrammeR/img/Graphviz_Engines.png
[2] https://www.graphviz.org/doc/info/attrs.html
[3] https://www.youtube.com/watch?v=uKwG5IgqFF4



>
> Cheers,
> Kevin
>
>
> > Are you interested?
> >
> > If so, then i would like to submit the first part: libcgraph.
> > These wrappers allows to create, manipulate and "walk" graphs. These
> > are value class that encapsulate underlying C pointers (and hide the
> > cgraph crazy/messy API). My value class based approach is IMHO very
> > efficient, but has few drawbacks. I'm happy to discuss and rework it.
> >
> > Next stage would be the wrapper for the layout and the rendering, I've
> > already implemented the layout wrappers and a "hot-pluggable" render
> > plugin  that renders a layed out graph into a QGraphicsScene. It's
> > surprisingly very lightweight and was easy too. This is IMHO way
> > better than invoking "dot" from the command line to display an SVG.
> > This will allow to access the full layed out graph structure,
> > including clusters, sub-graph, etc...
> >
> > After that, i would like to propose "attributes" handling, which i'm
> > still working on.
> > The attributes allows you to configure the layout algorithms (dot,
> > neato, ...)  and tweak a few geometric/visual things at
> > graph/node/edge level. So far, i've taken the path of wrapping the
> > whole graphviz string pairs attribute zoo [1] behind a carefully
> > selected and named sub-set implemented as enums/qvariant, I think the
> > pain was worth the effort.
> >
> > Finally, there will be a need for export in dot/xdot files, and a
> > proper "GraphWidget" UI. I am confident with handling this too, see
> > eg. [2].
> >
> > But then, ... We'll need some real usage within gammaray! :)
> >
> > Chris
> >
> > [1] https://www.graphviz.org/doc/info/attrs.html
> > [2]
> > https://gitlab.com/chgans/le-ipc2581-viewer/raw/master/Screenshot_20170109_
> > 135029.png
> >
> > PS: Demo time!
> > using namespace graphviz;
> > void test3()
> > {
> >     auto rootGraph = Graph("root", DirectedGraph);
> >     auto graph1 = rootGraph.addSubgraph("cluster_1");
> >     graph1.setLabel("Cluster#1");
> >
> >     auto node1 = graph1.addNode("1 circle/solid");
> >     node1.setShape("circle");
> >     node1.setStyle("solid");
> >      ...
> > }
> > int main(int argc, char *argv[])
> > {
> >     QApplication a(argc, argv);
> >     auto l = new Layout();
> >     auto w = new QMainWindow();
> >     w->showMaximized();
> >     auto s = new QGraphicsScene(w);
> >     auto r = new Render(s);
> >     auto v = new QGraphicsView();
> >     v->setScene(s);
> >     v->scale(1.0, -1.0); // Y down
> >     w->setCentralWidget(v);
> >     auto g = test3();
> >     l->render(r, g, HierarchicalLayout);
> >     return a.exec();
> > }
> >
> > and the result: https://i.imgur.com/MInEFJX.png
> > _______________________________________________
> > Gammaray-interest mailing list
> > Gammaray-interest at mail.kdab.com
> > https://mail.kdab.com/mailman/listinfo/gammaray-interest
>
>
> --
> Kevin Funk | kevin.funk at kdab.com | Senior Software Engineer
> KDAB (Deutschland) GmbH, a KDAB Group company
> Tel: +49-30-521325470
> KDAB - The Qt, C++ and OpenGL Experts