y.layout.planar
Class SimplePlanarInformation

java.lang.Object
  |
  +--y.layout.planar.SimplePlanarInformation
Direct Known Subclasses:
DualPlanarInformation, PlanarInformation

public class SimplePlanarInformation
extends Object

This class defines a planar embedded graph. It manages the faces and reverse edges of a planar graph.
The planar embedding of a graph is defined by the ordering of the outgoing edges arround a node and its faces. The ordering is assumed to be in mathematical positive sense, i.e., counter-clockwise ordering. Note that computer output devices usually have a mirrored coordinate system (they have the origin in the upper left corner of the output device and the y-axis pointing downward). On these devices, the mathematically positive orientation corresponds to a clockwise ordering, albeit the ordering is counter-clockwise in a pure mathematical sense.


Nested Class Summary
static class SimplePlanarInformation.SimpleEdgeInfo
          Class hold all information related to an edge.
 
Field Summary
 YList faceList
           
protected  Graph graph
           
protected  Face outerFace
           
 
Constructor Summary
SimplePlanarInformation(Graph graph)
          Returns a new instance of Planar Information for a graph.
 
Method Summary
 void calcFaces()
          Calculates the faces of the graph from a given edge order.
 void calcFaces(EdgeOrder edgeOrder)
          Calculates the faces of the graph from the cyclic order of the edges around their source nodes.
 void calcOrdering()
          Calculates the cyclic order of the edges around their source nodes from the set of faces of the graph.
 Face createFace(Edge edge, EdgeOrder edgeOrder, boolean[] mark)
          Creates a face starting at an edge and using the cyclic order of the outgoing edges.
 FaceMap createFaceMap()
          Creates a FaceMap for the faces in the graph.
 Edge createReverse(Edge edge)
          Creates the reverse edge for a given edge.
protected  SimplePlanarInformation.SimpleEdgeInfo createSimpleEdgeInfo()
          Factory to create edge tupels.
 Edge cyclicNextEdge(Edge edge)
          Returns the counterclockwise next edge of an edge at the source node.
 Edge cyclicPrevEdge(Edge edge)
          Returns the counterclockwise preceeding edge of an edge at the source node.
 void dispose()
          Remove all information from graph concerning planar Information: reverse Edge-Key,inserted reverse edges
 void disposeFaceMap(FaceMap map)
          Disposes a FaceMap formerly created with createFaceMap().
 int faceCount()
          Returns the number of Faces.
 Face faceOf(Edge edge)
          Get the face to which an edge belongs.
 FaceCursor faces()
          Get cursor over faces.
protected  Edge followingEdge(Edge e)
          Returns the counterclockwise next edge of another edge around a node
 Graph getGraph()
          Returns the graph for which this planar information is kept.
 Face getOuterFace()
          Returns the outer face of the planar graph
 Edge getReverse(Edge e)
          Returns the reverse edge of an edge.
protected  SimplePlanarInformation.SimpleEdgeInfo getSimpleEdgeInfo(Edge edge)
          Returns the information for an edge.
 boolean isInsertedEdge(Edge edge)
          Returns if an edge is inserted in the planarization process or is an original edge of the input graph
 boolean isOuterFaceSetCorrectly()
          Returns if the current planar embedding has a correctly set outer face.
 boolean isPlanar()
          This method returns if the current embedding defined by the faces is planar.
 void markAsInsertedEdge(Edge edge)
          Marks an edge as inserted by an planarization process.
 void setFaceOf(Edge edge, Face face)
          Sets to which face an edge belongs.
 void setIsInsertedEdge(Edge edge, boolean value)
          Sets if an edge had been inserted in the planarization process.
 void setOuterFace(Face face)
          Sets the outer(unbound,exterior) face of the planar graph.
 void setReverse(Edge e1, Edge e2)
          Set two edges as reverse to each other.
 void showCircularEdgeOrder()
          Prints circular edge order on output.
 void showFaces()
          Prints faces on output.
 String toString()
          Returns a String of the list of faces
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

graph

protected Graph graph

faceList

public YList faceList

outerFace

protected Face outerFace
Constructor Detail

SimplePlanarInformation

