graph.algorithms.planarity.dual

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

java.lang.Object

graph.elements.Graph<DualGraphVertex<V,E>,DualGraphEdge<V,E>>

graph.algorithms.planarity.dual.STDualGraph<V,E>

Type Parameters:

V - The vertex type

E - The edge type

public class STDualGraph<V extends Vertex,E extends Edge<V>>
extends Graph<DualGraphVertex<V,E>,DualGraphEdge<V,E>>

Constructs a st-dual graph Given a planar st-graph G, the dual planar st-graph G = (V, E) is a digraph with the following properties: - V* is the set of faces in G with the addition that the external face (s, . . . , t, . . . , s) is broken into two parts S* representing the portion of the face from s to t and T* representing the portion rom t to s. - For every edge e in E, we have an edge e* = (f, g) where f is the face the left of e and g is the face to the right of e.

Author:

Renata

Constructor Summary

Constructors

Constructor and Description
STDualGraph(Graph<V,E> graph, java.util.List<E> externalFace, V s, V t) Construct the st-dual graph given a graph, external face and s and t vertices

Method Summary

Modifier and Type	Method and Description
java.util.List<E>	getExternalFace()
V	getS()
java.util.List<E>	getsStar()
V	getT()
java.util.List<E>	gettStar()
java.lang.String	toString()

Methods inherited from class graph.elements.Graph

addEdge, addVertex, addVertex, addVertexBeginning, adjacencyMatrix, adjacentEdges, adjacentVertices, allEdges, edgeBetween, edgeesBetween, edgesBetween, equals, getAdjacentLists, getAllSelfLoopEdges, getAllSinks, getAllSources, getEdges, getTreeLeaves, getVertexByContent, getVertices, graphMaxDegree, hasEdge, hashCode, hasSelfLoopEdges, hasVertex, inDegree, inEdges, isBiconnected, isConnected, isConnected, isCyclic, isDirected, isRing, isSimple, isSink, isSource, isTree, listBiconnectedComponents, listCutVertices, listMultiEdges, outDegree, outEdges, printAdjacencyMatrix, removeEdge, removeVertex, setDirected, setEdges, setVertices, subgraph, vertexDegree

Methods inherited from class java.lang.Object

getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

STDualGraph

public STDualGraph(Graph<V,E> graph,
                   java.util.List<E> externalFace,
                   V s,
                   V t)

Construct the st-dual graph given a graph, external face and s and t vertices

Parameters:

graph - Graph

externalFace - Edges of the external face

s - The first vertex of the st-numbering

t - The last vertex of the st-numbering

Method Detail

toString

public java.lang.String toString()

Overrides:

toString in class Graph<DualGraphVertex<V extends Vertex,E extends Edge<V>>,DualGraphEdge<V extends Vertex,E extends Edge<V>>>

getExternalFace

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

Returns:

Edges on the external face

getS

public V getS()

Returns:

S vertex

getT

public V getT()

Returns:

T vertex

getsStar

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

Returns:

S* edges

gettStar

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

Returns:

T* edges