Package 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 Description private java.util.List<Edge<T>>
edges
Vectorof edges in the graph private Vertex<T>
rootVertex
The vertex identified as the root of the graphprivate java.util.Map<java.lang.String,Vertex<T>>
verticies
Mapof graph verticies static int
VISIT_COLOR_BLACK
Color used to mark nodes after descendants are completely visitedstatic int
VISIT_COLOR_GREY
Color used to mark nodes as they are first visited in DFS orderstatic int
VISIT_COLOR_WHITE
Color used to mark unvisited nodes
-
Constructor Summary
Constructors Constructor Description Graph()
Construct a new graph without any vertices or edges
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description boolean
addEdge(Vertex<T> from, Vertex<T> to, int cost)
Insert a directed, weighted Edgeinto the graph. boolean
addVertex(Vertex<T> v)
Add a vertex to the graphvoid
breadthFirstSearch(Vertex<T> v, Visitor<T> visitor)
Perform a breadth first search of this graph, starting at v.<E extends java.lang.Exception>
voidbreadthFirstSearch(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>
voiddepthFirstSearch(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 edgesVertex<T>
getRootVertex()
Get the root vertexVertex<T>
getVertex(int n)
Get the given Vertex.java.util.List<Vertex<T>>
getVerticies()
Get the graph verticiesboolean
insertBiEdge(Vertex<T> from, Vertex<T> to, int cost)
Insert a bidirectional Edgein the graph boolean
isEmpty()
Are there any verticies in the graphboolean
removeEdge(Vertex<T> from, Vertex<T> to)
Remove an Edgefrom the graph boolean
removeVertex(Vertex<T> v)
Remove a vertex from the graphvoid
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)
-
-
-
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
-
-
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 Edgeinto the graph. - Parameters:
from
- - the Edgestarting vertex to
- - the Edgeending vertex cost
- - the Edgeweight/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 Edgein the graph - Parameters:
from
- - the Edgestarting vertex to
- - the Edgeending vertex cost
- - the Edgeweight/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
-
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 Edgefrom the graph - Parameters:
from
- - the Edgestarting vertex to
- - the Edgeending 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 fromvisitor
- - 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 fromvisitor
- - the vistor to inform prior to- Throws:
E
- if visitor.visit throws an exceptionE 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 pointvisitor
- - 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 pointvisitor
- - the vistor whose vist method is called prior to visting a vertex.- Throws:
E
- if vistor.visit throws an exceptionE 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 fromvisitor
- - 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 matchcompare
- - 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 java.lang.String toString()
- Overrides:
toString
in classjava.lang.Object
-
-