org.dishevelled.graph.impl
Class GraphUtils

java.lang.Object
  org.dishevelled.graph.impl.GraphUtils

public final class GraphUtils
extends Object

Static utility methods on directed graphs.

Version:

$Revision$ $Date$

Author:

Michael Heuer

Method Summary

static <N,E> void	breadthFirstSearch(Graph<N,E> graph, Node<N,E> node, UnaryProcedure<Node<N,E>> procedure) Breadth-first search.
static <N,E> Set<Set<Node<N,E>>>	connectedComponents(Graph<N,E> graph) Find the connected components of the specified graph.
static <N,E> Graph<N,E>	createGraph() Create and return a new directed graph.
static <N,E> Graph<N,E>	createGraph(Graph<N,E> graph) Create and return a new directed graph with the same structure and same node and edge values as the specified graph.
static <N,E> Graph<N,E>	createGraph(int nodeCapacity, int edgeCapacity) Create and return a new directed graph with the specified initial node and edge capacities.
static <N,E> void	depthFirstSearch(Graph<N,E> graph, Node<N,E> node, UnaryProcedure<Node<N,E>> procedure) Depth-first search.
static <N,E> void	undirectedBreadthFirstSearch(Graph<N,E> graph, Node<N,E> node, UnaryProcedure<Node<N,E>> procedure) Undirected breadth-first search.
static <N,E> Graph<N,E>	unmodifiableGraph(Graph<N,E> graph) Create and return an unmodifiable graph decorator that decorates the specified graph.

Methods inherited from class java.lang.Object

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

Method Detail

createGraph

public static <N,E> Graph<N,E> createGraph()

Create and return a new directed graph. The graph will not be null.

Type Parameters:

N - node value type

E - edge value type

Returns:

a new directed graph

createGraph

public static <N,E> Graph<N,E> createGraph(int nodeCapacity,
                                           int edgeCapacity)

Create and return a new directed graph with the specified initial node and edge capacities. The graph will not be null.

Type Parameters:

N - node value type

E - edge value type

Parameters:

nodeCapacity - initial node capacity, must be >= 0

edgeCapacity - initial edge capacity, must be >= 0

Returns:

a new directed graph with the specified initial node and edge capacities

createGraph

public static <N,E> Graph<N,E> createGraph(Graph<N,E> graph)

Create and return a new directed graph with the same structure and same node and edge values as the specified graph. The graph will not be null.

Type Parameters:

N - node value type

E - edge value type

Parameters:

graph - graph to copy, must not be null

Returns:

a new directed graph with the same structure and same node and edge values as the specified graph

connectedComponents

public static <N,E> Set<Set<Node<N,E>>> connectedComponents(Graph<N,E> graph)

Find the connected components of the specified graph.

Type Parameters:

N - node value type

E - edge value type

Parameters:

graph - graph, must not be null

Returns:

a set of the connected components of the specified graph

depthFirstSearch

public static <N,E> void depthFirstSearch(Graph<N,E> graph,
                                          Node<N,E> node,
                                          UnaryProcedure<Node<N,E>> procedure)

Depth-first search.

Type Parameters:

N - node value type

E - edge value type

Parameters:

graph - graph to search, must not be null

node - node to start from, must not be null and must be contained in the specified graph

procedure - procedure to run when visiting each node, must not be null

breadthFirstSearch

public static <N,E> void breadthFirstSearch(Graph<N,E> graph,
                                            Node<N,E> node,
                                            UnaryProcedure<Node<N,E>> procedure)

Breadth-first search.

Type Parameters:

N - node value type

E - edge value type

Parameters:

graph - graph to search, must not be null

node - node to start from, must not be null and must be contained in the specified graph

procedure - procedure to run when visiting each node, must not be null

undirectedBreadthFirstSearch

public static <N,E> void undirectedBreadthFirstSearch(Graph<N,E> graph,
                                                      Node<N,E> node,
                                                      UnaryProcedure<Node<N,E>> procedure)

Undirected breadth-first search.

Type Parameters:

N - node value type

E - edge value type

Parameters:

graph - graph to search, must not be null

node - node to start from, must not be null and must be contained in the specified graph

procedure - procedure to run when visiting each node, must not be null

unmodifiableGraph

public static <N,E> Graph<N,E> unmodifiableGraph(Graph<N,E> graph)

Create and return an unmodifiable graph decorator that decorates the specified graph.

Type Parameters:

N - node value type

E - edge value type

Parameters:

graph - graph to decorate, must not be null

Returns:

an unmodifiable graph decorator that decorates the specified graph