Package diva.graph.layout

Class LevelLayout

  • All Implemented Interfaces:
    GlobalLayout
    public class LevelLayout
extends AbstractGlobalLayout
    A level-based layout algorithm originally implemented by Ulfar Erlingsson at Cornell/RPI and modified to fit into this system.

    The algorithm is structured in the following way:

    • Copy the original graph. The copy will be augmented with dummy nodes, edges, etc. The method which performs the copy can be overridden in a subclass so that the the layout can be customized. For example, one might wish to create dummy edges from a composite node, which represent edges from subnodes of the composite node to subnodes in other composite nodes in the graph (e.g. if you are laying out a circuit schematic, with composite nodes representing components and subnodes representing pins on the components).
    • Perform the levelizing layout on the graph copy. This process consists of several steps:
      • Calculate the levels of the nodes in the graph.
      • Add dummy nodes on edges which span multiple levels in the graph.
      • Perform a sorting on each level in the graph based on some cost function (not yet implemented).
      • Assign a position based on the level and sorting order of the node.
    • Copy the layout results from the graph copy back into the original graph, ignoring dummy nodes. This should also be overridden if the copy process was overridden (described above).
    TODO:
    • Break cycles in the graph.
    • Implement barycentric layout (currently commented out).
    Version:
    $Id$
    Author:
    Michael Shilman
    Pt.AcceptedRating:
    Red

    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      class  LevelLayout.LevelData  
      static class  LevelLayout.LevelInfo
      The semantic object of each node in the graph copy that is being laid out.

    • Field Summary

      Fields 
      Modifier and Type Field Description
      protected int _orientation
      Keep track of the orientation; vertical by default.
      static int HORIZONTAL
      Layout the graph in levels from left to right.
      static int VERTICAL
      Layout the graph in levels from top to bottom.

    • Constructor Summary

      Constructors 
      Constructor Description
      LevelLayout​(LayoutTarget target)
      Construct a new levelizing layout with a vertical orientation.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void applyLayout​(LevelLayout.LevelData levelData, java.lang.Object g)
      Place the nodes in the target environment according to their levels and sorting order which are specified in levelData.
      void applyLayout​(LevelLayout.LevelData levelData, java.lang.Object g, boolean useDummies)
      Place the nodes in the target environment according to their levels and sorting order which are specified in levelData.
      LevelLayout.LevelData calculateLayout​(java.lang.Object composite)
      This method performs levelizing layout on the given composite.
      protected java.lang.Object copyComposite​(java.lang.Object origComposite)
      Copy the given graph and make the nodes/edges in the copied graph point to the nodes/edges in the original.
      protected void copyLayout​(java.lang.Object origComposite, java.lang.Object copyComposite)
      Take the layout generated by the core layout algorithm and copy it back into the view of the original composite passed in by the user.
      BasicGraphModel getLocalGraphModel()
      Return the local graph model.
      int getOrientation()
      Return the orientation in which the graph is to be laid out, either VERTICAL or HORIZONTAL.
      boolean getRandomizedPlacement()
      Return whether or not placement will be randomized.
      boolean isVisited​(java.lang.Object node)  
      void layout​(java.lang.Object composite)
      Perform the levelizing layout on the given composite in the given target environment.
      void setAllVisited​(java.lang.Object composite, boolean val)  
      void setOrientation​(int o)
      Set the orientation in which the graph is to be laid out, either VERTICAL or HORIZONTAL.
      void setRandomizedPlacement​(boolean flag)
      Set whether or not placement will be randomized.
      void setVisited​(java.lang.Object node, boolean val)  

      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • Constructor Detail

      • LevelLayout

        public LevelLayout​(LayoutTarget target)
        Construct a new levelizing layout with a vertical orientation.

    • Method Detail

      • copyComposite

        protected java.lang.Object copyComposite​(java.lang.Object origComposite)
        Copy the given graph and make the nodes/edges in the copied graph point to the nodes/edges in the original.

      • copyLayout

        protected void copyLayout​(java.lang.Object origComposite,
                          java.lang.Object copyComposite)
        Take the layout generated by the core layout algorithm and copy it back into the view of the original composite passed in by the user.

      • getLocalGraphModel

        public BasicGraphModel getLocalGraphModel()
        Return the local graph model.

      • getOrientation

        public int getOrientation()
        Return the orientation in which the graph is to be laid out, either VERTICAL or HORIZONTAL.

      • getRandomizedPlacement

        public boolean getRandomizedPlacement()
        Return whether or not placement will be randomized.

      • layout

        public void layout​(java.lang.Object composite)
        Perform the levelizing layout on the given composite in the given target environment. It operates on a copy of the composite and then copies the layout results back into the original view (the given layout target).
        Specified by:
        layout in interface GlobalLayout
        Specified by:
        layout in class AbstractGlobalLayout

      • calculateLayout

        public LevelLayout.LevelData calculateLayout​(java.lang.Object composite)
        This method performs levelizing layout on the given composite. It figures out the node levels, but doesn't actually layout the composite in the target environment yet. The level information can be accessed through the returned LevelData. This information can be used to size the viewport. The following are the operations performed in this method:
        • Make a copy of the original composite. All operations are performed on the copy of the composite.
        • Break the cycles in the composite if there are any.
        • Add dummies to edges that span multiple levels in the composite.
        • Assign level numbers to the nodes in the composite. This creates the _levels data structure which provides access to all the nodes in each level.
        To apply this layout to the target environment, call applyLayout with the returned LevelData.

      • applyLayout

        public void applyLayout​(LevelLayout.LevelData levelData,
                        java.lang.Object g)
        Place the nodes in the target environment according to their levels and sorting order which are specified in levelData. By default, the dummy nodes are used while doing the layout. This method should be called after calculateLayout(t, g) which returns the levelData used by this method.

      • applyLayout

        public void applyLayout​(LevelLayout.LevelData levelData,
                        java.lang.Object g,
                        boolean useDummies)
        Place the nodes in the target environment according to their levels and sorting order which are specified in levelData. If "useDummies" is false, the dummy nodes are not used in the layout which produces a more compact layout: nodes in the same level may overlap and edges may cross over nodes. If "useDummies" is true, the dummy nodes are used in the layout. This method should be called after calculateLayout(t, g) which returns the levelData used by this method.

      • setOrientation

        public void setOrientation​(int o)
        Set the orientation in which the graph is to be laid out, either VERTICAL or HORIZONTAL.

      • setRandomizedPlacement

        public void setRandomizedPlacement​(boolean flag)
        Set whether or not placement will be randomized.

      • setVisited

        public void setVisited​(java.lang.Object node,
                       boolean val)

      • setAllVisited

        public void setAllVisited​(java.lang.Object composite,
                          boolean val)

      • isVisited

        public boolean isVisited​(java.lang.Object node)