Bookmark with del.icio.us submit Force%20Directed%20Graphs%20in%20Javascript%3F digg.com reddit

Force Directed Graphs in Javascript?

Force Directed Graphs are self-organizing, visually appealing tools for representing relational data. The look is organic, because algorithms simulate the way charged particles arrange in space. They work great in user interfaces because the user has access to data nodes while the graph is being organized. Take a look (go ahead and play, they're interactive):

Show Example

So, what am I using these for?

Recently, I've been considering alternatives to the traditional list and tree views used in search result user interfaces. I'm looking for display tools that can show relationships among results, rather than simply ranking them by score. Force Directed Graphs looked promising, so I started writing this library to determine if a client-resident implementation in Javascript is a viable option.

Initial Findings

Next Steps

I need to produce some functional user interfaces. Lists make very efficient use of space. Users greatly benefit from lengthy titles, annotations, urls, and even thumbnail images in results. It'll certainly be a challenge to incorporate large amounts of text in a user interface based on force directed graphs. Please please please leave a comment if you've seen examples in the wild or have some suggestions. I'll be publishing the results here, so be sure to check back.


Update on Licensing:
Creative Commons License
This work is licensed under a Creative Commons Attribution 2.5 License.

As promised, I'm providing an open source license for the files referenced here. I've chosen a Creative Commons Attribution License, which means you are free to distribute the files and create derivative works as long as you include the license and attribution information contained in each file. I will follow up with a post describing each of these files to help you integrate with your project.

Trackback

Listed below are links to weblogs that reference Force Directed Graphs in Javascript?:

» First Whack at JavaScript Visual Wordnet from kylescholz.com :: blog
Here's my first whack at a Visual Wordnet. It's the first application that uses my Force Directed Graph engine for Javascript. Yes ... Javascript. This is an exercise to see if Javascript-driven Force Directed Graphs might be useable in web... [Read More]

» Using Force Directed Graphs in Your App from kylescholz.com :: blog
I'm really pleased with the response to my first posts on Force Directed Graphs in JavaScript. A number of people have expressed interest in using these libararies in their own applications so I'm providing some details on how to... [Read More]

» Links: 6-8-2006 from Aaron Johnson
kylescholz.com :: blog: Force Directed Graphs in Javascript? It's amazing what you can do with JavaScript these days. (categories: graphing infoviz javascript visualization )... [Read More]

» Visual Wordnet from GreenCode
Kyle Scholz has created a Visual Wordnet based on his Force Directed Graph engine written in JavaScript. Force Directed Graphs are self-organizing, visually appealing tools for representing relational data. The look is organic, because algorithms si... [Read More]

Comments

Titles, URLs and thumbnails could be displayed in a GoogleMap way

Can you elaborate on this? I'm unclear which feature of Google Maps you're referring to...

I think he's referring to the letter placeholder and the sidebar that expands on that with the actual information. All the information is presented at once, because of the sidebar, but the graph is not cluttered, and the tooltip-like breakout on click that duplicates the sidebar information for each node lets you still allow users to navigate totally within the graph if they want to.

There are certainly worse solutions.

is Force Directed Graphs open source?

daniele,

Yes. I'll post a version with an approriate open source license this evening.

great job. Wednus ppl love this sort of stuff. =)
I have one interface suggestion though.

[quote]
var node1 = control.addNode( null, 3, true, 55 );
graphui.getNode(node1.id).style.backgroundColor="#99ee55";
graphui.getNode( node1.id ).style.border="1px solid #69be25";
[/quote]

object handle, DOM handle.. we don't want to manage multiple handles.
it seems your Node(or equivalent) class and the visual representation of the node(a DIV) are seperated. In my experience, this is neither convenient nor efficient.

var node1 = control.addNode( null, 3, true, 55 );
node1.setBorder('1px');
node1.setBackground('1px solid #69be25');

