Functions

src/hybrid_algorithm.h File Reference

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).

Detailed Description

see hybrid_algorithm.c

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

Copyright (c) 2011 Darren Strash. This code is released under the GNU Public License (GPL) 3.0.

gplv3-127x51.png
See GPL 3.0 here

Function Documentation

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).

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 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.

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.
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.
 All Data Structures Files Functions Variables Typedefs Defines