y25.base
Class LayeredGraph

java.lang.Object
  extended byy25.base.LayeredGraph
Direct Known Subclasses:
LayeredLayoutGraph

public class LayeredGraph
extends Object

The base for the entire y25 package.

Layers

The LayeredGraph holds the graphs it is composed of in an ordered list. Adding graphs to that list is either accomplished by creating new graphs via the createGraph and duplicateGraphmethods or by importing an existing graph not created by the previous methods using the importGraph method. The order of the graphs is guaranteed not to change as long as no new graphs are created. Iterating over the graphs is usually accomplished by getting a GraphCursor via the graphs method. (See GraphCursor or the package description for an example.)

LayerEdges

In addition to the graphs, the LayeredGraph also stores LayerEdges. These are edges between arbitrary nodes inside the layered graph, i.e. the layer edge can have a source node residing in one graph and a target node residing in another graph - something that is not allowed for ordinary edges as used in the yFiles library. Creating these layer edges can be accomplished only by utilizing the layered graph createLayerEdge method (since the only constructor of the LayerEdge is made protected).

IDs

Most applications of the LayeredGraph require means of identifying nodes and edges across multiple layers. Therefore, each node and each edge inside a LayeredGraph has its own id. Newly created nodes or edges automatically recieve a new and unique id (valid ids are in the range [1,inf)), which can be read and changed by the get[Node|Edge]Id and set[Node|Edge]Id methods. Different nodes can have the same id, the same is true for edges. This way, nodes or edges belonging to different layers inside the LayeredGraph can be marked as beeing logically the same.

Additionaly, every node can be assigned a parent id. The default for every node is a parent id of 0, which means that this node has no parents. Again, getParentId and setParentId can be used to access the parent id of a node.

Maps

When working with a LayeredGraph, sometimes there is a need for attaching data to its nodes, edges, layer edges or layers. For this reason, maps can be created for each entities by using the create[Node|Edge|LayerEdge|Graph]Map methods.

Building a LayeredGraph

A common way to build a layered graph is to start with one layer, do some work on it, then add another layer that has the same contents as the layer before and modify some aspects of it, then create yet another layer with the same contents as the second layer, do some modifications on it etc. This work path can be accomplished by the following template:
      // create the LayeredGraph
      LayeredGraph lg = new LayeredGraph();
      
      // create the first layer
      Graph currentLayer = lg.createGraph();
      
      // do some work on the first layer
      ...
      
      while ( stillNewLayersToAdd ) {
          
          // create a new layer with the same contents as the one before
          currentLayer = lg.duplicateGraph(currentLayer);
          
          // do some work on the new layer
          ...
      }
 

Subclassing LayeredGraph

When subclassing this layered graph, it is important to define the type of graphs this layered graph will store. Currently, this layered graph stores Graphs, but subclasses may need to store other types, for instance LayoutGraphs or Graph2Ds.

Defining the type of graphs that are stored is done by assigning the type of the used graphs to the variable graphType in the constructor:

 graphType = Graph.class;
 
 or
 
 graphType = Graph2D.class;
 


Nested Class Summary
protected  class LayeredGraph.EdgeMapImpl
          An Implementation of the EdgeMap interface based on a HashMap.
protected  class LayeredGraph.GraphMapImpl
          An Implementation of the GraphMap interface based on a HashMap.
protected  class LayeredGraph.IDAssigner
          A GraphListener that is responsible for assigning new and unique IDs to newly created nodes and edges in graphs that belong to this LayeredGraph.
protected  class LayeredGraph.IDCreator
          A utility class that creates unique IDs.
protected  class LayeredGraph.LayerEdgeMapImpl
          An Implementation of the LayerEdgeMap interface based on a HashMap.
protected  class LayeredGraph.NodeMapImpl
          An Implementation of the NodeMap interface based on a HashMap.
 
Field Summary
static int AFTER
          Object insertion specifier.
static int BEFORE
          Object insertion specifier.
static Object EDGE_ID_DPKEY
          This key is used to register a DataProvider with a graph, that holds the IDs of the graphs edges.
