y.algo
Class Groups

java.lang.Object
  y.algo.Groups

public class Groups
extends Object

This class provides methods for automatically partitioning nodes of a graph into groups.

Method Summary

static int	biconnectedComponentGrouping(Graph graph, NodeMap groupIDs) This method partitions the graph by analysing its biconnected component structure.
static int	edgeBetweennessClustering(Graph graph, NodeMap clusterIDs, boolean directed, int minGroupCount, int maxGroupCount, DataProvider edgeCosts) This method partitions the graph into groups using edge betweenness centrality (see Centrality.edgeBetweenness(Graph, EdgeMap, boolean, DataProvider).

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

edgeBetweennessClustering

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

This method partitions the graph into groups using edge betweenness centrality (see Centrality.edgeBetweenness(Graph, EdgeMap, boolean, DataProvider). 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.

Parameters:

graph - - the input graph.

clusterIDs - - return value. this map holds a cluster ID of integer type for every node.

directed - - whether or not to consider the edges of the graph as directed.

minGroupCount - - the minimum number of groups to be returned. The smaller this value is chosen the

maxGroupCount - - 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 - - when 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:

the number of different groups found.

Complexity:

O(graph.E())*O(edgeBetweenness) (Note: is practical faster because edgeBetweenness is called for subgraphs during the process)

Preconditions:

minGroupCount <= maxGroupCount

minGroupCount <= graph.N()

maxGroupCount > 0

biconnectedComponentGrouping

public static int biconnectedComponentGrouping(Graph graph,
                                               NodeMap groupIDs)

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

Parameters:

graph - - the input graph.

groupIDs - - return value. this map holds a cluster ID of integer type for every node.

Returns:

the number of different groups found.

Complexity:

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