com.jn.langx.util.collection.graph

类 Graph<T>

java.lang.Object

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

类型参数:

T -

直接已知子类:

DAG

public class Graph<T>
extends Object

A directed graph data structure.

字段概要

字段

限定符和类型	字段和说明
protected List<Edge<T>>	edges Vector of edges in the graph
protected Vertex<T>	rootVertex The vertex identified as the root of the graph
protected Map<String,Vertex<T>>	vertices Map of graph vertices
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	addBiEdge(Vertex<T> from, Vertex<T> to, int weight) Insert a bidirectional (两个方向的) Edge in the graph
boolean	addEdge(String from, String to)
boolean	addEdge(String from, String to, int weight)
boolean	addEdge(String from, String to, String label, int weight)
boolean	addEdge(Vertex<T> from, Vertex<T> to)
boolean	addEdge(Vertex<T> from, Vertex<T> to, int weight)
boolean	addEdge(Vertex<T> from, Vertex<T> to, String label, int weight) Insert a directed, weighted Edge into the graph.
boolean	addVertex(String name, T data)
boolean	addVertex(Vertex<T> v) Add a vertex to the graph
Vertex<T>	findVertexByData(T data, Comparator<T> compare) Search the verticies for one with data.
List<Edge<T>>	getEdges() Get the graph edges
Vertex<T>	getRootVertex() Get the root vertex
Vertex<T>	getVertex(int n) Get the given Vertex.
Vertex<T>	getVertex(String name) Search the verticies for one with name.
List<String>	getVertexNames()
List<Vertex<T>>	getVertices() Get the graph vertices
boolean	hasBiEdge(String from, String to)
boolean	hasEdge(String from, String to)
boolean	hasVertex(String name)
boolean	isEmpty() Are there any verticies in the graph
boolean	removeEdge(String from, String to)
boolean	removeEdge(Vertex<T> from, Vertex<T> to) Remove an Edge from the graph
boolean	removeVertex(String name)
boolean	removeVertex(String vertexName, boolean removeUnsharedOutgoing)
boolean	removeVertex(Vertex<T> v) Remove a vertex from the graph
boolean	removeVertex(Vertex<T> v, boolean removeUnsharedOutgoing)
void	setRootVertex(Vertex<T> vertex) Set a vertex 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

另请参阅:

常量字段值

vertices

protected Map<String,Vertex<T>> vertices

Map of graph vertices

edges

protected List<Edge<T>> edges

Vector of edges in the graph

rootVertex

protected Vertex<T> rootVertex

The vertex identified as the root of the graph

构造器详细资料

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

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> vertex)

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

参数:

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

addVertex

public boolean addVertex(String name,
                         T data)

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.

removeVertex

public boolean removeVertex(String name)

removeVertex

public boolean removeVertex(Vertex<T> v)

Remove a vertex from the graph

参数:

v - the Vertex to remove

返回:

true if the Vertex was removed

removeVertex

public boolean removeVertex(String vertexName,
                            boolean removeUnsharedOutgoing)

removeVertex

public boolean removeVertex(Vertex<T> v,
                            boolean removeUnsharedOutgoing)

getVertices

public List<Vertex<T>> getVertices()

Get the graph vertices

返回:

the graph vertices

getVertexNames

public List<String> getVertexNames()

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

getVertex

public Vertex<T> getVertex(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

hasVertex

public boolean hasVertex(String name)

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

addEdge

public boolean addEdge(String from,
                       String to)
                throws IllegalArgumentException

抛出:

IllegalArgumentException

addEdge

public boolean addEdge(String from,
                       String to,
                       int weight)
                throws IllegalArgumentException

抛出:

IllegalArgumentException

addEdge

public boolean addEdge(String from,
                       String to,
                       String label,
                       int weight)
                throws IllegalArgumentException

抛出:

IllegalArgumentException

addEdge

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

addEdge

public boolean addEdge(Vertex<T> from,
                       Vertex<T> to,
                       int weight)

addEdge

public boolean addEdge(Vertex<T> from,
                       Vertex<T> to,
                       String label,
                       int weight)

Insert a directed, weighted Edge into the graph.

参数:

from - - the Edge starting vertex

to - - the Edge ending vertex

weight - - the Edge weight

返回:

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

addBiEdge

public boolean addBiEdge(Vertex<T> from,
                         Vertex<T> to,
                         int weight)

Insert a bidirectional (两个方向的) Edge in the graph

参数:

from - - the Edge starting vertex

to - - the Edge ending vertex

weight - - 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

removeEdge

public boolean removeEdge(String from,
                          String to)

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

hasEdge

public boolean hasEdge(String from,
                       String to)

hasBiEdge

public boolean hasBiEdge(String from,
                         String to)

toString

public String toString()

覆盖:

toString 在类中 Object