protected  LayeredGraph.IDCreator edgeIDCreator
          Utilized by idAssigner to create new edge IDs and to store and free already used IDs.
protected  GraphList graphList
          Stores the graphs that compose this layered graph in an ordered fashion.
protected  Class graphType
          Specifies the type of the graphs this layered graph stores in the graphList.
protected  LayeredGraph.IDAssigner idAssigner
          Assigns new and unique IDs to all newly created nodes and edges.
protected  NodeMap inLayerEdges
          Stores a list of incoming layer edges for each node that has at least one incoming layer edge.
protected  LayerEdgeList layerEdgeList
          Stores all edges between different layers in this layered graph.
static Object NODE_ID_DPKEY
          This key is used to register a DataProvider with a graph, that holds the IDs of the graphs nodes.
protected  LayeredGraph.IDCreator nodeIDCreator
          Utilized by idAssigner to create new node IDs and to store and free already used IDs.
protected  NodeMap outLayerEdges
          Stores a list of outgoing layer edges for each node that has at least one outgoing layer edge.
static Object PARENT_ID_DPKEY
          This key is used to register a DataProvider with a graph, that holds the parent IDs of the graphs nodes.
 
Constructor Summary
LayeredGraph()
          Instantiates an empty LayeredGraph object.
 
Method Summary
 void clear()
          Resets the LayeredGraph to its initial state.
 void clearLayerEdges()
          Removes all layer edges present in this LayeredGraph.
protected  void copyCreateStructureData(Graph graph, Graph copy)
          Helper method for importGraph.
 EdgeMap createEdgeMap()
          Creates an EdgeMap and returns it.
 Graph createGraph()
          Creates a new graph and returns it.
 Graph createGraph(int where, Graph reference)
          Creates a new graph at a specified location and returns it.
 GraphMap createGraphMap()
          Creates a GraphMap and returns it.
 LayerEdge createLayerEdge(Node source, Node target)
          Creates a new layer edge from the source to the target node.
 LayerEdgeMap createLayerEdgeMap()
          Creates a LayerEdgeMap and returns it.
 NodeMap createNodeMap()
          Creates a NodeMap and returns it.
 Graph duplicateGraph(Graph original)
          Creates a new graph by copying the passed graph.
 int E()
          Returns the number of edges (layer edges are not included) inside this LayeredGraph.
 int edgeCount()
          Returns the number of edges (layer edges are not included) inside this LayeredGraph.
 int G()
          Returns the number of graphs inside this LayeredGraph.
 int getEdgeID(Edge e)
          Returns the edge ID of the passed edge.
 Graph[] getGraphArray()
          Returns an array of all graphs inside this LayeredGraph.
 GraphCursor getGraphCursorAfter(Graph ref)
          Returns a cursor over all graphs inside this LayeredGraph that occur after the given reference.
 GraphCursor getGraphCursorBefore(Graph ref)
          Returns a cursor over all graphs inside this LayeredGraph that occur before the given reference.
 LayerEdge[] getLayerEdgeArray()
          Returns an array of all layer edges inside this LayeredGraph.
 int getNodeID(Node n)
          Returns the ID of the passed node.
 int getParentID(Node n)
          Returns the ID of the parent of the passed node.
 int graphCount()
          Returns the number of graphs inside this LayeredGraph.
 GraphCursor graphs()
          Returns a cursor over all graphs inside this LayeredGraph.
 Graph importGraph(Graph graph)
          Creates a new graph by copying the passed graph.
 LayerEdgeCursor inLayerEdges(Node node)
          Returns a cursor over all layer edges that have the given node as their target.
 int layerEdgeCount()
          Returns the number of layer edges inside this LayeredGraph.
 LayerEdgeCursor layerEdges()
          Returns a cursor over all layer edges inside this LayeredGraph.
 int LE()
          Returns the number of layer edges inside this LayeredGraph.
 void moveBackward(Graph graph)
          Moves the passed graph backward in the graph list.
 void moveForward(Graph graph)
          Moves the passed graph forward in the graph list.
 void moveToBack(Graph graph)
          Moves the passed graph to the back of the graph list.
 void moveToFront(Graph graph)
          Moves the passed graph to the front of the graph list.
 int N()
          Returns the number of nodes inside this LayeredGraph.
 int nodeCount()
          Returns the number of nodes inside this LayeredGraph.
 LayerEdgeCursor outLayerEdges(Node node)
          Returns a cursor over all layer edges that originate from the given node.
 void removeGraph(Graph graph)
          Removes the passed graph from this LayeredGraph.
 void removeLayerEdge(LayerEdge layerEdge)
          Removes the passed layer edge from this LayeredGraph.
 int setEdgeID(Edge e, int id)
          Sets the ID of the passed edge to the value specified by id.
 int setNodeID(Node n, int id)
          Sets the ID of the passed node to the value specified by id.
 int setParentID(Node n, int id)
          Sets the parent ID for the given node.
 void sortGraphs(Comparator comparator)
          Sorts the graphs with respect to the given Comparator.
 String toString()
          Prints a string representation of this LayeredGraph.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

