ForceDirectedLayout avoiding link collisions

I’ve another question for you. I’m not expecting the final solution, but just some guidelines would be great.
I’m experimenting with ForceDirectedLayout and tweaking arrangement options (spring length, electrical charge, etc…), I obtained a good result with my data, i.e. the nodes are correctly placed without overlaps.

However, I realized that nodes are positioned taking into account only the positions of the other nodes and not where the actual links are drawn. You can see this behavior in the following screenshot.

Manually dragging some nodes around, I can obtain the desired results, where nodes and links are not colliding, and labels are visible, too.

I see from the Dynamic Ports sample that using custom connections, node ports, avoidNodes and JumpGap, links can be kept parallel and not colliding, but I was hoping that this overhead could be avoided for a simpler case like mine, where there is no interaction, just an alternative view of data otherwise displayed with a TreeLayout.

Do you have some suggestions on how to automatically get an better initial positioning of nodes taking into account link/node collisions?

Many thanks,
Guido

In general there is no good solution that does not involve rerouting links and shifting link labels, and ForceDirectedLayout does not do that. (Although it’s on the list of features we’d like to implement some day.)

Sorry. I suppose you could reduce such occurrences by detecting them, programmatically moving nodes, and then maybe doing some more layout. But this is complicated to get right.

Ok, thanks, I will take a look at rerouting, labels should come as a consequence, even if simple node re-positioning keeping straight links would be much simpler and elegant.

Just thinking out loud, maybe an idea could be to consider the median points of every link as additional “masses” just like nodes, in order for the algorithm to consider the repulsion needed to separate them from each other. This should be not so hard to add to the current iterative optimization…

Yes, that’s right – I remember implementing this for GoDiagram (or maybe it was for GoXam), and that helped with avoiding overlapping labels. I don’t think we’ve ported that code to GoJS. Maybe I can find it, or else I’ll have to reimplement it from scratch.

Ok, let’s hope for a future update :)
Thanks for the information!

I had to reimplement this, basically treating all midlabels as if they were separate vertexes that push and can be pushed by other vertexes. However I found that although the number of overlaps between labels and nodes and labels and labels greatly decreased, they were not guaranteed to be avoided and the area covered by the graph became much larger, due to the outward pressure from the midlabels acting as extra vertexes.

So I wasn’t happy with that solution. I suggest instead that you increase the electrical repulsion and the length of the springs and ForceDirectedLayout.maxIterations. That will help a little bit, even though it still cannot guarantee that there will be no overlaps between nodes or between nodes and midlabels.

Some day we’ll come up with a better solution. I’m sorry I cannot provide it right now.

Yes, that solution was what I was thinking about, too.

I faced a similar issue when working on system optimization during my university course. Could it be of any help to just reinitialize the algorithm from another random start if the final energy (sum of spring forces between nodes and labels) is too high? I am referring to something like a Simulated Annealing procedure in order to avoid local maxima/minima.

Yes, this is what I am doing for now, the graph is more spread and separated, but some nodes still need manual repositioning to avoid collisions of labels.

No problem! In the meantime, for my curiosity, I will make some private test on optimization algorithms for generic graphs, I found some nice bibliography here, even if it seems they do not consider labels on links… if I found a better solution, you will be the first to know!

You are doing a wonderful job with GoJS software and Support forum, my personal congratulations! :)

Thanks for your kind comments. Yes, I’m familiar with simulated annealing; I spent time with Geoff Hinton in the early 80’s, in a previous lifetime. And I’m familiar with those works you found in a bibliography, since we used some of them when we first created our layouts.

@walter @g.bartoli did you resolve this issue??

We haven’t come out with an example layout that does what I think was desired. But we’re considering doing so.

Another (simple but not a perfect) idea is to just use Link label segmentOrientation to orient the angle of the label object relative to the angle of the link segment. You end up with a less cluttered look with the same data.