how to find all completely connected sub-graphs?

[odeits]

On Mar 3, 12:07 am, Andre Engels <andreeng... at gmail.com> wrote:
> On Tue, Mar 3, 2009 at 7:35 AM, Hyunchul Kim <sun... 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, andreeng... at gmail.com

Seems to me the definition of the completely connected graph is:

for a given node N with an edge set of E

the complete graph is the intersection of all of the edge sets
belonging to each element in E

so assuming you have a dictionary that is d[Node] = list(edgeNodes)

for Node, EdgeNodes in d:
   connectedGraph = set(EdgeNodes}
   connectedGraph.add(Node)
   for EdgeNode in EdgeNodes:
     EdgeSet = set(d[EdgeNode])
     EdgeSet.add(EdgeNode)
     connectedGraph.intersectionUpdate( EdgeSet)
   yield connectedGraph

Code is untested but i think illustrates my theory.

Regards,