KruskalMST.__init__() - Code Metrics - Inspection of "Implement Kruskal minimum spanning tree" - chen0040/pyalgs - Measure and Improve Code Quality continuously with Scrutinizer

Passed

Push — master ( be817c...e0c5f6 )

by Xianshun

created 2017-04-26 15:06 UTC

KruskalMST.init() B

↳ Parent: KruskalMST

Complexity

Conditions

Size

Total Lines

Duplication

Lines	0
Ratio	0 %

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
cc	5
c	1
b	0
f	0
dl	0
loc	15
rs	8.5454

from abc import ABCMeta, abstractmethod

from pyalgs.algorithms.commons.union_find import UnionFind
from pyalgs.data_structures.commons.bag import Bag
from pyalgs.data_structures.commons.priority_queue import MinPQ


class MST(object):
    __metaclass__ = ABCMeta

    @abstractmethod
    def spanning_tree(self):
        pass


class KruskalMST(MST):
    tree = None

    def __init__(self, G):
        minpq = MinPQ.create()
        self.tree = Bag()
        for e in G.edges():
            minpq.enqueue(e)

        uf = UnionFind.create(G.vertex_count())

        while not minpq.is_empty() and self.tree.size() < G.vertex_count() - 1:
            e = minpq.del_min()
            v = e.start()
            w = e.end()
            if not uf.connected(v, w):
                uf.union(v, w)
                self.tree.add(e)

    def spanning_tree(self):
        return self.tree.iterate()


1			from abc import ABCMeta, abstractmethod
2
3			from pyalgs.algorithms.commons.union_find import UnionFind
4			from pyalgs.data_structures.commons.bag import Bag
5			from pyalgs.data_structures.commons.priority_queue import MinPQ
6
7
8			class MST(object):
9			__metaclass__ = ABCMeta
10
11			@abstractmethod
12			def spanning_tree(self):
13			pass
14
15
16			class KruskalMST(MST):
17			tree = None
18
19			def __init__(self, G):
20			minpq = MinPQ.create()
21			self.tree = Bag()
22			for e in G.edges():
23			minpq.enqueue(e)
24
25			uf = UnionFind.create(G.vertex_count())
26
27			while not minpq.is_empty() and self.tree.size() < G.vertex_count() - 1:
28			e = minpq.del_min()
29			v = e.start()
30			w = e.end()
31			if not uf.connected(v, w):
32			uf.union(v, w)
33			self.tree.add(e)
34
35			def spanning_tree(self):
36			return self.tree.iterate()
37

chen0040 / pyalgs

Push — master ( be817c...e0c5f6 )

KruskalMST.__init__() B

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like

KruskalMST.init() B