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

Completed

Push — master ( a35e0e...167e73 )

by Xianshun

created 2017-04-27 03:47 UTC

EagerPrimMST.spanning_tree() A

↳ Parent: EagerPrimMST

Complexity

Conditions

Size

Total Lines

Duplication

Lines	0
Ratio	0 %

Importance

Changes	1
Bugs	0	Features	0

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

from abc import ABCMeta, abstractmethod

from pyalgs.algorithms.commons.union_find import UnionFind
from pyalgs.algorithms.commons.util import less
from pyalgs.data_structures.commons.bag import Bag
from pyalgs.data_structures.commons.priority_queue import MinPQ, IndexMinPQ


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


class EagerPrimMST(MST):
    path = None
    pq = None
    marked = None

    def __init__(self, G):
        vertex_count = G.vertex_count()
        self.pq = IndexMinPQ(vertex_count)
        self.path = Bag()
        self.marked = [False] * vertex_count

        self.visit(G, 0)

        while not self.pq.is_empty() and self.path.size() < vertex_count - 1:
            e = self.pq.min_key()
            w = self.pq.del_min()
            self.path.add(e)
            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]:
                if self.pq.contains_index(w):
                    old_e = self.pq.get(w)
                    if less(e, old_e):
                        self.pq.decrease_key(w, e)
                else:
                    self.pq.insert(w, e)

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


1			from abc import ABCMeta, abstractmethod
2
3			from pyalgs.algorithms.commons.union_find import UnionFind
4			from pyalgs.algorithms.commons.util import less
5			from pyalgs.data_structures.commons.bag import Bag
6			from pyalgs.data_structures.commons.priority_queue import MinPQ, IndexMinPQ
7
8
9			class MST(object):
10			__metaclass__ = ABCMeta
11
12			@abstractmethod
13			def spanning_tree(self):
14			pass
15
16
17			class KruskalMST(MST):
18			tree = None
19
20			def __init__(self, G):
21			minpq = MinPQ.create()
22			self.tree = Bag()
23			for e in G.edges():
24			minpq.enqueue(e)
25
26			uf = UnionFind.create(G.vertex_count())
27
28			while not minpq.is_empty() and self.tree.size() < G.vertex_count() - 1:
29			e = minpq.del_min()
30			v = e.start()
31			w = e.end()
32			if not uf.connected(v, w):
33			uf.union(v, w)
34			self.tree.add(e)
35
36			def spanning_tree(self):
37			return self.tree.iterate()
38
39
40			class LazyPrimMST(MST):
41			tree = None
42			marked = None
43			minpq = None
44
45			def __init__(self, G):
46			self.minpq = MinPQ.create()
47			self.tree = Bag()
48			vertex_count = G.vertex_count()
49			self.marked = [False] * vertex_count
50			self.visit(G, 0)
51
52			while not self.minpq.is_empty() and self.tree.size() < vertex_count - 1:
53			edge = self.minpq.del_min()
54			v = edge.start()
55			w = edge.end()
56			if self.marked[v] and self.marked[w]:
57			continue
58			self.tree.add(edge)
59			if not self.marked[v]:
60			self.visit(G, v)
61			if not self.marked[w]:
62			self.visit(G, w)
63
64			def visit(self, G, v):
65			self.marked[v] = True
66			for e in G.adj(v):
67			w = e.other(v)
68			if not self.marked[w]:
69			self.minpq.enqueue(e)
70
71			def spanning_tree(self):
72			return self.tree.iterate()
73
74
75			class EagerPrimMST(MST):
76			path = None
77			pq = None
78			marked = None
79
80			def __init__(self, G):
81			vertex_count = G.vertex_count()
82			self.pq = IndexMinPQ(vertex_count)
83			self.path = Bag()
84			self.marked = [False] * vertex_count
85
86			self.visit(G, 0)
87
88			while not self.pq.is_empty() and self.path.size() < vertex_count - 1:
89			e = self.pq.min_key()
90			w = self.pq.del_min()
91			self.path.add(e)
92			if not self.marked[w]:
93			self.visit(G, w)
94
95			def visit(self, G, v):
96			self.marked[v] = True
97			for e in G.adj(v):
98			w = e.other(v)
99			if not self.marked[w]:
100			if self.pq.contains_index(w):
101			old_e = self.pq.get(w)
102			if less(e, old_e):
103			self.pq.decrease_key(w, e)
104			else:
105			self.pq.insert(w, e)
106
107			def spanning_tree(self):
108			return self.path.iterate()
109

chen0040 / pyalgs

Push — master ( a35e0e...167e73 )

EagerPrimMST.spanning_tree() A

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like