T
- public class Graph<T> extends Object
Modifier and Type | Field and Description |
---|---|
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 and Description |
---|
Graph()
Construct a new graph without any vertices or edges
|
Modifier and Type | Method and Description |
---|---|
boolean |
addEdge(Vertex<T> from,
Vertex<T> to,
int cost)
Insert a directed, weighted Edge
|
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> |
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> |
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
|
boolean |
isEmpty()
Are there any verticies in the graph
|
boolean |
removeEdge(Vertex<T> from,
Vertex<T> to)
Remove an Edge
|
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() |
public static final int VISIT_COLOR_WHITE
public static final int VISIT_COLOR_GREY
public static final int VISIT_COLOR_BLACK
public boolean isEmpty()
public boolean addVertex(Vertex<T> v)
v
- the Vertex to addpublic int size()
public Vertex<T> getRootVertex()
public void setRootVertex(Vertex<T> root)
root
- - the vertex to set as the root and optionally add if it
does not exist in the graph.public Vertex<T> getVertex(int n)
n
- the index [0, size()-1] of the Vertex to accesspublic List<Vertex<T>> getVerticies()
public boolean addEdge(Vertex<T> from, Vertex<T> to, int cost) throws IllegalArgumentException
from
- - the Edgeto
- - the Edgecost
- - the EdgeIllegalArgumentException
- if from/to are not verticies in
the graphpublic boolean insertBiEdge(Vertex<T> from, Vertex<T> to, int cost) throws IllegalArgumentException
from
- - the Edgeto
- - the Edgecost
- - the EdgeIllegalArgumentException
- if from/to are not verticies in
the graphpublic boolean removeVertex(Vertex<T> v)
v
- the Vertex to removepublic boolean removeEdge(Vertex<T> from, Vertex<T> to)
from
- - the Edgeto
- - the Edgepublic void clearMark()
Vertex.clearMark()
public void clearEdges()
public void depthFirstSearch(Vertex<T> v, Visitor<T> visitor)
v
- - the Vertex to start the search fromvisitor
- - the vistor to inform prior toVisitor.visit(Graph, Vertex)
public <E extends Exception> void depthFirstSearch(Vertex<T> v, VisitorEX<T,E> visitor) throws E extends Exception
E
- exception typev
- - the Vertex to start the search fromvisitor
- - the vistor to inform prior toE
- if visitor.visit throws an exceptionE extends Exception
Visitor.visit(Graph, Vertex)
public void breadthFirstSearch(Vertex<T> v, Visitor<T> visitor)
v
- - the search starting pointvisitor
- - the vistor whose vist method is called prior
to visting a vertex.public <E extends Exception> void breadthFirstSearch(Vertex<T> v, VisitorEX<T,E> visitor) throws E extends Exception
E
- exception typev
- - the search starting pointvisitor
- - the vistor whose vist method is called prior
to visting a vertex.E
- if vistor.visit throws an exceptionE extends Exception
public void dfsSpanningTree(Vertex<T> v, DFSVisitor<T> visitor)
v
- - the vertex to start the search fromvisitor
- - visitor invoked after each vertex
is visited and an edge is added to the tree.public Vertex<T> findVertexByName(String name)
name
- - the vertex namepublic Vertex<T> findVertexByData(T data, Comparator<T> compare)
data
- - the vertex data to matchcompare
- - the comparator to perform the matchpublic Edge<T>[] findCycles()
Copyright © 2018 JBoss by Red Hat. All rights reserved.