Untitled

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