public final class GraphUtils extends Object
Graph
.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.
|
Modifier and Type | Method and Description |
---|---|
static <V,E extends HyperEdge<V>> |
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>> |
getDisjointGraphs(UnDiGraph<V,E> g) |
static <V,E extends UndirectedEdge<V>,G extends UnDiGraph<V,E>> |
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>> |
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>> |
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.
|
public static <V> boolean containsVertex(Graph<V,?> g, V v)
v
V
- vertex typeg
- a graphv
- the vertex whose presence is being queriedtrue
if this graph contains the vertexpublic static <V> boolean containsEdge(Graph<V,?> g, HyperEdge<V> e)
e
V
- vertex typeg
- a graphe
- the edge whose presence is being queriedtrue
if this graph contains the edgepublic static <V> int numberOfEdges(Graph<V,?> g)
V
- vertex typeg
- a graphpublic static <V> int numberOfVertices(Graph<V,?> g)
V
- vertex typeg
- a graphpublic static <V> Set<V> getNeighbors(Graph<V,?> g, V v)
v
via any edges in this graph.V
- vertex typeg
- a graphv
- a vertexpublic static <V> Set<HyperEdge<V>> getEdges(Graph<V,?> g, V v1, V v2)
V
- vertex typeg
- a graphv1
- a vertexv2
- a vertex (could be the same as v1
)v1
and v2
public static <V,E extends HyperEdge<V>> Graph<V,E> removeIsolatedVertices(Graph<V,E> g)
V
- vertex typeE
- edge typeg
- a graphpublic static <V,E extends HyperEdge<V>> void addEdges(Graph<V,E> g, E... edges)
V
- vertex typeE
- edge typeg
- a graphedges
- edgespublic static <V> void addVertices(Graph<V,?> G, V... V)
V
- vertex typeG
- a graphV
- verticespublic static <V> boolean equals(Graph<V,?> g1, Graph<V,?> g2)
V
- vertex typeg1
- a graphg2
- a graphtrue
if the two graphs are equalpublic static <V> boolean isAcyclic(UnDiGraph<V,UndirectedEdge<V>> g)
V
- vertex typeg
- an undirected graphtrue
if the undirected graph is acyclicpublic static <V> boolean isConnected(UnDiGraph<V,? extends UndirectedEdge<V>> g)
V
- vertex typeg
- a graphtrue
if an undirected graph is connectedpublic static <V> UnDiGraph<V,UndirectedEdge<V>> di2UnDiGraph(DiGraph<V,? extends Arc<V>> diG)
V
- vertex typediG
- a directed graphpublic static <V,E extends UndirectedEdge<V>,G extends UnDiGraph<V,E>> List<G> getDisjointGraphs(UnDiGraph<V,E> g, GraphUtils.GraphFactory<G> gCtor)
V
- vertex typeE
- edge typeG
- graph typeg
- an undirected graphgCtor
- a factory to construct instances of the graph typepublic static <V,E extends UndirectedEdge<V>> List<UnDiGraph<V,E>> getDisjointGraphs(UnDiGraph<V,E> g)
public static <V> Set<V> getParents(DiGraph<V,? extends Arc<V>> g, V v)
V
- vertex typeg
- a directed graphv
- a vertexpublic static <V> int numberOfParents(DiGraph<V,? extends Arc<V>> g, V v)
V
- vertex typeg
- a graphv
- a vertexpublic static <V> Set<V> getChildren(DiGraph<V,? extends Arc<V>> g, V v)
V
- vertex typeg
- a graphv
- a vertexpublic static <V> int numberOfChildren(DiGraph<V,? extends Arc<V>> g, V v)
V
- vertex typeg
- a graphv
- a vertexpublic static <V> boolean isStronglyConnected(DiGraph<V,? extends Arc<V>> g)
V
- vertex typeg
- a directed graphtrue
if a directed graph is strongly connectedpublic 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)
V
- vertex type in the original undirected graphN
- node type in the new directed acyclic graphE
- edge type in the new directed acyclic graphg
- an (connected) undirected graphroot
- a designated rootedgeFactory
- the method to create an edge in the new directed acyclic graphpublic static <V> DAGraph<V,Arc<V>> unDi2DAGraph(UnDiGraph<V,? extends UndirectedEdge<V>> g, V root)
V
- vertex typeg
- an undirected graphroot
- a designated rootCopyright © 2010-2020 NM FinTech Ltd.. All Rights Reserved.