SuanShu, a Java numerical and statistical library

com.numericalmethod.suanshu.graph

Class GraphUtils

• public final class GraphUtils
extends Object
These are the utility functions to manipulate Graph.
• Nested Class Summary

Nested Classes
Modifier and Type Class and Description
static interface  GraphUtils.EdgeFactory<V,N,E extends Edge<N>,X>
This interface specifies how an edge is created for two nodes.
static interface  GraphUtils.GraphFactory<G>
The factory to construct instances of the graph type.
• Method Summary

All Methods
Modifier and Type Method and Description
static <V,E extends HyperEdge<V>>void addEdges(Graph<V,E> g, E... edges)
Add a set of edges to a graph.
static <V> void addVertices(Graph<V,?> G, V... V)
Add a set of vertices to a graph.
static <V> boolean containsEdge(Graph<V,?> g, HyperEdge<V> e)
Returns true if this graph's edge collection contains e
static <V> boolean containsVertex(Graph<V,?> g, V v)
Returns true if this graph's vertex collection contains v
static <V> UnDiGraph<V,UndirectedEdge<V>> di2UnDiGraph(DiGraph<V,? extends Arc<V>> diG)
Converts a directed graph into an undirected graph by removing the direction of all arcs.
static <V> boolean equals(Graph<V,?> g1, Graph<V,?> g2)
Check if two graphs are equal in terms of node values and edges.
static <V> Set<V> getChildren(DiGraph<V,? extends Arc<V>> g, V v)
Get the set of vertices that have an incoming arc coming from a vertex.
static <V,E extends UndirectedEdge<V>>List<UnDiGraph<V,E>> getDisjointGraphs(UnDiGraph<V,E> g)
static <V,E extends UndirectedEdge<V>,G extends UnDiGraph<V,E>>List<G> getDisjointGraphs(UnDiGraph<V,E> g, GraphUtils.GraphFactory<G> gCtor)
Separate an undirected graph into disjointed connected graphs.
static <V> Set<HyperEdge<V>> getEdges(Graph<V,?> g, V v1, V v2)
Gets the set of edges that connect the two vertices.
static <V> Set<V> getNeighbors(Graph<V,?> g, V v)
Gets the set of vertices which are connected to v via any edges in this graph.
static <V> Set<V> getParents(DiGraph<V,? extends Arc<V>> g, V v)
Get the set of vertices that have an outgoing arc pointing to a vertex.
static <V> boolean isAcyclic(UnDiGraph<V,UndirectedEdge<V>> g)
Check if an undirected graph is acyclic.
static <V> boolean isConnected(UnDiGraph<V,? extends UndirectedEdge<V>> g)
Check whether an undirected graph is connected.
static <V> boolean isStronglyConnected(DiGraph<V,? extends Arc<V>> g)
Check whether a directed graph is strongly connected.
static <V> int numberOfChildren(DiGraph<V,? extends Arc<V>> g, V v)
Gets the number of children.
static <V> int numberOfEdges(Graph<V,?> g)
Gets the number of edges in this graph.
static <V> int numberOfParents(DiGraph<V,? extends Arc<V>> g, V v)
Gets the number of parents.
static <V> int numberOfVertices(Graph<V,?> g)
Gets the number of vertices in this graph.
static <V,E extends HyperEdge<V>>Graph<V,E> removeIsolatedVertices(Graph<V,E> g)
Removes those nodes that have no edges from a graph.
static <V> DAGraph<V,Arc<V>> unDi2DAGraph(UnDiGraph<V,? extends UndirectedEdge<V>> g, V root)
Converts an undirected graph into a directed acyclic graph, arcs are created from the edges by parent-child relations as determined by breadth-first-search.
static <V,N,E extends Arc<N>>DAGraph<N,E> unDi2DAGraph(UnDiGraph<V,? extends UndirectedEdge<V>> g, V root, GraphUtils.EdgeFactory<V,N,E,UndirectedEdge<V>> edgeFactory)
Converts an undirected graph into a directed acyclic graph, arcs are created from the edges by parent-child relations as determined by breadth-first-search.
• Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
• Method Detail

• containsVertex

public static <V> boolean containsVertex(Graph<V,?> g,
V v)
Returns true if this graph's vertex collection contains v
Type Parameters:
V - vertex type
Parameters:
g - a graph
v - the vertex whose presence is being queried
Returns:
true if this graph contains the vertex
• containsEdge

public static <V> boolean containsEdge(Graph<V,?> g,
HyperEdge<V> e)
Returns true if this graph's edge collection contains e
Type Parameters:
V - vertex type
Parameters:
g - a graph
e - the edge whose presence is being queried
Returns:
true if this graph contains the edge
• numberOfEdges

public static <V> int numberOfEdges(Graph<V,?> g)
Gets the number of edges in this graph.
Type Parameters:
V - vertex type
Parameters:
g - a graph
Returns:
the number of edges in this graph
• numberOfVertices

public static <V> int numberOfVertices(Graph<V,?> g)
Gets the number of vertices in this graph.
Type Parameters:
V - vertex type
Parameters:
g - a graph
Returns:
the number of vertices in this graph
• getNeighbors

public static <V> Set<V> getNeighbors(Graph<V,?> g,
V v)
Gets the set of vertices which are connected to v via any edges in this graph.
Type Parameters:
V - vertex type
Parameters:
g - a graph
v - a vertex
Returns:
the neighbors of the vertex
• getEdges

