Connected components algorithm does not scale past 10,000 nodes

Question

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()
            seen.add(node)
            unseen_nodes |= adjacent(node, neighborhood) - seen
            yield node
    return (set(component(node)) for node in neighborhood if node not in seen)

def adjacent(a, n):
    """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'])),
])

Answer 1

In algorithm implementation there are usually subtleties that are difficult to spot in a code review. In these cases, I always recommend to have a look at the implementation in other libraries in which smarter people have already spent time to get a good performance.

In this case, I think the library to look at is NetworkX and the implementation for the algorithm you're working on is here.

I hope this helps.