springlayoutstrategy.java

JPowerGraph is a Java library for creating directed graphs for SWT. It supports graph movement, sele

package net.sourceforge.jpowergraph.layout;

import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

import net.sourceforge.jpowergraph.Edge;
import net.sourceforge.jpowergraph.Graph;
import net.sourceforge.jpowergraph.Node;

/**
 * The layout strategy that models edges as springs. This algorithm is a refactoring of the graph layout algorithm originally implemented
 * in the <a href="http://www.touchgraph.com/">TouchGraph</a> library.
 */
public class SpringLayoutStrategy implements LayoutStrategy {
    /** Specifies how long a node remains in a special state after it is inserted into the graph. */
    protected static final long TIME_NODE_REMAINS_CHANGED=200;

    /** The graph being manipulated by this strategy. */
    protected Graph m_graph;
    /** The the graph manager. */
    protected GraphManager m_graphManager;
    /** The damper value. A low damper value causes the graph to move slowly. A value of 1 means no damping. */
    protected double m_damper=0.0;
    /** The maximum motion value after the last move. Used to see when the graph is stabilizinh. */
    protected double m_maxMotion=0;
    /** The motion ration after the last move. */
    protected double m_motionRatio=0;
    /** Then dampoing is true, the damper value decreases. */
    protected boolean m_damping=true;
    /** The rigidity has the same effect as the damper, except that it is a constant. */
    protected double m_rigidity=1;

