Packagecom.yworks.yfiles.algo
Classpublic class GraphConnectivity
InheritanceGraphConnectivity Inheritance YObject Inheritance Object

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


Public Methods
 MethodDefined By
  
GraphConnectivity(init:Boolean = true)
GraphConnectivity
  
biconnectedComponents(graph:Graph):Vector.<Object>
[static] Calculates the biconnected components of a given undirected graph.
GraphConnectivity
  
biconnectedComponents2(graph:Graph, compNum:EdgeMap):int
[static] Calculates the biconnected components of a given undirected graph.
GraphConnectivity
  
biconnectedComponentsWithArticulationPoints(graph:Graph, compNum:EdgeMap, aPoint:NodeMap):int
[static] Calculates the biconnected components of a given undirected graph.
GraphConnectivity
  
connectedComponents(graph:Graph):Vector.<Object>
[static] Returns the connected components of a given graph.
GraphConnectivity
  
connectedComponentsWithComponentNumber(graph:Graph, compNum:NodeMap):int
[static] Returns the connected components of a given graph.
GraphConnectivity
 Inherited
equals(o:Object):Boolean
YObject
  
getClass():Class
[override]
GraphConnectivity
  
getNeighbors(graph:Graph, startNodes:NodeList, maxDistance:int):NodeList
[static] Determines the direct or indirect neighbors of a given set of nodes.
GraphConnectivity
  
getPredecessors(graph:Graph, startNodes:NodeList, maxDistance:int):NodeList
[static] Determines the direct or indirect predecessors of a given set of nodes.
GraphConnectivity
  
getSuccessors(graph:Graph, startNodes:NodeList, maxDistance:int):NodeList
[static] Determines the direct or indirect successors of a given set of nodes.
GraphConnectivity
 Inherited
hashCode():int
YObject
  
isBiconnected(graph:Graph):Boolean
[static] Checks whether or not the given graph is biconnected.
GraphConnectivity
  
isConnected(graph:Graph):Boolean
[static] Checks whether or not the given graph is connected.
GraphConnectivity
  
isStronglyConnected(graph:Graph):Boolean
[static] Checks whether or not the given graph is strongly connected.
GraphConnectivity
  
makeBiconnected(graph:Graph):EdgeList
[static] Makes the given graph biconnected by inserting a minimum number of edges in the graph.
GraphConnectivity
  
makeConnected(graph:Graph):EdgeList
[static] Makes a graph connected by adding additional edges to the graph.
GraphConnectivity
  
newGraphConnectivity():GraphConnectivity
[static]
GraphConnectivity
  
reachable(graph:Graph, start:Node, directed:Boolean, reached:Vector.<Boolean>):void
[static] Determines the set of nodes that can be reached in the given graph when starting from a given node.
GraphConnectivity
  
reachableWithForbiddenEdges(graph:Graph, start:Node, directed:Boolean, forbidden:Vector.<Boolean>, reached:Vector.<Boolean>):void
[static] Similar to reachable().
GraphConnectivity
  
stronglyConnectedComponents(graph:Graph):Vector.<Object>
[static] Returns the connected components of a given graph.
GraphConnectivity
  
stronglyConnectedComponents2(graph:Graph, compNum:NodeMap):int
[static] Returns the connected components of a given graph.
GraphConnectivity
  
toEdgeListArray(graph:Graph, compNum:EdgeMap, maxCompNum:int):Vector.<Object>
[static] Transforms the return values of biconnectedComponents2() to an array of com.yworks.yfiles.base.EdgeList s, like it is returned by biconnectedComponents().
GraphConnectivity
  
toNodeListArray(graph:Graph, compNum:NodeMap, maxCompNum:int):Vector.<Object>
[static] Transforms the return values of connectedComponentsWithComponentNumber() to an array of type NodeList, like it is returned by connectedComponents().
GraphConnectivity
Protected Methods
 MethodDefined By
  
initGraphConnectivity():void
GraphConnectivity
Constructor Detail
GraphConnectivity()Constructor
public function GraphConnectivity(init:Boolean = true)



Parameters
init:Boolean (default = true)
Method Detail
biconnectedComponents()method
public static function biconnectedComponents(graph:Graph):Vector.<Object>

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.

Precondition GraphChecker.isConnected(graph)

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

Parameters

graph:Graph — the input graph

Returns
Vector.<Object>
biconnectedComponents2()method 
public static function biconnectedComponents2(graph:Graph, compNum:EdgeMap):int

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.

Precondition GraphChecker.isConnected(graph)

Precondition compNum defined for each edge in the graph.

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

Parameters

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

Returns
int — the number of biconnected components found
biconnectedComponentsWithArticulationPoints()method 
public static function biconnectedComponentsWithArticulationPoints(graph:Graph, compNum:EdgeMap, aPoint:NodeMap):int

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.

Precondition aPoint defined for each node in the graph

Parameters

graph:Graph
 
compNum:EdgeMap
 
aPoint:NodeMap — return value that provides for each node a boolean value indicating whether or not it is an articulation point.

Returns
int
connectedComponents()method 
public static function connectedComponents(graph:Graph):Vector.<Object>

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:Graph — the input graph

