Untitled
unknown
python
10 months ago
2.1 kB
9
Indexable
Never
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())