[kgraphviewer-devel] Re: kgraphviewer libkgraphviz corrections

Kevin Funk krf at gmx.de
Mon Mar 21 22:09:55 CET 2011


Monday 21 March 2011, "Gaël \(aka Kleag\)" <kleag at free.fr>:
> Hi Kevin,

Hey Gaël,

> I have started to use your version of kgraphviewer to build an ontology
> viewer. It is really usefull to have a direct API to the graph. But I have
> found that you have maybe been a little bit excessive on some
> simplifications

The work invested in kgraphviz was part of my thesis. As you may have noticed 
by the stalling commit rate the thesis is already over. ;)
Note however, that I am still interested in viewing and manipulating graph 
data sets. I must admit, that I've had quite a few problems polishing up the 
kgraphviewer code base and digging through different KGraphViewer and the more 
ugly Graphviz bugs.
I dropped a lot of redundant code during the transition to kgraphviz and in 
general paid most of my attention on increasing layouting performance.

Sorry for not replying earlier, the past month(s) I've been very short of time 
both caused by real life and work. Some conclusions on the whole project can 
be found later on.

Let's start with your questions.

> For example, you have oversimplified the DotGraph::addNewEdge method. Here
> are the problems with your version:
> - a detail, you have renamed the src and tgt parameters to sourceState and
> targetState. I don't understand why ? They are not states but nodes.

My project involved displaying large state charts. I didnt try to convert 
kgraphviz into a state chart drawing library, though. This is still a pure 
graph library. However, these two strings must have slipped through :)
Feel free to fix.

> - you have replaced the elementNamed calls by node Named. This is an error
> as edges can also link subgraphs.

Sure. This is a general problem in kgraphviewer. The distinction between the 
different graph elements is not clear and not type-safe. E.g. the setters for 
source and target nodes for Edge accepted arbitrary graph elements, for 
example other edges.

> - that's why there was backoff calls using the "cluster_" + elementNamed,
> dur to the way graphviz names the subgraphs. It should not be removed

I tried to use clustered sub graphs as well but afair it didnt really work 
when I started working on kgraphviewer. This part is badly solved in Graphviz. 
Feel free to improve that.

> - concerning the naming of the new edge id, the method you used is not
> sure: there can be also an edge named nbedges+1 in the dot file. That's
> why I used an uuid which is a bit too long but which insures it is uniques
> - finaly if the id is given in the attribute, you must use it such as to be
> able to save the graph exactly as you read it.

Possible. In general I did not work that much on the DOT I/O part. My projet 
was based on accessing the Graphviz API directly. However, as you may imagine, 
that UUID functionality caused problems when re-layouting using the Graphviz 
library (not command-line) as custom edge ids could not be saved back to the 
Agedge_t objects.

> Would you mind if I commit the corrections of these problems and possibly
> also others I could find ?

I do not mind at all. I am very happy if my work is of any value and gets 
merged back to the master branch. Currently I can't really offer any help for 
this (but will do this later on).

In conclusion, I spent a lot of work on improving performance in kgraphviz and 
cleaning up the interfaces. However, I missed spending more time on actually 
refactoring the concrete graph access API. To be honest, I did not even plan 
to invest that much work into KGraphViewer (fixing bugs) for my thesis.

To be more concrete, I think the whole abstraction level of KGraphviz over 
Graphviz is too low and error-prone. The sub graph abstraction is not well 
designed (and I didn't really improve that during the project). My use case 
included multiple nested sub graphs and creating these programmatically caused 
of lot of headaches with the current design. I didnt manage to fix this in 
time, however.
Another problem I tried to solve was the clear distinction between direct 
library access and command-line tools for layouting the graph. Personally, I 
would choose one (preferably direct Graphviz access) and drop the other one. 
Maintaining and synchronising both is a headache.

In my (currently limited spare-time) I started writing some generic graph API 
independent from but using Graphviz as a backend. Not sure if I find time to 
improve it or release it at some point but it may be useful to KGraphViewer as 
well. I am trying to do that with a high abstraction level in mind.

> Best regards,
> 
> Gaël

As I said, feel free to commit to the kgraphviz branch as you like. I might 
give a hand when I find the time. Not before the begin of April, though.

Best regards

-- 
Kevin


More information about the kgraphviewer-devel mailing list