org.jboss.util.graph

Class Graph<T>

java.lang.Object

org.jboss.util.graph.Graph<T>

Type Parameters:

T -

public class Graph<T>
extends java.lang.Object

A directed graph data structure.

Version:

$Revision$

Field Summary

Fields

Modifier and Type	Field and Description
private java.util.List<Edge<T>>	edges Vector of edges in the graph
private Vertex<T>	rootVertex The vertex identified as the root of the graph
private java.util.Map<java.lang.String,Vertex<T>>	verticies Map of graph verticies
static int	VISIT_COLOR_BLACK Color used to mark nodes after descendants are completely visited
static int	VISIT_COLOR_GREY Color used to mark nodes as they are first visited in DFS order
static int	VISIT_COLOR_WHITE Color used to mark unvisited nodes

Constructor Summary

Constructors

Constructor and Description
Graph() Construct a new graph without any vertices or edges

Method Summary

Modifier and Type	Method and Description
boolean	addEdge(Vertex<T> from, Vertex<T> to, int cost) Insert a directed, weighted Edge into the graph.
boolean	addVertex(Vertex<T> v) Add a vertex to the graph
void	breadthFirstSearch(Vertex<T> v, Visitor<T> visitor) Perform a breadth first search of this graph, starting at v.
<E extends java.lang.Exception> void	breadthFirstSearch(Vertex<T> v, VisitorEX<T,E> visitor) Perform a breadth first search of this graph, starting at v.
void	clearEdges() Clear the mark state of all edges in the graph by calling clearMark() on all edges.
void	clearMark() Clear the mark state of all verticies in the graph by calling clearMark() on all verticies.
void	depthFirstSearch(Vertex<T> v, Visitor<T> visitor) Perform a depth first serach using recursion.
<E extends java.lang.Exception> void	depthFirstSearch(Vertex<T> v, VisitorEX<T,E> visitor) Perform a depth first serach using recursion.
void	dfsSpanningTree(Vertex<T> v, DFSVisitor<T> visitor) Find the spanning tree using a DFS starting from v.
Edge<T>[]	findCycles() Search the graph for cycles.
Vertex<T>	findVertexByData(T data, java.util.Comparator<T> compare) Search the verticies for one with data.
Vertex<T>	findVertexByName(java.lang.String name) Search the verticies for one with name.
java.util.List<Edge<T>>	getEdges() Get the graph edges
Vertex<T>	getRootVertex() Get the root vertex
Vertex<T>	getVertex(int n) Get the given Vertex.
java.util.List<Vertex<T>>	getVerticies() Get the graph verticies
boolean	insertBiEdge(Vertex<T> from, Vertex<T> to, int cost) Insert a bidirectional Edge in the graph
boolean	isEmpty() Are there any verticies in the graph
boolean	removeEdge(Vertex<T> from, Vertex<T> to) Remove an Edge from the graph
boolean	removeVertex(Vertex<T> v) Remove a vertex from the graph
void	setRootVertex(Vertex<T> root) Set a root vertex.
int	size() Get the vertex count.
java.lang.String	toString()
private void	visit(Vertex<T> v, java.util.ArrayList<Edge<T>> cycleEdges)

Methods inherited from class java.lang.Object

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

Field Detail

VISIT_COLOR_WHITE

public static final int VISIT_COLOR_WHITE

Color used to mark unvisited nodes

See Also:

Constant Field Values

VISIT_COLOR_GREY

public static final int VISIT_COLOR_GREY

Color used to mark nodes as they are first visited in DFS order

See Also:

Constant Field Values

VISIT_COLOR_BLACK

public static final int VISIT_COLOR_BLACK

Color used to mark nodes after descendants are completely visited

See Also:

Constant Field Values

verticies

private java.util.Map<java.lang.String,Vertex<T>> verticies

Map of graph verticies

edges

private java.util.List<Edge<T>> edges

Vector of edges in the graph

rootVertex

private Vertex<T> rootVertex

The vertex identified as the root of the graph

Constructor Detail

Graph

public Graph()

Construct a new graph without any vertices or edges

Method Detail

isEmpty

public boolean isEmpty()

Are there any verticies in the graph

Returns:

true if there are no verticies in the graph

addVertex

public boolean addVertex(Vertex<T> v)

Add a vertex to the graph

Parameters:

v - the Vertex to add

Returns:

true if the vertex was added, false if it was already in the graph.

size

public int size()

Get the vertex count.

Returns:

the number of verticies in the graph.

getRootVertex

public Vertex<T> getRootVertex()

Get the root vertex

Returns:

the root vertex if one is set, null if no vertex has been set as the root.

setRootVertex

public void setRootVertex(Vertex<T> root)

Set a root vertex. If root does no exist in the graph it is added.

Parameters:

root - - the vertex to set as the root and optionally add if it does not exist in the graph.

getVertex

public Vertex<T> getVertex(int n)

Get the given Vertex.