BEFORE

public static final int BEFORE
Object insertion specifier. Object gets inserted before another one.

See Also:
Constant Field Values

AFTER

public static final int AFTER
Object insertion specifier. Object gets inserted after another one.

See Also:
Constant Field Values

NODE_ID_DPKEY

public static final Object NODE_ID_DPKEY
This key is used to register a DataProvider with a graph, that holds the IDs of the graphs nodes.


PARENT_ID_DPKEY

public static final Object PARENT_ID_DPKEY
This key is used to register a DataProvider with a graph, that holds the parent IDs of the graphs nodes.


EDGE_ID_DPKEY

public static final Object EDGE_ID_DPKEY
This key is used to register a DataProvider with a graph, that holds the IDs of the graphs edges.


graphType

protected Class graphType
Specifies the type of the graphs this layered graph stores in the graphList. This type is also used whenever a new Graph has to be created, for example in the createGraph methods. Therefore the type stored in this variable always needs to have a default constructor !


graphList

protected GraphList graphList
Stores the graphs that compose this layered graph in an ordered fashion.


layerEdgeList

protected LayerEdgeList layerEdgeList
Stores all edges between different layers in this layered graph.


outLayerEdges

protected NodeMap outLayerEdges
Stores a list of outgoing layer edges for each node that has at least one outgoing layer edge.


inLayerEdges

protected NodeMap inLayerEdges
Stores a list of incoming layer edges for each node that has at least one incoming layer edge.


idAssigner

protected LayeredGraph.IDAssigner idAssigner
Assigns new and unique IDs to all newly created nodes and edges.


nodeIDCreator

protected LayeredGraph.IDCreator nodeIDCreator
Utilized by idAssigner to create new node IDs and to store and free already used IDs.


edgeIDCreator

protected LayeredGraph.IDCreator edgeIDCreator
Utilized by idAssigner to create new edge IDs and to store and free already used IDs.

Constructor Detail

LayeredGraph

public LayeredGraph()
Instantiates an empty LayeredGraph object.

Method Detail

clear

public void clear()
Resets the LayeredGraph to its initial state. More precisely, this means that all graphs and layer edges are removed and the automatic ID assignment process is reset (i.e. newly created IDs start from 1).

Subclasses should override this method by first doing the work necessary on their part and then calling clear.


clearLayerEdges

public void clearLayerEdges()
Removes all layer edges present in this LayeredGraph.

Subclasses should override this method by first doing the work necessary on their part and then calling super.clearLayerEdges.


createGraph

public Graph createGraph()
Creates a new graph and returns it. The new graph will be located at the end of the graph list inside the LayeredGraph.

The returned graph automatically assigns new and unique IDs to nodes and edges as soon as they are created. After creation, changing these automatically assigned IDs is accomplished by calling the LayeredGraph methods setNodeID, setParentID and setEdgeID.

Returns:
The newly created graph.

createGraph

public Graph createGraph(int where,
                         Graph reference)
Creates a new graph at a specified location and returns it.

