com.atlassian.fisheye.dag

Class GraphUtils

java.lang.Object

com.atlassian.fisheye.dag.GraphUtils

public class GraphUtils
extends Object

Utility class for walking Directed Acyclic Graphs. COPIED FROM FISHEYE SOURCE

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
protected static class	GraphUtils.BreadthFirstNodeInserter<N> node inserter for breadth first search
protected static class	GraphUtils.DefaultGraphIterator<E,ID>
protected static class	GraphUtils.DepthFirstNodeInserter<N> Node inserter for depth-first-search
protected static interface	GraphUtils.NodeInserter<N> Interface to abstract the type of search (breadth-first / depth-first)
protected static class	GraphUtils.PredicateMatcher<N>

Method Summary

Modifier and Type	Method and Description
static <N,ID> GraphIterator<N>	iterateBreadthFirst(Collection<N> fromNodes, com.google.common.base.Function<N,Collection<N>> nextNodeProvider, com.google.common.base.Function<N,ID> nodeIdExtractor) Iterates a graph in breadth-first order.
static <N,ID> GraphIterator<N>	iterateDepthFirst(Collection<N> fromNodes, com.google.common.base.Function<N,Collection<N>> nextNodeProvider, com.google.common.base.Function<N,ID> nodeIdExtractor) Iterates a graph in depth-first order.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

iterateDepthFirst

public static <N,ID> GraphIterator<N> iterateDepthFirst(Collection<N> fromNodes,
                                                        com.google.common.base.Function<N,Collection<N>> nextNodeProvider,
                                                        com.google.common.base.Function<N,ID> nodeIdExtractor)

Iterates a graph in depth-first order.

Type Parameters:

N -

Parameters:

fromNodes - the nodes to start the iteration from

nextNodeProvider - a function that provides the next nodes for a node

nodeIdExtractor - a function that returns the id of a node, used for detecting nodes that have already been traversed

Returns:

a GraphIterator that can be used to traverse the graph

iterateBreadthFirst

public static <N,ID> GraphIterator<N> iterateBreadthFirst(Collection<N> fromNodes,
                                                          com.google.common.base.Function<N,Collection<N>> nextNodeProvider,
                                                          com.google.common.base.Function<N,ID> nodeIdExtractor)

Iterates a graph in breadth-first order.

Type Parameters:

N -

Parameters:

fromNodes - the nodes to start the iteration from

nextNodeProvider - a function that provides the next nodes for a node

nodeIdExtractor - a function that returns the id of a node, used for detecting nodes that have already been traversed

Returns:

a GraphIterator that can be used to traverse the graph