We have added space partitioning to the graph layout engine in the modeling tool (rev. 411 now live in test). This will improve performance for very large graphs. The idea is to first divide the space containing the graph into a number of sections called partitions, then calculate the “center of mass” for each partition with respect to the contained nodes, and then calculate the collective repelling force in each partition by the other partitions. Rather than having to do an exponentially growing iteration over nodes and other nodes, we can now iterate only over nodes in the same partition, calculate their respective forces with an addition of the already calculated force in the partition, and move to the next partition.
Looking at recent research in graph layout, an octree is used for the partitioning. However, constructing an octree was not fast enough, so we decided upon another method. The partitioning is made by dividing the node coordinates by the partition size and converting the result to an integer. A hashtable is used to contain the partitions with a pointer to an array of the contained nodes.
This works well, except that since we are continuously moving nodes around, we may get into a situation where nodes are “jumping” between two different partitions, and the layout never reaches equilibrium. We were able to remove such jittering by making the partitions fuzzy, with respect to their size. Every iteration of the layout, the size of a partition will be somewhat different, resulting in the nodes always settling down in a single partition.
In the screenshot above you can see the different partitions in grey (switch on debugging in the test version to see for yourself), and a grey small square in each partition indicating its center of mass.
