com.inubit.research.rpst.graph

Class PalmTree

java.lang.Object

com.inubit.research.rpst.graph.Graph

com.inubit.research.rpst.graph.PalmTree

public class PalmTree
extends Graph

Class for representing palm trees as introduced by Hopcroft and Tarjan in "Dividing a graph into triconnected components". A palm tree consists of two disjoint sets of edges called tree arcs (-->) and fronds (^-->). The set of tree arcs form a spanning tree of the graph. If B ^--> A, then A -->* B.

Field Summary

Fields inherited from class com.inubit.research.rpst.graph.Graph

adjacency, edges, isDirected, nodes, sinks, sources

Constructor Summary

Constructors

Constructor and Description
PalmTree(NormalizedGraph graph) Construct a new palm tree from the given graph.

Method Summary

Modifier and Type	Method and Description
java.util.List<SplitComponent>	determineSplitComponents() Derive the split components of this palm tree.
java.lang.String	toString()

Methods inherited from class com.inubit.research.rpst.graph.Graph

addSink, addSource, addToAdjacency, createEdge, createNode, getAdjacency, getNodes, getSinks, getSources, isDirected, isTwoTerminalGraph, setDirected

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

PalmTree

public PalmTree(NormalizedGraph graph)
         throws SourceNodeException

Construct a new palm tree from the given graph. For the sake of simplicity we only consider graphs with one source. If the given graph has multiple sources an exception is thrown.

Parameters:

graph - the graph

Throws:

SourceNodeException - This exception is thrown if the graph has multiple source nodes.

Method Detail

determineSplitComponents

public java.util.List<SplitComponent> determineSplitComponents()

Derive the split components of this palm tree. This method is taken from the paper of Gutwenger and Mutzel "A linear time implementation of SPQR trees".

Parameters:

v -

toString

public java.lang.String toString()

Overrides:

toString in class Graph