TopologicalSortShortestPath.path_length_to() - Code Metrics - chen0040/pyalgs - Measure and Improve Code Quality continuously with Scrutinizer

TopologicalSortShortestPath.path_length_to() A
last analyzed 2017-05-26 05:56 UTC

↳ Parent: TopologicalSortShortestPath

Complexity

Conditions

Size

Total Lines

Duplication

Lines	0
Ratio	0 %

Importance

Changes	2
Bugs	0	Features	0

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

from abc import ABCMeta, abstractmethod

from pyalgs.algorithms.commons import util
from pyalgs.algorithms.graphs.topological_sort import DepthFirstOrder
from pyalgs.data_structures.commons.priority_queue import IndexMinPQ
from pyalgs.data_structures.commons.stack import Stack
from pyalgs.data_structures.graphs.graph import Digraph, Graph, EdgeWeightedGraph


class ShortestPath(object):
    __metaclass__ = ABCMeta

    @abstractmethod
    def shortestPathTo(self, v):
        pass

    @abstractmethod
    def hasPathTo(self, v):
        pass

    @abstractmethod
    def path_length_to(self, v):
        pass


class DijkstraShortestPath(ShortestPath):
    edgeTo = None
    s = 0
    pq = None
    cost = None

    def __init__(self, G, s):
        if isinstance(G, Graph):
            raise ValueError('Graph must be edge weighted')
        if isinstance(G, Digraph):
            raise ValueError('Graph must be edge weighted')
        if isinstance(G, EdgeWeightedGraph):
            G = G.to_edge_weighted_digraph()

        vertex_count = G.vertex_count()
        self.pq = IndexMinPQ(vertex_count)
        self.s = s

        self.marked = [False] * vertex_count
        self.edgeTo = [None] * vertex_count
        self.cost = [float("inf")] * vertex_count

        self.cost[s] = 0
        self.pq.insert(s, 0.0)

        while not self.pq.is_empty():
            v = self.pq.del_min()
            self.marked[v] = True
            for e in G.adj(v):
                self.relax(e)

    def relax(self, e):
        v = e.start()
        w = e.end()
        if self.cost[w] > self.cost[v] + e.weight:
            self.cost[w] = self.cost[v] + e.weight
            self.edgeTo[w] = e
            if self.pq.contains_index(w):
                self.pq.decrease_key(w, self.cost[w])
            else:
                self.pq.insert(w, self.cost[w])

    def hasPathTo(self, v):
        return self.marked[v]

    def shortestPathTo(self, v):
        path = Stack.create()
        x = v
        while x != self.s:
            path.push(self.edgeTo[x])
            x = self.edgeTo[x].start()

        return path.iterate()

    def path_length_to(self, v):
        return self.cost[v]


class TopologicalSortShortestPath(ShortestPath):
    marked = None
    edgeTo = None
    cost = None
    s = 0

    def __init__(self, G, s):
        vertex_count = G.vertex_count()
        self.marked = [False] * vertex_count
        self.edgeTo = [None] * vertex_count
        self.cost = [float('inf')] * vertex_count
        self.s = s

        dfo = DepthFirstOrder(G)
        orders = dfo.postOrder()

        self.cost[s] = 0

        for v in orders:
            for e in G.adj(v):
                self.relax(e)

    def relax(self, e):
        v = e.start()
        w = e.end()
        if self.cost[w] > self.cost[v] + e.weight:
            self.cost[w] = self.cost[v] + e.weight
            self.edgeTo[w] = e
            self.marked[w] = True

    def shortestPathTo(self, v):
        path = Stack.create()
        x = v
        while x != self.s:
            path.push(self.edgeTo[x])
            x = self.edgeTo[x].start()

        return path.iterate()

    def hasPathTo(self, v):
        return self.marked[v]

    def path_length_to(self, v):
        return self.cost[v]


class BellmanFordShortestPath(ShortestPath):

    s = None
    edgeTo = None
    cost = None
    negativeDirectedCycle = False
    vertexCount = 0

    def __init__(self, G, s):
        self.vertexCount = G.vertex_count()
        self.cost = [float('inf')] * self.vertexCount
        self.edgeTo = [None] * self.vertexCount

        self.cost[s] = 0
        self.s = s

        for i in range(self.vertexCount):
            for v in range(self.vertexCount):
                for e in G.adj(v):
                    self.relax(e)

        for v in range(self.vertexCount):
            for e in G.adj(v):
                if self.relax(e):
                    self.negativeDirectedCycle = True

    def relax(self, e):
        v = e.start()
        w = e.end()

        if self.cost[w] > self.cost[v] + e.weight:
            self.cost[w] = self.cost[v] + e.weight
            self.edgeTo[w] = e
            return True
        return False

    def hasNegativeDirectedCycle(self):
        return self.negativeDirectedCycle

    def shortestPathTo(self, v):
        path = Stack.create()
        x = v
        counter = 0
        while x != self.s:
            path.push(self.edgeTo[x])
            if self.edgeTo[x] is None:
                return None
            x = self.edgeTo[x].start()
            counter += 1
            if counter > self.vertexCount:
                return None

        return path.iterate()

    def hasPathTo(self, v):
        return self.shortestPathTo(v) is not None

    def path_length_to(self, v):
        return self.cost[v]


