how to find all completely connected sub-graphs?

[Hyunchul Kim]

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

 

[odeits]

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?

 

[Hyunchul Kim]

Dear Odeits,

Yes, I meant directly connected to each other.

Thanks.

Hyunchul

 

[odeits]

Dear Odeits,

Yes, I meant directly connected to each other.

Thanks.

Hyunchul

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.