DisjointSet Python class with linking by weight, path compression, splitting, halving.

disjointset.py

'''
DisjointSet class with linking by weight, path compression, splitting, halving.
Test - implementation of Karger global min-cut algorithm.

Used in my SPOJ solutions.
http://www.spoj.com/problems/PT07Y/
http://www.spoj.com/problems/FOXLINGS/
http://www.spoj.com/problems/FRNDCIRC/
http://www.spoj.com/problems/MST/
http://www.spoj.com/problems/CSTREET/
http://www.spoj.com/problems/BLINNET/
http://www.spoj.com/problems/HERDING/
http://www.spoj.com/problems/ADABANKET/
and
https://www.hackerrank.com/challenges/merging-communities/problem
https://www.hackerrank.com/challenges/components-in-graph/problem
https://www.hackerrank.com/challenges/kundu-and-tree/problem
https://www.hackerrank.com/challenges/kruskalmstrsub/problem
https://www.hackerrank.com/challenges/journey-to-the-moon/problem
'''
class DisjointSet:

  def __init__(self, s, pathop=None):
    self._parent = {x: x for x in s}
    self._weight = {x: 1 for x in s}
    self._root = set(s)
    if pathop == 'compression':
      self.root = self.__compression
    elif pathop == 'splitting':
      self.root = self.__splitting
    elif pathop == 'halving':
      self.root = self.__halving

  def __compression(self, x):
    r = x
    while r != self._parent[r]:
      r = self._parent[r]
    while x != r:
      p = self._parent[x]
      self._parent[x] = r
      x = p
    return(x)

  def __splitting(self, x):
    while x != self._parent[x]:
      p = self._parent[x]
      self._parent[x] = self._parent[p]
      x = p
    return(x)

  def __halving(self, x):
    while x != self._parent[x]:
      p = self._parent[x]
      self._parent[x] = self._parent[p]
      x = self._parent[x]
    return(x)

  def root(self, x):
    while x != self._parent[x]:
      x = self._parent[x]
    return(x)

  def root_set(self):
    return(self._root.copy())

  def make_set(self, x):
    if x not in self._parent:
      self._parent[x] = x
      self._weight[x] = 1
      self._root.add(x)

  def joined(self, x, y):
    return(self.root(x) == self.root(y))

  def join(self, x, y):
    rx, ry = self.root(x), self.root(y)
    if rx == ry:
      return(rx)
    if self._weight[rx] < self._weight[ry]:
      rx, ry = ry, rx
    self._parent[ry] = rx
    self._weight[rx] += self._weight[ry]
    self._root.remove(ry)
    return(rx)

  def size(self, x=None):
    if x is None:
      return(len(self._root))
    else:
      return(self._weight[self.root(x)])

  def __len__(self):
    return(len(self._parent))
'''
import networkx as nx
from random import shuffle
grph = nx.erdos_renyi_graph(600, 0.1, seed=None, directed=False)
edg = list(grph.edges())
print ("edges - ", len(edg))
cut_value, partition = nx.stoer_wagner(grph)
print ("stoer_wagner - ", cut_value)
gmin_cut = float('inf')
for __ in range(600):
  shuffle(edg)
  ds = DisjointSet(range(600), pathop='splitting')
  i = 0
  while ds.size() > 2 and i < len(edg):
    ds.join(edg[i][0], edg[i][1])
    i += 1
  #print(ds.size(), i)  
  min_cut = 0
  while i < len(edg):
    if not ds.joined(edg[i][0], edg[i][1]):
      min_cut += 1
      if min_cut >= gmin_cut:
        break
    i += 1    
  if min_cut < gmin_cut:
    gmin_cut = min_cut
print ("karger - ", gmin_cut)
'''