Returns
Vector.<Object> — an array of NodeLists each of which contains the nodes that belong to a common connected component of the graph.
connectedComponentsWithComponentNumber()method 
public static function connectedComponentsWithComponentNumber(graph:Graph, compNum:NodeMap):int

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:Graph — the input graph
 
compNum:NodeMap — 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
int — the number of connected components of this graph.
getClass()method 
override public function getClass():Class

Returns
Class
getNeighbors()method 
public static function getNeighbors(graph:Graph, startNodes:NodeList, maxDistance:int):NodeList

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:Graph — the graph to act upon
 
startNodes:NodeList — contains the node the search is started from
 
maxDistance:int — 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
NodeList — 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.
getPredecessors()method 
public static function getPredecessors(graph:Graph, startNodes:NodeList, maxDistance:int):NodeList

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:Graph — the graph to act upon
 
startNodes:NodeList — contains the node the search is started from
 
maxDistance:int — 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
NodeList — 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.
getSuccessors()method 
public static function getSuccessors(graph:Graph, startNodes:NodeList, maxDistance:int):NodeList

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:Graph — the graph to act upon
 
startNodes:NodeList — contains the node the search is started from
 
maxDistance:int — 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
NodeList — 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.
initGraphConnectivity()method 
protected final function initGraphConnectivity():void

isBiconnected()method 
public static function isBiconnected(graph:Graph):Boolean

Checks whether or not the given graph is biconnected.

Parameters

graph:Graph

Returns
Boolean
isConnected()method 
public static function isConnected(graph:Graph):Boolean

Checks whether or not the given graph is connected.

Parameters

graph:Graph

Returns
Boolean
isStronglyConnected()method 
public static function isStronglyConnected(graph:Graph):Boolean

Checks whether or not the given graph is strongly connected.

Parameters

graph:Graph

Returns
Boolean
makeBiconnected()method 
public static function makeBiconnected(graph:Graph):EdgeList

Makes the given graph biconnected by inserting a minimum number of edges in the graph. The given graph is considered to be undirected.

Precondition GraphChecker.isConnected(graph)

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

Parameters

graph:Graph — the input graph

Returns
EdgeList — an edge list containing the edges added to this graph.
makeConnected()method 
public static function makeConnected(graph:Graph):EdgeList

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.

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

Parameters

graph:Graph — the input graph

Returns
EdgeList — an edge list containing the edges added to this graph.
newGraphConnectivity()method 
public static function newGraphConnectivity():GraphConnectivity

Returns
GraphConnectivity
reachable()method 
public static function reachable(graph:Graph, start:Node, directed:Boolean, reached:Vector.<Boolean>):void

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:Graph — the graph the search is performed on
 
start:Node — the node the search is started from
 
directed:Boolean — traverses edges only from source to target if true. Otherwise traverses edges in both directions.
 
reached:Vector.<Boolean> — the return value. a boolean array that has value true at field v.index() iff node v can be reached by the dfs search.

reachableWithForbiddenEdges()method 
public static function reachableWithForbiddenEdges(graph:Graph, start:Node, directed:Boolean, forbidden:Vector.<Boolean>, reached:Vector.<Boolean>):void

Similar to reachable(). 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:Graph — the graph DFS is performed on
 
start:Node — the node DFS is started from
 
directed:Boolean — traverses edges only from source to target if true. Otherwise traverses edges in both directions.
 
forbidden:Vector.<Boolean> — marks edges that may not be traversed by DFS. An edge e is marked as forbidden if forbidden[e.index()] == true.
 
reached:Vector.<Boolean> — the return value. a boolean array that has value true at field v.index() iff node v can be reached by the dfs search.

See also

reachable()
stronglyConnectedComponents()method 
public static function stronglyConnectedComponents(graph:Graph):Vector.<Object>

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.

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

Parameters

graph:Graph — the input graph

Returns
Vector.<Object> — an array of NodeLists each of which contains the nodes that belong to a common connected component of the graph.
stronglyConnectedComponents2()method 
public static function stronglyConnectedComponents2(graph:Graph, compNum:NodeMap):int

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.

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

Parameters

graph:Graph — the input graph
 
compNum:NodeMap — 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
int — the number of strongly connected components of this graph.
toEdgeListArray()method 
public static function toEdgeListArray(graph:Graph, compNum:EdgeMap, maxCompNum:int):Vector.<Object>

Transforms the return values of biconnectedComponents2() to an array of com.yworks.yfiles.base.EdgeList s, like it is returned by biconnectedComponents().

Parameters

graph:Graph
 
compNum:EdgeMap
 
maxCompNum:int

Returns
Vector.<Object>

See also

biconnectedComponents2()
com.yworks.yfiles.base.EdgeList
biconnectedComponents()
toNodeListArray()method 
public static function toNodeListArray(graph:Graph, compNum:NodeMap, maxCompNum:int):Vector.<Object>

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

Parameters

graph:Graph
 
compNum:NodeMap
 
maxCompNum:int

Returns
Vector.<Object>

See also

connectedComponentsWithComponentNumber()
connectedComponents()




Wed Oct 7 2015, 04:43 PM +02:00