public static function biconnectedComponentGrouping(graph:Graph, groupIDs:NodeMap):int

This method partitions the graph by analyzing its biconnected component structure. Nodes will be grouped in a way that the nodes within each group are biconnected. Nodes that belong to multiple biconnected components will be assigned to exactly one of these components.

Note: Biconnected components are defined for undirected graphs only. As a consequence, this algorithm ignores selfloops and isolated nodes with only selfloop edges or no edges at all are not assigned to any group, i.e. the groupID for such a node will be null.

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

Parameters

	graph:Graph — the input graph.
	groupIDs:NodeMap — used as return value. This map gets a cluster ID of integer type for every node.

Returns

int — the number of different groups found.

public static function edgeBetweennessClustering(graph:Graph, clusterIDs:NodeMap, directed:Boolean, minGroupCount:int, maxGroupCount:int, edgeCosts:DataProvider):int

Partitions the graph into groups using edge betweenness centrality (see com.yworks.yfiles.algo.Centrality.edgeBetweenness(). In each iteration the edge with the highest betweenness centrality is removed from the graph. The method stops, if there are no more edges to remove. The clustering with the best quality reached during the process will be returned.

Complexity O(graph.E())*O(edgeBetweenness) (Note: is practical faster because edge betweenness is computed for subgraphs during the process and this algorithm terminates after maxGroupCount groups have been determined.)

Precondition minGroupCount <= maxGroupCount

Precondition minGroupCount <= graph.N()

Precondition maxGroupCount > 0

Parameters

	graph:Graph — the input graph.
	clusterIDs:NodeMap — used as return value. This map gets a cluster ID of integer type for every node.
	directed:Boolean — whether or not to consider the edges of the graph as directed.
	minGroupCount:int — the minimum number of groups to be returned.
	maxGroupCount:int — the maximum number of groups to be returned. The smaller this value is chosen the faster the overall computation time. Note that the upper bound on the number of groups is graph.N(). Note, that the number of returned groups is never less than the number of connected components of the graph.
	edgeCosts:DataProvider — if null the edges of the graph are considered to have equal cost. Otherwise it must provide a non-negative double value (its cost) for every edge.

Returns

int — the number of different groups found.

See also

public static function edgeBetweennessClustering2(graph:Graph, clusterIDs:NodeMap, qualityTimeRatio:Number, minGroupCount:int, maxGroupCount:int, refine:Boolean):int

Partitions the graph into groups using Edge Betweenness Clustering proposed by Girvan and Newman. In each iteration the edge with the highest betweenness centrality is removed from the graph. The method stops, if there are no more edges to remove or if the requested maximum number of groups is found. The clustering with the best quality reached during the process is returned.

The algorithm includes several heuristic speed-up techniques available through the quality/time ratio. For the highest quality setting, it is used almost unmodified. The fast betweenness approximation of Brandes und Pich (Centrality Estimation in Large Networks) is employed for values around 0.5. Typically, this results in a tiny decrease in quality but a large speed-up and is the recommended setting. To achieve the lowest running time, a local betweenness calculation is used (Gregory: Local Betweenness for Finding Communities in Networks).

Complexity O(graph.E())*O(edgeBetweenness) (Note: is practical faster because edge betweenness is computed for subgraphs during the process and this algorithm terminates after maxGroupCount groups have been determined.)

Precondition minGroupCount <= maxGroupCount

Precondition minGroupCount <= graph.N()

Precondition maxGroupCount > 0

Parameters

	graph:Graph — the input graph.
	clusterIDs:NodeMap — used as return value. This map gets a cluster ID of integer type for every node.
	qualityTimeRatio:Number — a value between 0.0 (low quality, fast) and 1.0 (high quality, slow). The recommended value is 0.5.
	minGroupCount:int — the minimum number of groups to be returned.
	maxGroupCount:int — the maximum number of groups to be returned. The smaller this value is chosen the faster the overall computation time. Note, that the upper bound on the number of groups is graph.N() and that the number of returned groups is never less than the number of connected components of the graph.
	refine:Boolean — whether the algorithm refines or discards the current grouping.

Returns

int — the number of different groups found