Bookmark with del.icio.us submit Using%20Force%20Directed%20Graphs%20in%20Your%20App digg.com reddit

Using Force Directed Graphs in Your App

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 do so here. Have fun!

Disclaimer

This is alpha code. I'm sharing it now because I want to see what you can do with it and what you think it should do.

License

Creative Commons License
This work is licensed under a Creative Commons Attribution 2.5 License.

JavaScript Files

  • graph.js: The graphing engine and supporting objects. The engine is independent of a UI implementation.
  • domui.js: A client to the graph engine. This implementation draws user interface components using the DOM.
  • control.js: Encapsulates event handling functions.
  • event.js: An event-handler factory.
  • timer.js: A object wrapper around JavaScript's "settimeout".

Example Implementation

Here's a simplified example. For a more complete example, see Example #1.

Import all of the supporting js files.

<html>
  <head>
    <script src="event.js"></script>
    <script src="timer.js"></script>
    <script src="graph.js"></script>
    <script src="domui.js"></script>
    <script src="control.js"></script>
  </head>

Add an "onload" event handler for the timer we're going to create below.

  <body onload="timer.start()">

Add an element to represent the origin of our graph.

    <div id="origin" style="position:absolute;"></div>

Add an element to frame to our graph.

    <div id="frame" style="width:400px;height:400px;
position:absolute;left:0px;top:0px;border:1px solid #444444;"></div>

Create and initialize the timer that will control this graph.

    <script>
    var timer = new TimerControl();
    timer.initialize( 1 );

Construct and initialize the object that draws the user interface components. We pass in the frame and origin elements from above and boolean flags indicated whether we wish to display origin and non-origin edges. For this example, we're going to display only the non-origin edges. See Example #1 for a better way to create the frame.

    var graphui=new GraphUI();
    graphui.initialize( document.getElementById('frame'), 
                        document.getElementById('origin'),
                        false,
                        true
    );

Create and initialize the Graph instance. We pass in the dimensions of the frame as well.

    var graph=new Graph();
    graph.initialize( 400, 400 );

Subscribe the GraphUI instance to the Graph so it will receive updates.

    graph.setUI( graphui );

Timers control other objects via an observer pattern. We subscribe the Graph instance to the Timer.

    timer.subscribe( graph );

Set up the control (which apparently knows about all the other objects ... yick).

    var control = new UserControl();
    control.initialize( timer, graph, graphui );

Finally, time for data. Add some nodes to the graph. A node may have text and mass, and connect to the origin with a specific edge weight.

    var node1 = control.addNode( null, 3, true, 55 );
    graphui.getNode( node1.id ).style.backgroundColor="#99ee55";
    graphui.getNode( node1.id ).style.border="1px solid #69be25";
    
    var node2 = control.addNode( null, 2, true, 55 );
    graphui.getNode( node2.id ).style.backgroundColor="#eeee66";
    graphui.getNode( node2.id ).style.border="1px solid #bebe36";
    
    var node3 = control.addNode( null, 1, true, 55 );
    graphui.getNode( node3.id ).style.backgroundColor="#ee9944";
    graphui.getNode( node3.id ).style.border="1px solid #be6914";

    var node4 = control.addNode( null, 3, true, 55 );
    graphui.getNode( node4.id ).style.backgroundColor="#6688ee";
    graphui.getNode( node4.id ).style.border="1px solid #3658be";

Add any edges.

    control.addEdge( node1, node2, 45 );

    </script>
  </body>
</html>

That's it! This is what it looks like. Give it a shot with your data! And please please please post a link for the rest of us.

Trackback

Listed below are links to weblogs that reference Using Force Directed Graphs in Your App:

» Force Directed Graphs, Performance, and Trees? from kylescholz.com :: blog
This weekend I finally got a chance to go over the wishlist that has been accumulating for the Force Directed Graph libraries I posted about earlier this month. Nearly everyone has asked that I do something about the performance problems,... [Read More]

Comments

Hi Kyle,
first of all, THANK YOU very much for this implementation! It really came at the right time for me :-). I'm currently working on a evolutionary algorithms problem at the university to solve a "which factories should be built and deliver to which customer" problem. Now I'll try to use your code to visualize the final result. Do do so I wanted to be the nodes something like "factory1" or "customer123" instead of a circle, just like in visual wordnet. I tried something like:

var node1 = control.addNode( 'factory1', 1, false, 55 );

but somehow the node still gets displayed as a circle. I tried to figure out the solution myself by reading your code but I'm more used to java then to Javascript ;-). Have you got any hints for me and my problem ;-)?
THANKS AGAIN!

Hi Kyle,

I appreciated very much your work, the idea was good and the library is easy to use. I'm a web developer of domainsbot and expirenced with ajax application. I've used your library to do some simple test displaying the realtion between the keywords contained in the zone file of registered domains, and the results are very nice. Unfortunally I can't publish the url of the sample but I can send you private to your mail. We are figuring out to disclose this work on our labs but first we need a more stable and perfroming version of your library. What are the road map of the project? Are you plaining to improve the performance of the render engine? Is it distributed under the creative commons license?

