

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object jpaul.Graphs.DiGraph<Vertex>
public abstract class DiGraph<Vertex>
DiGraph
models a directed graph. A directed graph is
defined by a set of root vertices and a navigator.
The navigator is an iterator over the graph: given a vertex
v
, it gives v
's direct successors (i.e.,
vertices pointed to by arcs that start in v
), and
(optionally), v
's direct predecessors. The digraph
contains all (transitive and reflexive) successors of the root
vertices.
This design allows the use of many graph algorithms (e.g., construction of strongly connected components) even for very general graphs where the arcs model only a subtle semantic relation (e.g., callercallee) that is not explicitly stored in the vertices.
There are two kinds of navigators: ForwardNavigators
(give only successors) and bidirectional BiDiNavigators
(both successors and predecessors). For a given graph you should
define at least one of them, i.e., you should override at least one
of the methods getBiDiNavigator()
and getForwardNavigator()
from DiGraph
. The standard implementation of these
methods is able to construct one navigator starting from the other
one. First, a bidirectional navigator is trivially a forward one
too. Next, we can use the roots and the forward navigator to build
the successor relation, and next revert it to build the predecessor
relation (linear in the size of the graph).
If you decide to implement both navigators (e.g., for efficiency)
you should make sure the two navigators are consistent. To see what
this means, let fnav
and nav
be the
forward, respectively the full navigator associated with a digraph.
For any vertex v
, fnav.next(v)
should
return the same vertices as nav.next(v)
. In addition,
nav
itself should be consistent, i.e., for any vertices
v1
, v2
from the digraph, if v1
appears in nav.next(v2)
, then v2
should
appear in nav.prev(v1)
.
To create a DiGraph
, you can use of the following
two static methods: diGraph(Collection,BiDiNavigator)
and
diGraph(Collection,ForwardNavigator)
. For fancier
things, you can also subclass DiGraph
.
Most of the algorithms are implemented as instance methods; very few are also implemented as static methods. Here is some sample code:
// set of arcs as a relation vertex > set of succs final jpaul.DataStructs.Relationarcs = ...; // construct a directed graph based on the relation arcs DiGraph diGraph = DiGraph. diGraph (// [ ... ] some set of roots, new ForwardNavigator () { public List next(Vertex v) { return new ArrayList(arcs.getValues(v)); } }); // iterate over the list of strongly connected components // in incremental topological order for(SCComponent scc : diGraph.getComponentDiGraph().incrOrder()) { System.out.println("SCC vertices: " + scc.vertices()); // potentially, do something more interesting with "scc" :) }
ForwardNavigator
,
BiDiNavigator
Field Summary  

protected boolean 
CACHING

Constructor Summary  


DiGraph()
Constructs a DiGraph with no caching (the safest
choice). 
protected 
DiGraph(boolean CACHING)
Constructs a DiGraph . 
Method Summary  

protected BiDiNavigator<Vertex> 
constructBiDiNavigator(RelationFactory<Vertex,Vertex> relFact)
Construct a full navigator, starting from the forward navigator, as given by the method getForwardNavigator . 

java.util.Set<Vertex> 
dfs(Action<Vertex> onEntry,
Action<Vertex> onExit)
DFS traversal of this digraph. 

java.util.Set<Vertex> 
dfs2(ActionPredicate<Vertex> onEntry,
Action<Vertex> onExit)
More customizable dfs traversal than that performed by the method dfs . 

static

diGraph(java.util.Collection<Vertex> roots,
BiDiNavigator<Vertex> navigator)
Constructs a DiGraph object. 

static

diGraph(java.util.Collection<Vertex> roots,
ForwardNavigator<Vertex> fnavigator)
Constructs a DiGraph object. 

java.util.List<Vertex> 
findPath(java.util.Collection<Vertex> sources,
Predicate<Vertex> predDest)


java.util.List<Vertex> 
findPath(Vertex source,
Vertex dest)


static

findPath(Vertex source,
Vertex dest,
ForwardNavigator<Vertex> navigator)


void 
forAllVertices(Action<Vertex> action)
Executes an action at most once for each vertex from this directed graph. 

BiDiNavigator<Vertex> 
getBiDiNavigator()
Returns the (bidirectional) navigator for this
digraph. 

TopSortedCompDiGraph<Vertex> 
getComponentDiGraph()
Returns the component graph for this graph. 

ForwardNavigator<Vertex> 
getForwardNavigator()
Returns the forward navigator for this digraph. 

abstract java.util.Collection<Vertex> 
getRoots()
Returns the roots of this directed graph. 

long 
numArcs()
Returns the number of arcs in this directed
graph. 

int 
numVertices()
Returns the number of vertices in this directed
graph. 

DiGraph<Vertex> 
reverseDiGraph()
Returns a reverse form of this directed graph: a
directed graph with the same set of vertices, that contains an
arc from v1 to v2 iff
this graph contains an arc from v2
to v1 . 

