com.yworks.yfiles.algorithms

Class GraphConnectivity

java.lang.Object

com.yworks.yfiles.algorithms.GraphConnectivity

public final class GraphConnectivity
extends Object

This class provides algorithms for determining certain connectivity components within a graph.

It also provides convenience methods for working with these components.

Definitions

• Connected graph: A graph is called connected if there exists an undirected path of edges between every pair of nodes.
• Strongly connected graph: A graph is called strongly connected if there exists a directed path between each pair of nodes.
• Biconnected graph: A graph is called biconnected if it has no cut vertex or articulation point (i.e., a node whose removal disconnects the remaining graph).

Method Summary

Modifier and Type	Method and Description
static EdgeList[]	biconnectedComponents(Graph graph) Calculates the biconnected components of a given undirected graph.
static int	biconnectedComponents(Graph graph, IEdgeMap compNum) Calculates the biconnected components and the articulation points of a given undirected graph and returns the number of biconnected components.
static int	biconnectedComponents(Graph graph, IEdgeMap compNum, INodeMap 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, INodeMap 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 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 when a set of edges that cannot be traversed is specified.
static void	reachable(Graph graph, Node start, boolean directed, boolean[] reached, boolean[] forbidden) 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, INodeMap compNum) Calculates the strongly connected components of a given graph and returns their number.
static EdgeList[]	toEdgeListArray(Graph graph, IEdgeMap compNum, int maxCompNum) Transforms the return values of biconnectedComponents(Graph, IEdgeMap, INodeMap) to an array of EdgeLists, like it is returned by biconnectedComponents(Graph).
static NodeList[]	toNodeListArray(Graph graph, INodeMap compNum, int maxCompNum) Transforms the return values of method connectedComponents(Graph, INodeMap) to an array of NodeLists, 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

biconnectedComponents

public static final EdgeList[] biconnectedComponents(Graph graph)

Calculates the biconnected components of a given undirected graph.

The result is returned as an array of EdgeLists each containing all edges that belong to the same biconnected component.

Self-loops do not belong to any biconnected component. Therefore, no self-loops are included in the returned EdgeLists.

Precondition:

The graph must be connected.

Complexity:

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

Parameters:

graph - the input graph

Returns:

an array of EdgeLists each containing all edges that belong to the same biconnected component

See Also:

biconnectedComponents(Graph, IEdgeMap, INodeMap)

biconnectedComponents

public static final int biconnectedComponents(Graph graph,
                                              IEdgeMap compNum)

Calculates the biconnected components and the articulation points of a given undirected graph and returns the number of biconnected components.

Articulation points are returned in the form of a INodeMap that returns for each node a boolean value indicating whether or not it is an articulation point.

Self-loops do not belong to any biconnected component. Therefore, the component index for self-loops is always -1.

Preconditions:

The graph must be connected.

compNum should not be null.

aPoint should not be null.

Complexity:

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

Parameters:

graph - the input graph

compNum - the IEdgeMap that will be filled during the execution and returns the zero-based index of the biconnected component to which each edge belongs or -1 for self-loops

Returns:

the number of biconnected components

See Also:

biconnectedComponents(Graph), biconnectedComponents(Graph, IEdgeMap, INodeMap)

biconnectedComponents

public static final int biconnectedComponents(Graph graph,
                                              IEdgeMap compNum,
                                              INodeMap aPoint)

Calculates the biconnected components and the articulation points of a given undirected graph and returns the number of biconnected components.

Articulation points are returned in the form of a INodeMap that returns for each node a boolean value indicating whether or not it is an articulation point.

Self-loops do not belong to any biconnected component. Therefore, the component index for self-loops is always -1.

Preconditions:

The graph must be connected.

compNum should not be null.

aPoint should not be null.

Complexity:

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

Parameters:

graph - the input graph

compNum - the IEdgeMap that will be filled during the execution and returns the zero-based index of the biconnected component to which each edge belongs or -1 for self-loops

aPoint - the INodeMap that will be filled during the execution and returns a boolean value indicating whether or not a given node is an articulation point

Returns:

the number of biconnected components

See Also:

biconnectedComponents(Graph), biconnectedComponents(Graph, IEdgeMap, INodeMap)

connectedComponents

public static final NodeList[] connectedComponents(Graph graph)

Calculates the connected components of a given 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.

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 the same connected component

connectedComponents

public static final int connectedComponents(Graph graph,
                                            INodeMap compNum)

Calculates the connected components of a given graph and returns their number.

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.

Complexity:

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

Parameters:

