\datethis
@i gb_types.w
@*Intro. This is a simple program to find all maximal cliques of a
graph, when the graph has at most 64 vertices and is given by
its adjacency matrix.
The algorithm, due to Moody and Hollis, is described in Appendix 5
of the book {\sl Mathematical Taxonomy\/} by Jardine and Sibson (1971).
I'm writing this program hastily today because it's a nice example of
bitwise manipulation in graph theory, probably suitable for Section
7.1.3 of {\sl The Art of Computer Programming}.
In brief, we have vectors $\rho_v$ and $\delta_v$ for each vertex~$v$,
where $\rho_v$ is $v$'s row in the adjacency matrix and
$\delta_v$ is all 1s except for 0 in position~$v$. (Position~$v$
in $\rho_v$ is always~1; in other words, we assume that each vertex
is adjacent to itself.) One can easily show that a set of
vertices~$q$ is a clique if and only if $q$ is the bitwise intersection
of $(v{\in}q?\,\rho_v{:}\,\delta_v)$ over all vertices~$v$.
To find all cliques, we could compute all $2^n$ such bitwise
intersections, discarding duplicates. To find all maximal cliques,
we could compute all $2^n$ such bitwise intersections and discard
any clique $q$ that is found to be contained in another. To speed
the process up, we can do those discards much more cleverly.
The input graph is specified by an ASCII file in Stanford GraphBase format.
The name of that file, say `\.{foo.gb}',
is the one-and-only command-line parameter.
I've instrumented this program to see how many memory references
it makes (|mems|) and how many words of workspace it needs (|space|),
exclusive of input-output.
(Note: I consider a ``clique'' to be any complete subgraph of
a graph. Many of the older books on graph theory define it to
be a {\it maximal\/} complete subgraph; but that terminology
is now dying out. The earlier definition is less desirable, because
for example we'd like a clique of~$G$ to be equivalent to
an independent set of $\overline G$.)
Beware: Memory overflow is not checked. This is not intended to
be a robust program; I wrote it only as a experiment.
@d size 100000 /* size reserved for the workspace */
@d o mems++
@d oo mems+=2
@c
#include
#include "gb_graph.h"
#include "gb_save.h"
unsigned long long rho[64]; /* rows of the adjacency matrix */
unsigned long long work[size];
unsigned int mems;
int space;
char table[64];
main(int argc, char* argv[])
{
register int i,j,k,l,m,n,p,q,r;
register Graph *g;
register Arc *a;
unsigned long long u,v,w;
@;
@;
@