public SimplePlanarInformation(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

getGraph

public Graph getGraph()
Returns the graph for which this planar information is kept.

Returns:
the graph the planar information object is associated with

createReverse

public Edge createReverse(Edge edge)
Creates the reverse edge for a given edge.

Parameters:
edge - The edge for which the reverse edge is created
Returns:
The new created reverse Edge

setReverse

public void setReverse(Edge e1,
                       Edge e2)
Set two edges as reverse to each other.

Precondition: source(e1) = target(e2), target(e1) = source(e2)

Parameters:
e1 - An Edge in a graph
e2 - An Edge in a graph

getReverse

public Edge getReverse(Edge e)
Returns the reverse edge of an edge.

Parameters:
e - an edge
Returns:
the reverse edge of edge<\code>

faces

public FaceCursor faces()
Get cursor over faces. The faces are edgelists

Returns:
a cursor over all faces of this planar embedding

setOuterFace

public void setOuterFace(Face face)
Sets the outer(unbound,exterior) face of the planar graph.

Parameters:
face - A face in the planar embedding

getOuterFace

public Face getOuterFace()
Returns the outer face of the planar graph

Returns:
The outer face

faceCount

public int faceCount()
Returns the number of Faces.

Returns:
The number of faces in this planar embedding

faceOf

public Face faceOf(Edge edge)
Get the face to which an edge belongs.

Parameters:
edge - An edge in the graph
Returns:
The face to which edge<\CODE> belongs

setFaceOf

public void setFaceOf(Edge edge,
                      Face face)
Sets to which face an edge belongs.

Parameters:
edge - an edge in the graph.
face - the new face.

calcOrdering

public void calcOrdering()
Calculates the cyclic order of the edges around their source nodes from the set of faces of the graph.

Precondition: The set of faces in the graph represents a planar embedding.


calcFaces

public void calcFaces()
Calculates the faces of the graph from a given edge order.

Precondition: Every edge has a reverse edge and the order of the outgoing edges around a node represent a planar embedding of the graph


calcFaces

public void calcFaces(EdgeOrder edgeOrder)
Calculates the faces of the graph from the cyclic order of the edges around their source nodes.

Precondition: Every edge has a reverse edge and the order of the outgoing edges around a node represent a planar embedding of the graph


createFace

public Face createFace(Edge edge,
                       EdgeOrder edgeOrder,
                       boolean[] mark)
Creates a face starting at an edge and using the cyclic order of the outgoing edges. The new face is inserted in the face list.

Parameters:
edge - an edge which belongs to the face
mark - marks which edges already belong to a face.

createFaceMap

public FaceMap createFaceMap()
Creates a FaceMap for the faces in the graph.

Returns:
an instanve of FaceMap

disposeFaceMap

public void disposeFaceMap(FaceMap map)
Disposes a FaceMap formerly created with createFaceMap().

Parameters:
map - the FaceMap to dispose.

cyclicNextEdge

public Edge cyclicNextEdge(Edge edge)
Returns the counterclockwise next edge of an edge at the source node.

Parameters:
edge - an edge.
Returns:
The edge following edge in ccw order around the source node of e.

cyclicPrevEdge

public Edge cyclicPrevEdge(Edge edge)
Returns the counterclockwise preceeding edge of an edge at the source node.

Parameters:
edge - an edge.
Returns:
The edge preceeding edge in ccw order around the source node of e.

followingEdge

protected Edge followingEdge(Edge e)
Returns the counterclockwise next edge of another edge around a node

Parameters:
e - An edge
Returns:
The edge following e in ccw order around the target node of e

isPlanar

public boolean isPlanar()
This method returns if the current embedding defined by the faces is planar.

Precondition: The faces of the graph must be calculated.

Returns:
true if the current set of faces describe a planar embedding.

dispose

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


isOuterFaceSetCorrectly

public boolean isOuterFaceSetCorrectly()
Returns if the current planar embedding has a correctly set outer face.


toString

public String toString()
Returns a String of the list of faces

Overrides:
toString in class Object

markAsInsertedEdge

public void markAsInsertedEdge(Edge edge)
Marks an edge as inserted by an planarization process.

Parameters:
edge - an edge in the graph

setIsInsertedEdge

public void setIsInsertedEdge(Edge edge,
                              boolean value)
Sets if an edge had been inserted in the planarization process.

Parameters:
edge - an edge in the graph

isInsertedEdge

public boolean isInsertedEdge(Edge edge)
Returns if an edge is inserted in the planarization process or is an original edge of the input graph

Parameters:
edge - An edge in the graph
Returns:
true<\CODE> if the edge is inserted, false<\CODE> otherwise

showCircularEdgeOrder

public void showCircularEdgeOrder()
Prints circular edge order on output.


showFaces

public void showFaces()
Prints faces on output.


getSimpleEdgeInfo

protected SimplePlanarInformation.SimpleEdgeInfo getSimpleEdgeInfo(Edge edge)
Returns the information for an edge.


createSimpleEdgeInfo

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


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

2003