Pinning node positions in layouts
Closed this issue · 12 comments
A feature where positions of some nodes could be pinned so that they don't get moved by the layout algorithm would
probably be quite useful. This feature is known as pinning in GraphViz. This arises in many graph visualization tasks (eg. artificial neural networks) where there are somehow 'special' nodes (eg. input and output) that should be easy to find in a graph visualization.
There seems to be a "freezing" feature in BarnesHutLayout, but freezing nodes doesn't seem to do anything and all the implemented layout algorithms in both gs-core and gs-algo seem to ignore it. If this functionality can be implemented in the current system, then this is probably a documentation bug.
Indeed, this feature is in the works but its goal was to use it internally in the viewer. With the github code, you can already put a "layout.frozen" attribute on a node. Its effect is to make the layout stop moving the node but still respect its x and y attributes as set by the user. The problem actually is that if you click on the node, the "layout.frozen" attribute will be removed : the viewer uses it also to allow moving a node while a layout is running.
A possible solution to this would be to have two attributes, one used by the viewer and one usable by the user, like say "layout.pin" to force a node to stay at a given position.
The current freezing behavior would work at least for my purposes, but it doesn't seem to have any effect in any of the layout implementations.
Is this the right usage for it? I also tried to use the layout API's freeze node directly without success.
node.addAttribute("ui.frozen");
node.addAttribute("x", 0.0);
node.addAttribute("y", 0.0);
It seems that the layout algorithm (well, all of them, but I've mostly tested the SpringLayout) just ignores the frozen-flag. There's also no checks for frozen nodes in the SpringLayout implementations and it seems to move the particles directly, although I still am a bit uneducated on how the layouting architecture works.
The attribute is "layout.frozen". It seems to work for me actually, but I did not tested it thoroughly. It will probably need more work.
Could you give me a small example, as I can't manage to get it work?
Antoine Dutot notifications@github.com wrote:
The attribute is "layout.frozen". It seems to work for me actually, but I did not tested it thoroughly. It will probably need more work.
Reply to this email directly or view it on GitHub:
#74 (comment)
Here is the small test I used (with the latest nightly builds).
Graph graph = new SingleGraph("pinning");
Node A = graph.addNode("A");
Node B = graph.addNode("B");
Node C = graph.addNode("C");
Node D = graph.addNode("D");
graph.addEdge("AB", "A", "B");
graph.addEdge("BC", "B", "C");
graph.addEdge("CD", "C", "D");
A.addAttribute("layout.frozen");
D.addAttribute("layout.frozen");
A.addAttribute("xy", 0, 0);
D.addAttribute("xy", 2, 0);
graph.display();Keep in mind that this will probably badly interact with the way the layout works. For example, the default layout tries to enforce an edge length of 1 (graph unit), so, as in the example above, the placement of free nodes will probably not be what you expect. More work is needed on the layout to fully support the feature.
Thanks a lot! Your example does work, for me too (with latest git), but for some reason my application does not. However, there are a lot of differences, my graph is a fully connected directed multigraph with weighted links and I'm trying to freeze four nodes. For some weird reason the frozen nodes seem to in some conditions form a "diagonal", ie their coordinates seem to be of form (x, x) and even weirder is that applying styling to the edges affect the behavior (I've fixed the seed in the SpringLayout's random number generation).
I'll look in to this more tomorrow and try to post a reproducible test case. But I think it should be considered that the error is on my end before I provide this.
No this is a "bug" in the layout. In fact when a node is first connected to another (when the first link appears), the layout tries to move the node close to the other. This should not happen when the link is frozen. I have pushed a change to do just that. This should appear in the nightly builds tomorrow night (given that we are past midnight ;-) )
However I do not know why the styling may affect this ?
Tell me if it works.
I did some testing and it's probably some kind of a race condition. The newest git helped it a bit, but it still breaks quite often, especially with larger graphs. Race condition would also explain the weird behavior with the styling. The following breaks it for me almost every time, but YMMV as it seems to be quite sensitive to the sleep duration. Sometimes it gives the "diagonal", sometimes something else and sometimes works as it should.
import org.graphstream.graph.implementations.*;
import org.graphstream.graph.*;
import org.graphstream.ui.layout.springbox.implementations.SpringBox;
import org.graphstream.ui.swingViewer.Viewer;
import java.util.Random;
import java.lang.System;
import java.lang.Thread;
public class FreezeTest3 {
public static void main(String argv[]) throws Exception {
System.setProperty("org.graphstream.ui.renderer",
"org.graphstream.ui.j2dviewer.J2DGraphRenderer");
MultiGraph g = new MultiGraph("test");
Viewer viewer = g.display(false);
g.addAttribute("ui.antialias");
g.addAttribute("ui.quality");
g.addNode("0");
g.addNode("1");
g.addNode("2");
g.addNode("3");
g.addNode("4");
g.addEdge("0_0", "0", "0", true).addAttribute("layout.weight", 1.227542);
g.addEdge("0_1", "0", "1", true).addAttribute("layout.weight", 2.800382);
g.addEdge("0_2", "0", "2", true).addAttribute("layout.weight", 1.555942);
g.addEdge("0_3", "0", "3", true).addAttribute("layout.weight", 1.458835);
g.addEdge("0_4", "0", "4", true).addAttribute("layout.weight", 5.358586);
g.addEdge("1_0", "1", "0", true).addAttribute("layout.weight", 34.739941);
g.addEdge("1_1", "1", "1", true).addAttribute("layout.weight", 6.793453);
g.addEdge("1_2", "1", "2", true).addAttribute("layout.weight", 4.321183);
g.addEdge("1_3", "1", "3", true).addAttribute("layout.weight", 4.722595);
g.addEdge("1_4", "1", "4", true).addAttribute("layout.weight", 3.855663);
g.addEdge("2_0", "2", "0", true).addAttribute("layout.weight", 3.940225);
g.addEdge("2_1", "2", "1", true).addAttribute("layout.weight", 6.686229);
g.addEdge("2_2", "2", "2", true).addAttribute("layout.weight", 3.365270);
g.addEdge("2_3", "2", "3", true).addAttribute("layout.weight", 3.579588);
g.addEdge("2_4", "2", "4", true).addAttribute("layout.weight", 12.345065);
g.addEdge("3_0", "3", "0", true).addAttribute("layout.weight", 1.000000);
g.addEdge("3_1", "3", "1", true).addAttribute("layout.weight", 8.582073);
g.addEdge("3_2", "3", "2", true).addAttribute("layout.weight", 26.649030);
g.addEdge("3_3", "3", "3", true).addAttribute("layout.weight", 4.708364);
g.addEdge("3_4", "3", "4", true).addAttribute("layout.weight", 39.450249);
g.addEdge("4_0", "4", "0", true).addAttribute("layout.weight", 14.329541);
g.addEdge("4_1", "4", "1", true).addAttribute("layout.weight", 13.686543);
g.addEdge("4_2", "4", "2", true).addAttribute("layout.weight", 24.973300);
g.addEdge("4_3", "4", "3", true).addAttribute("layout.weight", 4.874955);
g.addEdge("4_4", "4", "4", true).addAttribute("layout.weight", 7.091967);
Thread.sleep(100);
g.getNode("0").addAttribute("xy", 0.0, -1.0);
g.getNode("0").addAttribute("layout.frozen");
g.getNode("1").addAttribute("xy", 0.0, 1.0);
g.getNode("1").addAttribute("layout.frozen");
g.getNode("2").addAttribute("xy", 10.0, -1.0);
g.getNode("2").addAttribute("layout.frozen");
g.getNode("3").addAttribute("xy", 10.0, 1.0);
g.getNode("3").addAttribute("layout.frozen");
SpringBox layout = new SpringBox(false, new Random(0));
viewer.enableAutoLayout(layout);
}
}
I can try to look into it, but somebody more acquainted with the codebase will find the bug a lot faster.
Oh, and as we are entering the voodoo-realm, here are some of my specs:
java -version:
java version "1.6.0_24"
OpenJDK Runtime Environment (IcedTea6 1.11.1) (6b24-1.11.1-4ubuntu3)
OpenJDK Server VM (build 20.0-b12, mixed mode)
uname -s -r -v -p: Linux 3.2.0-25-generic-pae #40-Ubuntu SMP Wed May 23 22:11:24 UTC 2012 i686
Distro: Ubuntu 12.04
Edit: Also happens with Oracle's JDK/JVM, so it's not another OpenJDK oddity.
java version "1.7.0_05"
Java(TM) SE Runtime Environment (build 1.7.0_05-b05)
Java HotSpot(TM) Server VM (build 23.1-b03, mixed mode)
In fact with this one it seems to break more often. Without the sleep it often gives the diagonal and with the 100ms sleep it gives practically always (just got the same result ten times out of ten) the "mess" (ie seems to just ignore the freeze).
Actually, the layout owns its own thread, the viewer its own thread and your graph runs in the main thread.
main-thread ----> viewer-thread ----> layout-thread
Each thread has its own event loop, and waits for "graph" events from the other. But it can take time. So just activating the layout at the end of the program will not ensure it runs when all the graph events are received by the layout. It can run before all graph events (attribute "frozen" or "xy") are issued.
Furthermore when you issue an "xy" event, time can pass before the "frozen" event is received. During this time the layout can still move the node. As we are dealing with threads, this time may be sufficient to indeed move the node far from your "xy" location. "xy" events are always honored by the layout, but if the node is not yet frozen, it will move from this location to the "best" location as the layout computes it.
However the order in which events are processed is guaranteed, therefore by merely putting the "xy" event after the freeze, you should obtain what you expect:
g.getNode("0").addAttribute("layout.frozen");
g.getNode("0").addAttribute("xy", 0.0, -1.0);
g.getNode("1").addAttribute("layout.frozen");
g.getNode("1").addAttribute("xy", 0.0, 1.0);
g.getNode("2").addAttribute("layout.frozen");
g.getNode("2").addAttribute("xy", 10.0, -1.0);
g.getNode("3").addAttribute("layout.frozen");
g.getNode("3").addAttribute("xy", 10.0, 1.0);And you can even remove the Thread.sleep().
OK, this makes perfect sense. However, even by ordering it like that it doesn't always work. And the sleep was in the test case as it seemed to make the problem worse. Changing the order does make it work a bit more often, but it still breaks often (about half the time). And without the sleep.
Ok, I ran it almost twenty time until, indeed, I encountered the same problem (your computer should be faster than mine ;-)).
I indeed found a problem (hope this will be the good one this time), when frozen the current implementation of the layout stopped sending move events (this is not strictly needed, but can save a lot of processing). Both the viewer and the layout receive your xy event. Therefore, sometimes the xy change emitted by you was received by the viewer after the layout stopped emitting events for the node, sometimes some layout events was still pending after the viewer received the xy event, which produced a wrong position on the display, although the layout did a good computation.
Forcing the layout to always emit events for node position at each time step is a solution, but I would like to avoid it.
Alternatively, I pushed a change that force the layout to issue one event when it receives a "xy" move event. it seems to work for me after a large number of runs. Tell me.
Excellent, the last fix worked. It doesn't break even with my largest graphs.