how to find all completely connected sub-graphs?

odeits odeits at gmail.com
Tue Mar 3 08:31:23 CET 2009


On Mar 2, 11:26 pm, Hyunchul Kim <sun... at sfc.keio.ac.jp> wrote:
> Dear Odeits,
>
> Yes, I meant directly connected to each other.
>
> Thanks.
>
> Hyunchul
>
> odeits wrote:
> > On Mar 2, 10:35 pm, Hyunchul Kim <sun... at sfc.keio.ac.jp> wrote:
>
> >> Hi, all,
>
> >> How can I find all "completely connected subgraphs" in a graph when node
> >> and edge data are available?
>
> >> "completely connected subgraph" is a group, all members of which are
> >> connected to each other.
>
> >> Thanks,
>
> >> Hyunchul
>
> > Do you mean all of the member are directly connected to each other?
> > --
> >http://mail.python.org/mailman/listinfo/python-list
>
>

I would start by creating sets for every node in your graph that are
made up of the node and all of its edges. Then you can use the
issubset to filter down your collection.

http://docs.python.org/library/sets.html

The idea is a node find its completely connected subset. once you have
done this, you can remove all of those nodes from the universal set
and chose another node. repeat until the universal set is empty.
Remember the smallest completely connected subset is an individual
node.

That should be a good enough starting point to figure out an alg that
works for you.

Cheers.



More information about the Python-list mailing list