-
Notifications
You must be signed in to change notification settings - Fork 66
/
bellmanford.py
257 lines (226 loc) · 7.66 KB
/
bellmanford.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
"""
* Copyright 2020, Departamento de sistemas y Computación,
* Universidad de Los Andes
*
* Desarrollado para el curso ISIS1225 - Estructuras de Datos y Algoritmos
*
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*
* Contribución de:
*
* Dario Correal
*
"""
import config
from DISClib.DataStructures import edge as e
from DISClib.ADT import list as lt
from DISClib.ADT import queue as q
from DISClib.ADT import map as map
from DISClib.ADT import graph as g
from DISClib.ADT import stack as st
from DISClib.Algorithms.Graphs import cycles as c
from DISClib.Utils import error as error
import math
assert config
def BellmanFord(graph, source):
"""
Implementa el algoritmo de Bellman-Ford
Args:
graph: El grafo de busqueda
source: El vertice de inicio
Returns:
La estructura search con los caminos de peso mínimos
Raises:
Exception
"""
try:
search = initSearch(graph, source)
map.put(search['distTo'], source, 0.0)
q.enqueue(search['qvertex'], source)
map.put(search['onQ'], source, True)
while (not q.isEmpty(search['qvertex']) and
(not hasNegativecycle(search))):
v = q.dequeue(search['qvertex'])
map.put(search['onQ'], v, False)
relax(graph, search, v)
return search
except Exception as exp:
error.reraise(exp, 'bf:BellmanFord')
def relax(graph, search, v):
"""
Relaja el peso de los arcos del grafo
Args:
search: La estructura de busqueda
v: Vertice desde donde se relajan los pesos
Returns:
El grafo con los arcos relajados
Raises:
Exception
"""
try:
edges = g.adjacentEdges(graph, v)
if edges is not None:
for edge in lt.iterator(edges):
v = e.either(edge)
w = e.other(edge, v)
distv = map.get(search['distTo'], v)['value']
distw = map.get(search['distTo'], w)['value']
distweight = distv + e.weight(edge)
if (distw > distweight):
map.put(search['distTo'], w, distweight)
map.put(search['edgeTo'], w, edge)
if (not map.get(search['onQ'], w)['value']):
q.enqueue(search['qvertex'], w)
map.put(search['onQ'], w, True)
cost = search['cost']
if ((cost % g.numVertices(graph)) == 0):
findneg = findNegativeCycle(graph, search)
if (hasNegativecycle(findneg)):
return
search['cost'] = cost + 1
return search
except Exception as exp:
error.reraise(exp, 'bellman:relax')
def distTo(search, vertex):
"""
Retorna el costo para llegar del vertice
source al vertice vertex.
Args:
search: La estructura de busqueda
vertex: El vertice destino
Returns:
El costo total para llegar de source a
vertex. Infinito si no existe camino
Raises:
Exception
"""
try:
distance = map.get(search['distTo'], vertex)['value']
if distance is None:
return math.inf
return distance
except Exception as exp:
error.reraise(exp, 'bellman:disto')
def hasPathTo(search, vertex):
"""
Indica si hay camino entre source
y vertex
Args:
search: La estructura de busqueda
vertex: El vertice de destino
Returns:
True si existe camino
Raises:
Exception
"""
try:
distance = map.get(search['distTo'], vertex)['value']
return not hasNegativecycle(search) and distance < math.inf
except Exception as exp:
error.reraise(exp, 'bellman:haspathto')
def pathTo(search, vertex):
"""
Retorna el camino entre source y vertex
en una pila.
Args:
search: La estructura de busqueda
vertex: El vertice de destino
Returns:
Una pila con el camino entre source y vertex
Raises:
Exception
"""
try:
if hasPathTo(search, vertex) is False:
return None
path = st.newStack()
while vertex != search['source']:
edge = map.get(search['edgeTo'], vertex)['value']
st.push(path, edge)
vertex = e.either(edge)
return path
except Exception as exp:
error.reraise(exp, 'bellman:pathto')
# ----------------------------------------------
# Funciones Auxiliares
# ----------------------------------------------
def findNegativeCycle(graph, search):
"""
Identifica ciclos negativos en el grafo
"""
try:
vertices = g.vertices(graph)
for vert in lt.iterator(vertices):
edge = map.get(search['edgeTo'], vert)
if (edge is not None):
edge = edge['value']
g.addEdge(search['spt'], e.either(edge),
e.other(edge, e.either(edge)), e.weight(edge))
finder = c.DirectedCycle(search['spt'])
search['cycle'] = not st.isEmpty(c.cycle(finder))
return search
except Exception as exp:
error.reraise(exp, 'bellman:pathto')
def hasNegativecycle(search):
return search['cycle']
def initSearch(graph, source):
"""
Inicializa la estructura de busqueda y deja
todos los arcos en infinito.
Se inserta en la cola el vertice source
Args:
graph: El grafo a examinar
source: El vertice fuente
Returns:
Estructura de busqueda inicializada
Raises:
Exception
"""
try:
search = {
'source': source,
'edgeTo': None,
'distTo': None,
'qvertex': None,
'onQ': None,
'cost': 0,
'spt': None,
'cycle': False
}
search['edgeTo'] = map.newMap(numelements=g.numVertices(graph),
maptype='PROBING',
cmpfunction=graph['cmpfunction']
)
search['distTo'] = map.newMap(numelements=g.numVertices(graph),
maptype='PROBING',
cmpfunction=graph['cmpfunction'])
search['onQ'] = map.newMap(numelements=g.numVertices(graph),
maptype='PROBING',
cmpfunction=graph['cmpfunction']
)
search['spt'] = g.newGraph(size=g.numVertices(graph),
directed=True,
cmpfunction=graph['cmpfunction']
)
vertices = g.vertices(graph)
for vert in lt.iterator(vertices):
map.put(search['distTo'], vert, math.inf)
map.put(search['onQ'], vert, False)
g.insertVertex(search['spt'], vert)
newq = q.newQueue()
search['qvertex'] = newq
return search
except Exception as exp:
error.reraise(exp, 'bellman:init')