compNum - the INodeMap that will be filled during the execution and returns the zero-based index of the connected component to which each node belongs

Returns:

the number of connected components of the given graph

getNeighbors

public static final 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.

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.

Returns:

a NodeList that contains all direct and indirect neighbors of a node

getPredecessors

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

Determines the direct or indirect predecessors of a given list of nodes.

• A direct predecessor of a node is the source node of an incoming edge connected to a node.
• An indirect predecessor of a node is a direct predecessor to another predecessor of a node.

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.

Parameters:

graph - the given graph

startNodes - a NodeList containing the nodes from which the search starts

maxDistance - an integer value that limits the distance between a start node and a returned node

Returns:

a NodeList that contains all direct and indirect predecessors of a node

getSuccessors

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

Determines the direct or indirect successors of a given list 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.

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.

Parameters:

graph - the given graph

startNodes - a NodeList containing the nodes from which the search starts

maxDistance - an integer value that limits the distance between a start node and a returned node

Returns:

a NodeList that contains all direct and indirect successors of a node

isBiconnected

public static final boolean isBiconnected(Graph graph)

Checks whether or not the given undirected graph is biconnected.

A graph is called biconnected if it has no cut vertex or articulation point, i.e., no node whose removal disconnects the graph.

Parameters:

graph - the given undirected graph

Returns:

true if the graph is biconnected, false otherwise

isConnected

public static final boolean isConnected(Graph graph)

Checks whether or not the given graph is connected.

A graph is called connected if there exists an undirected path of edges between every pair of nodes.

Parameters:

graph - the given graph

Returns:

true if the graph is connected, false otherwise

isStronglyConnected

public static final boolean isStronglyConnected(Graph graph)

Checks whether or not the given directed graph is strongly connected.

A graph is called strongly connected if there exists a directed path between each pair of nodes.

Parameters:

graph - the given directed graph

Returns:

true if the graph is strongly connected, false, otherwise

makeBiconnected

public static final EdgeList makeBiconnected(Graph graph)

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

The given graph is considered to be undirected.

Precondition:

The graph must be connected.

Complexity:

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

Parameters:

graph - the input graph

Returns:

an EdgeList containing the edges added to the graph

makeConnected

public static final EdgeList makeConnected(Graph graph)

Makes a graph connected by adding additional edges to the graph.

The number of edges that will be added equals the number of separate components of the original graph minus 1.

Complexity:

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

Parameters:

graph - the input graph

Returns:

an EdgeList containing the edges added to the graph

reachable

public static final void reachable(Graph graph,
                                   Node start,
                                   boolean directed,
                                   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.

The result is based on a depth first search.

Precondition:

forbiddenEdges.length = graph.E()

Parameters:

graph - the given graph

start - the node from which the search starts

directed - true if the edges should be traversed from source to target, false if edges can be traversed in both directions

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

reachable

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

Determines the set of nodes that are reachable from a given node when a set of edges that cannot be traversed is specified.

The result is based on a depth first search.

Precondition:

forbiddenEdges.length = graph.E()

Parameters:

graph - the given graph

start - the node from which the search starts

directed - true if the edges should be traversed from source to target, false if edges can be traversed in both directions

forbidden - 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

stronglyConnectedComponents

public static final NodeList[] stronglyConnectedComponents(Graph graph)

Calculates the strongly connected components of a given 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.

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 the same strongly connected component

See Also:

stronglyConnectedComponents(Graph, INodeMap)

stronglyConnectedComponents

public static final int stronglyConnectedComponents(Graph graph,
                                                    INodeMap compNum)

Calculates the strongly connected components of a given graph and returns their number.

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.

Complexity:

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

Parameters:

graph - the input graph

compNum - the INodeMap that will be filled during the execution and returns the zero-based index of the connected component to which each node belongs

Returns:

the number of strongly connected components of the given graph

See Also:

stronglyConnectedComponents(Graph)

toEdgeListArray

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

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

Parameters:

graph - the input graph

compNum - the IEdgeMap that will be filled during the execution and returns the zero-based index of the connected component to which each edge belongs

maxCompNum - the maximum number of biconnected components

Returns:

an array of EdgeLists each containing all edges that belong to the same biconnected component

toNodeListArray

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

Transforms the return values of method connectedComponents(Graph, INodeMap) to an array of NodeLists, like it is returned by connectedComponents(Graph).

Parameters:

graph - the input graph

compNum - the INodeMap that will be filled during the execution and returns the zero-based index of the connected component to which each node belongs

maxCompNum - the maximum number of connected components

Returns:

an array of NodeLists each of which contains the nodes that belong to the same connected component