public static <V> Set<HyperEdge<V>> getEdges(Graph<V,?> g,
V v1,
V v2)
Gets the set of edges that connect the two vertices. Direction is not taken into account.
Type Parameters:
V - vertex type
Parameters:
g - a graph
v1 - a vertex
v2 - a vertex (could be the same as v1)
Returns:
the set of edges that connect v1 and v2
• removeIsolatedVertices

public static <V,E extends HyperEdge<V>> Graph<V,E> removeIsolatedVertices(Graph<V,E> g)
Removes those nodes that have no edges from a graph.
Type Parameters:
V - vertex type
E - edge type
Parameters:
g - a graph
Returns:
a purged graph

public static <V,E extends HyperEdge<V>> void addEdges(Graph<V,E> g,
E... edges)
Add a set of edges to a graph.
Type Parameters:
V - vertex type
E - edge type
Parameters:
g - a graph
edges - edges

public static <V> void addVertices(Graph<V,?> G,
V... V)
Add a set of vertices to a graph.
Type Parameters:
V - vertex type
Parameters:
G - a graph
V - vertices
• equals

public static <V> boolean equals(Graph<V,?> g1,
Graph<V,?> g2)
Check if two graphs are equal in terms of node values and edges.
Type Parameters:
V - vertex type
Parameters:
g1 - a graph
g2 - a graph
Returns:
true if the two graphs are equal
• isAcyclic

public static <V> boolean isAcyclic(UnDiGraph<V,UndirectedEdge<V>> g)
Check if an undirected graph is acyclic.
Type Parameters:
V - vertex type
Parameters:
g - an undirected graph
Returns:
true if the undirected graph is acyclic
• isConnected

public static <V> boolean isConnected(UnDiGraph<V,? extends UndirectedEdge<V>> g)
Check whether an undirected graph is connected.
Type Parameters:
V - vertex type
Parameters:
g - a graph
Returns:
true if an undirected graph is connected
"http://www.brpreiss.com/books/opus4/html/page561.html"
• di2UnDiGraph

public static <V> UnDiGraph<V,UndirectedEdge<V>> di2UnDiGraph(DiGraph<V,? extends Arc<V>> diG)
Converts a directed graph into an undirected graph by removing the direction of all arcs.
Type Parameters:
V - vertex type
Parameters:
diG - a directed graph
Returns:
an undirected graph
• getDisjointGraphs

public static <V,E extends UndirectedEdge<V>,G extends UnDiGraph<V,E>> List<G> getDisjointGraphs(UnDiGraph<V,E> g,
GraphUtils.GraphFactory<G> gCtor)
Separate an undirected graph into disjointed connected graphs.
Type Parameters:
V - vertex type
E - edge type
G - graph type
Parameters:
g - an undirected graph
gCtor - a factory to construct instances of the graph type
Returns:
a collection of disjointed connected graphs
• getDisjointGraphs

public static <V,E extends UndirectedEdge<V>> List<UnDiGraph<V,E>> getDisjointGraphs(UnDiGraph<V,E> g)
• getParents

public static <V> Set<V> getParents(DiGraph<V,? extends Arc<V>> g,
V v)
Get the set of vertices that have an outgoing arc pointing to a vertex.
Type Parameters:
V - vertex type
Parameters:
g - a directed graph
v - a vertex
Returns:
the set of parents/predecessors vertices
• numberOfParents

public static <V> int numberOfParents(DiGraph<V,? extends Arc<V>> g,
V v)
Gets the number of parents.
Type Parameters:
V - vertex type
Parameters:
g - a graph
v - a vertex
Returns:
the number of parents
• getChildren

public static <V> Set<V> getChildren(DiGraph<V,? extends Arc<V>> g,
V v)
Get the set of vertices that have an incoming arc coming from a vertex.
Type Parameters:
V - vertex type
Parameters:
g - a graph
v - a vertex
Returns:
the set of children/successor vertices
• numberOfChildren

public static <V> int numberOfChildren(DiGraph<V,? extends Arc<V>> g,
V v)
Gets the number of children.
Type Parameters:
V - vertex type
Parameters:
g - a graph
v - a vertex
Returns:
the number of children
• isStronglyConnected

public static <V> boolean isStronglyConnected(DiGraph<V,? extends Arc<V>> g)
Check whether a directed graph is strongly connected.
Type Parameters:
V - vertex type
Parameters:
g - a directed graph
Returns:
true if a directed graph is strongly connected
"http://www.brpreiss.com/books/opus4/html/page562.html"
• unDi2DAGraph

public static <V,N,E extends Arc<N>> DAGraph<N,E> unDi2DAGraph(UnDiGraph<V,? extends UndirectedEdge<V>> g,
V root,
GraphUtils.EdgeFactory<V,N,E,UndirectedEdge<V>> edgeFactory)
Converts an undirected graph into a directed acyclic graph, arcs are created from the edges by parent-child relations as determined by breadth-first-search. Cyclic, same-depth edges are removed from the graph.
Type Parameters:
V - vertex type in the original undirected graph
N - node type in the new directed acyclic graph
E - edge type in the new directed acyclic graph
Parameters:
g - an (connected) undirected graph
root - a designated root
edgeFactory - the method to create an edge in the new directed acyclic graph
Returns:
a directed acyclic graph
• unDi2DAGraph

public static <V> DAGraph<V,Arc<V>> unDi2DAGraph(UnDiGraph<V,? extends UndirectedEdge<V>> g,
V root)
Converts an undirected graph into a directed acyclic graph, arcs are created from the edges by parent-child relations as determined by breadth-first-search. Cyclic, same-depth edges are removed from the graph.
Type Parameters:
V - vertex type
Parameters:
g - an undirected graph
root - a designated root
Returns:
a directed acyclic graph