com.jn.langx.util.collection.graph

类 Graph<T>

java.lang.Object

com.jn.langx.util.collection.graph.Graph<T>

类型参数:

T -

public class Graph<T>
extends Object

A directed graph data structure.

字段概要

字段

限定符和类型	字段和说明
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

构造器概要

构造器

构造器和说明
Graph() Construct a new graph without any vertices or edges

方法概要

限定符和类型	方法和说明
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.
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.
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()

从类继承的方法 java.lang.Object

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

字段详细资料

VISIT_COLOR_WHITE

public static final int VISIT_COLOR_WHITE

Color used to mark unvisited nodes

另请参阅:

常量字段值

VISIT_COLOR_GREY

public static final int VISIT_COLOR_GREY

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

另请参阅:

常量字段值

VISIT_COLOR_BLACK

public static final int VISIT_COLOR_BLACK

Color used to mark nodes after descendants are completely visited

另请参阅:

常量字段值

构造器详细资料

Graph

public Graph()

Construct a new graph without any vertices or edges

方法详细资料

isEmpty

public boolean isEmpty()

Are there any verticies in the graph

返回:

true if there are no verticies in the graph

addVertex

public boolean addVertex(Vertex<T> v)

Add a vertex to the graph

参数:

v - the Vertex to add

返回:

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

size

public int size()

Get the vertex count.

返回:

the number of verticies in the graph.

getRootVertex

public Vertex<T> getRootVertex()

Get the root vertex

返回:

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.

参数:

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.

参数:

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

返回:

the nth Vertex

getVerticies

public List<Vertex<T>> getVerticies()

Get the graph verticies

返回:

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.

参数:

from - - the Edge starting vertex

to - - the Edge ending vertex

cost - - the Edge weight/cost

返回:

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

抛出:

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

参数:

from - - the Edge starting vertex

to - - the Edge ending vertex

cost - - the Edge weight/cost

返回:

true if edges between both nodes were added, false otherwise

抛出:

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

getEdges

public List<Edge<T>> getEdges()

Get the graph edges

返回:

the graph edges

removeVertex

public boolean removeVertex(Vertex<T> v)

Remove a vertex from the graph

参数:

v - the Vertex to remove

返回:

true if the Vertex was removed

removeEdge

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

Remove an Edge from the graph

参数:

from - - the Edge starting vertex

to - - the Edge ending vertex

返回:

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.

另请参阅:

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. The search may be cut short if the visitor throws an exception.

参数:

v - - the Vertex to start the search from

visitor - - the vistor to inform prior to

抛出:

Exception - if visitor.visit throws an exception

另请参阅:

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. The vist may be cut short if visitor throws an exception during a vist callback.

参数:

v - - the search starting point

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

抛出:

Exception - if vistor.visit throws an exception

dfsSpanningTree

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

Find the spanning tree using a DFS starting from v.

参数:

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.

参数:

name - - the vertex name

返回:

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.

参数:

data - - the vertex data to match

compare - - the comparator to perform the match

返回:

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.

返回:

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

toString

public String toString()

覆盖:

toString 在类中 Object