graph.algorithms.planarity

Class PlanarFaces<V extends Vertex,E extends Edge<V>>

java.lang.Object

graph.algorithms.planarity.PlanarFaces<V,E>

Type Parameters:

V - The vertex type

E - The edge type

public class PlanarFaces<V extends Vertex,E extends Edge<V>>
extends java.lang.Object

Finds planar faces of a graph. Crucial step of many graph drawing algorithms. For eac1h edge, there should be a right and a left face If (v,w) is an edge, the left face is the one that contains (v,w) and the right face is the one that contains (w,v)

Author:

Renata

Constructor Summary

Constructors

Constructor and Description
PlanarFaces(Graph<V,E> graph)
PlanarFaces(Graph<V,E> graph, STNumbering<V,E> stNumbering)

Method Summary

Modifier and Type	Method and Description
void	formFaces(V s, V t) Runs the algorithm for forming planar faces
java.util.List<java.util.List<E>>	getAllFaces()
java.util.Map<E,java.util.List<java.util.List<E>>>	getEdgeFacesMap()
java.util.Map<V,java.util.List<E>>	getPlanarEmbedding()
java.util.List<E>	leftFaceOf(E edge) Left face of the given edge
java.util.List<E>	rightFaceOf(E edge) Right face of the given edge
void	setAllFaces(java.util.List<java.util.List<E>> allFaces)

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

PlanarFaces

public PlanarFaces(Graph<V,E> graph)

PlanarFaces

public PlanarFaces(Graph<V,E> graph,
                   STNumbering<V,E> stNumbering)

Method Detail

formFaces

public void formFaces(V s,
                      V t)
               throws CannotBeAppliedException

Runs the algorithm for forming planar faces

Parameters:

s - The first vertex of the st-numbering

t - The last vertex of the st-numbering

Throws:

CannotBeAppliedException - If the graph is not planar

leftFaceOf

public java.util.List<E> leftFaceOf(E edge)

Left face of the given edge

Parameters:

edge - Edge

Returns:

left face Edge's left face

rightFaceOf

public java.util.List<E> rightFaceOf(E edge)

Right face of the given edge

Parameters:

edge - Edge

Returns:

right face Edge's right face

getAllFaces

public java.util.List<java.util.List<E>> getAllFaces()

Returns:

All planar faces

setAllFaces

public void setAllFaces(java.util.List<java.util.List<E>> allFaces)

Parameters:

allFaces - the allFaces to set

getEdgeFacesMap

public java.util.Map<E,java.util.List<java.util.List<E>>> getEdgeFacesMap()

Returns:

the edgeFacesMap

getPlanarEmbedding

public java.util.Map<V,java.util.List<E>> getPlanarEmbedding()