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 -- http://mail.python.org/mailman/listinfo/python-list