This file contains the algorithm for listing all cliques according to the algorithm of Eppstein et al. (ISAAC 2010/SEA 2011). More...

#include <limits.h>
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include "misc.h"
#include "LinkedList.h"
#include "MemoryManager.h"
#include "degeneracy_helper.h"
#include "degeneracy_algorithm.h"

Functions
int	findBestPivotNonNeighborsDegeneracy (int *pivotNonNeighbors, int numNonNeighbors, int vertexSets, int vertexLookup, int *neighborsInP, int numNeighbors, int beginX, int beginP, int beginR)
	Computes the vertex v in P union X that has the most neighbors in P, and places P \ {neighborhood of v} in an array. These are the vertices to consider adding to the partial clique during the current recursive call of the algorithm.
void	fillInPandXForRecursiveCallDegeneracy (int vertex, int orderNumber, int vertexSets, int vertexLookup, NeighborListArray orderingArray, int neighborsInP, int numNeighbors, int pBeginX, int pBeginP, int pBeginR, int pNewBeginX, int pNewBeginP, int *pNewBeginR)
	Move vertex to R, set P to vertex's later neighbors and set X to vertex's earlier neighbors.
long	listAllMaximalCliquesDegeneracy (LinkedList adjList, int adjacencyList, LinkedList cliques, int degree, int size)
	List all maximal cliques in a given graph using the algorithm by Eppstein et al. (ISAAC 2010/SEA 2011).
void	moveToRDegeneracy (int vertex, int vertexSets, int vertexLookup, int *neighborsInP, int numNeighbors, int pBeginX, int pBeginP, int pBeginR, int pNewBeginX, int pNewBeginP, int pNewBeginR)
	Move a vertex to the set R, and update sets P and X and the arrays of neighbors in P.
void	moveFromRToXDegeneracy (int vertex, int vertexSets, int vertexLookup, int pBeginX, int pBeginP, int *pBeginR)
	Move a vertex from the set R to the set X, and update all necessary pointers and arrays of neighbors in P.
void	listAllMaximalCliquesDegeneracyRecursive (long cliqueCount, LinkedList cliques, LinkedList partialClique, int vertexSets, int vertexLookup, int neighborsInP, int numNeighbors, int beginX, int beginP, int beginR)
	Recursively list all maximal cliques containing all of all vertices in R, some vertices in P and no vertices in X.

Detailed Description

This file contains the algorithm for listing all cliques according to the algorithm of Eppstein et al. (ISAAC 2010/SEA 2011).

Author:: Darren Strash (first name DOT last name AT gmail DOT com)

See GPL 3.0 here

See the algorithm's description in http://dx.doi.org/10.1007/978-3-642-20662-7_31 and http://dx.doi.org/10.1007/978-3-642-17517-6_36

This algorithm first orders the vertices in a degeneracy order (vertices are removed from the graph in order by degree in the remaining subgraph and placed in this order in the ordering).

We then recursively call a modified version of the algorithm of Tomita et al. (2006) http://dx.doi.org/10.1016/j.tcs.2006.06.015, for each vertex v in the ordering, where R = {v}, P = v's neighbors that are after v in the degneracy order, and X = v's neighbors that are before v in the degeneracy order.

This is a recursive backtracking algorithm that maintains three sets of vertices, R, a partial clique, P, the common neighbors of vertices in R that are candidates to add to the partial clique, and X, the set of common neighbors of R that have been listed in a maximal clique with R already.

The algorithm recursively adds vertices to R from P, then updates the sets P and X to be the new common neighbors of R and recurses. When P and X are empty, R is a maximal clique, and is reported.

Updating the sets P and X is done by iterating over the later neighbors of vertices in P and X to see if they contain the vertex v added to R as a neighbor, and then testing if v's later neighbors are in P or X. Neighbors of v remain in their respective sets. For sparse graphs (graphs with low degeneracy) the number of neighbors of any vertex that come later in the degeneracy order is expected to be small. Then testing for neighbors in this way should be fast.

Besides the ordering, this algorithm includes more efficient pivot computation for sparse graphs. To find a "good" pivot, we must find the vertex in P union X that has the most neighbors in P. We accompish this step by maintaining a data structure that stores, for each vertex in P union X, its neighbors in P.

Function Documentation

void fillInPandXForRecursiveCallDegeneracy	(	int	vertex,
		int	orderNumber,
		int *	vertexSets,
		int *	vertexLookup,
		NeighborListArray **	orderingArray,
		int **	neighborsInP,
		int *	numNeighbors,
		int *	pBeginX,
		int *	pBeginP,
		int *	pBeginR,
		int *	pNewBeginX,
		int *	pNewBeginP,
		int *	pNewBeginR
	)			`[inline]`

Move vertex to R, set P to vertex's later neighbors and set X to vertex's earlier neighbors.

Parameters:

	vertex	The vertex to move to R.
	orderNumber	The position of vertex in the ordering.
	vertexSets	An array containing sets of vertices divided into sets X, P, and other.
	vertexLookup	A lookup table indexed by vertex number, storing the index of that vertex in vertexSets.
	orderingArray	A degeneracy order of the input graph.
	neighborsInP	Maps vertices to arrays of neighbors such that neighbors in P fill the first cells
	numNeighbors	An the neighbor of neighbors a vertex had in P, the first time this function is called, this bound is used to keep us from allocating more than linear space.
	pBeginX	The index where set X begins in vertexSets.
	pBeginP	The index where set P begins in vertexSets.
	pBeginR	The index where set R begins in vertexSets.
	pNewBeginX	After function, contains the new index where set X begins in vertexSets after adding vertex to R.
	pNewBeginP	After function, contains the new index where set P begins in vertexSets after adding vertex to P.
	pNewBeginR	After function, contains the new index where set R begins in vertexSets after adding vertex to R.