The returned graph automatically assigns new and unique IDs to nodes and edges as soon as they are created. After creation, changing these automatically assigned IDs is accomplished by calling the LayeredGraph methods setNodeID, setParentID and setEdgeID.

Parameters:
where - Can be either LayeredGraph.BEFORE or LayeredGraph.AFTER. In the fromer case, the new graph is inserted into the list right before the passed reference graph, in the latter case it is inserted after the passed reference graph.
reference - A graph that is already in the graph list of this LayeredGraph. If null is passed, the newly created graph is inserted at the very beginning of the list if where is LayeredGraph.BEFORE or at the very end of the graph list if where is LayeredGraph.AFTER.
Returns:
The newly created graph.

duplicateGraph

public Graph duplicateGraph(Graph original)
Creates a new graph by copying the passed graph. The passed graph has to be part of this LayeredGraph. The new graph's location inside the graph list will be right after the original graph.

The new graph is then returned. It has exactly the same nodes and edges as the original graph. All node, edge and parent IDs are also identical to the original. The returned graph automatically assigns new and unique IDs to newly created nodes and edges. After creation, changing these automatically assigned IDs is accomplished by calling the LayeredGraph methods setNodeID, setParentID and setEdgeID.

Parameters:
original - the graph that will be copied.
Returns:
the newly created graph that is a duplicate of the original.

importGraph

public Graph importGraph(Graph graph)
Creates a new graph by copying the passed graph. The difference to the duplicateGraph method is, that the passed graph is not part of this layered graph. If you already have code that generates a graph and you want to use that graph inside a layered graph, this is the method you have to use. (It is an error to pass a graph that is already inside this layered graph to this method.)

The new graph will be located at the end of the graph list inside the LayeredGraph. It has exactly the same nodes and edges as the original graph.

Regarding node, edge and parent IDs, there are two possibilities:

  1. If the graph you pass has no DataProviders for the keys LayeredGraph.NODE_ID_DPKEY, LayeredGraph.PARENT_ID_DPKEY and LayeredGraph.EDGE_ID_DPKEY, new IDs will be created for every node and edge in the copied graph. The parent IDs will all be set to 0.
  2. If you want to specify node, edge and parent IDs, you have to register DataProviders for the following keys: LayeredGraph.NODE_ID_DPKEY, LayeredGraph.PARENT_ID_DPKEY, LayeredGraph.EDGE_ID_DPKEY. Then you can assign node, edge and parent IDs as you like. These IDs will then be copied to the new graph that is created. Note that you have to perform these steps before you call this method.
The new graph automatically assigns new and unique IDs to newly created nodes and edges. After creation, changing these automatically assigned IDs is accomplished by calling the LayeredGraph methods setNodeID, setParentID and setEdgeID.

Parameters:
graph - the graph that will be copied.
Returns:
the newly created graph that is a duplicate of the passed graph.

copyCreateStructureData

protected void copyCreateStructureData(Graph graph,
                                       Graph copy)
Helper method for importGraph.

This method copies structure data (node, edge and parent IDs) from graph to copy. copy has to have exactly the same number and order of nodes and edges as graph.

If the original graph has only partial structure information (say, it only has node IDs but no edge and no parent IDs, and not every node has a valid ID (!=0)), structure data is created as follows: Nodes without IDs get a new ID, edges without IDs get a new ID and nodes without a parent ID get 0 assigned.

Parameters:
graph -
copy -

removeGraph

public void removeGraph(Graph graph)
Removes the passed graph from this LayeredGraph.

All node and edge IDs that were associated with some node or edge inside this graph will be freed for reuse by the automatic ID assignment process. This is only the case, however, if the same node or edge ID is not used by another node or edge inside this LayeredGraph. If a node ID is freed, the parent IDs of all child nodes are set to 0.

All layer edges originating or ending at some node inside the removed graph will be removed as well.

Subclasses should override this method by first doing the work necessary on their part and then calling super.removeGraph.

