com.arsdigita.util
Class Graphs

java.lang.Object
  extended bycom.arsdigita.util.Graphs

public class Graphs
extends Object

A collection of methods that operate on graphs.

Since:
2003-01-22
Version:
$Date: 2004/04/07 $
Author:
Archit Shah (ashah@mit.edu), Vadim Nasardinov (vadimn@redhat.com)

Nested Class Summary
static interface Graphs.EdgeSelector
           
static class Graphs.EqualityTerminator
           
static interface Graphs.NodeSelector
           
 
Field Summary
static Graphs.EdgeSelector FORWARD_SELECTOR
          A simple implementation of the Graphs.EdgeSelector interface that selects outgoing edges.
 
Method Summary
static List edgePathToNodePath(List edgePath)
           
static List findPath(Graph graph, Object startNode, Graphs.EdgeSelector selector, Graphs.NodeSelector terminator)
          Performs a traversal of graph looking for path that starts with startNode and terminates with a node that satisfies the test specified by terminator and consists only of those edges that satisfy the test specified by selector.
static List findPath(Graph graph, Object begin, Object end)
          Finds a path in graph from begin to end
static List getSinkNodes(Graph gg)
          Returns a list of nodes in gg that have no outgoing edges.
static Graph nodesReachableFrom(Graph graph, Object start)
           
static void printGraph(Graph graph, GraphFormatter fmtr, PrintWriter writer)
          Pretty-prints the graph.
static void printTree(Tree tree, GraphFormatter fmtr, PrintWriter writer)
          Pretty-prints the tree in a format patterned off of the DOT language.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

FORWARD_SELECTOR

public static final Graphs.EdgeSelector FORWARD_SELECTOR
A simple implementation of the Graphs.EdgeSelector interface that selects outgoing edges.

Method Detail

findPath

public static final List findPath(Graph graph,
                                  Object begin,
                                  Object end)
Finds a path in graph from begin to end

Throws:
NullPointerException - if any of the three arguments is null.
See Also:
findPath(Graph, Object, Graphs.EdgeSelector, Graphs.NodeSelector)

findPath

public static List findPath(Graph graph,
                            Object startNode,
                            Graphs.EdgeSelector selector,
                            Graphs.NodeSelector terminator)
Performs a traversal of graph looking for path that starts with startNode and terminates with a node that satisfies the test specified by terminator and consists only of those edges that satisfy the test specified by selector.

Returns:
a path from start node to a node that satisfies the condition specified by terminator, such that all edges in the path satisfy the condition specified by selector. An empty list is returned, if no such path can be found.

edgePathToNodePath

public static final List edgePathToNodePath(List edgePath)
Parameters:
edgePath - a list of edges such as the one returned by findPath(Graph, Object, Object).
Returns:
the same path represented as a list of nodes rather than edges.
Throws:
IllegalStateException - if edgePath is not a valid path. For example, (a->b, c->d, d->e) is invalid, because the edge between b and c is missing.
NullPointerException - if edgePath is null

nodesReachableFrom

public static Graph nodesReachableFrom(Graph graph,
                                       Object start)
Returns:
nodes reachable from start, including the start node itself.

getSinkNodes

public static List getSinkNodes(Graph gg)
Returns a list of nodes in gg that have no outgoing edges.


printTree

public static void printTree(Tree tree,
                             GraphFormatter fmtr,
                             PrintWriter writer)
Pretty-prints the tree in a format patterned off of the DOT language.


printGraph

public static void printGraph(Graph graph,
                              GraphFormatter fmtr,
                              PrintWriter writer)
Pretty-prints the graph.

See Also:
printTree(Tree, GraphFormatter, PrintWriter)


Copyright (c) 2004 Red Hat, Inc. Corporation. All Rights Reserved. Generated at July 20 2004:2337 UTC