graph.tree.pq

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

java.lang.Object

graph.elements.Graph<PQTreeNode,PQTreeEdge>

graph.tree.pq.PQTree<V,E>

public class PQTree<V extends Vertex,E extends Edge<V>>
extends Graph<PQTreeNode,PQTreeEdge>

Class represents a PQ-tree, which is used in some algorithms for planarity testing P nodes are cut vertices Q nodes are nonseparable components Leaves are virtual vertices (vertices on the other side of edges where one vertex is on subgraph Gk and the other one is in V-Vk)

Author:

Renata

Constructor Summary

Constructors

Constructor and Description
PQTree(Graph<V,E> graph, java.util.List<E> virtualEdges, java.util.Map<V,java.lang.Integer> stNumbering) Construct the PQ tree, given the a graph, a list of virtual edges and st-numbering

Method Summary

Modifier and Type	Method and Description
void	addEdge(PQTreeEdge... edges)
void	addVertex(PQTreeNode node) Add one vertex to the graph
java.util.List<PQTreeNode>	allDescendantsOf(PQTreeNode node) Finds all descendants of a tree node
java.util.List<PQTreeNode>	findLeavesOf(java.util.List<E> virtualEdges) Finds all leaves which are destination or source of the edge belonging to the provided list
java.util.List<PQTreeNode>	getLeaves()
java.util.List<PQTreeNode>	getpNodes()
java.util.List<PQTreeNode>	getqNodes()
PQTreeNode	getRoot()
void	removeVertex(PQTreeNode node) Removes a vertex from the graph, thus updating all relevant structures and also removing the edges it was a part of
void	setLeaves(java.util.List<PQTreeNode> leaves)
void	setRoot(PQTreeNode root)
java.lang.String	toString()

Methods inherited from class graph.elements.Graph

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, setDirected, setEdges, setVertices, subgraph, vertexDegree

Methods inherited from class java.lang.Object

getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

PQTree

public PQTree(Graph<V,E> graph,
              java.util.List<E> virtualEdges,
              java.util.Map<V,java.lang.Integer> stNumbering)

Construct the PQ tree, given the a graph, a list of virtual edges and st-numbering

Parameters:

graph - Graph for which the PQ-tree in being constructed

virtualEdges - Virtual edges

stNumbering - ST-numbering

Method Detail

addVertex

public void addVertex(PQTreeNode node)

Description copied from class: Graph

Add one vertex to the graph

Overrides:

addVertex in class Graph<PQTreeNode,PQTreeEdge>

Parameters:

node - Vertex to add

removeVertex

public void removeVertex(PQTreeNode node)

Description copied from class: Graph

Removes a vertex from the graph, thus updating all relevant structures and also removing the edges it was a part of

Overrides:

removeVertex in class Graph<PQTreeNode,PQTreeEdge>

Parameters:

node - Vertex to remove

addEdge

public void addEdge(PQTreeEdge... edges)

Overrides:

addEdge in class Graph<PQTreeNode,PQTreeEdge>

findLeavesOf

public java.util.List<PQTreeNode> findLeavesOf(java.util.List<E> virtualEdges)

Finds all leaves which are destination or source of the edge belonging to the provided list

Parameters:

virtualEdges - A list of virtual edges

Returns:

A list of leaves which are either source or destination nodes of edges belonging to virtualEdges list

allDescendantsOf

public java.util.List<PQTreeNode> allDescendantsOf(PQTreeNode node)

Finds all descendants of a tree node

Parameters:

node - Node

Returns:

A list of descendants of node

toString

public java.lang.String toString()

Overrides:

toString in class Graph<PQTreeNode,PQTreeEdge>

getRoot

public PQTreeNode getRoot()

Returns:

Root of the tree

setRoot

public void setRoot(PQTreeNode root)

Parameters:

root - Root to set

getpNodes

public java.util.List<PQTreeNode> getpNodes()

Returns:

The list of P nodes

getqNodes

public java.util.List<PQTreeNode> getqNodes()

Returns:

A list of Q nodes

getLeaves

public java.util.List<PQTreeNode> getLeaves()

Returns:

A list of leaves

setLeaves

public void setLeaves(java.util.List<PQTreeNode> leaves)

Parameters:

leaves - the leaves to set