...
var Node = function(){
this.id = ...;
this.---;
// you may want to do something like this
this.body = document.createElement('div');
this.body.style.position = 'absolute';
....
// forward 'this' to member method def.
var self = this;
this.setBorder = function(border){
self.body.style.border = border;
};
this.setBackground = function(background){
self.body.style.background = background;
};
document.body.appendChild(this.body);
};

I developed something very similar a few months back:

http://dev.buildpatterns.com/trac/wiki/GraphProject

It's at a very early stage, but the implementation is very similar.

Aslak

I've been looking for simple a way of doing this since finding the visual thesaurus some years ago now.

It provides a lovely way to representing relationships between organisations in supply chains.

Looking forward to you posting it Open Source.

ok, am I right to understand you are looking for examples to implement it? this page shows my library collection www.crm20.com/optimize I wanted to setup some sort of interface like yours to the library, page doesn't show all possible parameters for each element, you can see some if you scroll down to function edit and click edit for a pop-up.

what do you think?

Sundew,

I think I get where you are going and it may be an effective optimization because it would reduce the number of objects active in the window. I made a deliberate barrier between the graph objects and the UI objects because I had hoped to make the graphing engine work with both DOM and "canvas" based user interfaces.

Aslak,

Good demo on your site. I'll be looking at your source this weekend. Thanks.

ark,

I am looking for some compelling, broad-audience, applications in search and entity navigation.

Looking at the link you provided, I'm not immediately certain how you wish to express your data as a connected graph. I'll be posting some instructions for integrating with the engine later this week. Try it out and post a link. I (and I'm sure others) would be happy to offer comments.

Looks great but where can I download your code for a lil play?

You got it, I was thinking I should be able to map the functions/classes and subroutines in how they relate inside the framework, each site on the framework also uses different subset of them(I even don't know which site uses what code, because each site builds it's own code based on what it needs). So it would be interesting to see my client's sites framework usage/relationships maps...

I am not that good with javascript so it will be slow for me to set it up, but I will send you the links once I get it done.

I modified Sala's htmlgraph applet built with the Processing toolkit to do something similar:

http://forreststevens.com/htmlgraph/

You can plug in a web page and it parses the HTML tags into a directed graph. The result is clickable, draggable, and presents the information just like it seems you might want. Source code is of course available.

I saw the visual thesaurus in Java a number of years ago. It inspired me to make a data clustering tool in Excel (quick and dirty, not efficient) for data mining. As you say, it doesn't scale very well.

I most recently used the technique in Quartz Composer on Mac OS X to make a screen saver. Invisible points bounce around the screen, dragging behind them pulsing stars that are attracted to their respective point, but repelled by the other stars. It is also written in Javascript, but as you note, just 12 stars eat up half the processing power of my new laptop.

I'm thinking of dividing the screen into regions. Each region would have a list of points inside it, and the lists would get updated after every point movement. A formula should determine which region the point is in. The force calculation is done only if the two points share a region or are in neighbouring regions. That might reduce the amount of calculations somewhat.

Calculating for neighbouring regions is necessary to consider having two points close to each other but in separate regions.

A further refinement might be to provide a "centre of gravity" calculation for each region so that a lone point would still feel an effect from distant regions. The vectors might be pre-calculated, then multiplied by the number of points and their values in each region. This would remove a couple of square root calculations, anyway. Although a square root might not be expensive compared to symbol parsing in JavaScript.

I created a FOAF (friend of a friend) browser with your graph.

Visual FOAF Explorer

I changed the timings a bit to help the speed issues with large groups.

Very interesting the forrest applet modification but...the source code seems not complete / correst.
Forrest, can you upload che correct version ?

I saw visual thesaurus and it seems to use a slightly different approach (the "spider" layout) that is more efficient for trees (or graphs with few
circular relationships)...or not ?

Ops...downloaded the Processing IDE, now it works.

Dan and David,

You should check out the latest post on "Tree Graphs". If your data can be modeled as a tree (or a few trees) rather than a particle system, the calculations are far less complex and rendering is much faster and less resource intense.

Efficient,useful,beautiful, incredible.You did a good job.
Congratulation

Thank you

neat!

Post a Comment

(optional)
(optional)