Class DAGLayout<V,​E>

  • All Implemented Interfaces:
    com.google.common.base.Function<V,​java.awt.geom.Point2D>, Layout<V,​E>, IterativeContext, java.util.function.Function<V,​java.awt.geom.Point2D>

    public class DAGLayout<V,​E>
    extends SpringLayout<V,​E>
    An implementation of Layout suitable for tree-like directed acyclic graphs. Parts of it will probably not terminate if the graph is cyclic! The layout will result in directed edges pointing generally upwards. Any vertices with no successors are considered to be level 0, and tend towards the top of the layout. Any vertex has a level one greater than the maximum level of all its successors.
    • Field Detail

      • minLevels

        private java.util.Map<V,​java.lang.Number> minLevels
        Each vertex has a minimumLevel. Any vertex with no successors has minimumLevel of zero. The minimumLevel of any vertex must be strictly greater than the minimumLevel of its parents. (Vertex A is a parent of Vertex B iff there is an edge from B to A.) Typically, a vertex will have a minimumLevel which is one greater than the minimumLevel of its parent's. However, if the vertex has two parents, its minimumLevel will be one greater than the maximum of the parents'. We need to calculate the minimumLevel for each vertex. When we layout the graph, vertices cannot be drawn any higher than the minimumLevel. The graphHeight of a graph is the greatest minimumLevel that is used. We will modify the SpringLayout calculations so that nodes cannot move above their assigned minimumLevel.
      • graphHeight

        static int graphHeight
      • numRoots

        static int numRoots
      • MSV_THRESHOLD

        final double MSV_THRESHOLD
        A bunch of parameters to help work out when to stop quivering. If the MeanSquareVel(ocity) ever gets below the MSV_THRESHOLD, then we will start a final cool-down phase of COOL_DOWN_INCREMENT increments. If the MeanSquareVel ever exceeds the threshold, we will exit the cool down phase, and continue looking for another opportunity.
        See Also:
        Constant Field Values
      • meanSquareVel

        double meanSquareVel
      • stoppingIncrements

        boolean stoppingIncrements
      • incrementsLeft

        int incrementsLeft
    • Constructor Detail

      • DAGLayout

        public DAGLayout​(Graph<V,​E> g)
    • Method Detail

      • setRoot

        public void setRoot()
        Calculates the level of each vertex in the graph. Level 0 is allocated to each vertex with no successors. Level n+1 is allocated to any vertex whose successors' maximum level is n.
      • setRoot

        public void setRoot​(V v)
        Set vertex v to be level 0.
        Parameters:
        v - the vertex to set as root
      • propagateMinimumLevel

        public void propagateMinimumLevel​(V v)
        A recursive method for allocating the level for each vertex. Ensures that all predecessors of v have a level which is at least one greater than the level of v.
        Parameters:
        v - the vertex whose minimum level is to be calculated
      • initializeLocation

        private void initializeLocation​(V v,
                                        java.awt.geom.Point2D coord,
                                        java.awt.Dimension d)
        Sets a random location for a vertex within the dimensions of the space.
        Parameters:
        v - the vertex whose position is to be set
        coord - the coordinates of the vertex once the position has been set
        d - the dimensions of the space
      • setSize

        public void setSize​(java.awt.Dimension size)
        Description copied from class: AbstractLayout
        When a visualization is resized, it presumably wants to fix the locations of the vertices and possibly to reinitialize its data. The current method calls initializeLocations followed by initialize_local.
        Specified by:
        setSize in interface Layout<V,​E>
        Overrides:
        setSize in class SpringLayout<V,​E>
        Parameters:
        size - the space to use to lay out this graph
      • initialize

        public void initialize()
        Had to override this one as well, to ensure that setRoot() is called.
        Specified by:
        initialize in interface Layout<V,​E>
        Overrides:
        initialize in class SpringLayout<V,​E>
      • moveNodes

        protected void moveNodes()
        Override the moveNodes() method from SpringLayout. The only change we need to make is to make sure that nodes don't float higher than the minY coordinate, as calculated by their minimumLevel.
        Overrides:
        moveNodes in class SpringLayout<V,​E>
      • done

        public boolean done()
        Override incrementsAreDone so that we can eventually stop.
        Specified by:
        done in interface IterativeContext
        Overrides:
        done in class SpringLayout<V,​E>
        Returns:
        false
      • setLocation

        public void setLocation​(V picked,
                                double x,
                                double y)
        Override forceMove so that if someone moves a node, we can re-layout everything.
        Overrides:
        setLocation in class AbstractLayout<V,​E>
        Parameters:
        picked - the vertex whose location is to be set
        x - the x coordinate of the location to set
        y - the y coordinate of the location to set
      • setLocation

        public void setLocation​(V picked,
                                java.awt.geom.Point2D p)
        Override forceMove so that if someone moves a node, we can re-layout everything.
        Specified by:
        setLocation in interface Layout<V,​E>
        Overrides:
        setLocation in class AbstractLayout<V,​E>
        Parameters:
        picked - the vertex whose location is to be set
        p - the location to set
      • relaxEdges

        protected void relaxEdges()
        Overridden relaxEdges. This one reduces the effect of edges between greatly different levels.
        Overrides:
        relaxEdges in class SpringLayout<V,​E>