Functions

src/adjlist_algorithm.h File Reference

see adjlist_algorithm.c More...

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "misc.h"
#include "LinkedList.h"
#include "MemoryManager.h"

Go to the source code of this file.

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 beginR, int beginP)
 Recursively list all maximal cliques containing all of all vertices in R, some vertices in P and no vertices in X.

Detailed Description

see adjlist_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

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