y.layout.planar
Class SimplePlanarInformation

java.lang.Object
  y.layout.planar.SimplePlanarInformation

Direct Known Subclasses:

DualPlanarInformation, PlanarInformation

public class SimplePlanarInformation
extends java.lang.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 around 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 tuples.
Edge	cyclicNextEdge(Edge edge) Returns the counterclockwise next edge of an edge at the source node.
Edge	cyclicPrevEdge(Edge edge) Returns the counterclockwise preceding 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() 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.
java.lang.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

faces

public FaceCursor faces()

Get cursor over faces. The faces are edge lists

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 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 instance 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 preceding edge of an edge at the source node.

Parameters:

edge - an edge.

Returns:

The edge preceding 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()

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 java.lang.String toString()

Returns a String of the list of faces

Overrides:

toString in class java.lang.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 if the edge is inserted, false 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 tuples.