y.algo
Class GraphConnectivity

java.lang.Object
  y.algo.GraphConnectivity

public class GraphConnectivity
extends Object

Provides algorithms for determining certain connectivity components within a graph. Also provides convenience method for working with these components.

Constructor Summary

GraphConnectivity()

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.
static int	biconnectedComponents(Graph graph, EdgeMap compNum, NodeMap aPoint) Calculates the biconnected components of a given undirected graph.
static NodeList[]	connectedComponents(Graph graph) Returns the connected components of a given graph.
static int	connectedComponents(Graph graph, NodeMap compNum) Returns the connected components of a given graph.
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 set of nodes.
static NodeList	getSuccessors(Graph graph, NodeList startNodes, int maxDistance) Determines the direct or indirect successors of a given set of nodes.
static boolean	isBiconnected(Graph graph) Checks whether or not the given graph his 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 graph is strongly connected.
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 can be reached in the given graph when starting from a given node.
static void	reachable(Graph graph, Node start, boolean directed, boolean[] forbidden, boolean[] reached) Similar to reachable(Graph,Node,boolean,boolean[]).
static NodeList[]	stronglyConnectedComponents(Graph graph) Returns the connected components of a given graph.
static int	stronglyConnectedComponents(Graph graph, NodeMap compNum) Returns the connected components of a given graph.
static EdgeList[]	toEdgeListArray(Graph graph, EdgeMap compNum, int maxCompNum) Transforms the return values of biconnectedComponents(Graph, EdgeMap) to an array of EdgeLists, like it is returned by biconnectedComponents(Graph).
static NodeList[]	toNodeListArray(Graph graph, NodeMap compNum, int maxCompNum) Transforms the return values of connectedComponents(Graph, NodeMap) to an array of type NodeList, 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

Constructor Detail

GraphConnectivity

public GraphConnectivity()

Method Detail

connectedComponents

public static NodeList[] connectedComponents(Graph graph)

Returns the connected components of a given graph.

A graph G is called connected if there is an undirected path between each pair of nodes belonging to G. The connected components of G are connected subgraphs that G consists of.

Parameters:

graph - the input graph

Returns:

an array of NodeLists each of which contains the nodes that belong to a common connected component of the graph.

Complexity:

O(graph.N() + graph.E())

connectedComponents

public static int connectedComponents(Graph graph,
                                      NodeMap compNum)

Returns the connected components of a given graph.

A graph G is called connected if there is an undirected path between each pair of nodes belonging to G. The connected components of G are connected subgraphs that G consists of.

Parameters:

graph - the input graph

compNum - return value that will hold the zero-based number of the connected component that it belongs to. The component number of Node v is compNum.getInt().

Returns:

the number of connected components of this graph.

Complexity:

O(graph.N() + graph.E())

makeConnected

public static EdgeList makeConnected(Graph graph)

Makes a graph connected by adding additional edges to the graph. The number of edges that will be added is equal to one less the number of separate components of the original graph.

Parameters:

graph - the input graph

Returns:

an edge list containing the edges added to this graph.

Complexity:

O(graph.N() + graph.E())

toNodeListArray

public static NodeList[] toNodeListArray(Graph graph,
                                         NodeMap compNum,
                                         int maxCompNum)

Transforms the return values of connectedComponents(Graph, NodeMap) to an array of type NodeList, like it is returned by connectedComponents(Graph).

isConnected

public static boolean isConnected(Graph graph)

Checks whether or not the given graph is connected.

biconnectedComponents

public static EdgeList[] biconnectedComponents(Graph graph)

Calculates the biconnected components of a given undirected graph. The result is returned as an array of EdgeList objects each containing all edges that belong to the same biconnected component of the graph.

Note: Selfloops do not belong to any biconnected component. Therefore no selfloops are included in the returned edge lists.

Parameters:

graph - the input graph

Complexity:

O(graph.N() + graph.E())

Precondition:

GraphChecker.isConnected(graph)

biconnectedComponents

public static int biconnectedComponents(Graph graph,
                                        EdgeMap compNum)

Calculates the biconnected components of a given undirected graph. The main result is returned in the form of an EdgeMap that provides for each edge a zero-based index of the biconnected component it belongs to.

Note: Selfloops do not belong to any biconnected component. Therefore the component index for selfloops is always -1.

Parameters:

graph - the input graph

compNum - return value that provides for each edge a zero-based index of the biconnected component it belongs to or -1 for selfloops.

Returns:

the number of biconnected components found

Complexity:

O(graph.N() + graph.E())

Preconditions:

GraphChecker.isConnected(graph)

compNum defined for each edge in the graph.

biconnectedComponents

public static int biconnectedComponents(Graph graph,
                                        EdgeMap compNum,
                                        NodeMap aPoint)

Calculates the biconnected components of a given undirected graph. Additionally, this method calculates the articulation points of the input graph. Articulation points are returned in the form of a NodeMap that provides for each node a boolean value indicating whether or not it is an articulation point.

Note: Selfloops do not belong to any biconnected component. Therefore the component index for selfloops is always -1.

Parameters:

aPoint - return value that provides for each node a boolean value indicating whether or not it is an articulation point.

Precondition:

aPoint defined for each node in the graph

toEdgeListArray

public static EdgeList[] toEdgeListArray(Graph graph,
                                         EdgeMap compNum,
                                         int maxCompNum)

