Package dev.nm.graph
Class GraphUtils
- java.lang.Object
-
- dev.nm.graph.GraphUtils
-
public final class GraphUtils extends Object
These are the utility functions to manipulateGraph
.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class 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 Static Methods Concrete Methods Modifier and Type Method Description static <V,E extends HyperEdge<V>>
voidaddEdges(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 containse
static <V> boolean
containsVertex(Graph<V,?> g, V v)
Returns true if this graph's vertex collection containsv
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 tov
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.
-
-
-
Method Detail
-
containsVertex
public static <V> boolean containsVertex(Graph<V,?> g, V v)
Returns true if this graph's vertex collection containsv
- Type Parameters:
V
- vertex type- Parameters:
g
- a graphv
- 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 containse
- Type Parameters:
V
- vertex type- Parameters:
g
- a graphe
- 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 tov
via any edges in this graph.- Type Parameters:
V
- vertex type- Parameters:
g
- a graphv
- 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 graphv1
- a vertexv2
- a vertex (could be the same asv1
)- Returns:
- the set of edges that connect
v1
andv2
-
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 typeE
- edge type- Parameters:
g
- a graph- Returns:
- a purged graph
-
addEdges
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 typeE
- edge type- Parameters:
g
- a graphedges
- edges
-
addVertices
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 graphV
- 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 graphg2
- 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- See Also:
- "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 typeE
- edge typeG
- graph type- Parameters:
g
- an undirected graphgCtor
- 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 graphv
- 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 graphv
- 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 graphv
- 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 graphv
- 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- See Also:
- "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 graphN
- node type in the new directed acyclic graphE
- edge type in the new directed acyclic graph- Parameters:
g
- an (connected) undirected graphroot
- a designated rootedgeFactory
- 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 graphroot
- a designated root- Returns:
- a directed acyclic graph
-
-