QuickUnion.union() - Code Metrics - Inspection of "Implement quick union with path compression" - chen0040/pyalgs - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( 7183e8...ac4041 )

by Xianshun

created 2017-04-25 17:10 UTC

QuickUnion.union() A

↳ Parent: QuickUnion

Complexity

Conditions

Size

Total Lines

Duplication

Lines	0
Ratio	0 %

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
cc	2
c	1
b	0
f	0
dl	0
loc	10
rs	9.4285

from abc import ABCMeta, abstractmethod


class UnionFind(object):
    __metaclass__ = ABCMeta

    @abstractmethod
    def union(self, v, w):
        pass

    @abstractmethod
    def connected(self, v, w):
        pass

    @staticmethod
    def create(size):
        return QuickUnion(size)


class QuickFind(UnionFind):
    id = None

    def __init__(self, capacity):
        self.id = [i for i in range(capacity)]

    def connected(self, v, w):
        return self.id[v] == self.id[w]

    def union(self, v, w):
        p = self.id[v]
        q = self.id[w]

        if p != q:
            for i in range(len(self.id)):
                if self.id[i] == p:
                    self.id[i] = q


class QuickUnion(UnionFind):
    id = None
    sizes = None

    def __init__(self, capacity):
        self.id = [i for i in range(capacity)]
        self.sizes = [1] * capacity

    def root(self, v):
        while v != self.id[v]:
            self.id[v] = self.id[self.id[v]]  # path compression
            v = self.id[v]
        return v

    def connected(self, v, w):
        return self.root(v) == self.root(w)

    def union(self, v, w):
        vroot = self.root(v)
        wroot = self.root(w)

        if self.sizes[vroot] > self.sizes[wroot]:
            self.id[wroot] = vroot
            self.sizes[vroot] += self.sizes[wroot]
        else:
            self.id[vroot] = wroot
            self.sizes[wroot] += self.sizes[vroot]


1			from abc import ABCMeta, abstractmethod
2
3
4			class UnionFind(object):
5			__metaclass__ = ABCMeta
6
7			@abstractmethod
8			def union(self, v, w):
9			pass
10
11			@abstractmethod
12			def connected(self, v, w):
13			pass
14
15			@staticmethod
16			def create(size):
17			return QuickUnion(size)
18
19
20			class QuickFind(UnionFind):
21			id = None
22
23			def __init__(self, capacity):
24			self.id = [i for i in range(capacity)]
25
26			def connected(self, v, w):
27			return self.id[v] == self.id[w]
28
29			def union(self, v, w):
30			p = self.id[v]
31			q = self.id[w]
32
33			if p != q:
34			for i in range(len(self.id)):
35			if self.id[i] == p:
36			self.id[i] = q
37
38
39			class QuickUnion(UnionFind):
40			id = None
41			sizes = None
42
43			def __init__(self, capacity):
44			self.id = [i for i in range(capacity)]
45			self.sizes = [1] * capacity
46
47			def root(self, v):
48			while v != self.id[v]:
49			self.id[v] = self.id[self.id[v]] # path compression
50			v = self.id[v]
51			return v
52
53			def connected(self, v, w):
54			return self.root(v) == self.root(w)
55
56			def union(self, v, w):
57			vroot = self.root(v)
58			wroot = self.root(w)
59
60			if self.sizes[vroot] > self.sizes[wroot]:
61			self.id[wroot] = vroot
62			self.sizes[vroot] += self.sizes[wroot]
63			else:
64			self.id[vroot] = wroot
65			self.sizes[wroot] += self.sizes[vroot]
66

chen0040 / pyalgs

Push — master ( 7183e8...ac4041 )

QuickUnion.union() A

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like