[Jprogramming] Clique problem

[John Randall]

I am working on a problem in topology which has as a subproblem the
clique problem from graph theory.

The graph is undirected and reflexive, so its incidence matrix is
symmetric and has 1s on the diagonal.  A clique is a complete
subgraph, so it is a subset of the vertices in which each pair of
vertices forms an edge.  For a given graph, I need all cliques, which
will correspond to simplexes in the topology problem.

I know that this is NP-complete, but it would be helpful to have J
solutions in the cases

(a) A small number of vertices.
(b) A graph which may have a lot of vertices, but no large cliques.

Here is my solution to part (a).  I would appreciate suggestions for
improvement.  I have a completely different algorithm for (b).

The idea is that if the number n of vertices is small, we can
represent all subsets of vertices, and check individually if a given
subset is a clique.  I am sure that the experts can express this more
concisely.

bin=:[: #: [: i.&.<: [: 2&^ #
f=:[: *./ #
c=:(bin f^:2"1 _ ])# bin NB. Generate cliques
m=:>1 1 0; 1 1 1;0 1 1   NB. example incidence matrix

   c m
0 0 1
0 1 0
0 1 1
1 0 0
1 1 0


I would appreciate any suggestions.

Best wishes,

John