This file contains the main algorithm for listing all cliques according to the algorithm of Tomita et al. (TCS 2006) with one crucial change: the input graph is represented as an adjacency list. More...

#include <limits.h>
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "misc.h"
#include "LinkedList.h"
#include "MemoryManager.h"
#include "adjlist_algorithm.h"

Functions
long	listAllMaximalCliquesAdjacencyList (LinkedList adjList, int adjacencyList, LinkedList cliques, int degree, int size)
	List all maximal cliques in a given graph using the algorithm by Tomita et al. (TCS 2006), modified to use an adjacency list representation of the graph instead of an adjacency matrix.
int	findBestPivotNonNeighborsAdjacencyList (int *pivotNonNeighbors, int numNonNeighbors, int *adjacencyList, int degree, int vertexSets, int vertexLookup, int size, 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	listAllMaximalCliquesAdjacencyListRecursive (long cliqueCount, LinkedList cliques, LinkedList partialClique, int adjacencyList, int degree, int vertexSets, int vertexLookup, int size, 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 main algorithm for listing all cliques according to the algorithm of Tomita et al. (TCS 2006) with one crucial change: the input graph is represented as an adjacency list.

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

See GPL 3.0 here

See the main algorithm's description in http://dx.doi.org/10.1016/j.tcs.2006.06.015, and a description of this variant of the algorithm in http://dx.doi.org/10.1007/978-3-642-20662-7_31

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 neighbors of the new vertex v added to R and testing if they are in P or X. Neighbors of v remain in their respective sets.

Function Documentation

int findBestPivotNonNeighborsAdjacencyList	(	int **	pivotNonNeighbors,
		int *	numNonNeighbors,
		int **	adjacencyList,
		int *	degree,
		int *	vertexSets,
		int *	vertexLookup,
		int	size,
		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.

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.
	adjacencyList	An array of arrays, representing the input graph in a more compact and cache-friendly adjacency list format.
	degree	An array, indexed by vertex, containing the degree of that vertex.
	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.
	size	The number of vertices in the graph.
	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 listAllMaximalCliquesAdjacencyList	(	LinkedList **	adjList,
		int **	adjacencyList,
		LinkedList *	cliques,
		int *	degree,
		int	size
	)

List all maximal cliques in a given graph using the algorithm by Tomita et al. (TCS 2006), modified to use an adjacency list representation of the graph instead of an adjacency matrix.

Parameters:

	adjList	An array of linked lists, representing the input graph in the "typical" adjacency list format. (not currently used)
	adjacencyList	an array of arrays, representing the input graph in a more compact and cache-friendly adjacency list format.
	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.
	size	The number of vertices in the graph.

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

void listAllMaximalCliquesAdjacencyListRecursive	(	long *	cliqueCount,
		LinkedList *	cliques,
		LinkedList *	partialClique,
		int **	adjacencyList,
		int *	degree,
		int *	vertexSets,
		int *	vertexLookup,
		int	size,
		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.
	adjacencyList	An array of arrays, representing the input graph in a more compact and cache-friendly adjacency list format.
	degree	An array, indexed by vertex, containing the degree of that vertex.
	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.
	size	The number of vertices in the graph.
	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.

src/adjlist_algorithm.c File Reference

Functions

Detailed Description

Function Documentation