After the graph has been removed, it can still be used by the user. The LayeredGraph has no further responsibility for the graph and the graph is not tied to the LayeredGraph by any means. The structure information that was present before removal (node/parent/edge ids) is not deleted, however, and is still available in the removed graph. To retrieve this information, no mehods from LayeredGraph can be used, but one has to manually retrieve the DataProviders for the given keys (LayeredGraph.NODE_ID_DPKEY, LayeredGraph.PARENT_ID_DPKEY, LayeredGraph.EDGE_ID_DPKEY) instead. Since all ties to the LayeredGraph are broken, newly created nodes and edges in the removed graph do not automatically recieve a new ID. Also, creation of new layer edges starting or ending in that graph is no longer possible.

Parameters:
graph - The graph that will be removed.

createLayerEdge

public LayerEdge createLayerEdge(Node source,
                                 Node target)
Creates a new layer edge from the source to the target node. Both nodes must be inside graphs that belong to this LayeredGraph.

Parameters:
source - The source node for the layer edge.
target - The target node for the layer edge.
Returns:
The newly created layer edge.

removeLayerEdge

public void removeLayerEdge(LayerEdge layerEdge)
Removes the passed layer edge from this LayeredGraph.

Subclasses should override this method by first doing the work necessary on their part and then calling super.removeLayerEdge.

Parameters:
layerEdge - The layer edge that will be removed.

moveForward

public void moveForward(Graph graph)
Moves the passed graph forward in the graph list. The passed graph has to be part of this layered graph. If it is already at the front of the graph list, nothing happens.

The first entry in the graph list is considered to be the backmost, the last entry is considered to be frontmost.


moveToFront

public void moveToFront(Graph graph)
Moves the passed graph to the front of the graph list. The passed graph has to be part of this layered graph. If it is already at the front of the graph list, nothing happens.

The first entry in the graph list is considered to be the backmost, the last entry is considered to be frontmost.


moveBackward

public void moveBackward(Graph graph)
Moves the passed graph backward in the graph list. The passed graph has to be part of this layered graph. If it is already at the back of the graph list, nothing happens.

The first entry in the graph list is considered to be the backmost, the last entry is considered to be frontmost.


moveToBack

public void moveToBack(Graph graph)
Moves the passed graph to the back of the graph list. The passed graph has to be part of this layered graph. If it is already at the back of the graph list, nothing happens.

The first entry in the graph list is considered to be the backmost, the last entry is considered to be frontmost.


getNodeID

public int getNodeID(Node n)
Returns the ID of the passed node. Valid node IDs are in the range [1,inf).


getParentID

public int getParentID(Node n)
Returns the ID of the parent of the passed node. A return value of 0 indicates, that the passed node has no parent.


getEdgeID

public int getEdgeID(Edge e)
Returns the edge ID of the passed edge. Valid edge IDs are in the range [1,inf).


setNodeID

public int setNodeID(Node n,
                     int id)
Sets the ID of the passed node to the value specified by id.

Parameters:
n - The node whose ID is to be set.
id - The new ID of the node. Valid IDs are in the range [1,inf). When 0 is passed, a new and unique ID will be created that has not been used by any other node. If a value less than 0 is passed, this method will not fail but assign that value to the node even if it is not a valid id. This way you can temporarily mark nodes, but you are responsible to reset the ID to a valid number.
Returns:
The ID that has been assigned to the given node.

setParentID

public int setParentID(Node n,
                       int id)
Sets the parent ID for the given node.

Parameters:
n - The node whose parent ID is to be set.
id - The ID of the parent of the given node. Valid IDs are in the range [1,inf). A value of 0 is also allowed and means, that the given node has no parent. When a value less than 0 is passed the method will not fail but stores that value as the parent ID of the node even if it is not a valid ID. This way you can temporarily mark nodes, but you are responsible to reset the ID to a valid number. Note that no actual node with the passed ID needs to exist. This gives you the possibility of assigning a parent ID to a node even if the parent node itself is not created yet. To ensure that this works correctly, the automatic ID assignment process is notified of the new parent ID, so that it does not accidentaly assign that ID to a newly created node.
Returns:
The parent ID that has been assigned to the given node.

setEdgeID

public int setEdgeID(Edge e,
                     int id)
