jpaul.Graphs
Class LDiGraph<Vertex,Label>

java.lang.Object
  extended by jpaul.Graphs.DiGraph<Vertex>
      extended by jpaul.Graphs.LDiGraph<Vertex,Label>
Direct Known Subclasses:
NFA

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

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

An LDiGraph 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 LDiGraph.

Version:
$Id: LDiGraph.java,v 1.5 2005/09/01 22:41:41 salcianu Exp $
Author:
Alexandru Salcianu - salcianu@alum.mit.edu
See Also:
DiGraph

Nested Class Summary
static class LDiGraph.LForwardNavigator<Vertex,Label>
          Forward iterator into a labeled graph.
static class LDiGraph.LNavigator<Vertex,Label>
          Bidirectional iterator into a labeled graph.
 
Field Summary
 
Fields inherited from class jpaul.Graphs.DiGraph
CACHING
 
Constructor Summary
LDiGraph()
          Creates a LDiGraph.
LDiGraph(boolean CACHING)
          Creates a LDiGraph.
 
Method Summary
 ForwardNavigator<Vertex> getForwardNavigator()
          Returns the forward navigator for this digraph.
 LDiGraph.LForwardNavigator<Vertex,Label> getLForwardNavigator()
          Returns a forward labeled navigator through this LDiGraph.
 LDiGraph.LNavigator<Vertex,Label> getLNavigator()
          Returns a bi-directional labeled navigator through LDiGraph.
 Navigator<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()
           
 
Methods inherited from class jpaul.Graphs.DiGraph
constructNavigator, dfs, diGraph, diGraph, findPath, findPath, forAllVertices, getComponentDiGraph, numArcs, numVertices, reverseDiGraph, subDiGraph, transitivePred, transitivePred, transitiveSucc, transitiveSucc, union, vertices
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

LDiGraph

public LDiGraph()
Creates a LDiGraph.


LDiGraph

public LDiGraph(boolean CACHING)
Creates a LDiGraph.

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.

Specified by:
getRoots in class DiGraph<Vertex>

getLNavigator

public LDiGraph.LNavigator<Vertex,Label> getLNavigator()
Returns a bi-directional labeled navigator through LDiGraph. The default implementation uses the forward navigator returned by LForwardNavigator to traverse the entire graph and construct the list of backward arcs. Note: You MUST override at least one of getLNavigator and getLForwardNavigator.


getLForwardNavigator

public LDiGraph.LForwardNavigator<Vertex,Label> getLForwardNavigator()
Returns a forward labeled navigator through this LDiGraph. The default implementation returns the full navigator produced by getLNavigator(). Note: You MUST override at least one of getLNavigator and getLForwardNavigator.


getNavigator

public Navigator<Vertex> getNavigator()
Returns the (bi-directional) navigator for this digraph. Default implementation for LDiGraphs: returns the same object as getLNavigator().

Overrides:
getNavigator in class DiGraph<Vertex>

getForwardNavigator

public ForwardNavigator<Vertex> getForwardNavigator()
Returns the forward navigator for this digraph. Default implementation for LDiGraphs: returns the same object as getLForwardNavigator().

Overrides:
getForwardNavigator in class DiGraph<Vertex>

toString

public java.lang.String toString()
Overrides:
toString in class java.lang.Object


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