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 11:40:17 +0000 (UTC)
Organization: Timothy S. Farajian, Inc.
Lines: 84
Message-ID: <fvuor1$sse$1@fred.mathworks.com>
References: <fvsvde$sb7$1@fred.mathworks.com> <fvtlpa$sd9$1@fred.mathworks.com>
Reply-To: "helper " <spamless@nospam.com>
NNTP-Posting-Host: webapp-02-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1210246817 29582 172.30.248.37 (8 May 2008 11:40:17 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Thu, 8 May 2008 11:40:17 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1272923
Xref: news.mathworks.com comp.soft-sys.matlab:467364


"helper " <spamless@nospam.com> wrote in message <fvtlpa$sd9
$1@fred.mathworks.com>...
> "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

I accidentally deleted the first line of code.  It should 
be:

function out = clique(A)
out = {};
...

Also, any occurrance of max(p) should simply be p(end)