Simulating Graphs as Physical Systems
by Arne Frick, Georg Sander, and Kathleen Wang

Listing One
import tomsawyer.util.*;
import tomsawyer.graph.*;
import tomsawyer.util.compatibility.*;
import java.util.*;

class SpringEmbedder
{
    /**  The main Iteration method doing the spring embedder.
     * The nodes are stored in a node array (a vector) and have an index.
     * We use three additional arrays:
     * temperature[nodeIndex] is the temperature of the node T(v).
     * oldImpulse.elementAt(nodeIndex) is the old impulse of the node I(v),
     * which is a 2-dimensional vector of type Vector2D.
     * skew[nodeIndex] is the skew value S(v) that indicates how often the
     * node rotated into the same direction. */
    public void mainIteration()
    {
        int iteration = 0;
        while(( iteration < MAXITERATION) &&
              (this.temperatureSum() < MAX_TEMPERATURE_SUM))
        {
            iteration = iteration + 1;
            List li = this.createRandomNodeNumberList();
            Iterator iter = li.iterator();
            // catch every node once
            while(iter.hasNext())
            {
              // get the node number in the node array and node
              int nodeIndex = ((Integer) iter.next()).intValue();
              TSDNode node = (TSDNode) (this.nodeArray.elementAt(nodeIndex));
              // compute the Impulse of the node
              Vector2D impulse = this.computeNodeImpulse(node);
              this.adjustTemperatureAndSkew(nodeIndex,Vector2D.angle(
                    (Vector2D)this.oldImpulse.elementAt(nodeIndex),impulse));
                // adjust local position
                node.moveBy( 
                        STEP_CONSTANT_C_4 * 
                            impulse.getX()  * this.temperature[nodeIndex],
                        STEP_CONSTANT_C_4 * 
                            impulse.getY () * this.temperature[nodeIndex]);
              ((Vector2D) this.oldImpulse.elementAt(nodeIndex)).set(impulse);
            }
        }
    }   
    /** This method adjust the temperature of the node according to the
     * old temperature and the the old impulse */
    public void adjustTemperatureAndSkew(int nodeIndex, double angle)
    {
        // Note that angle is a positive value between 0 and approx. 6.283
        // i.e. 2 pi. Hence, 45 degree is 0.707 and -45 degree is
        // 6.283 - 0.707 = 5.576
        if (angle < 0.707 || angle > 5.576 ||
            (angle > 2.434 && angle < 3.848))
        {
            // between -0.707 and 0.707 (-45 and 45 degree), there is
            // acceleration, between 2.434 and 3.848 (145 and 225 degree)
            // there is oscillation, described by this temperature scheme:
            this.temperature[nodeIndex] =
                this.temperature[nodeIndex] * 
                    (1 + OSCI_CONSTANT_C_5 * Math.cos(angle));
        }
        else
       {
            // in the other ranges of the angle, there is rotation:
            this.skew[nodeIndex] = 
                 this.skew[nodeIndex] + SKEW_CONSTANT_C_6 * Math.sin(angle);
            this.temperature[nodeIndex] = this.temperature[nodeIndex] -
                 ROTA_CONSTANT_C_7 * Math.abs(this.skew[nodeIndex]);
        }
    }
    /** This method computes the normalized impulse of the node by
     * the sum of all force vectors. */
    public Vector2D computeNodeImpulse(TSDNode node)
    {
        Vector2D resultForce = new Vector2D();
        // Iterate through all adjacent edges to calculate attractive forces
        Iterator adjacentEdgesIter = node.inEdges().iterator();
        while (adjacentEdgesIter.hasNext())
        {
            TSDEdge edge = (TSDEdge) adjacentEdgesIter.next();
            // compute the other adjacent node
            TSDNode otherNode = (TSDNode) edge.getTargetNode();
            if (otherNode == node)
            {
                // it has to be the other node we do not allow self loops
                otherNode = (TSDNode) edge.getSourceNode();
            }
            // add all attractive forces together
            resultForce = resultForce.
                add(this.attractiveForce(node, otherNode));
        }
        // Iterate through all other nodes to calculate repulsive forces.
        Iterator nodeIterator = graph.nodes().iterator();
        while (nodeIterator.hasNext())
        {
            TSDNode otherNode = (TSDNode) nodeIterator.next();
            if (otherNode != node)
           {
                resultForce = resultForce.
                    sub(this.repulsiveForce(node, otherNode));
            } 
        }
        // Finally add the random force and the gravitaional force
        resultForce = resultForce.
            add(this.gravitionalForce(node)).
            add(this.randomForce());
        // we only need the impulse
        return (this.impulse(resultForce));
    }
    /** This method returns the impulse vector of a force vector. */
    public Vector2D impulse (Vector2D vector)
    {
        return (new Vector2D(vector).div(vector.norm()));
    }
    /** This method computes the attractive force between two nodes */
    public Vector2D attractiveForce(TSDNode node1, TSDNode node2)
    {
        // We need the squared distance of the two nodes
        double distance =  node1.getCenter().distance(node2.getCenter());
        // create Vectors out of the node positions
        Vector2D node1Vector = new Vector2D(node1.getCenter());
        Vector2D node2Vector = new Vector2D(node1.getCenter());
        // (c_1 * (node1 - node2) / distance * (log( distance / c_2)))
        // c_2 should be approx. the desired edge length.
        return (node1Vector.sub(node2Vector).
                div(distance).
                mul(Math.log(distance / ATTR_CONSTANT_C_2)).
                mul(ATTR_CONSTANT_C_1));
    }
    /** This method computes the repulsive force between two nodes */
    public Vector2D repulsiveForce(TSDNode node1, TSDNode node2)
    {
        Vector2D resultForce = new Vector2D();
        // We need the squared distance of the two nodes
        double distance = node1.getCenter().distance(node2.getCenter());
        if (distance != 0.0)
        {
            double tripleDistance = distance * distance * distance;
            // create Vectors out of the nodes
            Vector2D node1Vector =  new Vector2D(node1.getCenter());
            Vector2D node2Vector =  new Vector2D(node1.getCenter());
            // (node1 - node2) * c_3 / distance ^ 3
            // c_3 should be approx. the square of the desired edge length.
            resultForce =
                node1Vector.sub(node2Vector).
                mul(REPL_CONSTANT_C_3).
                div(tripleDistance);
        }
        return(resultForce);
    }
    /** This method computes the random force. */
    public Vector2D randomForce()
    {
        // We need a random impulse [-RAND_CONSTANT, ..., +RAND_CONSTANT]
        // Range should be approx. [-1/4 ... +1/4] of desired edge length.
        double maxRandom = RAND_CONSTANT;
        return new Vector2D(
            (this.random.nextDouble() * maxRandom * 2) - maxRandom,
            (this.random.nextDouble() * maxRandom * 2) - maxRandom);
    }
    /** This method computes the gravitional force between a node and 
     * the barycenter of the drawing. */
    public Vector2D gravitionalForce(TSDNode node)
   {
        // compute the mass with the node degree
        double phi = 1 + node.degree() / 3;
        // create vectors from position of node and center of graph
        Vector2D barycenter = new Vector2D(this.graph.getCenter());
        Vector2D nodeVector = new Vector2D(node.getCenter());
        // GRAV_CONSTANT_C_8 * ( barycenter - nodeVector) * phi
        return(barycenter.sub(nodeVector)).mul(phi).mul(GRAV_CONSTANT_C_8);
    }
    /** This method returns the sum of all temperatures */
    public double temperatureSum()
    {
        double result = 0;
        for( int i = 0; i < this.graph.nodes().size(); i++)
        {
            result = result + this.temperature[i];
        }
        return (result);
    }
    /** This method returns the list of nodes in a random sequence. */
    public List createRandomNodeNumberList()
    {
        // ... to be filled in ... Creating good random sequences is beyond 
        // the scope of this paper and can be a separate paper.
        return (null);
    }
//------------------------------------------------------------
    public static int MAXITERATION = 10000;
    public static double ATTR_CONSTANT_C_1 = 1.0;
    public static double ATTR_CONSTANT_C_2 = 8.0;
    public static double REPL_CONSTANT_C_3 = 64.0;
    public static double STEP_CONSTANT_C_4 = 1.0;
    public static double OSCI_CONSTANT_C_5 = 1.0;
    public static double SKEW_CONSTANT_C_6 = 1.0;
    public static double ROTA_CONSTANT_C_7 = 1.0;
    public static double GRAV_CONSTANT_C_8 = 1.0;
    public static double RAND_CONSTANT = 2.0;
    public static double MAX_TEMPERATURE_SUM = 1.0;
    public static int MAX_NODES = 1000;
    public Random random = new Random();
    public TSDGraph graph = new TSDGraph();

    Vector oldImpulse = new Vector(MAX_NODES);
    Vector nodeArray = new Vector(MAX_NODES);
    double temperature[] = new double[MAX_NODES];
    double skew[] = new double[MAX_NODES];
}





4


