jpaul.Graphs
Class LabeledDiGraph<Vertex,Label>

java.lang.Object
  extended by jpaul.Graphs.DiGraph<Vertex>
      extended by 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>


Copyright 2005 Alexandru Salcianu - salcianu@alum.mit.edu