y.layout.planar
Class PlanarInformation

java.lang.Object
  |
  +--y.layout.planar.SimplePlanarInformation
        |
        +--y.layout.planar.PlanarInformation

public class PlanarInformation
extends SimplePlanarInformation

This class defines a planar graph. It manages the faces and reverse edges of a planar graph. The edges adjacent to a node are supposed to be ordered clockwise.


Nested Class Summary
static class PlanarInformation.EdgeInfo
          Class hold all information related to an edge.
static class PlanarInformation.NodeInfo
          Class hold all information related to a node.
 
Nested classes inherited from class y.layout.planar.SimplePlanarInformation
 
Field Summary
static int SPLIT
           
static int UNIFY
           
 
Fields inherited from class y.layout.planar.SimplePlanarInformation
faceList, graph, outerFace
 
Constructor Summary
PlanarInformation(Graph graph)
          Returns a new instance of Planar Information for a graph.
 
Method Summary
 void addSubdivisionHandler(SubdivisionHandler handler)
           
 Face bridgeFace(Edge e)
          This method updates the faces of the graph when an edge is inserted which connects two diferent connected components.
 Face bridgeFace(Edge e, Edge _start, Edge _stop)
          This method updates the faces of the graph when an edge is inserted which connects two diferent connected components.
 void checkEdgeRecovery()
          Verifies if the edge recovery information is consistent.
 int countCrossings()
          Returns the number of dummy nodes currently contained in the graph
protected  PlanarInformation.EdgeInfo createEdgeInfo()
          Factory to create edge tupels.
protected  PlanarInformation.NodeInfo createNodeInfo()
          Factory to create edge tupels.
protected  SimplePlanarInformation.SimpleEdgeInfo createSimpleEdgeInfo()
          Factory to create edge tupels.
 void dispose()
          Remove all information from graph concerning planar Information: reverse Edge-Key,inserted reverse edges
 void doEdgeRecovery()
          this method restores all the substituted edges in the graph and removes the dummy nodes that represent crossings
 void doRemoveOriginalEdges(EdgeList _el)
          Removes a list of edges from the graph.
protected  void fireSplitFaceEvent(Edge e, Face[] oldFaces, Face[] newFaces)
           
protected  void fireSubdivisionEvent(Edge e, Edge[] result)
           
protected  void fireUnsplitFaceEvent(Edge e, Face[] oldFaces, Face[] newFaces)
           
protected  void fireUnsubdivideEvent(Edge[] splitEdges, Edge resultingEdge)
           
 EdgeCursor getCurrentPath(Edge edge)
          This method returns the path generated by split operations on one edge.
protected  PlanarInformation.EdgeInfo getEdgeInfo(Edge edge)
          Returns the information for an edge.
protected  PlanarInformation.NodeInfo getNodeInfo(Node node)
          Returns the information for an edge.
 int getType(Node node)
          Returns the type of a node.
 Edge getUnsplitEdge(Edge edge)
          This method returns the original edge for a split edge.
 void insertNodeWithEdge(Edge edge, Node node, Face face)
          Insert a node with one edge into a face.
 boolean isBend(Node node)
          Returns if a node is a dummy node representing a bend.
 boolean isCrossing(Node node)
          Returns if a node is a dummy node representing a crossing.
 boolean isVertex(Node node)
          Returns if a node is a real node and no dummy node.
 void markAsBend(Node node)
          Sets, that a node should be handeled like a dummy node representing a bend.
 void markAsCrossing(Node node)
          Marks a vertex as crossing.
 void markAsOriginalEdge(Edge edge)
          Marks an edge as original
 void markAsVertex(Node node)
          Sets, that a node should be handeled like a real node in a graph.
 void removeSubdivisionHandler(SubdivisionHandler handler)
           
 void setType(Node node, int type)
          Sets the type for a node.
 void showEdgeRecoveryInfo(boolean verbose)
          this method shows all edges being split to planarize the graph and what has become of them (a list of subedges).
 Face[] splitFace(Face _face, Edge _edge)
          Splits a face into two parts by introducing an edge.
 Face[] splitFace(Face _face, Edge _e, Edge _start, Edge _stop)
          Splits a face into two parts by introducing an edge.
 void splitFaceWithSelfLoop(Edge faceEdge, Edge selfLoop)
          Inserts one selfloop into an existing face.
 Node subdivideEdge(Edge edge)
          Splits an edge into two parts by introducing a dummy node.
 EdgeList subdivideEdge(Edge edge, int count)
          Splits an edge into two parts by introducing a dummy node.
 void unsplitFace(Edge e)
          this method unifies two faces seperated by a single edge.
 Edge unsubdivideEdge(Node dummyNode)
          reconstruct the edge that was subdivided to gain the dummy node given as the parameter.
 void updateEdgeRecoveryInfo(Edge e, EdgeList segments, int spec)
          this method collects bookkeeping information for consistent recovery.
 
