Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Union-find data structure implementation
#! /usr/bin/env python
# Copyright 2012 Saravana Kumar(RIT)
# Licensed under the Apache License, Version 2.0 (the "License"); you may
# not use this file except in compliance with the License. You may obtain
# a copy of the License at
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
# WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
# License for the specific language governing permissions and limitations
# under the License.
Author : Saravana Kumar
E-mail :
Union-find data structure.
Based on Algorithm from Introduction to Algorithms Book(,
from node import Node
class UnionFind(object):
def __init__(self):
#To hold the clusters
self.clusters = []
#create a new set(cluster) with a node
def makeSet(self,node):
#set the nodes parent to the node itself
node.parent = node
#set initial rank of node to 0
node.rank = 0
#add the node to cluster list
#union the nodeA and nodeB clusters
def union(self, nodeA, nodeB):, self.findSet(nodeB))
#link the nodeA to nodeB or vice versa based upon the rank(number of nodes in the cluster) of the cluster
def link(self, nodeA, nodeB):
if nodeA.rank > nodeB.rank:
nodeB.parent = nodeA
#remove the nodeB from the cluster list, since it is merged with nodeA
nodeA.parent = nodeB
#remove the nodeA from the cluster list, since it is merged with nodeB
#increade the rank of the cluster after merging the cluster
if nodeA.rank == nodeB.rank:
nodeB.rank = nodeB.rank + 1
#find set will path compress(makes the nodes in cluster points to single leader/parent) and returns the leader/parent of the cluster
def findSet(self, node):
if node != node.parent:
node.parent = self.findSet(node.parent)
return node.parent
#get cluster size
def clusterSize(self):
return len(self.clusters)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment