
Search this API  
PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object y.algo.GraphConnectivity
public class GraphConnectivity
This class provides algorithms for determining certain connectivity components within a graph.
It also provides convenience methods for working with these components.
kcores
of a graph are the maximal connected subgraphs in which all nodes have
degree greater or equal to k
.
Method Summary  

static EdgeList[] 
biconnectedComponents(Graph graph)
Calculates the biconnected components of a given undirected graph. 
static int 
biconnectedComponents(Graph graph,
EdgeMap compNum)
Calculates the biconnected components of a given undirected graph and returns their number. 
static int 
biconnectedComponents(Graph graph,
EdgeMap compNum,
NodeMap aPoint)
Calculates the biconnected components and the articulation points of a given undirected graph and returns the number of biconnected components. 
static NodeList[] 
connectedComponents(Graph graph)
Calculates the connected components of a given graph. 
static int 
connectedComponents(Graph graph,
NodeMap compNum)
Calculates the connected components of a given graph and returns their number. 
static NodeList 
getNeighbors(Graph graph,
NodeList startNodes,
int maxDistance)
Determines the direct or indirect neighbors of a given set of nodes. 
static NodeList 
getPredecessors(Graph graph,
NodeList startNodes,
int maxDistance)
Determines the direct or indirect predecessors of a given list of nodes. 
static NodeList 
getSuccessors(Graph graph,
NodeList startNodes,
int maxDistance)
Determines the direct or indirect successors of a given list of nodes. 
static boolean 
isBiconnected(Graph graph)
Checks whether or not the given undirected graph is biconnected. 
static boolean 
isConnected(Graph graph)
Checks whether or not the given graph is connected. 
static boolean 
isStronglyConnected(Graph graph)
Checks whether or not the given directed graph is strongly connected. 
static NodeList 
kCore(Graph graph,
int k)
Calculates the kcore for a given undirected input graph and k value. 
static int 
kCore(Graph graph,
NodeMap kValue)
Calculates the kcores of an undirected input graph. 
static EdgeList 
makeBiconnected(Graph graph)
Makes the given graph biconnected by inserting a minimum number of edges in the graph. 
static EdgeList 
makeConnected(Graph graph)
Makes a graph connected by adding additional edges to the graph. 
static void 
reachable(Graph graph,
Node start,
boolean directed,
boolean[] reached)
Determines the set of nodes that are reachable from a given node. 
static void 
reachable(Graph graph,
Node start,
boolean directed,
boolean[] forbidden,
boolean[] reached)
Determines the set of nodes that are reachable from a given node when a set of edges that cannot be traversed is specified. 
static NodeList[] 
stronglyConnectedComponents(Graph graph)
Calculates the strongly connected components of a given graph. 
static int 
stronglyConnectedComponents(Graph graph,
NodeMap compNum)
Calculates the strongly connected components of a given graph and returns their number. 
static EdgeList[] 
toEdgeListArray(Graph graph,
EdgeMap compNum,
int maxCompNum)
Transforms the return values of biconnectedComponents(Graph, EdgeMap) to
an array of EdgeList s, like it is returned by
biconnectedComponents(Graph) . 
static NodeList[] 
toNodeListArray(Graph graph,
NodeMap compNum,
int maxCompNum)
Transforms the return values of method connectedComponents(Graph, NodeMap) to
an array of NodeList s, like it is returned by connectedComponents(Graph) . 
Methods inherited from class java.lang.Object 

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

public static NodeList[] connectedComponents(Graph graph)
A graph G
is called connected if there exists an undirected path of edges between every pair
of nodes.
The connected components of a graph are the maximal connected subgraphs of which the graph consists.
O(graph.N() + graph.E())
graph
 the input graph
NodeList
s each of which contains the nodes that belong to the same connected
componentpublic static int connectedComponents(Graph graph, NodeMap compNum)
A graph G
is called connected if there exists an undirected path of edges between every pair
of nodes.
The connected components of a graph are the maximal connected subgraphs of which the graph consists.
O(graph.N() + graph.E())
compNum
 the NodeMap
