Path: news.mathworks.com!not-for-mail
From: "Ahmad " <ahmad.humyn@gmail.com>
Newsgroups: comp.soft-sys.matlab
Subject: Re: Graph Problem - Finding all sets of nodes forming complete sub-graphs
Date: Thu, 8 May 2008 15:08:04 +0000 (UTC)
Organization: University of Lahore
Lines: 93
Message-ID: <fvv50k$jbc$1@fred.mathworks.com>
References: <fvsvde$sb7$1@fred.mathworks.com> <fvtlpa$sd9$1@fred.mathworks.com> <fvuor1$sse$1@fred.mathworks.com>
Reply-To: "Ahmad " <ahmad.humyn@gmail.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 1210259284 19820 172.30.248.37 (8 May 2008 15:08:04 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Thu, 8 May 2008 15:08:04 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 687196
Xref: news.mathworks.com comp.soft-sys.matlab:467413


Thanks sir!

will just try it out :)



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