src/degeneracy_algorithm.h File Reference

see degeneracy_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	listAllMaximalCliquesDegeneracyRecursive (long *cliqueCount, LinkedList *cliques, LinkedList *partialClique, int *vertexSets, int *vertexLookup, int **neighborsInP, int *numNeighbors, 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.
long	listAllMaximalCliquesDegeneracy (LinkedList **adjList, int **adjacencyList, LinkedList *cliques, int *degree, int size)
	List all maximal cliques in a given graph using the algorithm by Eppstein et al. (ISAAC 2010/SEA 2011).

---

Detailed Description

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

See GPL 3.0 here

---

Function Documentation

long listAllMaximalCliquesDegeneracy	(	LinkedList **	adjList,
		int **	adjacencyList,
		LinkedList *	cliques,
		int *	degree,
		int	size
	)

List all maximal cliques in a given graph using the algorithm by Eppstein et al. (ISAAC 2010/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 listAllMaximalCliquesDegeneracyRecursive	(	long *	cliqueCount,
		LinkedList *	cliques,
		LinkedList *	partialClique,
		int *	vertexSets,
		int *	vertexLookup,
		int **	neighborsInP,
		int *	numNeighbors,
		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.
	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.
	neighborsInP	Maps vertices to arrays of neighbors such that neighbors in P fill the first cells
	numNeighbors	An the neighbor of neighbors a vertex had in P, the first time this function is called, this bound is used to keep us from allocating more than linear space.
	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.