how to find all completely connected sub-graphs?

[Andre Engels]

On Tue, Mar 3, 2009 at 7:35 AM, Hyunchul Kim <sundol at sfc.keio.ac.jp> wrote:

> 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.

Here is an algorithm I came up with in a few minutes of thinking,
complexity O(N*SN) with N being the number of nodes in the graph and
SN the sum of the nodes in each connected subgraph (there may well be
faster algorithms, but then you'd probably have to ask someone who
either already knows it, or spends significantly more time on it than
I did) - in pseudocode, but translating pseudocode into Python is an
easy thing to do:

Let N be the nodes in the graph.
A = {emptyset}      # that is, a set containing only the empty set in
the beginning
foreach node k in N:
    foreach set a in A:
        if k is connected to each node in a:
            add k+{a} to A   # in such a way that it's not included in
the loop for the current node k

The completely connected subgraphs are the subgraphs for which the set
of nodes in the subgraph is in A.


-- 
André Engels, andreengels at gmail.com