CDPL.Util.BronKerboschAlgorithm Class Reference

Implementation of the Bron-Kerbosch clique-detection algorithm [BKA]. More...

Inheritance diagram for CDPL.Util.BronKerboschAlgorithm:

Public Member Functions
None	__init__ ()
	Constructs the BronKerboschAlgorithm instance without an associated adjacency matrix.
None	__init__ (BronKerboschAlgorithm bka)
	Constructs a copy of the BronKerboschAlgorithm instance bka. More...
None	__init__ (BitSetArray adj_mtx)
	Constructs the BronKerboschAlgorithm instance and immediately initializes it with the adjacency matrix adj_mtx. More...
int	getObjectID ()
	Returns the numeric identifier (ID) of the wrapped C++ class instance. More...
None	init (BitSetArray adj_mtx)
	(Re-)initializes the algorithm with the adjacency matrix adj_mtx and resets the clique iterator. More...
bool	nextClique (BitSet clique)
	Advances the clique iterator and writes the next maximal clique into clique. More...
BronKerboschAlgorithm	assign (BronKerboschAlgorithm bka)
	Copy assignment operator. More...

Properties
	objectID = property(getObjectID)

Detailed Description

Implementation of the Bron-Kerbosch clique-detection algorithm [BKA].

Constructor & Destructor Documentation

__init__() [1/2]

None CDPL.Util.BronKerboschAlgorithm.__init__

(

BronKerboschAlgorithm

bka

)

Constructs a copy of the BronKerboschAlgorithm instance bka.

Parameters

bka	The BronKerboschAlgorithm instance to copy.

__init__() [2/2]

None CDPL.Util.BronKerboschAlgorithm.__init__

(

BitSetArray

adj_mtx

)

Constructs the BronKerboschAlgorithm instance and immediately initializes it with the adjacency matrix adj_mtx.

Parameters

adj_mtx

The graph adjacency matrix (one Util.BitSet per node).

Member Function Documentation

getObjectID()

int CDPL.Util.BronKerboschAlgorithm.getObjectID

(

)

Returns the numeric identifier (ID) of the wrapped C++ class instance.

Different Python BronKerboschAlgorithm instances may reference the same underlying C++ class instance. The commonly used Python expression a is not b thus cannot tell reliably whether the two BronKerboschAlgorithm instances a and b reference different C++ objects. The numeric identifier returned by this method allows to correctly implement such an identity test via the simple expression a.getObjectID() != b.getObjectID().

Returns

The numeric ID of the internally referenced C++ class instance.

init()

None CDPL.Util.BronKerboschAlgorithm.init

(

BitSetArray

adj_mtx

)

(Re-)initializes the algorithm with the adjacency matrix adj_mtx and resets the clique iterator.

Parameters

adj_mtx

The graph adjacency matrix (one Util.BitSet per node).

nextClique()

bool CDPL.Util.BronKerboschAlgorithm.nextClique

(

BitSet

clique

)

Advances the clique iterator and writes the next maximal clique into clique.

Parameters

clique

The output clique (set of node indices).

Returns

True if a clique was emitted, and False when the iteration is exhausted.

assign()

BronKerboschAlgorithm CDPL.Util.BronKerboschAlgorithm.assign

(

BronKerboschAlgorithm

bka

)

Copy assignment operator.

Parameters

bka	The other BronKerboschAlgorithm instance.

Returns

self