JBoss Common Classes 2.2.17.GA

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

java.lang.Object
  extended by org.jboss.util.graph.Graph<T>
Type Parameters:
T -

public class Graph<T>
extends Object

A directed graph data structure.

Version:
$Revision$
Author:
Scott.Stark@jboss.org, Ales.Justin@jboss.org

Field Summary
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
Graph()
          Construct a new graph without any vertices or edges
 
Method Summary
 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 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 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, Comparator<T> compare)
          Search the verticies for one with data.
 Vertex<T> findVertexByName(String name)
          Search the verticies for one with name.
 List<Edge<T>> getEdges()
          Get the graph edges
 Vertex<T> getRootVertex()
          Get the root vertex
 Vertex<T> getVertex(int n)
          Get the given Vertex.
 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.
 String toString()
           
 
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
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 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 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:
IllegalArgumentException - if from/to are not verticies in the graph

insertBiEdge

public boolean insertBiEdge(Vertex<T> from,
                            Vertex<T> to,
                            int cost)
                     throws 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:
IllegalArgumentException - if from/to are not verticies in the graph

getEdges

public 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 Exception> void depthFirstSearch(Vertex<T> v,
                                                   VisitorEX<T,E> visitor)
                      throws E extends 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 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 Exception> void breadthFirstSearch(Vertex<T> v,
                                                     VisitorEX<T,E> visitor)
                        throws E extends 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 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(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,
                                  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.

toString

public String toString()
Overrides:
toString in class Object

JBoss Common Classes 2.2.17.GA

Copyright © 2011 JBoss, a division of Red Hat, Inc.. All Rights Reserved.