Imported Code

l = "12\nunion 1 2\nunion 3 4\nunion 3 5\nunion 1 7\nfind 7\nunion 3 6\nunion 8 9\nunion 1 8\nfind 9\nfind 9\nunion 3 10\nunion 3 11\nfind 11\nunion 1 3\nfind 9\nfind 9" def insertFileNoFile(self, f, compress=False): totalcount = 0 l = f.split() elements = int(l.pop(0)) for i in range(1, elements + 1): self.addValue(i) while len(l): if l[0] == 'union': l.pop(0) i = int(l.pop(0)) j = int(l.pop(0)) [ic, jc, counter] = self.union(i, j) print("%d made a child of %d: %d steps" % (jc.value, ic.value, counter)) totalcount += counter elif l[0] == 'find': l.pop(0) i = int(l.pop(0)) [counter, root] = self.find(i, compress) if counter: print("%d was found in %d: %d steps" % (i, root.value, counter)) else: print("%d was not found" % (i)) totalcount += counter else: return False print("All find operations completed in %d steps" % (totalcount)) return True

Project Code

class disjointSet: def __init__(self, value=None, superroot=True): self.value = value self.superroot = superroot self.children = [] self.superset = [] self.size = 1 self.parent = None def addValue(self, value): child = disjointSet(value, False) child.parent = self child.size = 1 self.size += 1 self.children.append(child) self.superset.append(child) def addChild(self, child): self.size += child.size child.parent = self for i in range(len(self.children)): if child.value < self.children[i].value: self.children.insert(i, child) return self.children.append(child) def deleteChild(self, child): for n in self.children: oldsize = n.size if n == child: self.children.pop(self.children.index(n)) self.size -= n.size return True else: if n.deleteChild(child): newsize = n.size self.size += newsize self.size -= oldsize return True return False def find(self, i, compress=False): if not self.superroot: return self.parent.find(i, compress) for n in self.superset: if n.value == i: if compress: return n._findCompress(n) else: return n._find() return [0, None] def _find(self): if self.parent.superroot: return [1, self] [count, root] = self.parent._find() return [count + 1, root] def _findCompress(self, child): if self.parent.superroot: if (self != child): self.deleteChild(child) self.addChild(child) return [1, self] [count, root] = self.parent._findCompress(child) return [count + 1, root] def union(self, i, j, compress=False): for n in self.superset: if n.value == i: [count1, ichild] = n.find(n.value, compress) if n.value == j: [count2, jchild] = n.find(n.value, compress) if ichild == jchild: return True if ichild.size > jchild.size: pass elif ichild.size < jchild.size: ichild, jchild = jchild, ichild elif ichild.value < jchild.value: pass else: ichild, jchild = jchild, ichild self.deleteChild(jchild) ichild.addChild(jchild) return [ichild, jchild, count1 + count2] def insertFile(self, filename, compress=False): totalcount = 0 f = open(filename) l = f.read() l = l.split() elements = int(l.pop(0)) for i in range(1, elements + 1): self.addValue(i) while len(l): if l[0] == 'union': l.pop(0) i = int(l.pop(0)) j = int(l.pop(0)) [ic, jc, counter] = self.union(i, j) print("%d made a child of %d: %d steps" % (jc.value, ic.value, counter)) totalcount += counter elif l[0] == 'find': l.pop(0) i = int(l.pop(0)) [counter, root] = self.find(i, compress) if counter: print("%d was found in %d: %d steps" % (i, root.value, counter)) else: print("%d was not found" % (i)) totalcount += counter else: return False print("All find operations completed in %d steps" % (totalcount)) return True

Commands

insertFileNoFile(disjointSet(), l) print '' insertFileNoFile(disjointSet(), l, compress=True)

Run

Output