jpaul.Graphs
Class ArcBasedDiGraph<Vertex>

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


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