From kde-edu-devel Sun Jun 07 17:31:00 2020 From: Andreas Cord-Landwehr Date: Sun, 07 Jun 2020 17:31:00 +0000 To: kde-edu-devel Subject: Re: Rocs general graph layout implementation question. Message-Id: <2606569.HNWgkkToRv () weatherwax> X-MARC-Message: https://marc.info/?l=kde-edu-devel&m=159155106628748 On Montag, 1. Juni 2020 14:23:07 CEST Dilson Guimar=E3es wrote: > Hello, >=20 > I am a GSoC student working on the graph layout (drawing) capabilities of > 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 thoug= ht > 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. >=20 > 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 gra= ph > layout algorithms for specific kinds of graph. For those, I did not find a > library ready for use. >=20 > 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 and its > GitHub repository can be found here > . Maybe there are some issues > about adding more dependencies. Hi Dilson and thank you very much for your work on Rocs! And also thanks fo= r=20 this interesting question :) I am trying to look from a user story point of view at the problem and I ca= n=20 imagine the following user stories (not all of them might be important and= =20 some might even be out of scope). What comes into my mind are the following= =20 possible desires by our users: =2D As a user, I want to transform my graph such that it is easier to under= stand=20 because I manually analyze the graph with my eyes (this could mean for=20 example: minimizing number of crossed edges, moving nodes closer together; = I=20 am not sure if this means that everything should be on the visible area=20 because there should be zooming options) =2D As a user, I want to transform my graph into a certain format (e.g. a r= ing)=20 because it is an established layout in my community (I know P2P researchers= ,=20 who usually look at ring graphs; this could still mean that e.g. the number= of=20 crossing edges shall be minimized). =2D As a user, I want to run my own graph transformation algorithm because = I am=20 doing research in the graph drawing field (this might be already possible, = but=20 it is a very different use case from the above ones). Regarding the use of third party libraries. It is much preferred if we stic= k=20 to packaged libraries, which are at least available on OpenSuse (because ou= r=20 CI system is running there) and Debian, because it covers another big part = of=20 the Linux universe. But if it is a good library and we really want to use i= t=20 because it helps us a lot, we should talk to packagers if we can make it=20 available. -- Yet dependencies always come with a cost for maintenance... I= f=20 it is only a simple self-contained layouting algorithm, it also might be an= =20 option to only use their algorithm code and integrate it into Rocs (the LGP= L=20 license of that library would allow it). Cheers, Andreas