Thanks

Francesco

Nils,

I'm glad you found an application for these libraries. I took a look and the problem was my fault. I had removed some functionailty to simplify the libraries before distributing them and broke support for text nodes as a result. I've patched "domui.js" and worked up an example. Please let me know if you find any other issues. Good luck!

Francesco,

I checked out your site and you have some great tools. I'm eager to see what you can do with the graphing engine.

All of the code is available under a Creative Commons Attribution License. You're under no obligation to share your work, but we'd all like to learn from anything you can show us.

I'm currently looking to user feedback to determine the right course for future development. I agree that performance issues (especially scaling and resource utilization) should be a primary focus. I'll share any promising work I have in this area and would greatly appreciate any contributions.

Hi Kyle,

very great library! I'm thinking of using it to visualize complex hierarchical structures. For that, I would like to make heavy use of text nodes.

However, there is (in both Firefox and Safari on macosx) the problem that when you drag a text node it gets detached from its edges. Is that known (and easy to fix)?

And do you already have a roadmap for dealing with performance issues?

Thanks a lot,

Martin

Hi Kyle,

very great library! I'm thinking of using it to visualize complex hierarchical structures. For that, I would like to make heavy use of text nodes.

However, there is (in both Firefox and Safari on macosx) the problem that when you drag a text node it gets detached from its edges. Is that known (and easy to fix)?

And do you already have a roadmap for dealing with performance issues?

Thanks a lot,

Martin

Martin,

add this line:
textNodeTmpl.style.width = "16px"; // or other value

after line#202(domui.js):
textNodeTmpl.style.height = "16px";

Kyle,

It happended because, at line#139(control.js):
tempX -= parseInt( this.ui.getNode( selectedNode ).style.width ) / 2;

It refers the 'width' value of the node, but since we haven't defined this prop. w/ any value (for textnode div), it remains being '', empty string (the default), and we did parseInt an empty string, so the answer is NaN. Later, positioning part uses this invalid numeric source for calculating the left and top, it crashed the javascript engine.

Again Kyle,
This is a great stuff. but, if I were you, I would redesign the codebase right now and release a 'v0.1.0' asap. After I finish making the architecture more in OO friendly, then I would consider the scalability and optimization issues or even application cases later. Hope you don't get me wrong. I'm just wishing, if there's any nice javascript FDG engine available, the author should be you but somebody else who stills others months' work in couple of hours.

stills -> steals

Martin and Sundew,

Thanks for catching this issue. I have patched domui.js with a fix. A future release should use offsetWidth instead so that dynamically-sized text elements can be supported.

and Sundew,

Thanks for the suggestions. It was important that I release this code early to get feedback and the input has been invaluable.

Kyle, this is exactly what I've been looking for. I'm working on an art project in which I'd like to visually display degrees of relationships between objects. I'm not a programmer and am not really up to the task of learning another language like Processing. So your solution may be the answer...

I am wondering if there is a way to change focus on click, ie. make the clicked item the primary node and then display related nodes.

Also wondering about the possiblity of using images rather than HTML rendering or text.

Thank you in advance for your time.

Great stuff!

Miscellaneous observations from my tinkering:

* I added a 'fixed' field to nodes that prevents their locations from being updated (except by drags). It could make sense to have a 'undraggable' flag too.
* If there are fixed and undraggable flags, it may not be necessary to have a specially handled distiguished origin node. (It's just a fixed, non-draggable node at the center with a lot of edges.) Convenience code for setting up the common central-origin makes sense, but special handling of the origin in code and function signatures wouldn't be required.
* As soon as I put more interesting HTML inside text nodes (eg a DIV with a background image and some text), animate speed for a small number of nodes goes waaaay down. I suppose this is primarily a browser issue -- altering position of DOM trees being much more time-consuming than simple DOM leafs. But, many interesting apps would have IMGs and other arbitrary HTML in nodes so performance optimizations or dynamic coarsening to event timing would be very helpful.
* Two annoyances when dragging (in firefox) are that on IMGs, the browser/native drag-start interferes with the JS/DOM drag, and text in the target node or others may 'select' even during a drag. The first can be remedied by placing the IMG in an element 'background' or placing another clear DIV 'in front of' the IMG; I haven't figured out a remedy for the second yet.

Thank for this -- it's really expanded my idea of what's practical in JS/DOM/HTML nowadays!

TS,

Regarding your first question about changing focus on click -- It certainly is possible. I should work up an example on this because I'm sure others are interested. Gordon's comment regarding "fixed" nodes alludes to a nice strategy for this.

And regarding images, sure. Here's an adaptation of Example #1 from my original post that uses images in the nodes. This is just one approach. You could also modify the "templates" at the bottom of "domui.js" to contain the appropriate css attributes -- This aspect of the system is a little cheesy and I hope to clean it up when I make more official release.

Gordon,

Fantastic! I totally agree with your suggestions about the "fixed" and "draggable" properties. And your suggestion about removing the hard-coded "origin" is interesting too ... I'm imagining applications where having multiple nodes that behave like the origin would be really useful. Great ideas!

Regarding the performance issues with complex nodes, I'm a little suprised. I've done some experiments with a similar configuration and I find the DOM updates aren't a major bottleneck. Can you provide a URL for your problem case?

And regarding the dragging issues, I've been annoyed by these too. Your image fix sounds reasonable, but I had been considering using offsetWidth and offsetHeight properties for bounds checking and edge positioning ... If background-image is used, the size of the node must be explicitly set. Either way, your suggestion would certainly suffice for a lot of applications. For the text-selection problem, I do have an IE-specific fix for this but I don't think that's adequate.

Thanks again Gordon! These were great comments and suggestions!

My test that gets really sluggish uses 4 nodes with scaled (shrunken ~50%) full-color JPGs. It even seems like it gets slower as time goes on, as the items approach the edges, and if the enclosing frame area is larger. I'm trying to better quantify what's happening and will work up a demo URL if possible.

Other ideas:
- provide a convenience method for turning any preexisting DOM node into an animated node -- would make setting up a starting arrangement easier
- allow CSS classes (or XHTML custom element attributes) to set up force/edge/fixedness/etc parameters. Combined with the first, almost everything could be initially setup via HTML/CSS, with just one 'start' call to the library that interates over the DOM, 'unleashing' all the appropriate nodes into absolute and animated positioning

Hi, I've been playing with your code, and I noticed that some of your classes reference a 'graph' variable in the global scope. Specifically, GraphUI and UserControl. Seems a bit messy considering how well structured your classes are! Otherwise, very nice library!

Also, I just finished hacking up a SVG version of your graph code. Thankfully all I had to do was write a different implementation of the GraphUI class, and it worked!

http://mavra.perilith.com/~luser/graphs/graphtest.html
http://mavra.perilith.com/~luser/graphs/svgui.js

View source on graphtest.html to see how to use it.

Great work Ted! I had been wondering if I should simplify the design and only support the DOM, but I'm glad to see someone is finding the engine useful for other rendering engines. I'm sure a lot of others will find your work useful and I'll be certain to include it in future releases.

You'll notice that the Tree Graph prototypes are pretty dependent on the DOM. I hope to make a clean, common interface for both tree graphs and force directed graphs so that you can effectively "drop in" an appropriate graphing engine ... I imagine there are other connected graph types that could share the interface, too.

What do you think about the model? Where a UI subscribes to a Graph and receives "drawEdge" and "drawNode" requests. I had tried some alternatives with less success. I had really intended "UserControl" to contain application-specific functionality but it seems to have a lot of useful, recyclable stuff. Maybe a lot of this should move to DomUI and the rest can just reside in the application as intended.

I really plan to address the global references issue in an upcoming release. I just need to settle on some design issues. Thanks Ted! Your comments are efforts are really helpful!

Hello, nice site looks this

First off, let me say that this is very impressive work!

I'm wondering if your library can/could be used for my project. It's a graph that shows objects (edges, with labels) moving from one entity (node) to another. So obviously the graph is directed. I've got it up and running with a toy database using PHP and Graphviz (god I love that software, I use it in my Ph.D research as well) but I'd absolutely LOVE a more dynamic viz engine. I haven't had time to look through most of the code (and my JS is a little rusty), but does/could your library support:

1. Edge labels? It'd be great if they were "clickable" or "HTML-able". Doesn't have to be too complex, but it'd be wonderful if it could pop up a window or something. Graphiz just supports a single link per edge label. Arbitrary HTML (with multiple links or whatever) would be wonderful.

2. Directed graphs? This, I'd imagine is nothing more than changing the edge graphic depending on the node.

3. 3D? I'm sure that'll explode your computation to have to compute a Z-axis as well, but lord would that be cool.

I'm really trying to decide if something like this, or a more heavyweight solution like Thinkmap (which seems to have a less active development community) is appropriate. I don't know how easy it'd be integrate PHP DB access to Thinkmap, but I'd imagine it'd be trivial for your code. Anyway, sorry for being so wordy, but when I get some time I'm going to play around with your code.

Thanks again!
Jeremy.

Wow Jeremy! 3d! That's quite a feature request! I'm trying to imagine what this would look like ... I'm guessing we'd control object size over the z-axis. How would a user move an object around on the z-axis? We'd probaby have to provide some way to rotate the graph so you can see nodes hiding behind others, etc. I'm interested in your ideas about this. Can you elaborate on your vision for this?

Edge labels should be no problem. I'll note it on the wishlist.

The graph engine can support the notion of directed edges but I haven't found a clever way to indicate them ... If you'd like to use arrow head images, you'd have to find a cross-browser method for rotating them. This would certainly be easier with SVG than with the DOM. I'll ponder this one, but you should check out Ted's post above for an SVG implentation of the UI component.

Interesting challenges Jeremy! It might takes some time, but I hope we can hook you up!