This class provides algorithms for determining certain connectivity components within a graph.
Remarks
Note: Methods of this class work with instances of Graph. To determine connectivity of IGraph instances use one of the following classes instead:
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).
- KCore: The
k-coresof a graph are the maximal connected subgraphs in which all nodes have degree greater or equal tok.
Type Details
- yfiles module
- algorithms
- yfiles-umd modules
- All layout modules, view-layout-bridge
- Legacy UMD name
- yfiles.algorithms.GraphConnectivity
Static Methods
Calculates the biconnected components of a given undirected graph.
Remarks
Note: This method works with instances of Graph. To determine biconnected components and articulation points in an IGraph use BiconnectedComponents instead.
The result is returned as an array of EdgeLists each containing all edges that belong to the same biconnected component.
Complexity
O(graph.N() + graph.E())
Preconditions
- The graph must be
.
Parameters
A map of options to pass to the method.
- graph - Graph
- the input graph
Returns
- ↪EdgeList[]
- an array of EdgeLists each containing all edges that belong to the same biconnected component
See Also
Calculates the biconnected components and the articulation points of a given undirected graph and returns the number of biconnected components.
Remarks
Note: This method works with instances of Graph. To determine biconnected components and articulation points in an IGraph use BiconnectedComponents instead.
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.
Complexity
O(graph.N() + graph.E())
Preconditions
- The graph must be
. compNumshould not benull.aPointshould not benull.
Parameters
A map of options to pass to the method.
- graph - Graph
- the input graph
- compNum - IEdgeMap
- 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
-1for self-loopsDomain Edge Values number the zero-based index of the biconnected component to which each edge belongs or -1for self-loops - aPoint - INodeMap
- 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
Domain YNode Values boolean trueif a node is an articulation point,falseotherwise
Returns
- ↪number
- the number of biconnected components
See Also
-1.Calculates the connected components of a given graph.
Remarks
Note: This method works with instances of Graph. To determine connected components in an IGraph use ConnectedComponents instead.
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
A map of options to pass to the method.
- graph - Graph
- the input graph
Returns
Calculates the connected components of a given graph and returns their number.
Remarks
Note: This method works with instances of Graph. To determine connected components in an IGraph use ConnectedComponents instead.
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
A map of options to pass to the method.
- graph - Graph
- compNum - INodeMap
- the INodeMap that will be filled during the execution and returns the zero-based index of the connected component to which each node belongs
Domain YNode Values number the zero-based index of the connected component to which each node belongs
Returns
- ↪number
- the number of connected components of the given graph
Determines the direct or indirect neighbors of a given set of nodes.
Remarks
Note: This method works with instances of Graph. To determine direct and indirect neighbors of nodes in an IGraph use neighbors (direct neighbors only) or Neighborhood instead.
- 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
Determines the direct or indirect predecessors of a given list of nodes.
Remarks
Note: This method works with instances of Graph. To determine direct and indirect predecessors of nodes in an IGraph use predecessors (direct predecessors only) or Neighborhood instead.
- 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
A map of options to pass to the method.
- graph - Graph
- the given graph
- startNodes - YNodeList
- a YNodeList containing the nodes from which the search starts
- maxDistance - number
- an integer value that limits the distance between a start node and a returned node
Returns
Determines the direct or indirect successors of a given list of nodes.
Remarks
Note: This method works with instances of Graph. To determine direct and indirect successors of nodes in an IGraph use successors (direct successors only) or Neighborhood instead.
- 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
A map of options to pass to the method.
- graph - Graph
- the given graph
- startNodes - YNodeList
- a YNodeList containing the nodes from which the search starts
- maxDistance - number
- an integer value that limits the distance between a start node and a returned node
Returns
Checks whether or not the given undirected graph is biconnected.
Remarks
Note: This method works with instances of Graph. To determine whether an IGraph is biconnected use isBiconnected instead.
A graph is called biconnected if it has no cut vertex or articulation point, i.e., no node whose removal disconnects the graph.
Parameters
A map of options to pass to the method.
- graph - Graph
- the given undirected graph
Returns
- ↪boolean
trueif the graph is biconnected,falseotherwise
Sample Graphs
Checks whether or not the given graph is connected.
Remarks
Note: This method works with instances of Graph. To determine whether an IGraph is connected use isConnected instead.
A graph is called connected if there exists an undirected path of edges between every pair of nodes.
Parameters
A map of options to pass to the method.
- graph - Graph
- the given graph
Returns
- ↪boolean
trueif the graph is connected,falseotherwise
Sample Graphs
Checks whether or not the given directed graph is strongly connected.
Remarks
Note: This method works with instances of Graph. To determine whether an IGraph is strongly connected use isStronglyConnected instead.
A graph is called strongly connected if there exists a directed path between each pair of nodes.
Parameters
A map of options to pass to the method.
- graph - Graph
- the given directed graph
Returns
- ↪boolean
trueif the graph is strongly connected,false, otherwise
Sample Graphs
Calculates the k-cores of an undirected input graph.
Remarks
k. The algorithm has runtime complexity O((n+m)log(n)) and requires linear space.Parameters
A map of options to pass to the method.
- graph - Graph
- the undirected input graph
- kValue - INodeMap
- stores the largest
kfor which a node is contained in the k-coreDomain YNode Values number the largest kfor which a node is contained in the k-core
Returns
- ↪number
- the largest
kfor which the k-core of the graph is not empty
k, the k-core of a graph can consists of all nodes with kValue value greater or equal to k.Calculates the k-core for a given undirected input graph and k value.
Remarks
k. The algorithm has runtime complexity O((n+m)log(n)) and requires linear space.Parameters
A map of options to pass to the method.
- graph - Graph
- the undirected input graph
- k - number
- the minimum degree (k-core) of a node in the resulting subgraph components
Returns
- ↪YNodeList
- a list that contains the nodes of the k-core (list may be empty)
Makes the given graph biconnected by inserting a minimum number of edges in the graph.
Makes a graph connected by adding additional edges to the graph.
Remarks
1.Complexity
O(graph.N() + graph.E())
Parameters
A map of options to pass to the method.
- graph - Graph
- the input graph
Returns
Determines the set of nodes that are reachable from a given node when a set of edges that cannot be traversed is specified.
Remarks
Note: This method works with instances of Graph. To determine reachability of nodes in an IGraph use Reachability instead.
The result is based on a depth first search.
Preconditions
forbiddenEdges.length = graph.E()
Parameters
A map of options to pass to the method.
- graph - Graph
- the given graph
- start - YNode
- the node from which the search starts
- directed - boolean
trueif the edges should be traversed from source to target,falseif edges can be traversed in both directions- reached - boolean[]
- an array that will be filled during the execution and returns for each YNode a boolean value based on whether the node can be reached during the DFS; if a node
vis reachable, thenreached[v.index()] = true - forbidden - boolean[]
- an array that holds for each Edge a boolean value indicating whether or not an edge can be traversed; an edge
eis marked as forbidden ifforbidden[e.index()] == true
Calculates the strongly connected components of a given graph.
Remarks
Note: This method works with instances of Graph. To determine strongly connected components in an IGraph use StronglyConnectedComponents instead.
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
A map of options to pass to the method.
- graph - Graph
- the input graph
Returns
- ↪YNodeList[]
- an array of YNodeLists each of which contains the nodes that belong to the same strongly connected component
See Also
Calculates the strongly connected components of a given graph and returns their number.
Remarks
Note: This method works with instances of Graph. To determine strongly connected components in an IGraph use StronglyConnectedComponents instead.
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
A map of options to pass to the method.
- graph - Graph
- the input graph
- compNum - INodeMap
- the INodeMap that will be filled during the execution and returns the zero-based index of the connected component to which each node belongs
Domain YNode Values number the zero-based index of of the connected component to which each node belongs
Returns
- ↪number
- the number of strongly connected components of the given graph
See Also
Transforms the return values of biconnectedComponents to an array of EdgeLists, like it is returned by biconnectedComponents.
Parameters
A map of options to pass to the method.
- graph - Graph
- the input graph
- compNum - IEdgeMap
- the IEdgeMap that will be filled during the execution and returns the zero-based index of the connected component to which each edge belongs
Domain Edge Values number the zero-based index of the biconnected component to which each edge belongs - maxCompNum - number
- the maximum number of biconnected components
Returns
Transforms the return values of method connectedComponents to an array of YNodeLists, like it is returned by connectedComponents.
Parameters
A map of options to pass to the method.
- graph - Graph
- the input graph
- compNum - INodeMap
- the INodeMap that will be filled during the execution and returns the zero-based index of the connected component to which each node belongs
Domain YNode Values number the zero-based index of the connected component to which each node belongs - maxCompNum - number
- the maximum number of connected components