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:

- Directed graphs data structure
- A generic tree (which is itself a directed graph) data structure
- layout management by using FlowAlgorithm objects

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; } }

- main sketch code
- support functions
- Node
- DirectedGraph (requires Node, CircleFlowAlgorithm)
- Tree (requires Node, TreeFlowAlgorithm)
- FlowAlgorithm.pde
- CircleFlowAlgorithm.pde (requires FlowAlgorithm)
- ForceDirectedFlowAlgorithm.pde (requires FlowAlgorithm)
- TreeFlowAlgorithm.pde (requires FlowAlgorithm)

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.

Pomax,

Download the zipped archive, unpack it to a directory/folder called "graphs", and then open "graphs.pde" in the Processing IDE. Hit run, and it'll work.

Hilal,

^_^ I was running it in NetBeans IDE
it is working fine in Processing IDE
I need to automate drawing of different graphs using ForceDirectedFlowAlgorithm
but i couldn't understand in witch base you did right this input
// 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);

Pomax,

All code is pure Processing, with all numbers base 10. The code you're quoting is creating nodes with a name (so "1" etc are strings) at specific coordinates. 'padding' is a value defined in graphs.pde, and width/height are global Processing variables. I don't know about running it in netbeans, but to run it as java core, using Processing's "core.jar" as a library dependency means you have to rewrite all the code to real Java. This means that every .pde files becomes a .java file, the code in graphs.pde must be wrapped by a class that extends PApplet, and only the PApplet extension can perform Processing functions. Things like width and height, and functions like line() and sin() are no longer global functions.

Hilal,

I got your point and I'm using Processing IDE now and it works fine. What I need to do is to draw different graphs with different nudes number and different connections. I have problem with "Node n1 = new Node("1",xxxx,yyyy);" what I could not understand is in witch way I should put the values of xxxx and yyyy for different nudes.

Alvaro,

Hi,
What is the license used for these files? Are them open source like MIT, or BSD?
Cheers

Pomax,

No license, it's public domain source code.

Alvaro,

Hi,
I think that's great, but while I'm no lawyer I think "legally" it's easier if you provide a license with your code. At least for big companies it should be easier to decide if they want to ship your code with their products if there were a explicit license with the distributed code.
Just my two cents.

Pomax,

It's in the public domain, no copyright is claimed, ergo you are free to use it for whatever you want. If there was a copyright, but no license, a license would definitely be necessary. There isn't, so there isn't. This code is way too simple.

Alvaro,

Sorry to be such a PITA but all those files have this as header in comments: "* (c) Mike "Pomax" Kamermans 2011".

Pomax,

Then I shall remove that! because that makes no sense.

Javier,

I just want to thank you for providing this very basic and fundamental graph theory sw demo for processing. I find it rather strange that the official examples has nothing close to this in terms of complexity (i.e.variants) and structure.
I hope you have received more thanks through other channels!
/J

This page was created by Michiel Kamermans from processingjs.nihongoresources.com |

^{th}2011 - 9:59 am (GMT-7)