1			from abc import ABCMeta, abstractmethod
2
3			from pyalgs.algorithms.commons import util
4			from pyalgs.algorithms.graphs.topological_sort import DepthFirstOrder
5			from pyalgs.data_structures.commons.priority_queue import IndexMinPQ
6			from pyalgs.data_structures.commons.stack import Stack
7			from pyalgs.data_structures.graphs.graph import Digraph, Graph, EdgeWeightedGraph
8
9
10			class ShortestPath(object):
11			__metaclass__ = ABCMeta
12
13			@abstractmethod
14			def shortestPathTo(self, v):
15			pass
16
17			@abstractmethod
18			def hasPathTo(self, v):
19			pass
20
21			@abstractmethod
22			def path_length_to(self, v):
23			pass
24
25
26			class DijkstraShortestPath(ShortestPath):
27			edgeTo = None
28			s = 0
29			pq = None
30			cost = None
31
32			def __init__(self, G, s):
33			if isinstance(G, Graph):
34			raise ValueError('Graph must be edge weighted')
35			if isinstance(G, Digraph):
36			raise ValueError('Graph must be edge weighted')
37			if isinstance(G, EdgeWeightedGraph):
38			G = G.to_edge_weighted_digraph()
39
40			vertex_count = G.vertex_count()
41			self.pq = IndexMinPQ(vertex_count)
42			self.s = s
43
44			self.marked = [False] * vertex_count
45			self.edgeTo = [None] * vertex_count
46			self.cost = [float("inf")] * vertex_count
47
48			self.cost[s] = 0
49			self.pq.insert(s, 0.0)
50
51			while not self.pq.is_empty():
52			v = self.pq.del_min()
53			self.marked[v] = True
54			for e in G.adj(v):
55			self.relax(e)
56
57			def relax(self, e):
58			v = e.start()
59			w = e.end()
60			if self.cost[w] > self.cost[v] + e.weight:
61			self.cost[w] = self.cost[v] + e.weight
62			self.edgeTo[w] = e
63			if self.pq.contains_index(w):
64			self.pq.decrease_key(w, self.cost[w])
65			else:
66			self.pq.insert(w, self.cost[w])
67
68			def hasPathTo(self, v):
69			return self.marked[v]
70
71			def shortestPathTo(self, v):
72			path = Stack.create()
73			x = v
74			while x != self.s:
75			path.push(self.edgeTo[x])
76			x = self.edgeTo[x].start()
77
78			return path.iterate()
79
80			def path_length_to(self, v):
81			return self.cost[v]
82
83
84			class TopologicalSortShortestPath(ShortestPath):
85			marked = None
86			edgeTo = None
87			cost = None
88			s = 0
89
90			def __init__(self, G, s):
91			vertex_count = G.vertex_count()
92			self.marked = [False] * vertex_count
93			self.edgeTo = [None] * vertex_count
94			self.cost = [float('inf')] * vertex_count
95			self.s = s
96
97			dfo = DepthFirstOrder(G)
98			orders = dfo.postOrder()
99
100			self.cost[s] = 0
101
102			for v in orders:
103			for e in G.adj(v):
104			self.relax(e)
105
106			def relax(self, e):
107			v = e.start()
108			w = e.end()
109			if self.cost[w] > self.cost[v] + e.weight:
110			self.cost[w] = self.cost[v] + e.weight
111			self.edgeTo[w] = e
112			self.marked[w] = True
113
114			def shortestPathTo(self, v):
115			path = Stack.create()
116			x = v
117			while x != self.s:
118			path.push(self.edgeTo[x])
119			x = self.edgeTo[x].start()
120
121			return path.iterate()
122
123			def hasPathTo(self, v):
124			return self.marked[v]
125
126			def path_length_to(self, v):
127			return self.cost[v]
128
129
130			class BellmanFordShortestPath(ShortestPath):
131
132			s = None
133			edgeTo = None
134			cost = None
135			negativeDirectedCycle = False
136			vertexCount = 0
137
138			def __init__(self, G, s):
139			self.vertexCount = G.vertex_count()
140			self.cost = [float('inf')] * self.vertexCount
141			self.edgeTo = [None] * self.vertexCount
142
143			self.cost[s] = 0
144			self.s = s
145
146			for i in range(self.vertexCount):
147			for v in range(self.vertexCount):
148			for e in G.adj(v):
149			self.relax(e)
150
151			for v in range(self.vertexCount):
152			for e in G.adj(v):
153			if self.relax(e):
154			self.negativeDirectedCycle = True
155
156			def relax(self, e):
157			v = e.start()
158			w = e.end()
159
160			if self.cost[w] > self.cost[v] + e.weight:
161			self.cost[w] = self.cost[v] + e.weight
162			self.edgeTo[w] = e
163			return True
164			return False
165
166			def hasNegativeDirectedCycle(self):
167			return self.negativeDirectedCycle
168
169			def shortestPathTo(self, v):
170			path = Stack.create()
171			x = v
172			counter = 0
173			while x != self.s:
174			path.push(self.edgeTo[x])
175			if self.edgeTo[x] is None:
176			return None
177			x = self.edgeTo[x].start()
178			counter += 1
179			if counter > self.vertexCount:
180			return None
181
182			return path.iterate()
183
184			def hasPathTo(self, v):
185			return self.shortestPathTo(v) is not None
186
187			def path_length_to(self, v):
188			return self.cost[v]
189

chen0040 / pyalgs

TopologicalSortShortestPath.path_length_to() A last analyzed 2017-05-26 05:56 UTC

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like

TopologicalSortShortestPath.path_length_to() A
last analyzed 2017-05-26 05:56 UTC