public class GraphUtils
extends java.lang.Object
Modifier and Type | Method and Description |
---|---|
static <V extends Vertex,E extends Edge> |
breadthFirstSearch(Graph<V,E> graph)
Performs a breadth first search (BFS) in the specified graph starting with the first vertex.
|
static <V extends Vertex,E extends Edge> |
breadthFirstSearch(Graph<V,E> graph,
V start)
Performs a breadth first search (BFS) in the specified graph starting at a given vertex.
|
static <V extends Vertex,E extends Edge> |
createAdjacencyMatrix(Graph<V,E> graph)
Creates an adjacency matrix of a specified graph.
|
static <V extends Vertex,E extends Edge> |
createAdjacencyMatrix(Graph<V,E> graph,
boolean asUpperTriangleMatrix)
Creates an adjacency matrix of a specified graph.
|
static SimpleGraph<Vertex,Edge> |
createCompleteBipartiteGraph(int n,
int m)
Creates a complete bipartite graph Kn,m of n vertices in the first and m vertices in the second subset.
|
static <V extends Vertex,E extends Edge> |
createCompleteBipartiteGraph(int n,
int m,
GraphFactory<V,E> factory)
Creates a complete bipartite graph Kn,m of n vertices in the first and m vertices in the second subset.
|
static <V extends Vertex,E extends Edge> |
createCompleteBipartiteGraph(int n,
int m,
GraphFactory<V,E> factory,
float maxEdgeWeight)
Creates a complete bipartite graph Kn,m of n vertices in the first and m vertices in the second subset.
|
static SimpleGraph<Vertex,Edge> |
createCompleteGraph(int n,
boolean directed)
Creates a complete graph Kn of n vertices.
|
static <V extends Vertex,E extends Edge> |
createCompleteGraph(int n,
boolean directed,
GraphFactory<V,E> factory)
Creates a complete graph Kn of n vertices.
|
static <V extends Vertex,E extends Edge> |
createCompleteGraph(int n,
boolean directed,
GraphFactory<V,E> factory,
float maxEdgeWeight)
Creates a complete graph Kn of n vertices.
|
static <V extends Vertex,E extends Edge> |
createGraph(Matrix<? extends java.lang.Number> adjacencyMatrix,
GraphFactory<V,E> factory,
boolean directed)
Creates a graph based on an adjacency matrix where a zero-weight edge indicates that there is no edge between two vertices.
|
static <V extends Vertex,E extends Edge> |
createGraph(Matrix<? extends java.lang.Number> adjacencyMatrix,
GraphFactory<V,E> factory,
boolean directed,
boolean zeroWeightsAllowed)
Creates a graph based on an adjacency matrix.
|
static SimpleGraph<Vertex,Edge> |
createRandomGraph(int n,
boolean directed)
Creates a random graph.
|
static <V extends Vertex,E extends Edge> |
createRandomGraph(int n,
boolean directed,
GraphFactory<V,E> factory)
Creates a random graph.
|
static <V extends Vertex,E extends Edge> |
createRandomGraph(int n,
boolean directed,
GraphFactory<V,E> factory,
float minEdgeWeight,
float maxEdgeWeight)
Creates a random graph.
|
static <V extends Vertex,E extends Edge> |
depthFirstSearch(Graph<V,E> graph)
Performs a depth first search (DFS) in the specified graph starting with the first vertex.
|
static <V extends Vertex,E extends Edge> |
depthFirstSearch(Graph<V,E> graph,
V start)
Performs a depth first search (DFS) in the specified graph starting at a given vertex.
|
static <V extends Vertex,E extends Edge> |
findAugmentingPath(Graph<V,E> graph,
V start,
Matching<E> m)
Finds an augmenting path beginning with a start vertex in a specified graph based on a given matching.
|
static <V extends Vertex,E extends Edge> |
findShortestPathFrom(Graph<V,E> graph,
V from,
java.util.Map<V,java.lang.Float> distance,
java.util.Map<V,V> path)
Finds the shortest path from a start vertex to all other vertices of a graph.
|
static <V extends Vertex,E extends Edge> |
findShortestPathFromTo(Graph<V,E> graph,
V from,
V to)
Finds the shortest path from a start vertex to all other vertices of a graph.
|
static <V extends Vertex,E extends Edge> |
findShortestPaths(Graph<V,E> graph,
Matrix<java.lang.Float> distMatrix,
Matrix<V> predMatrix)
Finds the shortest paths from every vertex to all other vertices of a graph.
|
static <V extends Vertex,E extends Edge> |
findShortestPaths(Graph<V,E> graph,
Matrix<java.lang.Float> distMatrix,
Matrix<V> predMatrix,
boolean considerAllVertices)
Finds the shortest paths from every vertex to all other vertices of a graph.
|
static <V extends Vertex,E extends Edge> |
getBipartiteVertexSets(Graph<V,E> graph)
Gets the vertex subsets
V1 and V2 so that V1 union V2 = V and V1 intersection V2 = empty set . |
static <V extends Vertex,E extends Edge> |
getBipartiteVertexSets(Graph<V,E> graph,
boolean nonIncidentVerticesToSubset1)
Gets the vertex subsets
V1 and V2 so that V1 union V2 = V and V1 intersection V2 = empty set . |
static <V extends Vertex,E extends Edge> |
getConnectedComponents(Graph<V,E> graph)
Gets all connected components from the given graph.
|
static <V extends Vertex,E extends Edge> |
invertGraph(Graph<V,E> graph,
GraphFactory<V,E> factory)
Inverts the specified graph meaning a directed graph is transferred in an undirected one and an undirected
graph is transferred in a directed one.
|
static Graph<Vertex,Edge> |
invertGraph(Graph<Vertex,Edge> graph)
Inverts the specified graph meaning a directed graph is transferred in an undirected one and an undirected
graph is transferred in a directed one.
|
static <V extends Vertex,E extends Edge> |
is2Colorable(Graph<V,E> graph)
Indicates whether the given graph is 2-colorable.
|
static <V extends Vertex,E extends Edge> |
isAugmentingPath(Path<V> path,
Matching<E> matching)
Indicates whether the specified path is an augmenting path on the given matching.
|
static <V extends Vertex,E extends Edge> |
isBipartite(Graph<V,E> graph)
Indicates whether the given graph is bipartite that means if the graph is simple and the set of vertices can be divided
into two disjoint subsets.
|
static <V extends Vertex,E extends Edge> |
isComplete(Graph<V,E> graph)
Indicates whether the given graph is complete that means if the graph is simple and each vertex of the graph is connected with
each other.
|
static <V extends Vertex,E extends Edge> |
isCompleteBipartite(Graph<V,E> graph)
Indicates whether the given graph is complete bipartite that means the graph is simple and each vertex of subset one
is connected with each vertex of subset two and vice versa.
|
static <V extends Vertex,E extends Edge> |
isConnected(Graph<V,E> graph)
Indicates whether the given graph is (strongly) connected.
|
static <V extends Vertex,E extends Edge> |
isEulerian(Graph<V,E> graph)
Indicates whether the specified graph is an Eulerian graph.
|
static <V extends Vertex,E extends Edge> |
isMultiGraph(Graph<V,E> graph)
Indicates whether the given graph is a multi graph that means the graph has vertices
with more than one edge between them.
|
static <V extends Vertex,E extends Edge> |
isSimpleGraph(Graph<V,E> graph)
Indicates whether the given graph is a simple graph that means the graph has no loops and two different
vertices are only connected by one edge.
|
static <V extends Vertex> |
toPath(java.lang.String path,
Graph<V,?> graph)
Converts a specified path as a string in a concrete
Path . |
static <V extends Vertex> |
toTrail(java.lang.String trail,
Graph<V,? extends Edge> graph,
Trail<Vertex> base)
Converts a specified trail as a string in a concrete
Trail . |
static <V extends Vertex> |
toWalk(java.lang.String walk,
Graph<V,?> graph)
Converts a specified walk as a string in a concrete
Walk . |
public static <V extends Vertex,E extends Edge> boolean isSimpleGraph(Graph<V,E> graph) throws java.lang.IllegalArgumentException
graph
- the graphtrue
if the graph is simple otherwise false
java.lang.IllegalArgumentException
- public static <V extends Vertex,E extends Edge> boolean isMultiGraph(Graph<V,E> graph) throws java.lang.IllegalArgumentException
graph
- the graphtrue
if it is a multi graph otherwise false
java.lang.IllegalArgumentException
- public static <V extends Vertex,E extends Edge> boolean isBipartite(Graph<V,E> graph) throws java.lang.IllegalArgumentException
graph
- the graphtrue
if the graph is bipartite otherwise false
java.lang.IllegalArgumentException
- getBipartiteVertexSets(Graph)
public static <V extends Vertex,E extends Edge> java.util.List<java.util.List<V>> getBipartiteVertexSets(Graph<V,E> graph) throws java.lang.IllegalArgumentException
V1
and V2
so that V1 union V2 = V
and V1 intersection V2 = empty set
.
This is only possible if the graph is bipartite.
graph
- the graphV1
and V2
in one list or null
if graph is not bipartitejava.lang.IllegalArgumentException
- isBipartite(Graph)
public static <V extends Vertex,E extends Edge> java.util.List<java.util.List<V>> getBipartiteVertexSets(Graph<V,E> graph, boolean nonIncidentVerticesToSubset1) throws java.lang.IllegalArgumentException
V1
and V2
so that V1 union V2 = V
and V1 intersection V2 = empty set
.
This is only possible if the graph is bipartite.
graph
- the graphnonIncidentVerticesToSubset1
- true
if non-incident vertices should be added to subset 1 or false
to add non-incident vertices to subset 2V1
and V2
in one list or null
if graph is not bipartitejava.lang.IllegalArgumentException
- isBipartite(Graph)
public static <V extends Vertex,E extends Edge> boolean is2Colorable(Graph<V,E> graph) throws java.lang.IllegalArgumentException
graph
- the graphtrue
if the graph is 2-colorable otherwise false
java.lang.IllegalArgumentException
- public static <V extends Vertex,E extends Edge> boolean isComplete(Graph<V,E> graph) throws java.lang.IllegalArgumentException
graph
- the graphtrue
if the graph is complete otherwise false
java.lang.IllegalArgumentException
- public static <V extends Vertex,E extends Edge> boolean isCompleteBipartite(Graph<V,E> graph) throws java.lang.IllegalArgumentException
graph
- the graphtrue
if the graph is complete bipartite otherwise false
java.lang.IllegalArgumentException
- public static <V extends Vertex,E extends Edge> java.util.List<java.util.List<V>> getConnectedComponents(Graph<V,E> graph) throws java.lang.IllegalArgumentException
graph
- the graphjava.lang.IllegalArgumentException
- public static <V extends Vertex,E extends Edge> boolean isConnected(Graph<V,E> graph) throws java.lang.IllegalArgumentException
invertGraph(Graph, GraphFactory)
to transfer
the directed graph in an undirected one and then check whether the undirected equivalent is connected.graph
- the graphtrue
if the given graph is (strongly) connected otherwise false
java.lang.IllegalArgumentException
- public static SimpleGraph<Vertex,Edge> createCompleteGraph(int n, boolean directed) throws java.lang.IllegalArgumentException
n
- the number of verticesdirected
- true
if the graph should be directed otherwise false
java.lang.IllegalArgumentException
- < 1
public static <V extends Vertex,E extends Edge> SimpleGraph<V,E> createCompleteGraph(int n, boolean directed, GraphFactory<V,E> factory) throws java.lang.IllegalArgumentException
n
- the number of verticesdirected
- true
if the graph should be directed otherwise false
factory
- the factory to create vertices and edges for the graphjava.lang.IllegalArgumentException
- < 1
public static <V extends Vertex,E extends Edge> SimpleGraph<V,E> createCompleteGraph(int n, boolean directed, GraphFactory<V,E> factory, float maxEdgeWeight) throws java.lang.IllegalArgumentException
n
- the number of verticesdirected
- true
if the graph should be directed otherwise false
factory
- the factory to create vertices and edges for the graphmaxEdgeWeight
- the max. weight of edges (the weights are generated randomly up to that value)java.lang.IllegalArgumentException
- < 1
public static SimpleGraph<Vertex,Edge> createCompleteBipartiteGraph(int n, int m) throws java.lang.IllegalArgumentException
n
- the number of vertices in the first subsetm
- the number of vertices in the first subsetjava.lang.IllegalArgumentException
- < 1
< 1
public static <V extends Vertex,E extends Edge> SimpleGraph<V,E> createCompleteBipartiteGraph(int n, int m, GraphFactory<V,E> factory) throws java.lang.IllegalArgumentException
n
- the number of vertices in the first subsetm
- the number of vertices in the first subsetfactory
- the factory to create vertices and edges for the graphjava.lang.IllegalArgumentException
- < 1
< 1
public static <V extends Vertex,E extends Edge> SimpleGraph<V,E> createCompleteBipartiteGraph(int n, int m, GraphFactory<V,E> factory, float maxEdgeWeight) throws java.lang.IllegalArgumentException
n
- the number of vertices in the first subsetm
- the number of vertices in the first subsetfactory
- the factory to create vertices and edges for the graphmaxEdgeWeight
- the max. weight of edges (the weights are generated randomly up to that value)java.lang.IllegalArgumentException
- < 1
< 1
public static <V extends Vertex,E extends Edge> SimpleGraph<V,E> createGraph(Matrix<? extends java.lang.Number> adjacencyMatrix, GraphFactory<V,E> factory, boolean directed)
adjacencyMatrix
- the adjacency matrixfactory
- the graph factorydirected
- true
if a directed graph should be created otherwise false
for an undirected onejava.lang.IllegalArgumentException
- public static <V extends Vertex,E extends Edge> SimpleGraph<V,E> createGraph(Matrix<? extends java.lang.Number> adjacencyMatrix, GraphFactory<V,E> factory, boolean directed, boolean zeroWeightsAllowed)
adjacencyMatrix
- the adjacency matrixfactory
- the graph factorydirected
- true
if a directed graph should be created otherwise false
for an undirected onezeroWeightsAllowed
- true
if zero-weight edges are allowed (in that case use Float.POSITIVE_INFINITY
to define that there is no edge between two vertices) otherwise false
meaning a zero-weight edge indicates that there is no edge between the two verticesjava.lang.IllegalArgumentException
- public static SimpleGraph<Vertex,Edge> createRandomGraph(int n, boolean directed)
n
- number of verticesdirected
- true
if a directed graph should be created otherwise false
for an undirected onejava.lang.IllegalArgumentException
- < 1
public static <V extends Vertex,E extends Edge> SimpleGraph<V,E> createRandomGraph(int n, boolean directed, GraphFactory<V,E> factory)
n
- number of verticesdirected
- true
if a directed graph should be created otherwise false
for an undirected onefactory
- the graph factoryjava.lang.IllegalArgumentException
- < 1
public static <V extends Vertex,E extends Edge> SimpleGraph<V,E> createRandomGraph(int n, boolean directed, GraphFactory<V,E> factory, float minEdgeWeight, float maxEdgeWeight)
n
- number of verticesdirected
- true
if a directed graph should be created otherwise false
for an undirected onefactory
- the graph factoryminEdgeWeight
- the min. weight of edgesmaxEdgeWeight
- the max. weight of edgesjava.lang.IllegalArgumentException
- < 1
public static Graph<Vertex,Edge> invertGraph(Graph<Vertex,Edge> graph) throws java.lang.IllegalArgumentException
graph
- the graphjava.lang.IllegalArgumentException
- public static <V extends Vertex,E extends Edge> Graph<V,E> invertGraph(Graph<V,E> graph, GraphFactory<V,E> factory) throws java.lang.IllegalArgumentException
graph
- the graphfactory
- the graph factoryjava.lang.IllegalArgumentException
- public static <V extends Vertex,E extends Edge> NumericMatrix<java.lang.Float> createAdjacencyMatrix(Graph<V,E> graph) throws java.lang.IllegalArgumentException
graph
- the graph its adjacency matrix should be creatednull
indicates that there is no edge between two verticesjava.lang.IllegalArgumentException
- public static <V extends Vertex,E extends Edge> NumericMatrix<java.lang.Float> createAdjacencyMatrix(Graph<V,E> graph, boolean asUpperTriangleMatrix) throws java.lang.IllegalArgumentException
graph
- the graph its adjacency matrix should be createdasUpperTriangleMatrix
- true
if the form of the adjacency matrix should be an upper triangle matrix (only possible if the graph is undirected and complete or complete bipartite) otherwise false
null
indicates that there is no edge between two verticesjava.lang.IllegalArgumentException
- public static <V extends Vertex,E extends Edge> void findShortestPathFrom(Graph<V,E> graph, V from, java.util.Map<V,java.lang.Float> distance, java.util.Map<V,V> path) throws java.lang.IllegalArgumentException
graph
- the graphfrom
- the start vertexdistance
- the output matrix of the distance (distance.get(v)
is the distance from the start vertex to v where Float.POSITIVE_INFINITY
means that there is no path from the start vertex to this vertex)path
- the output matrix of the path (path.get(v)
is the predecessor of v on the shortest path from the start vertex to v or null
if there is no path from the start vertex to v)java.lang.IllegalArgumentException
- public static <V extends Vertex,E extends Edge> Path<V> findShortestPathFromTo(Graph<V,E> graph, V from, V to) throws java.lang.IllegalArgumentException
graph
- the graphfrom
- the start vertexto
- the end vertexjava.lang.IllegalArgumentException
- public static <V extends Vertex,E extends Edge> void findShortestPaths(Graph<V,E> graph, Matrix<java.lang.Float> distMatrix, Matrix<V> predMatrix) throws java.lang.IllegalArgumentException
graph
- the graphdistMatrix
- the distance matrix (output parameter) that has to be an n-by-n matrix where n is the order of the graphpredMatrix
- the predecessor matrix (output parameter) that has to be an n-by-n matrix where n is the order of the graphjava.lang.IllegalArgumentException
- public static <V extends Vertex,E extends Edge> void findShortestPaths(Graph<V,E> graph, Matrix<java.lang.Float> distMatrix, Matrix<V> predMatrix, boolean considerAllVertices) throws java.lang.IllegalArgumentException
graph
- the graphdistMatrix
- the distance matrix (output parameter) that has to be an n-by-n matrix where n is the order of the graphpredMatrix
- the predecessor matrix (output parameter) that has to be an n-by-n matrix where n is the order of the graphconsiderAllVertices
- true
if all vertices should be considered (to check against negative cycles) otherwise false
(default)java.lang.IllegalArgumentException
- public static <V extends Vertex,E extends Edge> SimpleGraph<Vertex,Edge> breadthFirstSearch(Graph<V,E> graph)
graph
- the graphjava.lang.IllegalArgumentException
- public static <V extends Vertex,E extends Edge> SimpleGraph<Vertex,Edge> breadthFirstSearch(Graph<V,E> graph, V start) throws java.lang.IllegalArgumentException
graph
- the graphstart
- the vertex to start withjava.lang.IllegalArgumentException
- public static <V extends Vertex,E extends Edge> SimpleGraph<Vertex,Edge> depthFirstSearch(Graph<V,E> graph)
graph
- the graphjava.lang.IllegalArgumentException
- public static <V extends Vertex,E extends Edge> SimpleGraph<Vertex,Edge> depthFirstSearch(Graph<V,E> graph, V start) throws java.lang.IllegalArgumentException
graph
- the graphstart
- the vertex to start withjava.lang.IllegalArgumentException
- public static <V extends Vertex,E extends Edge> boolean isAugmentingPath(Path<V> path, Matching<E> matching) throws java.lang.IllegalArgumentException
G = (V, E)
, a path (v_1,...v_k)
on a matching M
is an augmenting path, if:
v_1
) and the last vertex (v_k
) of the path are not matched meaning they are not endpoints of an edge of M
path
- the pathmatching
- the matchingtrue
if it is an augmenting path otherwise false
java.lang.IllegalArgumentException
- public static <V extends Vertex,E extends Edge> Path<V> findAugmentingPath(Graph<V,E> graph, V start, Matching<E> m) throws java.lang.IllegalArgumentException
graph
- the graphstart
- the start vertexm
- the matching (ensure that this matching is associated with the given graph)null
if there is no augmenting path starting with the specified vertex in the graph based on the given matchingjava.lang.IllegalArgumentException
- public static <V extends Vertex,E extends Edge> boolean isEulerian(Graph<V,E> graph)
G = (V,E)
, G
is eulerian
if and only if the degree of each vertex is even.G = (V,E)
, G
is eulerian if
and only if the outdegree is euqal to the indegree of each vertex.graph
- the graphtrue
if the graph is an Eulerian graph otherwise false
public static <V extends Vertex> Walk<V> toWalk(java.lang.String walk, Graph<V,?> graph)
Walk
.walk
- the walk with the captions of the verticesgraph
- the related graphnull
if the input walk contains invalid vertex captionspublic static <V extends Vertex> Path<V> toPath(java.lang.String path, Graph<V,?> graph)
Path
.path
- the path with the captions of the verticesgraph
- the related graphnull
if the input path contains invalid vertex captionspublic static <V extends Vertex> Trail<V> toTrail(java.lang.String trail, Graph<V,? extends Edge> graph, Trail<Vertex> base)
Trail
.trail
- the trail with the captions of the verticesgraph
- the related graphbase
- the base trail its edges may not contained in the returned trail or null
if there is no base trailnull
if the input trail contains invalid vertex captions