LazyPrimMST.__init__() - Code Metrics - Inspection of "Implement Prim's lazy MST implementation" - chen0040/pyalgs - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( 6ecd56...a35e0e )

by Xianshun

created 2017-04-27 02:13 UTC

LazyPrimMST.init() B

↳ Parent: LazyPrimMST

Complexity

Conditions

Size

Total Lines

Duplication

Lines	0
Ratio	0 %

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
cc	7
c	1
b	0
f	0
dl	0
loc	18
rs	7.3333

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()


class LazyPrimMST(MST):
    tree = None
    marked = None
    minpq = None

    def __init__(self, G):
        self.minpq = MinPQ.create()
        self.tree = Bag()
        vertex_count = G.vertex_count()
        self.marked = [False] * vertex_count
        self.visit(G, 0)

        while not self.minpq.is_empty() and self.tree.size() < vertex_count-1:
            edge = self.minpq.del_min()
            v = edge.start()
            w = edge.end()
            if self.marked[v] and self.marked[w]:
                continue
            self.tree.add(edge)
            if not self.marked[v]:
                self.visit(G, v)
            if not self.marked[w]:
                self.visit(G, w)

    def visit(self, G, v):
        self.marked[v] = True
        for e in G.adj(v):
            w = e.other(v)
            if not self.marked[w]:
                self.minpq.enqueue(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
38
39			class LazyPrimMST(MST):
40			tree = None
41			marked = None
42			minpq = None
43
44			def __init__(self, G):
45			self.minpq = MinPQ.create()
46			self.tree = Bag()
47			vertex_count = G.vertex_count()
48			self.marked = [False] * vertex_count
49			self.visit(G, 0)
50
51			while not self.minpq.is_empty() and self.tree.size() < vertex_count-1:
52			edge = self.minpq.del_min()
53			v = edge.start()
54			w = edge.end()
55			if self.marked[v] and self.marked[w]:
56			continue
57			self.tree.add(edge)
58			if not self.marked[v]:
59			self.visit(G, v)
60			if not self.marked[w]:
61			self.visit(G, w)
62
63			def visit(self, G, v):
64			self.marked[v] = True
65			for e in G.adj(v):
66			w = e.other(v)
67			if not self.marked[w]:
68			self.minpq.enqueue(e)
69
70			def spanning_tree(self):
71			return self.tree.iterate()
72
73

chen0040 / pyalgs

Push — master ( 6ecd56...a35e0e )

LazyPrimMST.__init__() B

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like

LazyPrimMST.init() B