Rocs general graph layout implementation question.

[Dilson Guimarães]

Thank you for your input.

On Sun, Jun 7, 2020 at 2:31 PM Andreas Cord-Landwehr <cordlandwehr at kde.org>
wrote:

> On Montag, 1. Juni 2020 14:23:07 CEST Dilson Guimarães wrote:
> > Hello,
> >
> > I am a GSoC student working on the graph layout (drawing) capabilities of
> > Rocs <https://kde.org/applications/education/org.kde.rocs>. I am going
> to
> > include graph layout algorithms to compute the positions for all the
> graph
> > vertices, satisfying some constraints such as keeping every vertex inside
> > the drawing area. I have two options here: use an existing library to do
> > that or implement the algorithms directly. Because I am new here, I
> thought
> > it would be a good idea to ask for your opinion. What option do you think
> > is more appropriate? Even if there is no clear answer, I would like get
> > your opinion about the pros and cons of each option. I am providing more
> > information about each option below.
> >
> > The graph layout algorithms I would have to implement are optimization
> > algorithms, which I have some experience with because I do research on
> > optimization. A positive thing about implementing the algorithms myself
> is
> > that I would have more flexibility to make them better suited for Rocs.
> > Besides that, on future phases of this GSoC project, I will implement
> graph
> > layout algorithms for specific kinds of graph. For those, I did not find
> a
> > library ready for use.
> >
> > On the other hand, going with the library can speed things up. I found
> one
> > library that seems to provide a good amount of functionality. Its name is
> > libcola <https://www.adaptagrams.org/documentation/libcola.html> and its
> > GitHub repository can be found here
> > <https://github.com/mjwybrow/adaptagrams>. Maybe there are some issues
> > about adding more dependencies.
>
> Hi Dilson and thank you very much for your work on Rocs! And also thanks
> for
> this interesting question :)
>
> I am trying to look from a user story point of view at the problem and I
> can
> imagine the following user stories (not all of them might be important and
> some might even be out of scope). What comes into my mind are the
> following
> possible desires by our users:
> - As a user, I want to transform my graph such that it is easier to
> understand
> because I manually analyze the graph with my eyes (this could mean for
> example: minimizing number of crossed edges, moving nodes closer together;
> I
> am not sure if this means that everything should be on the visible area
> because there should be zooming options)
>

You are right. Having everything visible is not always desirable and,
sometimes, it is impossible. Currently, Rocs use scroll bars to solve this
problem.

The current version of the graph layout plugin I am developing allows the
user to control some parameters of the algorithm in order to customize  the
layout. However, the level of control is very limited. Some criteria such
as the emphasis on reducing the number of crosses between edges and
spreading nodes as evenly as possible  are not represented yet, because the
current algorithm does not support them directly. Once I add an algorithm
that does, I am thinking about having an user interface that lets the user
choose the emphasis of the algorithm.


> - As a user, I want to transform my graph into a certain format (e.g. a
> ring)
> because it is an established layout in my community (I know P2P
> researchers,
> who usually look at ring graphs; this could still mean that e.g. the
> number of
> crossing edges shall be minimized).
>

It is not easy to define what makes a graph layout good. Worse than that,
this definition changes from one use case to the other. Getting some
guidance from the user can help Rocs produce layouts that fulfills the
needs of the user. I am going to try to find a way to get such guidance
without having to support each "format" separately.

- As a user, I want to run my own graph transformation algorithm because I
> am
> doing research in the graph drawing field (this might be already possible,
> but
> it is a very different use case from the above ones).
>
>
I think this is already possible. Thanks to the comments given by Adriaan de
Groot, I am considering creating an example implementation of a layout
algorithm in JavaScript. This would be more useful for those learning
layout algorithms and those trying to run their own.


> Regarding the use of third party libraries. It is much preferred if we
> stick
> to packaged libraries, which are at least available on OpenSuse (because
> our
> CI system is running there) and Debian, because it covers another big part
> of
> the Linux universe. But if it is a good library and we really want to use
> it
> because it helps us a lot, we should talk to packagers if we can make it
> available. -- Yet dependencies always come with a cost for maintenance...
> If
> it is only a simple self-contained layouting algorithm, it also might be
> an
> option to only use their algorithm code and integrate it into Rocs (the
> LGPL
> license of that library would allow it).
>

Thank you for the explanation. For now, I decided to go with my own
implementation. I found out that I will have to customize some details and
parameters of the algorithm to achieve layouts that look nice. Although
some libraries can be customized in some ways, I think it is easier to do
in my own implementation


Best regards,
Dilson Guimarães.

>
> Cheers,
> Andreas
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.kde.org/pipermail/kde-edu/attachments/20200621/fad276d5/attachment-0001.htm>