|Posted by kyle on June 25, 2006 11:56 PM||bookmark / share:|
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, and I have some good news. If you're new to this discussion, check out the earlier postings and comments:
First, a recap
Let's talk briefly about why Force Directed Graph algorithms don't scale very well.
Each node in a graph behaves like a "particle" in space. Some particles have attractive forces between them. These are usually represented as edges on the graph. Every particle has repulsive forces between itself and every other particle. These are the forces that make nodes "avoid" each other while the graph organizes. The combination of these forces on a given node help dictate a new position for the node. Any time a node has changed position, the forces it places on all of the other nodes have changed, so we have to reculate their positions.
Attractive forces are no problem to calculate because the number of edges in a graph is normally relatively small compared to the number of nodes. The repulsive forces are the painful part, but a critical part of what makes these graphs neat to look at. The calculation of the repulsive force acting on a node at any given time has On2 complexity. If this is a new concept, this means that the number of calculations performed doubles for every node added to the graph. Optimizing such algorithms is difficult.
What to do about this? Trees?
I like Force Directed Graphs, but there will always be a scaling problem. I noticed that a lot of the apps people have submitted to me via comments and e-mails model tree structures and might not need all of the features of a Force Directed Graph. Even Visual Wordnet is really a tree model. So over Saturday morning cartoons I decided to tackle Tree Graphs. In my implementation of these graphs, each node is only aware of its own children, so calculations are much less complex, but it's possible for nodes from disperate branches to collide.
Some prototypes have emerged. I'm trying to merge in a few concepts from the world of Force Directed Graphs to make Tree Graphs more visually appealing. Understand these examples aren't yet fully interactive, but they'll give you a sneak peak at the speed improvement.
I hope you can see some promise here. The end result should be a little faster due to some unexploited optimizations and will enable an author to sacrifice fluidity for speed when more drawing power is needed. Already, these scale a whole lot better than a Force Directed implementation.
And what about Visual Wordnet?
Okay, I mocked that up too. Remember this is just an early prototype so it may look and act a little funny.
Using this code for your applications
I hope to have time to make a more "official" version of the Force Directed and Tree Graph code that anyone can use as a library in applications. I've gotten a lot of great comments and suggestions that I will be addressing soon. In the meantime, I'm not going to let my busy schedule get in the way of your app, so if you're brave you can use this stuff right now. It's all covered under a Creative Commons Attribution License.
The critical code is in treegraph.js. See examples for usage.
Also, let me know what you think and what you're up to. It really drives where this stuff goes from here. Thanks!