Path: news.mathworks.com!not-for-mail
From: "helper " <spamless@nospam.com>
Newsgroups: comp.soft-sys.matlab
Subject: Re: Graph Problem - Finding all sets of nodes forming complete sub-graphs
Date: Thu, 8 May 2008 01:42:02 +0000 (UTC)
Organization: Timothy S. Farajian, Inc.
Lines: 67
Message-ID: <fvtlpa$sd9$1@fred.mathworks.com>
References: <fvsvde$sb7$1@fred.mathworks.com>
Reply-To: "helper " <spamless@nospam.com>
NNTP-Posting-Host: webapp-03-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1210210922 29097 172.30.248.38 (8 May 2008 01:42:02 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Thu, 8 May 2008 01:42:02 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1272923
Xref: news.mathworks.com comp.soft-sys.matlab:467281


"Ahmad " <ahmad.humyn@gmail.com> wrote in message 
<fvsvde$sb7$1@fred.mathworks.com>...
> Hi there,
> 
> I want to find all the sets of nodes in a graph which have
> edges between all the nodes in the set....in other words I
> want to find all the complete sub-graphs in an
> un-directional graph: e.g.
> 
> If I have this upper-triangular graph (un-directed graph)
> where each
> edge is denoted by a 1 (0 is no edge) ... e.g. C is
> connected to D:
>     A    B    C    D    E    F
> A   X    1    1    0    0    0
> B   X    X    1    0    0    0
> C   X    X    X    1    0    1
> D   X    X    X    X    0    1
> E   X    X    X    X    X    0
> F   X    X    X    X    X    X
> 
> If I give the algo this matrix, it should return me two
> answer sets -> (A,B,C) and (C,D,F).
> 
> Am I looking for finding cliques? If so what is the 
fastest
> way known to compute these quickly? Anybody implemented 
this
> on Matlab? What is the most standard easiest way to 
compute
> these sets. I have heard cliques are 3-SAT (NP complete)?
> 
> Please help!!
> 
> Thanks

I've played with a couple methods for accomplishing this.  
Here is a simple reliable one using recursion.  I don't 
know if these are called "cliques", but thats a word you 
mentioned so thats what I called the function.  

There are a few ways to clean this up, but I'm just giving 
you what I got at this point.  I might clean this up and 
post it and/or create a better method if one of my other 
methods works out.


function out = clique(A)

[i j] = find(A(:,1:end-1));
for n = 1:length(i)
  recurse([i(n) j(n)])
end

  function recurse(p)
    nPts = length(p) + 1;
    q = find(all(A(p,max(p)+1:end),1))+max(p);
    if ~isempty(q) &&  length(out)<nPts-2
      out{nPts-2} = zeros(0,nPts);
    end
    for m = 1:length(q)
      out{nPts-2}(end+1,1:nPts) = [p q(m)];
      recurse([p q(m)])
    end
  end

end