download the source code
This is some simple graph visualisation code for Processing sketches, constrained to the sketch size. It's really a setup for other people to work with, so there's no pan/zoom controls, and the number of default algorithms is low. What's included:
The idea is that you make a graph or a tree, and then to have it drawn you make sure it uses the desired flow algorithm. For DirectedGraph object, for instance, there are two demo algorithms: CircularFlowAlgorithm, which simply arranges the nodes in your graph in a circle, and then draws them, and a simple ForceDirectedFlowAlgorithm, which treats the links between nodes as force vectors, and repositions nodes based on the direction of the total force vector acting on each node, constrained by link "elasticity".
Some code examples; first, a directed graph:
// define a new directed graph
g = new DirectedGraph();
// define some nodes
Node n1 = new Node("1",padding,padding);
Node n2 = new Node("2",padding,height-padding);
Node n3 = new Node("3",width-padding,height-padding);
Node n4 = new Node("4",width-padding,padding);
Node n5 = new Node("5",width-3*padding,height-2*padding);
Node n6 = new Node("6",width-3*padding,2*padding);
// add nodes to graph
g.addNode(n1);
g.addNode(n2);
g.addNode(n3);
g.addNode(n4);
g.addNode(n5);
g.addNode(n6);
// link nodes
g.linkNodes(n1,n2);
g.linkNodes(n2,n3);
g.linkNodes(n3,n4);
g.linkNodes(n4,n1);
g.linkNodes(n1,n3);
g.linkNodes(n2,n4);
g.linkNodes(n5,n6);
g.linkNodes(n1,n6);
g.linkNodes(n2,n5);
// by default this uses the circular flow algorithm, so let's change that
g.setFlowAlgorithm(new ForceDirectedFlowAlgorithm());
and then a tree:
// define a root node
Node root = new Node("root",0,0);
// define a tree, with this root node
g = new Tree(root);
// g has type "DirectedGraph", so get a "Tree" alias before we continue
Tree t = (Tree) g;
// define some children for this tree
Node ca = new Node("a",0,0);
Node caa = new Node("aa",0,0);
Node cab = new Node("ab",0,0);
Node cb = new Node("b",0,0);
Node cba = new Node("ba",0,0);
Node cbb = new Node("bb",0,0);
Node cbba = new Node("bba",0,0);
Node cbbb = new Node("bbb",0,0);
Node cbbba = new Node("bbba",0,0);
Node cbbbb = new Node("bbbb",0,0);
// and add all of them
t.addChild(root, ca);
t.addChild(root, cb);
t.addChild(ca, caa);
t.addChild(ca, cab);
t.addChild(cb, cba);
t.addChild(cb, cbb);
t.addChild(cbb, cbba);
t.addChild(cbb, cbbb);
t.addChild(cbbb, cbbba);
t.addChild(cbbb, cbbbb);
Drawing simply involves calling the reflow method on the graph:
boolean done = g.reflow();
If the reflow is iterative (like the force directed flow algorithm) the reflow method returns "false" until it has converged. Single-step algorithms simply immediately return "true", because they don't have to run multiple times before they reach the final layout.
In order to see the "current" state of the graph, simply call draw:
g.draw();
Circular layout
class CircleFlowAlgorithm implements FlowAlgorithm
{
boolean reflow(DirectedGraph g)
{
float interval = 2*PI / (float)g.size();
int cx = width/2;
int cy = height/2;
float vl = cx - (2*g.getNode(0).r1) - 10;
for(int a=0; a<g.size(); a++)
{
int[] nc = rotateCoordinate(vl, 0, (float)a*interval);
g.getNode(a).x = cx+nc[0];
g.getNode(a).y = cy+nc[1];
}
return true;
}
}
Force-directed layout
class ForceDirectedFlowAlgorithm implements FlowAlgorithm
{
float elasticity = 100.0;
void setElasticity(float e) { elasticity = e; }
float repulsion = 4.0;
void setRepulsion(float r) { repulsion = r; }
boolean reflow(DirectedGraph g)
{
ArrayList<Node> nodes = g.getNodes();
int reset = 0;
for(Node n: nodes)
{
ArrayList<Node> incoming = n.getIncomingLinks();
ArrayList<Node> outgoing = n.getOutgoingLinks();
// compute the total push force acting on this node
int dx = 0;
int dy = 0;
for(Node ni: incoming) {
dx += (ni.x-n.x);
dy += (ni.y-n.y); }
float len = sqrt(dx*dx + dy*dy);
float angle = getDirection(dx, dy);
int[] motion = rotateCoordinate(0.9*repulsion,0.0,angle);
// move node
int px = n.x;
int py = n.y;
n.x += motion[0];
n.y += motion[1];
if(n.x<0) { n.x=0; } else if(n.x>width) { n.x=width; }
if(n.y<0) { n.y=0; } else if(n.y>height) { n.y=height; }
// undo repositioning if elasticity is violated
if(n.getShortedLinkLength()<elasticity/2 ||
n.getShortedLinkLength()>elasticity*2) {
reset++;
n.x=px; n.y=py; }
}
return reset==nodes.size();
}
}
Tree layout
class TreeFlowAlgorithm implements FlowAlgorithm
{
boolean reflow(DirectedGraph g)
{
if(g instanceof Tree) {
Tree t = (Tree) g;
int depth = t.getDepth();
int vstep = (height-20)/depth;
int vpos = 30;
Node first = t.root;
first.x = width/2;
first.y = vpos;
// breadth-first iteration
ArrayList<Node> children = t.root.getOutgoingLinks();
while(children.size()>0)
{
vpos += vstep;
int cnum = children.size();
int hstep = (width-20) / cnum;
int hpos = 10 + (hstep/2);
ArrayList<Node> newnodes = new ArrayList<Node>();
for(Node child: children) {
child.x = hpos;
child.y = vpos;
addAll(newnodes, child.getOutgoingLinks());
hpos += hstep;
}
children = newnodes;
}
}
return true;
}
}
Or if you wish to download this as a convenient single package: zipped archive with all source
If you have any questions about anything on this page (including how the graphics work, etc.), or you just want to leave a comment, this is the place to do it.
|
This page was created by Michiel Kamermans from processingjs.nihongoresources.com |