Force directed graph layout in JavaScript | Hacker News Reader

Force directed graph layout in JavaScript

dhotson.tumblr.com

22 pointsdhotson17 comments

Nice! I did the same thing a couple weeks ago <http://github.com/jackrusher/jssvggraph>; to help explain the simplicity of the algorithm to a friend. Mine paints SVG directly rather than using Raphael, so it only works with browsers that support that standard. One thing this brought to my attention is that the WebKit SVG implementation is much, much faster than Gecko's.

If you want to click, use http://github.com/jackrusher/jssvggraph

Thanks! I wasn't familiar with HN's post formatting.

Normal parens (like this) seem to work with URLs on HN.

Thanks for sharing Jack.

For this demo I was really focusing on simplicity and getting the basics right. I just wanted dots and lines but was too lazy to figure SVG DOM manipulation. Raphael makes it really easy.

The best force-directed graph I've seen - that is really interactive and extensible, although it is Flash - is http://www.creativesynthesis.net/blog/?page_id=60 Demo: http://www.creativesynthesis.net/recycling/graphgeardemo/

I thought it was drag drop until I realized the animation on Chrome is too quick.

Very neat animation. Is it always the same graph, if you reload ? (with different initial random placements, I mean)

In one case, I observed an edge coming to rest just across an unconnected (to that edge) node. Might be hard to detect/work around ...

[Many moons ago, for an exercise, implemented a force-directed placement, with team-mates doing Kernighan-Lin min-cut (also fast) and simulated annealing (slow) ...]

P.S. Two observations:

- You highlight the node on mouse over. If the edges connected directly to that node were also highlighted, it would palliate the false connection problem.

- Adding some edge-edge repulsion ? Sometimes edges cross, and one of them could be flipped to another side for a locally planar solution.

Yep, it's currently the same hardcoded graph each time. The node starting positions are random so you get a slightly different layout each time.

I was thinking about making edges repel nodes in some way to avoid the problem you mentioned. I'll have to experiment some more..

That's really neat.

I hit the same problem of crossing edges when doing this a while ago (in Python rather than JavaScript).

Rather than trying to get everything done automatically by the code I added the ability to click and drag a point. So the algorithm gets you close to a good layout and you can then make adjustments to avoid unwanted crossings.

It reminds me of an old HN comment "think cyborg, not robot" (http://news.ycombinator.com/item?id=164833).

Thanks jonp. :-)

I think that's a good idea. The force directed layout algorithm isn't bullet proof, but it's a good approximate layout for a human to tweak.

Just remembered this discussion http://news.ycombinator.com/item?id=1218376 also featured a force-directed graph layout algorithm, with brief paper and all. Just in case you missed it.

Very nice. I'm thinking of an interactive editor for directed acyclic graphs with labeled nodes and wondering if there's anything out there already. This is clear and simple enough to be a good starting point.

You may find something useful here: http://news.ycombinator.com/item?id=1218376

(If you have a Mac, check the included Grapher tool mentioned in that discussion - may not have edge labels)

Look at the Github network charts as Git basically uses directed acyclic graphs.

http://github.com/blog/621-bye-bye-flash-network-graph-is-no...

and

http://raphaeljs.com/github/demo.html

Direct link to demo: http://dhotson.github.com/springy.html

http://code.google.com/p/jsviz/ It might be dead, but either way it's kind of cool as well.

Reply on news.ycombinator.com