src/tomita_algorithm.h File Reference

see tomita_algorithm.c More...

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

Go to the source code of this file.

Functions
long	listAllMaximalCliquesMatrix (char **adjacencyMatrix, LinkedList *cliques, int numVertices)
	List all maximal cliques in a given graph using the algorithm by Tomita et al. (TCS 2006).
int	findBestPivotNonNeighborsMatrix (int **pivotNonNeighbors, int *numNonNeighbors, char **adjacencyMatrix, 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	listAllMaximalCliquesMatrixRecursive (long *cliqueCount, LinkedList *cliques, LinkedList *partialClique, char **adjacencyMatrix, 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.

---

Detailed Description

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

int findBestPivotNonNeighborsMatrix	(	int **	pivotNonNeighbors,
		int *	numNonNeighbors,
		char **	adjacencyMatrix,
		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.
	adjacencyMatrix	The input graph in adjacency matrix format.
	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 listAllMaximalCliquesMatrix	(	char **	adjacencyMatrix,
		LinkedList *	cliques,
		int	numVertices
	)

List all maximal cliques in a given graph using the algorithm by Tomita et al. (TCS 2006).

Parameters:

	adjacencyMatrix	An input graph in the adjacency matrix format.
	cliques	A linked list of cliques to return. (only available when compiled with RETURN_CLIQUES_ONE_BY_ONE defined)
	numVertices	The number of vertices in the graph.

Returns:

the number of maximal cliques of the input graph.

void listAllMaximalCliquesMatrixRecursive	(	long *	cliqueCount,
		LinkedList *	cliques,
		LinkedList *	partialClique,
		char **	adjacencyMatrix,
		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.
	adjacencyMatrix	The input graph in adjacency matrix format.
	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.