org.apache.ignite.internal.cluster.graph

Class FullyConnectedComponentSearcher

java.lang.Object

org.apache.ignite.internal.cluster.graph.FullyConnectedComponentSearcher

public class FullyConnectedComponentSearcher
extends Object

Class to find (possibly) largest fully-connected component (also can be called as complete subgraph) in graph. This problem is also known as Clique problem which is NP-complete. For small number of nodes simple brute-force algorithm is used which finds such component guaranteed. For large number of nodes some sort of greedy heuristic is used which works well for real-life scenarios but doesn't guarantee to find largest component, however very close to ideal result.

Constructor Summary

Constructors

Constructor and Description
FullyConnectedComponentSearcher(BitSet[] connections) Constructor.

Method Summary

Modifier and Type	Method and Description
BitSet	findLargest(BitSet where) Find largest fully connected component from presented set of the nodes where.

Methods inherited from class java.lang.Object

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

Constructor Detail

FullyConnectedComponentSearcher

public FullyConnectedComponentSearcher(BitSet[] connections)

Constructor.

Parameters:

connections - Adjacency matrix.

Method Detail

findLargest

public BitSet findLargest(BitSet where)

Find largest fully connected component from presented set of the nodes where.

Parameters:

where - Set of nodes where fully connected component must be found.

Returns:

Set of nodes forming fully connected component.