DiGraph<Vertex> 
subDiGraph(java.util.Collection<Vertex> verts)
Returns a subgraph of this directed graph
containing only the vertices from verts . 

java.lang.String 
toString()
Returns a string representation of this DiGraph. 

java.util.Set<Vertex> 
transitivePred(java.util.Collection<Vertex> roots)


java.util.Set<Vertex> 
transitivePred(Vertex vertex)


java.util.Set<Vertex> 
transitivePredWithFrontier(java.util.Collection<Vertex> roots,
Predicate<Vertex> frontier,
boolean includeFrontier)


java.util.Set<Vertex> 
transitiveSucc(java.util.Collection<Vertex> roots)


java.util.Set<Vertex> 
transitiveSucc(Vertex vertex)


java.util.Set<Vertex> 
transitiveSuccWithFrontier(java.util.Collection<Vertex> roots,
Predicate<Vertex> frontier,
boolean includeFrontier)


static

union(DiGraph<V> dg1,
DiGraph<V> dg2)
Computes the union of two directed graphs. 

java.util.Set<Vertex> 
vertices()
Returns the set of all vertices from this
digraph: vertices that are (trasitively and reflexively)
reachable from the root vertices by following the forward arcs
provided by the navigator. 
Methods inherited from class java.lang.Object 

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait 
Field Detail 

protected final boolean CACHING
Constructor Detail 

public DiGraph()
DiGraph
with no caching (the safest
choice).
protected DiGraph(boolean CACHING)
DiGraph
.
CACHING
 If true
, the implementation of the
various methods of this DiGraph
assume that the
graph does not change in time. Therefore, caching is used for
performance reasons: e.g., once the set of vertices is
computed, it is cached and used ever after.Method Detail 

public abstract java.util.Collection<Vertex> getRoots()
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.
public BiDiNavigator<Vertex> getBiDiNavigator()
this
digraph. The default implementation gets the forward
navigator by calling getForwardNavigator
,
explores the entire digraph and constructs the predecessor
relation. Clearly, this is quite costly, and does not
terminate for infinite digraphs.
Note: You MUST overwrite at least one of
getBiDiNavigator
and
getForwardNavigator
.
protected BiDiNavigator<Vertex> constructBiDiNavigator(RelationFactory<Vertex,Vertex> relFact)
getForwardNavigator
. To construct the list of
prdecessors, we reverse the edges by with the help of a
relation constructed using the forward naviator.
By default, getBiDiNavigator
calls this method using
the default (hashmap and hashset based)
jpaul.DataStructs.MapSetRelationFactory
. For a
graph with a small degree, a subclass may choose to override
getBiDiNavigator
to use some other
RelationFactory
.
public ForwardNavigator<Vertex> getForwardNavigator()
this
digraph.
The default implementations returns the bidirectional
navigator (obtained by calling getBiDiNavigator
).
Note: You MUST overwrite at least one of
getBiDiNavigator
and
getForwardNavigator
.
public static <Vertex> DiGraph<Vertex> diGraph(java.util.Collection<Vertex> roots, BiDiNavigator<Vertex> navigator)
DiGraph
object.
roots
 Collection of root vertices. This collection
will be used directly, without being cloned or copied into
another collection; none of the graph algoritrhms will mutate
it.navigator
 Bidirectional digraph navigatorpublic static <Vertex> DiGraph<Vertex> diGraph(java.util.Collection<Vertex> roots, ForwardNavigator<Vertex> fnavigator)
DiGraph
object.
roots
 Collection of root vertices. This collection
will be used directly, without being cloned or copied into
another collection; none of the graph algorithms will mutate
it.fnavigator
 forward digraph navigatorpublic java.util.Set<Vertex> transitiveSucc(Vertex vertex)
vertex
. The caller is free to mutate the
returned set.public java.util.Set<Vertex> transitiveSucc(java.util.Collection<Vertex> roots)
roots
. The caller is free to
mutate the returned set.public java.util.Set<Vertex> transitiveSuccWithFrontier(java.util.Collection<Vertex> roots, Predicate<Vertex> frontier, boolean includeFrontier)
roots
, but not navigating through
the frontier vertices indicated by the predicate
frontier
. This is equivalent to the classic
transitiveSucc(Collection)
in a directed graph
identical to this one, except that no arc exits the frontier
vertices. The boolean parameter includeFrontier
indicates whether to include the reachable frontier vertices
in the returned set.public java.util.Set<Vertex> transitivePred(Vertex vertex)
vertex
. The caller is free to mutate the
returned set.public java.util.Set<Vertex> transitivePred(java.util.Collection<Vertex> roots)
roots
. The caller is free to
mutate the returned set.public java.util.Set<Vertex> transitivePredWithFrontier(java.util.Collection<Vertex> roots, Predicate<Vertex> frontier, boolean includeFrontier)
roots
, but not navigating through
the frontier vertices indicated by the predicate
frontier
. This is equivalent to the classic
transitivePred(Collection)
in a directed graph
identical to this one, except that no arc enters the frontier
vertices. The boolean parameter includeFrontier
indicates whether to include the reachable frontier vertices
in the returned set.public static <Vertex> java.util.List<Vertex> findPath(Vertex source, Vertex dest, ForwardNavigator<Vertex> navigator)
source
to dest
, along arcs indicated by
navigator
; returns null
if no such
path exists. The caller is free to mutate the returned
list.public java.util.List<Vertex> findPath(Vertex source, Vertex dest)
source
to dest
, along arcs from
this
graph; returns null
if no such
path exists. The caller is free to mutate the returned list.public java.util.List<Vertex> findPath(java.util.Collection<Vertex> sources, Predicate<Vertex> predDest)
sources
to a vertex that satisfies
the predDest
predicate, along arcs from
this
graph; returns null
if no such
path exists. The caller is free to mutate the returned list.public java.util.Set<Vertex> dfs(Action<Vertex> onEntry, Action<Vertex> onExit)
this
digraph. The traversal may
be stoped at any point by throwing an InterruptTraversalException
from one of the visitors (the
arguments of this method); the exception is caught internally
by the implementation of this method.
onEntry
 action executed when a node is first time
