MATLAB Central Newsreader - Graph Problem - Finding all sets of nodes forming complete sub-graphs

Graph Problem - Finding all sets of nodes forming complete sub-graphs

Ahmad — Wed, 07 May 2008 19:20:14 -0400

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

Re: Graph Problem - Finding all sets of nodes forming complete sub-graphs

helper — Thu, 08 May 2008 01:42:02 -0400

"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

Re: Graph Problem - Finding all sets of nodes forming complete sub-graphs

helper — Thu, 08 May 2008 11:40:17 -0400

"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)

Re: Graph Problem - Finding all sets of nodes forming complete sub-graphs

Ahmad — Thu, 08 May 2008 15:08:04 -0400

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)