    /**
     * Creates an instance of this class.
     *
     * @param graph                         the graph that is active
     */
    public SpringLayoutStrategy(Graph graph) {
        m_graph=graph;
        m_graphManager=new GraphManager();
    }
    /**
     * Returns the graph of the strategy.
     *
     * @return                              the graph of the strategy
     */
    public Graph getGraph() {
        return m_graph;
    }
    /**
     * Notifies the strategy that elements were inserted into the graph.
     *
     * @param nodes                         the inserted nodes (may be <code>null</code>)
     * @param edges                         the inserted edges (may be <code>null</code>)
     */
    public void elementsAdded(Collection nodes,Collection edges) {
        m_graphManager.elementsAdded(nodes,edges);
    }
    /**
     * Notifies the strategy that elements were removed from the graph.
     *
     * @param nodes                         the removed nodes (may be <code>null</code>)
     * @param edges                         the removed edges (may be <code>null</code>)
     */
    public void elementsRemoved(Collection nodes,Collection edges) {
        m_graphManager.elementsRemoved(nodes,edges);
    }
    /**
     * Called when the graph is completely changed.
     */
    public void graphContentsChanged() {
        m_graphManager.graphContentsChanged();
    }
    /**
     * Notifies the strategy that the graph has changed due to an event that is not caused by
     * the strategy itself.
     */
    public void notifyGraphLayoutUpdated() {
        m_damping=true;
        m_damper=1.0;
    }
    /**
     * Executes one step in the layout.
     */
    public void executeGraphLayoutStep() {
        for (int i=0;i<10;i++) {
            relaxEdges();
            adjustNodePairs();
            moveNodes();
            damp();
        }
    }
    /**
     * Returns <code>true</code> if more steps in the layout should be executed.
     *
     * @return                              <code>true</code> if more steps should be executed
     */
    public boolean shouldExecuteStep() {
        return !(m_damper<0.1 && m_damping && m_maxMotion<0.001);
    }
    /**
     * Relaxes the edges.
     */
    protected void relaxEdges() {
        Iterator edges=m_graph.getEdges().iterator();
        while (edges.hasNext()) {
            Edge edge=(Edge)edges.next();
            Node from=edge.getFrom();
            Node to=edge.getTo();
            double deltaX=to.getX()-from.getX();
            double deltaY=to.getY()-from.getY();
            double currentLength=Math.sqrt(deltaX*deltaX+deltaY*deltaY);
            double factor=m_rigidity*currentLength/(edge.getLength()*100.0);
            double dx=deltaX*factor;
            double dy=deltaY*factor;
            // Edges pull directly in proportion to the distance between the nodes. This is good,
            // because we want the edges to be stretchy.  The edges are ideal rubberbands.
            // They don't become springs when they are too short.  That only causes the graph to oscillate.
            applyDelta(from,m_graphManager.getNodeMovement(from),dx,dy);
            applyDelta(to,m_graphManager.getNodeMovement(to),-dx,-dy);
        }
    }
    /**
     * Adjusts the pairs of nodes.
     */
    private void adjustNodePairs() {
        SubGraph currentSubGraph=m_graphManager.getFirstSubGraph();
        while (currentSubGraph!=null) {
            NodeMovement node1Movement=currentSubGraph.getFirstNodeMovement();
            while (node1Movement!=null) {
                Node node1=node1Movement.m_node;
                NodeMovement node2Movement=currentSubGraph.getFirstNodeMovement();
                while (node2Movement!=null) {
                    Node node2=node2Movement.m_node;
                    if (node1!=node2) {
                        double dx=0;
                        double dy=0;
                        double deltaX=node1.getX()-node2.getX();
                        double deltaY=node1.getY()-node2.getY();
                        double currentLengthSquared=deltaX*deltaX+deltaY*deltaY; //so it's length squared
                        if (Math.abs(currentLengthSquared)<0.1) {
                            dx=Math.random(); //If two nodes are right on top of each other, randomly separate
                            dy=Math.random();
                        }
                        else if (currentLengthSquared<600*600) {    // 600, because we don't want deleted nodes to fly too far away
                            dx=deltaX/currentLengthSquared;         // If it was sqrt(len) then a single node surrounded by many others will
                            dy=deltaY/currentLengthSquared;         // always look like a circle.  This might look good at first, but I think
                                                                    // it makes large graphs look ugly+it contributes to oscillation.  A
                                                                    // linear function does not fall off fast enough, so you get rough edges
                                                                    // in the 'force field'
                        }
                        double factor=100.0*node1.getRepulsion()*node2.getRepulsion()*m_rigidity;
                        dx*=factor;
                        dy*=factor;
                        applyDelta(node1,node1Movement,dx,dy);
                        applyDelta(node2,node2Movement,-dx,-dy);
                    }
                    node2Movement=(NodeMovement)node2Movement.m_next;
                }
                node1Movement=(NodeMovement)node1Movement.m_next;
            }
            currentSubGraph=(SubGraph)currentSubGraph.m_next;
        }
    }
    /**
     * Moves nodes for the computed delta.
     */
    protected void moveNodes() {
        double lastMaxMotion=m_maxMotion;
        m_maxMotion=0;
        Iterator iterator=m_graph.getNodes().iterator();
        while (iterator.hasNext()) {
            Node node=(Node)iterator.next();
            NodeMovement movement=m_graphManager.getNodeMovement(node);
            double dx=movement.m_dx;
            double dy=movement.m_dy;
            dx*=m_damper;   // The damper slows things down.  It cuts down jiggling at the last moment, and optimizes
            dy*=m_damper;   // layout.  As an experiment, get rid of the damper in these lines, and make a
                            // long straight line of nodes.  It wiggles too much and doesn't straighten out.
            // Slow down, but don't stop.  Nodes in motion store momentum.  This helps when the force
            // on a node is very low, but you still want to get optimal layout.
            movement.m_dx=dx/2;
            movement.m_dy=dy/2;
            if (!node.isFixed()) {
                double distanceMoved=Math.sqrt(dx*dx+dy*dy);
                // Don't move faster then 30 units at a time. Important in order toprevent severed nodes from flying away.
                double x=node.getX()+Math.max(-30,Math.min(30,dx));
                double y=node.getY()+Math.max(-30,Math.min(30,dy));
                node.setLocation(x,y);
                m_maxMotion=Math.max(distanceMoved,m_maxMotion);
            }
            if (movement.m_justChanged) {
                if (System.currentTimeMillis()>movement.m_timeWhenNodeBecomesNormal)
                    movement.m_justChanged=false;
            }
        }
        if (m_maxMotion>0)
            m_motionRatio=lastMaxMotion/m_maxMotion-1; //subtract 1 to make a positive value mean that things are moving faster
        else
            m_motionRatio=0;
    }
    /**
     * Applies a delta to a node.
     *
     * @param node                      the node to which the delta is added
     * @param nodeMovement              the node movement
     * @param dx                        delta in the X direction
     * @param dy                        delta in the Y direction
     */
    protected void applyDelta(Node node,NodeMovement nodeMovement,double dx,double dy) {
        if (nodeMovement.m_justChanged) {
            nodeMovement.m_dx+=dx/10;
            nodeMovement.m_dy+=dy/10;
        }
        else {
            nodeMovement.m_dx+=dx;
            nodeMovement.m_dy+=dy;
        }
    }
    /**
     * Turns damping off.
     */
    public void stopDamper() {
        m_damping=false;
        m_damper=1.0;
    }
    /**
     * Stabilizes the graph gently, by setting the damper to a low value.
     */
    public void stopMotion() {
        m_damping=true;
        if (m_damper>0.3)
            m_damper=0.3;
        else
            m_damper=0;
    }
    /**
     * Applies the damping.
     */
    public void damp() {
        if (m_damping) {
            // This is important.  Only damp when the graph starts to move faster
            // When there is noise, you damp roughly half the time. (Which is a lot)
            // If things are slowing down, then you can let them do so on their own,
            // without damping.
            if (m_motionRatio<=0.001) {