visited by the DFS traversalonExit
 action executed after the DFS traversal of a
node finished
public java.util.Set<Vertex> dfs2(ActionPredicate<Vertex> onEntry, Action<Vertex> onExit)
dfs
. On entry to a specific
(yetunvisited) vertex v
, the traversal adds the
node to the set of visited vertices and performs the
onEntry
ActionPredicate
. If the value returned by
onEntry
is true
, the visit of the
vertex continues as in the case of the simple traversal dfs(jpaul.Misc.Action, jpaul.Misc.Action)
with the (recursive) visit of the children and the
execution of the action onExit
. OTHERWISE, the
visit of the current vertex v
stops immediately:
no recursive visit of its children, no execution of the exit
action.
Notice that the onEntry
parameter is a
combination of a predicate and an action. Initially, we
thought about having two parameters: a predicate and an
action. Still, that solution would left unspecified the
problem of the order between the predicate and the action.
Worse still, one can imagine the action being split into two
parts: one executed (unconditionally) before the predicate,
and the second one executed (conditionally) after the
predicate. To simplify things, we decided to allow the client
to specify the desired combination of an action and a
predicate.
As in the case of the "simple" {#dfs dfs}, the traversal
may be stoped at any point by throwing an InterruptTraversalException
from one of the visitors (the
arguments of this method); the exception is caught internally
by the implementation of this method. Notice the difference
between the case when onEntry
returns
false
and the case when onEntry
or
onExit
throws an InterruptTraversalException
: in the first case, we skip only
the (recursive) visit of the current vertex's children; in the
second case, we skip the visit of all the remaining vertices.
onEntry
 action executed when a node is first time
visited by the DFS traversalonExit
 action executed after the DFS traversal of a
node finished
public void forAllVertices(Action<Vertex> action)
this
directed graph. The traversal may be
terminated at each moment by throwing an InterruptTraversalException
. If no such exception is thrown,
then action
is applied exactly once to each
vertex from this digraph. The
InterruptTraversalException
(if any) is caught
inside this method.
vertices()
public TopSortedCompDiGraph<Vertex> getComponentDiGraph()
this
graph. The
"component graph" of a graph G
is the
directed, acyclic graph consisting of the strongly connected
components of G
. As it doesn't affect the
asymptotic complexity, we also sort it topologically.
public java.util.Set<Vertex> vertices()
this
digraph: vertices that are (trasitively and reflexively)
reachable from the root vertices by following the forward arcs
provided by the navigator.
The returned set is unmodifiable and has a deterministic
iteration order (it's based on a LinkedHashSet
).
Moreover, if the following conditions are met, different calls
to vertices()
return equal sets of vertices, with
the same deterministic iteration order; here are the
conditions: (1) the navigator and the set of graph roots do
not change, (2) for each node, the forward graph navigator
always returns the same list of neighbors (instead of
rearragements of them), (3) the set of roots has a
deterministic iteration order.
public DiGraph<Vertex> reverseDiGraph()
this
directed graph: a
directed graph with the same set of vertices, that contains an
arc from v1
to v2
iff
this
graph contains an arc from v2
to v1
.
public DiGraph<Vertex> subDiGraph(java.util.Collection<Vertex> verts)
this
directed graph
containing only the vertices from verts
.
public int numVertices()
this
directed
graph.
Complexity: linear in the size of the graph. Cached if the
CACHING
argument to the constructor was true.
public long numArcs()
this
directed
graph.
Complexity: linear in the size of the graph. Cached if the
CACHING
argument to the constructor was true.
public java.lang.String toString()
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.
toString
in class java.lang.Object
public static <V> DiGraph<V> union(DiGraph<V> dg1, DiGraph<V> dg2)
DiGraph
is not computed
explicitly; instead, the lists of predecessors/successors are
generated ondemand.


PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 