5
\$\begingroup\$

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'])),
])
\$\endgroup\$
  • \$\begingroup\$ 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). \$\endgroup\$ – SylvainD Jul 23 '14 at 20:00
  • \$\begingroup\$ @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. \$\endgroup\$ – Air Jul 24 '14 at 0:04
1
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ You should include some of the more important material from the link here so mitigate against link rot. \$\endgroup\$ – syb0rg Aug 10 '14 at 16:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.