Sets the ID of the passed edge to the value specified by id.

Parameters:
e - The edge whose ID is to be set.
id - The new ID of the edge. Valid IDs are in the range [1,inf). When 0 is passed, a new and unique ID will be created that has not been used by any other edge. If a value less than 0 is passed, this method will not fail but assign that value to the edge even if it is not a valid id. This way you can temporarily mark edges, but you are responsible to reset the ID to a valid number.
Returns:
The ID that has been assigned to the given edge.

G

public int G()
Returns the number of graphs inside this LayeredGraph.


graphCount

public int graphCount()
Returns the number of graphs inside this LayeredGraph.


LE

public int LE()
Returns the number of layer edges inside this LayeredGraph.


layerEdgeCount

public int layerEdgeCount()
Returns the number of layer edges inside this LayeredGraph.


N

public int N()
Returns the number of nodes inside this LayeredGraph. This is just the sum of the node counts of the graphs that belong to this LayeredGraph.


nodeCount

public int nodeCount()
Returns the number of nodes inside this LayeredGraph. This is just the sum of the node counts of the graphs that belong to this LayeredGraph.


E

public int E()
Returns the number of edges (layer edges are not included) inside this LayeredGraph. This is just the sum of the edge counts of the graphs that belong to this LayeredGraph.


edgeCount

public int edgeCount()
Returns the number of edges (layer edges are not included) inside this LayeredGraph. This is just the sum of the edge counts of the graphs that belong to this LayeredGraph.


sortGraphs

public void sortGraphs(Comparator comparator)
Sorts the graphs with respect to the given Comparator.


graphs

public GraphCursor graphs()
Returns a cursor over all graphs inside this LayeredGraph.


getGraphCursorAfter

public GraphCursor getGraphCursorAfter(Graph ref)
Returns a cursor over all graphs inside this LayeredGraph that occur after the given reference. So, if the list of graphs can be decomposed into 3 sublists [g_first...g_(ref-1)] [g_ref] [g_(ref+1)...g_last], this method returns a cursor over the last sublist.

Parameters:
ref - The reference graph as described above.

getGraphCursorBefore

public GraphCursor getGraphCursorBefore(Graph ref)
Returns a cursor over all graphs inside this LayeredGraph that occur before the given reference. So, if the list of graphs can be decomposed into 3 sublists [g_first...g_(ref-1)] [g_ref] [g_(ref+1)...g_last], this method returns a cursor over the first sublist.

Parameters:
ref - The reference graph as described above.

layerEdges

public LayerEdgeCursor layerEdges()
Returns a cursor over all layer edges inside this LayeredGraph.


outLayerEdges

public LayerEdgeCursor outLayerEdges(Node node)
Returns a cursor over all layer edges that originate from the given node.

Parameters:
node - The source of the layer edges.
Returns:
A cursor over all outgoing layer edges starting at the given node.

inLayerEdges

public LayerEdgeCursor inLayerEdges(Node node)
Returns a cursor over all layer edges that have the given node as their target.

Parameters:
node - The target of the layer edges.
Returns:
A cursor over all incoming layer edges at the given node.

getGraphArray

public Graph[] getGraphArray()
Returns an array of all graphs inside this LayeredGraph.


getLayerEdgeArray

public LayerEdge[] getLayerEdgeArray()
Returns an array of all layer edges inside this LayeredGraph.


createNodeMap

public NodeMap createNodeMap()
Creates a NodeMap and returns it. In contrast to the y.base.NodeMap this NodeMap can be used for mapping values to nodes from different graphs.


createEdgeMap

public EdgeMap createEdgeMap()
Creates an EdgeMap and returns it. In contrast to the y.base.EdgeMap this EdgeMap can be used for mapping values to edges from different graphs.


createGraphMap

public GraphMap createGraphMap()
Creates a GraphMap and returns it.


createLayerEdgeMap

public LayerEdgeMap createLayerEdgeMap()
Creates a LayerEdgeMap and returns it.


toString

public String toString()
Prints a string representation of this LayeredGraph.

See Also:
Object.toString()