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 conveniance 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) Like GraphConnectivity.biconnectedComponents(Graph, EdgeMap).
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 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 his 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 GraphConnectivity.reachable(Graph,Node,boolean,boolean[]).
static EdgeList[]	toEdgeListArray(Graph graph, EdgeMap compNum, int maxCompNum) Transforms the return values of GraphConnectivity.biconnectedComponents(Graph, EdgeMap) to an array of type EdgeList, like it is returned by GraphConnectivity.biconnectedComponents(Graph).
static NodeList[]	toNodeListArray(Graph graph, NodeMap compNum, int maxCompNum) Transforms the return values of GraphConnectivity.connectedComponents(Graph, NodeMap) to an array of type NodeList, like it is returned by GraphConnectivity.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.

Complexity:

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

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.

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.

Complexity:

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

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.

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 sepearate components of the original graph.

Complexity:

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

Parameters:

graph - the input graph

Returns:

an edge list containing the edges added to this graph.

toNodeListArray

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

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

isConnected

public static boolean isConnected(Graph graph)

Checks whether or not the given graph his 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.

Precondition:

GraphChecker.isConnected(graph)

Complexity:

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

Parameters:

graph - the input 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.

Preconditions:

GraphChecker.isConnected(graph)

compNum defined for each edge in the graph.

Complexity:

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

Parameters:

graph - the input graph

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

Returns:

the number of biconnected components found

biconnectedComponents

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

Like GraphConnectivity.biconnectedComponents(Graph, EdgeMap). 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.

Precondition:

aPoint defined for each node in the graph

Parameters:

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

toEdgeListArray

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

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

makeBiconnected

public static EdgeList makeBiconnected(Graph graph)

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

Precondition:

GraphChecker.isConnected(graph)

Complexity:

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

Parameters:

graph - the input graph

Returns:

an edge list containing the edges added to this 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.

Precondition:

reached.length = graph.N()

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.

reachable

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

Similar to GraphConnectivity.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.

Precondition:

forbiddenEdges.length = graph.E()

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.