← Back to branch summary

~ubuntu-branches/ubuntu/utopic/python-networkx/utopic

« back to all changes in this revision

Viewing changes to networkx/utils/union_find.py

  • Committer: Package Import Robot
  • Author(s): Sandro Tosi
  • Date: 2012-08-11 12:41:30 UTC
  • mfrom: (1.4.1) (5.1.13 sid)
  • Revision ID: package-import@ubuntu.com-20120811124130-whr6uso7fncyg8bi
Tags: 1.7-1
* New upstream release
* debian/patches/changeset_*
  - removed, included upstream

Show diffs side-by-side

added added

removed removed

Lines of Context:
networkx/utils/union_find.py
 
1
"""
 
2
Union-find data structure.
 
3
"""
 
4
#    Copyright (C) 2004-2011 by 
 
5
#    Aric Hagberg <hagberg@lanl.gov>
 
6
#    Dan Schult <dschult@colgate.edu>
 
7
#    Pieter Swart <swart@lanl.gov>
 
8
#    All rights reserved.
 
9
#    BSD license.
 
10
import networkx as nx
 
11
 
 
12
class UnionFind:
 
13
    """Union-find data structure.
 
14
 
 
15
    Each unionFind instance X maintains a family of disjoint sets of
 
16
    hashable objects, supporting the following two methods:
 
17
 
 
18
    - X[item] returns a name for the set containing the given item.
 
19
      Each set is named by an arbitrarily-chosen one of its members; as
 
20
      long as the set remains unchanged it will keep the same name. If
 
21
      the item is not yet part of a set in X, a new singleton set is
 
22
      created for it.
 
23
 
 
24
    - X.union(item1, item2, ...) merges the sets containing each item
 
25
      into a single larger set.  If any item is not yet part of a set
 
26
      in X, it is added to X as one of the members of the merged set.
 
27
 
 
28
      Union-find data structure. Based on Josiah Carlson's code,
 
29
      http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
 
30
      with significant additional changes by D. Eppstein.
 
31
      http://www.ics.uci.edu/~eppstein/PADS/UnionFind.py
 
32
 
 
33
    """
 
34
 
 
35
    def __init__(self):
 
36
        """Create a new empty union-find structure."""
 
37
        self.weights = {}
 
38
        self.parents = {}
 
39
 
 
40
    def __getitem__(self, object):
 
41
        """Find and return the name of the set containing the object."""
 
42
 
 
43
        # check for previously unknown object
 
44
        if object not in self.parents:
 
45
            self.parents[object] = object
 
46
            self.weights[object] = 1
 
47
            return object
 
48
 
 
49
        # find path of objects leading to the root
 
50
        path = [object]
 
51
        root = self.parents[object]
 
52
        while root != path[-1]:
 
53
            path.append(root)
 
54
            root = self.parents[root]
 
55
 
 
56
        # compress the path and return
 
57
        for ancestor in path:
 
58
            self.parents[ancestor] = root
 
59
        return root
 
60
        
 
61
    def __iter__(self):
 
62
        """Iterate through all items ever found or unioned by this structure."""
 
63
        return iter(self.parents)
 
64
 
 
65
    def union(self, *objects):
 
66
        """Find the sets containing the objects and merge them all."""
 
67
        roots = [self[x] for x in objects]
 
68
        heaviest = max([(self.weights[r],r) for r in roots])[1]
 
69
        for r in roots:
 
70
            if r != heaviest:
 
71
                self.weights[heaviest] += self.weights[r]
 
72
                self.parents[r] = heaviest
 
73
 
 
74
 
 
75