Automatic graph layout spring theory

Question

I'm trying to position entities visualy to show their relationships to each other. It looks like for automatic graph layout, the spring algorithm would suit my needs. I'd like to implement this in silverlight using c#, so I'm looking for code samples, or links to good explanations of the theory. Any help appreciated

Preetum Nakkiran · Accepted Answer

I wrote some code awhile ago to perform dynamic graph layouts using C# and XNA (full source available upon request).

Here are some of the critical functions:

        public void UpdateNodes()
        {
            for (int i = 0; i < nodes.Count; i++)
            {
                Vector2 netForce = Vector2.Zero;
                foreach (Node otherNode in nodes)
                {
                    if (otherNode != nodes[i])
                    {
                        netForce += CoulombRepulsion(nodes[i], otherNode); //calculate repulsion for all nodes
                        if (nodes[i].links.Contains(otherNode))
                        {
                            netForce += HookeAttraction(nodes[i], otherNode); //only calc attraction for linked nodes
                        }
                    }
                }
                nodes[i].Velocity += netForce;
                nodes[i].Velocity *= .99f;
                nodes[i].Position += nodes[i].Velocity;
            }
        }


        public Vector2 HookeAttraction(Node node1, Node node2) //ON node1 BY node2
        {
            Vector2 direction = Vector2.Subtract(node2.Position, node1.Position);
            direction.Normalize();

            return hookeConst* node2.Mass * Vector2.Distance(node1.Position, node2.Position) * direction;
        }

        public Vector2 GravAttraction(Node node1, Node node2) //ON node1 BY node2
        {
            Vector2 direction = Vector2.Subtract(node2.Position, node1.Position);
            direction.Normalize();

            return gravConst * node2.Mass * Vector2.DistanceSquared(node1.Position, node2.Position) * direction;
        }

Pick the two constants based on how fast you want the graph to converge. I used these:

        private const float hookeConst = .000005f;
        private const float gravConst = .00000001f;

That code is pretty self-explanatory, but feel free to ask if you need anything. Basically, call the UpdateNodes() function in a loop, and your graph will converge on its minimal-energy state.

Automatic graph layout spring theory

Answers (2)

Related Questions