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/interfaces inherited from class y.layout.planar.SimplePlanarInformation

SimplePlanarInformation.SimpleEdgeInfo

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 different 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 different 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 tuples.
protected PlanarInformation.NodeInfo	createNodeInfo() Factory to create edge tuples.
protected SimplePlanarInformation.SimpleEdgeInfo	createSimpleEdgeInfo() Factory to create edge tuples.
void	dispose() Remove all information from graph concerning planar Information: reverse Edge-Key,inserted reverse edges Note: don't use the PlanarInformation after disposal!
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)
BendAndCrossingCostHelper	getBendAndCrossingCostHelper()
int	getBendCost(Edge e)
int	getCrossingCost(Edge e)
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 handled 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 handled like a real node in a graph.
void	removeSubdivisionHandler(SubdivisionHandler handler)
void	setBendAndCrossingCostHelper(BendAndCrossingCostHelper bendAndCrossingCostHelper)
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 self-loop 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 separated 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:

updateEdgeRecoveryInfo(y.base.Edge, y.base.EdgeList, int), Constant Field Values

SPLIT

public static final int SPLIT

See Also:

updateEdgeRecoveryInfo(y.base.Edge, y.base.EdgeList, int), 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

getBendAndCrossingCostHelper

public BendAndCrossingCostHelper getBendAndCrossingCostHelper()

setBendAndCrossingCostHelper

public void setBendAndCrossingCostHelper(BendAndCrossingCostHelper bendAndCrossingCostHelper)

getCrossingCost

public int getCrossingCost(Edge e)

getBendCost

public int getBendCost(Edge e)

dispose

public void dispose()

Remove all information from graph concerning planar Information: reverse Edge-Key,inserted reverse edges

Note: don't use the PlanarInformation after disposal!

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 handled 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 handled 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 self-loop 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 different 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 different 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 separated by a single edge. The faces are identified via the the edge and its reverse

Parameters:

e - edge that separates 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 specifier 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 whether 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 tuples.

getEdgeInfo

protected PlanarInformation.EdgeInfo getEdgeInfo(Edge edge)

Returns the information for an edge.

createEdgeInfo

protected PlanarInformation.EdgeInfo createEdgeInfo()

Factory to create edge tuples.

createSimpleEdgeInfo

protected SimplePlanarInformation.SimpleEdgeInfo createSimpleEdgeInfo()

Factory to create edge tuples.

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 whether more or less information is wanted.