that will be filled during the execution and returns the zerobased index of
the connected component to which each node belongs
public static EdgeList makeConnected(Graph graph)
The number of edges that will be added equals the number of
separate components of the original graph minus 1
.
O(graph.N() + graph.E())
graph
 the input graph
EdgeList
containing the edges added to the graphpublic static NodeList[] toNodeListArray(Graph graph, NodeMap compNum, int maxCompNum)
connectedComponents(Graph, NodeMap)
to
an array of NodeList
s, like it is returned by connectedComponents(Graph)
.
graph
 the input graphcompNum
 the NodeMap
that will be filled during the execution and returns the zerobased index of
the connected component to which each node belongsmaxCompNum
 the maximum number of connected components
NodeList
s each of which contains the nodes that belong to the same connected
componentpublic static boolean isConnected(Graph graph)
A graph is called connected if there exists an undirected path of edges between every pair of nodes.
public static EdgeList[] biconnectedComponents(Graph graph)
The result is returned as an array of EdgeList
s each containing all
edges that belong to the same biconnected component.
EdgeList
s.connected
.O(graph.N() + graph.E())
graph
 the input graph
EdgeList
s each containing all edges that belong to the same biconnected componentbiconnectedComponents(Graph, EdgeMap)
,
biconnectedComponents(Graph, EdgeMap, NodeMap)
public static int biconnectedComponents(Graph graph, EdgeMap compNum)
The main result is returned in the form of an EdgeMap
that provides for each edge the zerobased index of the
biconnected component to which it belongs.
1
.connected
.compNum
must not be null
.O(graph.N() + graph.E())
graph
 the input graphcompNum
 the EdgeMap
that will be filled during the execution and returns the zerobased index of
the biconnected component to which each edge belongs or 1
for selfloops
biconnectedComponents(Graph)
,
biconnectedComponents(Graph, EdgeMap, NodeMap)
public static int biconnectedComponents(Graph graph, EdgeMap compNum, NodeMap aPoint)
Articulation points are returned in the form of a NodeMap
that returns for each node a boolean value
indicating whether or not it is an articulation point.
1
.connected
.compNum
should not be null
.aPoint
should not be null
.O(graph.N() + graph.E())
graph
 the input graphcompNum
 the EdgeMap
that will be filled during the execution and returns the zerobased index of
the biconnected component to which each edge belongs or 1
for selfloopsaPoint
 the NodeMap
that will be filled during the execution and returns a boolean value indicating
whether or not a given node is an articulation point
biconnectedComponents(Graph)
,
biconnectedComponents(Graph, EdgeMap)
public static EdgeList[] toEdgeListArray(Graph graph, EdgeMap compNum, int maxCompNum)
biconnectedComponents(Graph, EdgeMap)
to
an array of EdgeList
s, like it is returned by
biconnectedComponents(Graph)
.
graph
 the input graphcompNum
 the EdgeMap
that will be filled during the execution and returns the zerobased index of
the connected component to which each edge belongsmaxCompNum
 the maximum number of biconnected components
EdgeList
s each containing all edges that belong to the same biconnected componentpublic static EdgeList makeBiconnected(Graph graph)
The given graph is considered to be undirected.
connected
.O(graph.N() + graph.E())
graph
 the input graph
EdgeList
containing the edges added to the graphpublic static boolean isBiconnected(Graph graph)
A graph is called biconnected if it has no cut vertex or articulation point, i.e., no node whose removal disconnects the graph.
public static void reachable(Graph graph, Node start, boolean directed, boolean[] reached)
The result is based on a depth first search.
reached.length = graph.N()
graph
 the given graphstart
 the node from which the search startsdirected
 true
if the edges should be traversed from source to target, false
if
edges can be traversed in both directionsreached
 an array that will be filled during the execution and returns for each Node
a Boolean
value based on whether the node can be reached during the DFS; if a node v
is
reachable, then reached[v.index()] = true
public static void reachable(Graph graph, Node start, boolean directed, boolean[] forbidden, boolean[] reached)
The result is based on a depth first search.
forbiddenEdges.length = graph.E()
graph
 the given graphstart
 the node from which the search startsdirected
 true
if the edges should be traversed from source to target, false
if
edges can be traversed in both directionsforbidden
 an array that holds for each Edge