Methods inherited from class y.layout.planar.SimplePlanarInformation
calcFaces, calcFaces, calcOrdering, createFace, createFaceMap, createReverse, cyclicNextEdge, cyclicPrevEdge, disposeFaceMap, faceCount, faceOf, faces, followingEdge, getGraph, getOuterFace, getReverse, getSimpleEdgeInfo, isInsertedEdge, isOuterFaceSetCorrectly, isPlanar, markAsInsertedEdge, setFaceOf, setIsInsertedEdge, setOuterFace, setReverse, showCircularEdgeOrder, showFaces, toString
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

UNIFY

public static final int UNIFY
See Also:
Constant Field Values

SPLIT

public static final int SPLIT
See Also:
Constant Field Values
Constructor Detail

PlanarInformation

public PlanarInformation(Graph graph)
Returns a new instance of Planar Information for a graph.

Parameters:
graph - The graph for which the planarity information is kept.
Method Detail

dispose

public void dispose()
Remove all information from graph concerning planar Information: reverse Edge-Key,inserted reverse edges

Overrides:
dispose in class SimplePlanarInformation

setType

public void setType(Node node,
                    int type)
Sets the type for a node.

Parameters:
node - a node in the graph.
type - the type marker for the node.

getType

public int getType(Node node)
Returns the type of a node.

Parameters:
node - a node in the graph.
Returns:
the type marker for the node.

isCrossing

public boolean isCrossing(Node node)
Returns if a node is a dummy node representing a crossing.

Parameters:
node - a node in the embedding
Returns:
boolean value indicating if the node is a crossing or not

markAsCrossing

public void markAsCrossing(Node node)
Marks a vertex as crossing.

Parameters:
node - The dummy node that represents a crossing

markAsBend

public void markAsBend(Node node)
Sets, that a node should be handeled like a dummy node representing a bend.


isBend

public boolean isBend(Node node)
Returns if a node is a dummy node representing a bend.


isVertex

public boolean isVertex(Node node)
Returns if a node is a real node and no dummy node.


markAsVertex

public void markAsVertex(Node node)
Sets, that a node should be handeled like a real node in a graph.


countCrossings

public int countCrossings()
Returns the number of dummy nodes currently contained in the graph

Returns:
int number of dummy nodes in the graph

splitFace

public Face[] splitFace(Face _face,
                        Edge _edge)
Splits a face into two parts by introducing an edge. The reverse edge is created.

Parameters:
_face - a face which is not a triangle.
_edge - an edge connecting two nodes in the face which are not already connected.

splitFace

public Face[] splitFace(Face _face,
                        Edge _e,
                        Edge _start,
                        Edge _stop)
Splits a face into two parts by introducing an edge. The reverse edge is created. The edges _start and _stop are given to overcome the insertion problems when the source or target of the inserted edge has bridges into the face to split.

Parameters:
_face - a face which is not a triangle.
_e - an edge connecting two nodes in the face which are not already connected.
_start - an edge after which edge _e is inserted. _start belongs to the one resulting face
_stop - the last edge of the other resulting face
Returns:
an array containing the two resulting faces

splitFaceWithSelfLoop

public void splitFaceWithSelfLoop(Edge faceEdge,
                                  Edge selfLoop)
Inserts one selfloop into an existing face.


bridgeFace

public Face bridgeFace(Edge e,
                       Edge _start,
                       Edge _stop)
This method updates the faces of the graph when an edge is inserted which connects two diferent connected components. The reverse edge is created.

Parameters:
e - edge that connects two connected components.
_start - the predecessor of e in the cyclic ordering on the source node of e, or null, if no specific predecessor is wanted.
_stop -

bridgeFace

public Face bridgeFace(Edge e)
This method updates the faces of the graph when an edge is inserted which connects two diferent connected components. The reverse edge is created.

Parameters:
e - edge that connects two connected components.

unsplitFace

public void unsplitFace(Edge e)
this method unifies two faces seperated by a single edge. The faces are identified via the the edge and its reverse

Parameters:
e - edge that seperates the two faces.

insertNodeWithEdge

public void insertNodeWithEdge(Edge edge,
                               Node node,
                               Face face)
Insert a node with one edge into a face. The reverse edge is created.

