see hybrid_algorithm.c More...
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "misc.h"
#include "LinkedList.h"
#include "MemoryManager.h"
#include "degeneracy_helper.h"
Go to the source code of this file.
Functions | |
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. | |
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). |
Copyright (c) 2011 Darren Strash. This code is released under the GNU Public License (GPL) 3.0.
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. |