a Boolean
value indicating whether or not an
edge can be traversed; an edge e
is marked as forbidden if
forbidden[e.index()] == true
reached
 an array that will be filled during the execution and returns for each Node
a Boolean
value based on whether the node can be reached during the DFS; if a node v
is
reachable, then reached[v.index()] = true
public static NodeList getSuccessors(Graph graph, NodeList startNodes, int maxDistance)
The order of the returned nodes is determined by a breadth first search. No start node will be part of the resulting set.
To obtain the result, an integer value should be given as input that limits the distance between a start node and a returned node. For all returned nodes there must be a path to a start node that has a length equal to or smaller than this distance.
Setting the maximum distance to 1
will only yield the direct successors of all start nodes.
On the other hand, setting the maximum distance to graph.N()
or larger will yield all successors
of all start nodes.
graph
 the given graphstartNodes
 a NodeList
containing the nodes from which the search startsmaxDistance
 an integer value that limits the distance between a start node and a returned node
NodeList
that contains all direct and indirect successors of a nodepublic static NodeList getPredecessors(Graph graph, NodeList startNodes, int maxDistance)
The order of the returned nodes is determined by a breadth first search. No start node will be part of the resulting set.
To obtain the result, an integer value should be given as input that limits the distance between a start node and a returned node. For all returned nodes there must be a path to a start node that has a length equal to or smaller than this distance.
Setting the maximum distance to 1
will only yield the direct predecessors of all start nodes.
On the other hand, setting the maximum distance to graph.N()
or larger will yield all predecessors
of all start nodes.
graph
 the given graphstartNodes
 a NodeList
containing the nodes from which the search startsmaxDistance
 an integer value that limits the distance between a start node and a returned node
NodeList
that contains all direct and indirect predecessors of a nodepublic static NodeList getNeighbors(Graph graph, NodeList startNodes, int maxDistance)
The order of the returned nodes is determined by a breadth first search. No start node will be part of the resulting set.
To obtain the result, an integer value should be given as input that limits the distance between a start node and a returned node. For all returned nodes there must be a path to a start node that has a length equal to or smaller than this distance.
Setting the maximum distance to 1
will only yield the direct neighbors of all start nodes.
On the other hand, setting the maximum distance to graph.N()
or larger will yield all neighbors
of all start nodes.
NodeList
that contains all direct and indirect neighbors of a nodepublic static NodeList[] stronglyConnectedComponents(Graph graph)
A graph is called strongly connected if there exists a directed path between each pair of nodes.
The strongly connected components of a graph are the strongly connected subgraphs of which it consists.
O(graph.N() + graph.E())
graph
 the input graph
NodeList
s each of which contains the nodes that belong to the same strongly connected
componentstronglyConnectedComponents(Graph, NodeMap)
public static int stronglyConnectedComponents(Graph graph, NodeMap compNum)
A graph is called strongly connected if there exists a directed path between each pair of nodes.
The strongly connected components of a graph are the strongly connected subgraphs of which it consists.
O(graph.N() + graph.E())
graph
 the input graphcompNum
 the NodeMap
that will be filled during the execution and returns the zerobased index of
the connected component to which each node belongs
stronglyConnectedComponents(Graph)
public static boolean isStronglyConnected(Graph graph)
A graph is called strongly connected if there exists a directed path between each pair of nodes.
public static int kCore(Graph graph, NodeMap kValue)
The kcore of an undirected input graph consists of the subgraph components where each node has at least degree
k
. The algorithm has runtime complexity O((n+m)log(n))
and requires linear space.
k
, the kcore of a graph can consists of all nodes with kValue
value greater or equal to k
.graph
 the undirected input graphkValue
 stores the largest k
for which a node is contained in the kcore
k
for which the kcore of the graph is not emptypublic static NodeList kCore(Graph graph, int k)
The kcore of an undirected input graph consists of the subgraph components where each node has at least degree
k
. The algorithm has runtime complexity O((n+m)log(n))
and requires linear space.
graph
 the undirected input graphk
 the minimum degree (kcore) of a node in the resulting subgraph components

© Copyright 20002021, yWorks GmbH. All rights reserved. 

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 