Parameters:
edge - the edge to be inserted with the node
node - the node that is inserted
face - the face in which the node is inserted

subdivideEdge

public Node subdivideEdge(Edge edge)
Splits an edge into two parts by introducing a dummy node. The reverse edge is split too. Both edges are hidden.

Parameters:
edge - the edge to be split
Returns:
the introduced dummy node.

subdivideEdge

public EdgeList subdivideEdge(Edge edge,
                              int count)
Splits an edge into two parts by introducing a dummy node. The reverse edge is split too. Both edges are hidden.

Parameters:
edge - the edge to be split
Returns:
the introduced dummy node.

unsubdivideEdge

public Edge unsubdivideEdge(Node dummyNode)
reconstruct the edge that was subdivided to gain the dummy node given as the parameter. This method is the complement of subdivideEdge.

Precondition: the node is a crossing with crossing edge removed. This means that there are exactly two incoming and two outgoing edges. So the state is the same as after applying the subdivideEdge method.

Parameters:
dummyNode - a node representing a crossing

addSubdivisionHandler

public void addSubdivisionHandler(SubdivisionHandler handler)

removeSubdivisionHandler

public void removeSubdivisionHandler(SubdivisionHandler handler)

fireSubdivisionEvent

protected void fireSubdivisionEvent(Edge e,
                                    Edge[] result)

fireUnsubdivideEvent

protected void fireUnsubdivideEvent(Edge[] splitEdges,
                                    Edge resultingEdge)

fireSplitFaceEvent

protected void fireSplitFaceEvent(Edge e,
                                  Face[] oldFaces,
                                  Face[] newFaces)

fireUnsplitFaceEvent

protected void fireUnsplitFaceEvent(Edge e,
                                    Face[] oldFaces,
                                    Face[] newFaces)

getCurrentPath

public EdgeCursor getCurrentPath(Edge edge)
This method returns the path generated by split operations on one edge. If there were no split operations, just return the edge.

Parameters:
edge - an edge currently in the graph, or which has been in the graph and has been split.

getUnsplitEdge

public Edge getUnsplitEdge(Edge edge)
This method returns the original edge for a split edge. If the edges was not split, the edge itself is returned.


updateEdgeRecoveryInfo

public void updateEdgeRecoveryInfo(Edge e,
                                   EdgeList segments,
                                   int spec)
this method collects bookkeeping information for consistent recovery. recovery means to reset the graph to the initial state (as it was on input). The meaning of the parameters e and segments depends on the recovery specificator spec.

Parameters:
e - an edge that is either substituted by segments (spec = SPLIT) or that substitutes segments (spec = UNIFY)
segments - the path that is either substituted or substitutes an edge
spec - specifies wheter an edge is split or a former splitting is undone.

doEdgeRecovery

public void doEdgeRecovery()
this method restores all the substituted edges in the graph and removes the dummy nodes that represent crossings


doRemoveOriginalEdges

public void doRemoveOriginalEdges(EdgeList _el)
Removes a list of edges from the graph. The edges may have been split by the subdivideEdge method. In this case the edges resulting from the subdivide operation are removed.

Parameters:
_el - the list of edges which should be removed.

markAsOriginalEdge

public void markAsOriginalEdge(Edge edge)
Marks an edge as original

Parameters:
edge - an edge that is as it was on insertion (not a segment of a split edge.

getNodeInfo

protected PlanarInformation.NodeInfo getNodeInfo(Node node)
Returns the information for an edge.


createNodeInfo

protected PlanarInformation.NodeInfo createNodeInfo()
Factory to create edge tupels.


getEdgeInfo

protected PlanarInformation.EdgeInfo getEdgeInfo(Edge edge)
Returns the information for an edge.


createEdgeInfo

protected PlanarInformation.EdgeInfo createEdgeInfo()
Factory to create edge tupels.


createSimpleEdgeInfo

protected SimplePlanarInformation.SimpleEdgeInfo createSimpleEdgeInfo()
Factory to create edge tupels.

Overrides:
createSimpleEdgeInfo in class SimplePlanarInformation

checkEdgeRecovery

public void checkEdgeRecovery()
Verifies if the edge recovery information is consistent. This method throws a runtime-exception if the edge recovery information is not consistent.


showEdgeRecoveryInfo

public void showEdgeRecoveryInfo(boolean verbose)
this method shows all edges being split to planarize the graph and what has become of them (a list of subedges).

Parameters:
verbose - a boolean value to indicate the wheter more or less information is wanted.

© Copyright 2000-2003,
yWorks GmbH.
All rights reserved.

2003