This file contains the algorithm for listing all cliques according to the algorithm of Tomita et al. (TCS 2006). 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 "tomita_algorithm.h"
Functions | |
long | listAllMaximalCliquesMatrix (char **adjacencyMatrix, LinkedList *cliques, int numVertices) |
List all maximal cliques in a given graph using the algorithm by Tomita et al. (TCS 2006). | |
int | findBestPivotNonNeighborsMatrix (int **pivotNonNeighbors, int *numNonNeighbors, char **adjacencyMatrix, 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 | moveToRMatrix (int vertex, int *vertexSets, int *vertexLookup, char **adjacencyMatrix, int *pBeginX, int *pBeginP, int *pBeginR, int *pNewBeginX, int *pNewBeginP, int *pNewBeginR) |
Move a vertex to the set R, and update the sets P and X. | |
void | moveFromRToXMatrix (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 | listAllMaximalCliquesMatrixRecursive (long *cliqueCount, LinkedList *cliques, LinkedList *partialClique, char **adjacencyMatrix, 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. |
This file contains the algorithm for listing all cliques according to the algorithm of Tomita et al. (TCS 2006).
Copyright (c) 2011 Darren Strash. This code is released under the GNU Public License (GPL) 3.0.
See the algorithm's description in http://dx.doi.org/10.1016/j.tcs.2006.06.015
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 testing if the vertices in P (X) have thee new vertex v added to R as a neighbor, by looking up the edge in the adjacency matrix. Neighbors of v remain in their respective sets.
int findBestPivotNonNeighborsMatrix | ( | int ** | pivotNonNeighbors, | |
int * | numNonNeighbors, | |||
char ** | adjacencyMatrix, | |||
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.
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. | |
adjacencyMatrix | The input graph in adjacency matrix format. | |
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 listAllMaximalCliquesMatrix | ( | char ** | adjacencyMatrix, | |
LinkedList * | cliques, | |||
int | numVertices | |||
) |
List all maximal cliques in a given graph using the algorithm by Tomita et al. (TCS 2006).
adjacencyMatrix | An input graph in the adjacency matrix format. | |
cliques | A linked list of cliques to return. (only available when compiled with RETURN_CLIQUES_ONE_BY_ONE defined) | |
numVertices | The number of vertices in the graph. |
void listAllMaximalCliquesMatrixRecursive | ( | long * | cliqueCount, | |
LinkedList * | cliques, | |||
LinkedList * | partialClique, | |||
char ** | adjacencyMatrix, | |||
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.
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. | |
adjacencyMatrix | The input graph in adjacency matrix format. | |
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. |
void moveFromRToXMatrix | ( | 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.
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 moveToRMatrix | ( | int | vertex, | |
int * | vertexSets, | |||
int * | vertexLookup, | |||
char ** | adjacencyMatrix, | |||
int * | pBeginX, | |||
int * | pBeginP, | |||
int * | pBeginR, | |||
int * | pNewBeginX, | |||
int * | pNewBeginP, | |||
int * | pNewBeginR | |||
) | [inline] |
Move a vertex to the set R, and update the sets P and X.
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. | |
adjacencyMatrix | An input graph in the adjacency matrix format. | |
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. |