This file contains an algorithm for listing all cliques according to the "hybrid" algorithm of Eppstein and Strash (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 "hybrid_algorithm.h"
Functions | |
int | findBestPivotNonNeighborsHybrid (int **pivotNonNeighbors, int *numNonNeighbors, int *vertexSets, int *vertexLookup, int beginX, int beginP, int beginR, NeighborListArray **orderingArray, int *scratch) |
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 | fillInPandXForRecursiveCallHybrid (int vertex, int orderNumber, int *vertexSets, int *vertexLookup, NeighborListArray **orderingArray, 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 | listAllMaximalCliquesHybrid (LinkedList **adjList, int **adjacencyList, LinkedList *cliques, int *degree, int size) |
List all maximal cliques in a given graph using the "hybrid" algorithm by Eppstein et al. (SEA 2011). | |
void | moveToRHybrid (int vertex, int *vertexSets, int *vertexLookup, NeighborListArray **orderingArray, 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 | moveFromRToXHybrid (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 | listAllMaximalCliquesHybridRecursive (long *cliqueCount, LinkedList *cliques, LinkedList *partialClique, NeighborListArray **orderingArray, int *vertexSets, int *vertexLookup, int beginX, int beginP, int beginR, int *scratch) |
Recursively list all maximal cliques containing all of all vertices in R, some vertices in P and no vertices in X. |
This file contains an algorithm for listing all cliques according to the "hybrid" algorithm of Eppstein and Strash (SEA 2011).
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.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 iterating through each vertex in X and P, and marking each vertex with the number of later neighbors that are in P. (if the vertex is in P, we add one to the count for the vertex itself as well) and then we iterate over the vertices has the highest count.
void fillInPandXForRecursiveCallHybrid | ( | int | vertex, | |
int | orderNumber, | |||
int * | vertexSets, | |||
int * | vertexLookup, | |||
NeighborListArray ** | orderingArray, | |||
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.
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. | |
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 findBestPivotNonNeighborsHybrid | ( | int ** | pivotNonNeighbors, | |
int * | numNonNeighbors, | |||
int * | vertexSets, | |||
int * | vertexLookup, | |||
int | beginX, | |||
int | beginP, | |||
int | beginR, | |||
NeighborListArray ** | orderingArray, | |||
int * | scratch | |||
) |
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. | |
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. | |
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. | |
orderingArray | A array storing the degeneracy order, with each vertex containing arrays of its later and earlier neighbrs in the order. | |
scratch | An array that we use for scratch space to avoid allocating and deallocating memory often. We use this space to count how many neighbors each vertex has in P. |
long listAllMaximalCliquesHybrid | ( | LinkedList ** | adjList, | |
int ** | adjacencyList, | |||
LinkedList * | cliques, | |||
int * | degree, | |||
int | size | |||
) |
List all maximal cliques in a given graph using the "hybrid" algorithm by Eppstein et al. (SEA 2011).
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. |
void listAllMaximalCliquesHybridRecursive | ( | long * | cliqueCount, | |
LinkedList * | cliques, | |||
LinkedList * | partialClique, | |||
NeighborListArray ** | orderingArray, | |||
int * | vertexSets, | |||
int * | vertexLookup, | |||
int | beginX, | |||
int | beginP, | |||
int | beginR, | |||
int * | scratch | |||
) |
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. | |
orderingArray | A array storing the degeneracy order, with each vertex containing arrays of its later and earlier neighbrs in the order. | |
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. | |
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. | |
scratch | An array that we use for scratch space to avoid allocating and deallocating memory often. We use this space to count how many neighbors each vertex has in P. |
void moveFromRToXHybrid | ( | 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 moveToRHybrid | ( | int | vertex, | |
int * | vertexSets, | |||
int * | vertexLookup, | |||
NeighborListArray ** | orderingArray, | |||
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. | |
orderingArray | A degeneracy order of the input graph. | |
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. |