[Gammaray-interest] Graph library
Kevin Funk
kevin.funk at kdab.com
Thu May 23 19:34:39 CEST 2019
On Thursday, 23 May 2019 18:50:02 CEST Christian Gagneraud wrote:
> 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.
Okay, that looks indeed like a different use case than KDSME's. The layouting
part in KDSME is just a tiny part of its feature set. The biggest focus lies
on the user interface integration, i.e. making interaction with the states/
transitions possible. And well, it's indeed state chart specific, not a
generic graph layouting tool. And there's lots of plumbing code around it
which makes it nice to use with existing state machine functionality in Qt
(QtSCXML & QStateMachine). So, very domain-specific after all.
At some point you need to bite the bullet and just write code for one use-
case; I've tried the too-generic approaches (wrapping GraphViz API in an
"open-minded" way) before, which failed.
> 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. :(
Let me also mention: GraphViz also has it's quirk when just being used via the
C API (or via .dot files): With more complex graphs, one can easily get the
GraphViz layouting algorithms to choke, in other words crash in funny ways
you'll never be able to debug without having read and understood one of the
accompanying papers:
https://graphviz.gitlab.io/theory/
How all the different node/edge/graph attributes actually affect each other,
or "break" each other, is another story which isn't entirely fun to debug.
That combined with the different graph layouting algorithms (dot, neato, fdp,
...) gives you a nice matrix of options which may all fail to work in
unobtrusive ways :)
tl;dr: Working with Graphviz can get you frustrated pretty easily. You've been
warned :)
> 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 indeed use Graphviz to only give me the layout, paths, bounding rects, etc.
-- but do the drawing of the items mostly myself. This has some benefits on
the UI side: I can freely apply animations, mouse-hover effects, etc. pp..
> 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.
I looked at KCacheGrind/KGraphViewer myself when working on GraphViz wrappers;
but I don't think they do anything super special. It's always the same
approach: Placing a thin/usable C++ abstraction layer over the (awful)
GraphViz C interface and then use this abstraction.
During my early days as KDABian I actually attempted to factor out the
internals of KGraphViewer as a library [1] but didn't manage to: due to lack
of commitment, time and motivation in the end. It looked like I was trying to
go a radically different approach while still maintaining backwards
compatibility with the way KGraphViewer worked which was doomed to fail.
[1] https://marc.info/?l=kde-commits&m=129226077719174&w=2
Looking forward to your results!
Regards,
Kevin
> 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_201701
> > > 09_
> > > 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
--
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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 5322 bytes
Desc: not available
URL: <http://mail.kdab.com/pipermail/gammaray-interest/attachments/20190523/149d74dd/attachment.p7s>
More information about the Gammaray-interest
mailing list