Transforms the return values of biconnectedComponents(Graph, EdgeMap) to an array of EdgeLists, like it is returned by biconnectedComponents(Graph).

makeBiconnected

public static EdgeList makeBiconnected(Graph graph)

Makes the given graph biconnected by inserting a minimum number of edges in the graph.

Parameters:

graph - the input graph

Returns:

an edge list containing the edges added to this graph.

Complexity:

O(graph.N() + graph.E())

Precondition:

GraphChecker.isConnected(graph)

isBiconnected

public static boolean isBiconnected(Graph graph)

Checks whether or not the given graph his biconnected.

reachable

public static void reachable(Graph graph,
                             Node start,
                             boolean directed,
                             boolean[] reached)

Determines the set of nodes that can be reached in the given graph when starting from a given node.

Parameters:

graph - the graph the search is performed on

start - the node the search is started from

directed - traverses edges only from source to target if true. Otherwise traverses edges in both directions.

reached - the return value. a boolean array that has value true at field v.index() iff node v can be reached by the dfs search.

Precondition:

reached.length = graph.N()

reachable

public static void reachable(Graph graph,
                             Node start,
                             boolean directed,
                             boolean[] forbidden,
                             boolean[] reached)

Similar to reachable(Graph,Node,boolean,boolean[]). Additionally it is possible to specify a set of forbidden edges that will not be traversed when performing the search.

Parameters:

graph - the graph DFS is performed on

start - the node DFS is started from

directed - traverses edges only from source to target if true. Otherwise traverses edges in both directions.

forbidden - marks edges that may not be traversed by DFS. An edge e is marked as forbidden if forbidden[e.index()] == true.

reached - the return value. a boolean array that has value true at field v.index() iff node v can be reached by the dfs search.

Precondition:

forbiddenEdges.length = graph.E()

getSuccessors

public static NodeList getSuccessors(Graph graph,
                                     NodeList startNodes,
                                     int maxDistance)

Determines the direct or indirect successors of a given set of nodes. A direct successor of a node is the target node of an outgoing edge connected to a node. An indirect successor of a node is a direct successor to another successor of a node.

Parameters:

graph - the graph to act upon

startNodes - contains the node the search is started from

maxDistance - 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 or smaller than maxDistance. Setting maxDistance to 1 will only yield the direct successors of all start nodes. On the other hand, setting maxDistance to graph.N() or larger, will yield all successors of all start nodes.

Returns:

a NodeList that contains all direct and indirect successors of a node. The order of the returned nodes follows is determined by a breadth first search. No start node will be part of the resulting set.

getPredecessors

public static NodeList getPredecessors(Graph graph,
                                       NodeList startNodes,
                                       int maxDistance)

Determines the direct or indirect predecessors of a given set of nodes. A direct predecessor of a node is the source node of an ingoing edge connected to a node. An indirect predecessor of a node is a direct predecessor to another predecessor of a node.

Parameters:

graph - the graph to act upon

startNodes - contains the node the search is started from

maxDistance - 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 or smaller than maxDistance. Setting maxDistance to 1 will only yield the direct predecessors of all start nodes. On the other hand, setting maxDistance to graph.N() or larger, will yield all predecessors of all start nodes.

Returns:

a NodeList that contains all direct and indirect predecessors of a node. The order of the returned nodes follows is determined by a breadth first search. No start node will be part of the resulting set.

getNeighbors

public static NodeList getNeighbors(Graph graph,
                                    NodeList startNodes,
                                    int maxDistance)

Determines the direct or indirect neighbors of a given set of nodes. A direct neighbor of a node is directly connected by an edge to that node. An indirect neighbor of a node is directly connected to another direct or indirect neighbor of a node.

Parameters:

graph - the graph to act upon

startNodes - contains the node the search is started from

maxDistance - 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 or smaller than maxDistance. Setting maxDistance to 1 will only yield the direct neighbors of all start nodes. On the other hand, setting maxDistance to graph.N() or larger, will yield all neighbors of all start nodes.

Returns:

a NodeList that contains all direct and indirect neighbors of a node. The order of the returned nodes follows is determined by a breadth first search. No start node will be part of the resulting set.

stronglyConnectedComponents

public static NodeList[] stronglyConnectedComponents(Graph graph)

Returns the connected components of a given graph.

A graph G is called strongly connected if there is an directed path between each pair of nodes belonging to G. The strongly connected components of G are strongly connected subgraphs that G consists of.

Parameters:

graph - the input graph

Returns:

an array of NodeLists each of which contains the nodes that belong to a common connected component of the graph.

Complexity:

O(graph.N() + graph.E())

stronglyConnectedComponents

public static int stronglyConnectedComponents(Graph graph,
                                              NodeMap compNum)

Returns the connected components of a given graph.

A graph G is called strongly connected if there is an directed path between each pair of nodes belonging to G. The strongly connected components of G are strongly connected subgraphs that G consists of.

Parameters:

graph - the input graph

compNum - return value that will hold the zero-based number of the strongly connected component that it belongs to. The component number of Node v is compNum.getInt().

Returns:

the number of strongly connected components of this graph.

Complexity:

O(graph.N() + graph.E())

isStronglyConnected

public static boolean isStronglyConnected(Graph graph)

Checks whether or not the given graph is strongly connected.