On Mar 3, 12:07 am, Andre Engels <andreeng...@gmail.com> wrote:
> On Tue, Mar 3, 2009 at 7:35 AM, Hyunchul Kim <sun...@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...@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,
--
http://mail.python.org/mailman/listinfo/python-list
