import random
import numpy as np
# graph edge abstraction
# represents an edge from vertex a to vertex b, its weight is w
class Edge:
def __init__(self, a, b, w):
self.a = a
self.b = b
self.w = w
class Net:
def __init__(self, n):
self.n = n
# array of shape (n,n) filled with zero
self.graph = np.zeros((n, n), dtype=np.double)
# edges of the graph
# data format: (source, dest, weight)
self.edges = list()
# distance from source s to each vertex
# at the beginning, distance[s] is 0 while others are inf
self.distance = list()
# assign value to elements in upper triangular
# then, according to real exchange rule,
# if exchange rate[i, j] = num1 / num2, then
# exchange rate[j, i] should be num2 / num1.
# And, according to the paper, it turns out to detect
# if there exists a negative weighted loop in directed graph.
for i in range(0, n):
for j in range(i, n):
num1 = random.randint(n, n * 10)
num2 = random.randint(n, n * 10)
# save edges
self.edges.append(Edge(i, j, -np.log(num1 / num2)))
self.edges.append(Edge(j, i, -np.log(num2 / num1)))
# bellman-ford algorithm implementation
# reference: https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm
def bellman_ford(self, source=0) -> bool:
# initialize the distances
self.distance = [np.inf for i in range(self.n)]
self.distance[source] = 0
for k in range(self.n - 1):
for edge in self.edges:
if self.distance[edge.a] + edge.w < self.distance[edge.b]:
self.distance[edge.b] = self.distance[edge.a] + edge.w
# check if negative circle exists
for edge in self.edges:
if self.distance[edge.b] > self.distance[edge.a] + edge.w:
return True
return False
if __name__ == "__main__":
print(Net(4).bellman_ford())