jpaul.Graphs
Class LDiGraph<Vertex,Label>

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