jpaul.Graphs
Class ArcBasedDiGraph<Vertex>

java.lang.Object
  jpaul.Graphs.DiGraph<Vertex>
      jpaul.Graphs.ArcBasedDiGraph<Vertex>

public class ArcBasedDiGraph<Vertex>
extends DiGraph<Vertex>

Digraph based on a list of arcs. Created: Sun Feb 7 20:00:00 2005

Version:

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

Author:

Alexandru Salcianu - salcianu@alum.mit.edu

Field Summary

Fields inherited from class jpaul.Graphs.DiGraph

CACHING

Constructor Summary

ArcBasedDiGraph(java.util.Collection<Pair<Vertex,Vertex>> arcs)
Constructs a digraph based on a collection of arcs between vertices.

ArcBasedDiGraph(Relation<Vertex,Vertex> succs)
Constructs a digraph based on a set of arcs given as a successor relation.

Method Summary

ForwardNavigator<Vertex>	getForwardNavigator() Returns the forward navigator for this digraph.
java.util.Set<Vertex>	getRoots() Returns the roots of this directed graph.

Methods inherited from class jpaul.Graphs.DiGraph

constructBiDiNavigator, dfs, dfs2, diGraph, diGraph, findPath, findPath, findPath, forAllVertices, getBiDiNavigator, getComponentDiGraph, numArcs, numVertices, reverseDiGraph, subDiGraph, toString, 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

ArcBasedDiGraph

public ArcBasedDiGraph(java.util.Collection<Pair<Vertex,Vertex>> arcs)

Constructs a digraph based on a collection of arcs between vertices. Each arc is given as a pair <source,target>.

ArcBasedDiGraph

public ArcBasedDiGraph(Relation<Vertex,Vertex> succs)

Constructs a digraph based on a set of arcs given as a successor relation.

Parameters:

succs - Relation between arc sources and arc targets.

Method Detail

getRoots

public java.util.Set<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>

getForwardNavigator

public ForwardNavigator<Vertex> getForwardNavigator()

Description copied from class: DiGraph

Returns the forward navigator for this digraph. The default implementations returns the bi-directional navigator (obtained by calling getBiDiNavigator).

Note: You MUST overwrite at least one of getBiDiNavigator and getForwardNavigator.

Overrides:

getForwardNavigator in class DiGraph<Vertex>