jpaul.Graphs
Class LabeledDiGraph<Vertex,Label>

java.lang.Object
  jpaul.Graphs.DiGraph<Vertex>
      jpaul.Graphs.LabeledDiGraph<Vertex,Label>

Direct Known Subclasses:

NFA

public abstract class LabeledDiGraph<Vertex,Label>
extends DiGraph<Vertex>

LabeledDiGraph models a labeled directed graph. This is a DiGraph where each arc has a label. Similar to a DiGraph, a LabeledDiGraph is defined by giving a set of roots and a navigator to iterate over the (labeled) arcs. The vertices from the LabeledDiGraph are those vertices that are reachable from the roots by following the forward arcs given by the navigator.

An LabeledDiGraph is trivially a DiGraph: it is enough to strip the labels off the arcs. All the algorithms for a DiGraph can be used for a LabeledDiGraph.

Version:

$Id: LabeledDiGraph.java,v 1.5 2006/03/14 02:29:31 salcianu Exp $

Author:

Alexandru Salcianu - salcianu@alum.mit.edu

See Also:

DiGraph

Nested Class Summary

static class	LabeledDiGraph.LabeledBiDiNavigator<Vertex,Label> Bidirectional iterator into a labeled graph.
static class	LabeledDiGraph.LabeledForwardNavigator<Vertex,Label> Forward iterator into a labeled graph.

Field Summary

Fields inherited from class jpaul.Graphs.DiGraph

CACHING

Constructor Summary

LabeledDiGraph()
Creates a LabeledDiGraph.

LabeledDiGraph(boolean CACHING)
Creates a LabeledDiGraph.

Method Summary

ForwardNavigator<Vertex>	getForwardNavigator() Returns the forward navigator for this digraph.
LabeledDiGraph.LabeledBiDiNavigator<Vertex,Label>	getLabeledBiDiNavigator() Returns a bi-directional labeled navigator through LabeledDiGraph.
LabeledDiGraph.LabeledForwardNavigator<Vertex,Label>	getLabeledForwardNavigator() Returns a forward labeled navigator through this LabeledDiGraph.
BiDiNavigator<Vertex>	getNavigator() Returns the (bi-directional) navigator for this digraph.
abstract java.util.Collection<Vertex>	getRoots() Returns the roots of this directed graph.
java.lang.String	toString() Returns a string representation of this DiGraph.

Methods inherited from class jpaul.Graphs.DiGraph

constructBiDiNavigator, dfs, dfs2, diGraph, diGraph, findPath, findPath, findPath, forAllVertices, getBiDiNavigator, getComponentDiGraph, numArcs, numVertices, reverseDiGraph, subDiGraph, transitivePred, transitivePred, transitivePredWithFrontier, transitiveSucc, transitiveSucc, transitiveSuccWithFrontier, union, vertices

Methods inherited from class java.lang.Object

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

Constructor Detail

LabeledDiGraph

public LabeledDiGraph()

Creates a LabeledDiGraph.

LabeledDiGraph

public LabeledDiGraph(boolean CACHING)

Creates a LabeledDiGraph.

Method Detail

getRoots

public abstract java.util.Collection<Vertex> getRoots()

Description copied from class: DiGraph

Returns the roots of this directed graph. By "roots of a digraph" we mean any set of vertices such that one can explore the entire graph by (transitively) navigating on their outgoing arcs (using the next method of the navigator). Notice that this set is not uniquely defined; also, it is OK to return ALL the vertices from the digraph. The caller is not supposed to mutate the returned collection.

Specified by:

getRoots in class DiGraph<Vertex>

getLabeledBiDiNavigator

public LabeledDiGraph.LabeledBiDiNavigator<Vertex,Label> getLabeledBiDiNavigator()

Returns a bi-directional labeled navigator through LabeledDiGraph. The default implementation uses the forward navigator returned by LabeledForwardNavigator to traverse the entire graph and construct the list of backward arcs. Note: You MUST override at least one of getLabeledBiDiNavigator and getLabeledForwardNavigator.

getLabeledForwardNavigator

public LabeledDiGraph.LabeledForwardNavigator<Vertex,Label> getLabeledForwardNavigator()

Returns a forward labeled navigator through this LabeledDiGraph. The default implementation returns the full navigator produced by getLabeledBiDiNavigator(). Note: You MUST override at least one of getLabeledBiDiNavigator and getLabeledForwardNavigator.

getNavigator

public BiDiNavigator<Vertex> getNavigator()

Returns the (bi-directional) navigator for this digraph. Default implementation for LabeledDiGraphs: returns the same object as getLabeledBiDiNavigator().

getForwardNavigator

public ForwardNavigator<Vertex> getForwardNavigator()

Returns the forward navigator for this digraph. Default implementation for LabeledDiGraphs: returns the same object as getLabeledForwardNavigator().

Overrides:

getForwardNavigator in class DiGraph<Vertex>

toString

public java.lang.String toString()

Description copied from class: DiGraph

Returns a string representation of this DiGraph. This string representation is adequate for debugging small graphs. For more complex graphs, try to output a dot representation of the graph and use an external tool to visualize it.

Overrides:

toString in class DiGraph<Vertex>