int findBestPivotNonNeighborsDegeneracy	(	int **	pivotNonNeighbors,
		int *	numNonNeighbors,
		int *	vertexSets,
		int *	vertexLookup,
		int **	neighborsInP,
		int *	numNeighbors,
		int	beginX,
		int	beginP,
		int	beginR
	)			`[inline]`

Computes the vertex v in P union X that has the most neighbors in P, and places P \ {neighborhood of v} in an array. These are the vertices to consider adding to the partial clique during the current recursive call of the algorithm.

Parameters:

	pivotNonNeighbors	An intially unallocated pointer, which will contain the set P \ {neighborhood of v} when this function completes.
	numNonNeighbors	A pointer to a single integer, which has been preallocated, which will contain the number of elements in pivotNonNeighbors.
	vertexSets	An array containing sets of vertices divided into sets X, P, R, and other.
	vertexLookup	A lookup table indexed by vertex number, storing the index of that vertex in vertexSets.
	neighborsInP	Maps vertices to arrays of neighbors such that neighbors in P fill the first cells
	numNeighbors	An the neighbor of neighbors a vertex had in P, the first time this function is called, this bound is used to keep us from allocating more than linear space.
	beginX	The index where set X begins in vertexSets.
	beginP	The index where set P begins in vertexSets.
	beginR	The index where set R begins in vertexSets.

long listAllMaximalCliquesDegeneracy	(	LinkedList **	adjList,
		int **	adjacencyList,
		LinkedList *	cliques,
		int *	degree,
		int	size
	)

List all maximal cliques in a given graph using the algorithm by Eppstein et al. (ISAAC 2010/SEA 2011).

Parameters:

	adjList	An array of linked lists, representing the input graph in the "typical" adjacency list format.
	adjacencyList	an array of arrays, representing the input graph in a more compact and cache-friendly adjacency list format. (not currently used)
	cliques	A linked list of cliques to return. (only available when compiled with RETURN_CLIQUES_ONE_BY_ONE defined)
	degree	An array, indexed by vertex, containing the degree of that vertex. (not currently used)
	size	The number of vertices in the graph.

Returns:: the number of maximal cliques of the input graph.

void listAllMaximalCliquesDegeneracyRecursive	(	long *	cliqueCount,
		LinkedList *	cliques,
		LinkedList *	partialClique,
		int *	vertexSets,
		int *	vertexLookup,
		int **	neighborsInP,
		int *	numNeighbors,
		int	beginX,
		int	beginP,
		int	beginR
	)

Recursively list all maximal cliques containing all of all vertices in R, some vertices in P and no vertices in X.

Parameters:

	cliqueCount	A pointer to the number of maximal cliques computed thus far.
	cliques	A linked list of cliques to return. (only available when compiled with RETURN_CLIQUES_ONE_BY_ONE defined)
	partialClique	A linked list storing R, the partial clique for this recursive call.
	vertexSets	An array containing sets of vertices divided into sets X, P, R and other.
	vertexLookup	A lookup table indexed by vertex number, storing the index of that vertex in vertexSets.
	neighborsInP	Maps vertices to arrays of neighbors such that neighbors in P fill the first cells
	numNeighbors	An the neighbor of neighbors a vertex had in P, the first time this function is called, this bound is used to keep us from allocating more than linear space.
	beginX	The index where set X begins in vertexSets.
	beginP	The index where set P begins in vertexSets.
	beginR	The index where set R begins in vertexSets.

void moveFromRToXDegeneracy	(	int	vertex,
		int *	vertexSets,
		int *	vertexLookup,
		int *	pBeginX,
		int *	pBeginP,
		int *	pBeginR
	)			`[inline]`

Move a vertex from the set R to the set X, and update all necessary pointers and arrays of neighbors in P.

Parameters:

	vertex	The vertex to move from R to X.
	vertexSets	An array containing sets of vertices divided into sets X, P, R, and other.
	vertexLookup	A lookup table indexed by vertex number, storing the index of that vertex in vertexSets.
	pBeginX	The index where set X begins in vertexSets.
	pBeginP	The index where set P begins in vertexSets.
	pBeginR	The index where set R begins in vertexSets.

void moveToRDegeneracy	(	int	vertex,
		int *	vertexSets,
		int *	vertexLookup,
		int **	neighborsInP,
		int *	numNeighbors,
		int *	pBeginX,
		int *	pBeginP,
		int *	pBeginR,
		int *	pNewBeginX,
		int *	pNewBeginP,
		int *	pNewBeginR
	)			`[inline]`

Move a vertex to the set R, and update sets P and X and the arrays of neighbors in P.

Parameters:

	vertex	The vertex to move to R.
	vertexSets	An array containing sets of vertices divided into sets X, P, R, and other.
	vertexLookup	A lookup table indexed by vertex number, storing the index of that vertex in vertexSets.
	neighborsInP	Maps vertices to arrays of neighbors such that neighbors in P fill the first cells
	numNeighbors	An the neighbor of neighbors a vertex had in P, the first time this function is called, this bound is used to keep us from allocating more than linear space.
	pBeginX	The index where set X begins in vertexSets.
	pBeginP	The index where set P begins in vertexSets.
	pBeginR	The index where set R begins in vertexSets.
	pNewBeginX	After function, contains the new index where set X begins in vertexSets after adding vertex to R.
	pNewBeginP	After function, contains the new index where set P begins in vertexSets after adding vertex to P.
	pNewBeginR	After function, contains the new index where set R begins in vertexSets after adding vertex to R.

src/degeneracy_algorithm.c File Reference

Functions

Detailed Description

Function Documentation