# Connected components algorithm does not scale past 10,000 nodes

I found a connected components algorithm posted here on SO and modified it for my own purposes. It runs well for small input sets, but doesn't scale as well as I would like.

The largest set I've been able to handle with it has just under 10,000 nodes and took 109 seconds to process. I threw in the towel when testing a set of about 107,000 nodes after 30 minutes at 100% CPU load (RAM utilization <10%).

I have several sets in the 100,000- to 300,000-node range in which I'd like to identify connected components. Is there some way I could modify this algorithm to scale better?

Node = collections.namedtuple('Node', 'fact_id person_ids names')

def grouped(neighborhood):
"""takes a flat set of nodes and returns the connected subsets"""
seen = set()
def component(node):
unseen_nodes = set((node,))
while unseen_nodes:
node = unseen_nodes.pop()
unseen_nodes |= adjacent(node, neighborhood) - seen
yield node
return (set(component(node)) for node in neighborhood if node not in seen)

"""returns all elements of n(eighborhood) adjacent to a(ctive node)"""
return {e for e in n if a.person_ids & e.person_ids or a.names & e.names}


My background is not in computer science but I'm willing to take some time to study and understand an alternative approach, within reason.

I can't provide my source data but here's set of example Nodes comprising four connected components, if that's helpful:

examples = set([
Node(49559, frozenset(['62169']), frozenset(['COX'])),
Node(56669, frozenset(['62169', '70260']), frozenset(['COX', 'HUGHES'])),
Node(71440, frozenset(['87830', '87829']), frozenset(['WARREN'])),
Node(267031, frozenset(['303253']), frozenset(['FOX'])),
Node(324771, frozenset(['358566']), frozenset(['FOX'])),
Node(405519, frozenset(['427822']), frozenset(['EVANS'])),
Node(437153, frozenset(['452540', '452541']), frozenset(['BOYD'])),
Node(474774, frozenset(['482316']), frozenset(['WARREN'])),
Node(509974, frozenset(['509895', '509894']), frozenset(['BOYD'])),
Node(552313, frozenset(['544087', '544086']), frozenset(['BOYD'])),
Node(566768, frozenset(['555467', '555468']), frozenset(['GARDNER', 'WARREN'])),
Node(603318, frozenset(['583882', '583883']), frozenset(['WARREN'])),
Node(886519, frozenset(['891668']), frozenset(['FOX'])),
Node(951212, frozenset(['973755', '973754']), frozenset(['COX'])),
Node(1043850, frozenset(['1090122']), frozenset(['GARDNER'])),
Node(1136082, frozenset(['1204393', '1204394']), frozenset(['WILSON', 'BOYD'])),
Node(28161119, frozenset(['1204393']), frozenset(['WILSON'])),
Node(1343476, frozenset(['973755', '973754']), frozenset(['COX'])),
Node(1347042, frozenset(['1457174']), frozenset(['BOYD'])),
Node(1469345, frozenset(['1597595']), frozenset(['GARDNER'])),
Node(1561624, frozenset(['1701196', '1701195']), frozenset(['GARDNER', 'EVANS'])),
Node(1643273, frozenset(['1783604', '1783603']), frozenset(['GARDNER'])),
Node(1801071, frozenset(['1963032', '1963031']), frozenset(['CHAPMAN', 'EVANS'])),
Node(1836980, frozenset(['2004300', '2004301']), frozenset(['BOYD'])),
Node(10298940, frozenset(['2004300', '2004301']), frozenset(['BOYD'])),
Node(1843190, frozenset(['2011505']), frozenset(['CHAPMAN'])),
Node(1905248, frozenset(['2082776']), frozenset(['GARDNER'])),
Node(1927031, frozenset(['2108156', '2108157']), frozenset(['FOX'])),
Node(2039106, frozenset(['2236190', '2236191']), frozenset(['FOX'])),
])

• Hi, welcome to code review.SE ! Maybe you could check how many times adjacent is called as the input set gets bigger. If the number of calls grows faster than the size of the set, it might be a good option to precompute it and save the result in a dict. Or maybe you could precompute dicts mapping person_ids to nodes and names to node. (In any case, can you provide test sets so that one can test the code with proper data). – SylvainD Jul 23 '14 at 20:00
• @Josay Thanks for the tips. I did some profiling with cProfile and it looks like the number of calls is increasing linearly with the number of input nodes. But I'm not too experienced so I may be missing something. – Air Jul 24 '14 at 0:04