Rocs general graph layout implementation question.

[Andreas Cord-Landwehr]

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)
- 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).
- 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).

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).

Cheers,
Andreas