Parameters:

n - the index [0, size()-1] of the Vertex to access

Returns:

the nth Vertex

getVerticies

public java.util.List<Vertex<T>> getVerticies()

Get the graph verticies

Returns:

the graph verticies

addEdge

public boolean addEdge(Vertex<T> from,
                       Vertex<T> to,
                       int cost)
                throws java.lang.IllegalArgumentException

Insert a directed, weighted Edge into the graph.

Parameters:

from - - the Edge starting vertex

to - - the Edge ending vertex

cost - - the Edge weight/cost

Returns:

true if the Edge was added, false if from already has this Edge

Throws:

java.lang.IllegalArgumentException - if from/to are not verticies in the graph

insertBiEdge

public boolean insertBiEdge(Vertex<T> from,
                            Vertex<T> to,
                            int cost)
                     throws java.lang.IllegalArgumentException

Insert a bidirectional Edge in the graph

Parameters:

from - - the Edge starting vertex

to - - the Edge ending vertex

cost - - the Edge weight/cost

Returns:

true if edges between both nodes were added, false otherwise

Throws:

java.lang.IllegalArgumentException - if from/to are not verticies in the graph

getEdges

public java.util.List<Edge<T>> getEdges()

Get the graph edges

Returns:

the graph edges

removeVertex

public boolean removeVertex(Vertex<T> v)

Remove a vertex from the graph

Parameters:

v - the Vertex to remove

Returns:

true if the Vertex was removed

removeEdge

public boolean removeEdge(Vertex<T> from,
                          Vertex<T> to)

Remove an Edge from the graph

Parameters:

from - - the Edge starting vertex

to - - the Edge ending vertex

Returns:

true if the Edge exists, false otherwise

clearMark

public void clearMark()

Clear the mark state of all verticies in the graph by calling clearMark() on all verticies.

See Also:

Vertex.clearMark()

clearEdges

public void clearEdges()

Clear the mark state of all edges in the graph by calling clearMark() on all edges.

depthFirstSearch

public void depthFirstSearch(Vertex<T> v,
                             Visitor<T> visitor)

Perform a depth first serach using recursion.

Parameters:

v - - the Vertex to start the search from

visitor - - the vistor to inform prior to

See Also:

Visitor.visit(Graph, Vertex)

depthFirstSearch

public <E extends java.lang.Exception> void depthFirstSearch(Vertex<T> v,
                                                             VisitorEX<T,E> visitor)
                                                      throws E extends java.lang.Exception

Perform a depth first serach using recursion. The search may be cut short if the visitor throws an exception.

Type Parameters:

E - exception type

Parameters:

v - - the Vertex to start the search from

visitor - - the vistor to inform prior to

Throws:

E - if visitor.visit throws an exception

E extends java.lang.Exception

See Also:

Visitor.visit(Graph, Vertex)

breadthFirstSearch

public void breadthFirstSearch(Vertex<T> v,
                               Visitor<T> visitor)

Perform a breadth first search of this graph, starting at v.

Parameters:

v - - the search starting point

visitor - - the vistor whose vist method is called prior to visting a vertex.

breadthFirstSearch

public <E extends java.lang.Exception> void breadthFirstSearch(Vertex<T> v,
                                                               VisitorEX<T,E> visitor)
                                                        throws E extends java.lang.Exception

Perform a breadth first search of this graph, starting at v. The vist may be cut short if visitor throws an exception during a vist callback.

Type Parameters:

E - exception type

Parameters:

v - - the search starting point

visitor - - the vistor whose vist method is called prior to visting a vertex.

Throws:

E - if vistor.visit throws an exception

E extends java.lang.Exception

dfsSpanningTree

public void dfsSpanningTree(Vertex<T> v,
                            DFSVisitor<T> visitor)

Find the spanning tree using a DFS starting from v.

Parameters:

v - - the vertex to start the search from

visitor - - visitor invoked after each vertex is visited and an edge is added to the tree.

findVertexByName

public Vertex<T> findVertexByName(java.lang.String name)

Search the verticies for one with name.

Parameters:

name - - the vertex name

Returns:

the first vertex with a matching name, null if no matches are found

findVertexByData

public Vertex<T> findVertexByData(T data,
                                  java.util.Comparator<T> compare)

Search the verticies for one with data.

Parameters:

data - - the vertex data to match

compare - - the comparator to perform the match

Returns:

the first vertex with a matching data, null if no matches are found

findCycles

public Edge<T>[] findCycles()

Search the graph for cycles. In order to detect cycles, we use a modified depth first search called a colored DFS. All nodes are initially marked white. When a node is encountered, it is marked grey, and when its descendants are completely visited, it is marked black. If a grey node is ever encountered, then there is a cycle.

Returns:

the edges that form cycles in the graph. The array will be empty if there are no cycles.

visit

private void visit(Vertex<T> v,
                   java.util.ArrayList<Edge<T>> cycleEdges)

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object