Untitled

# sahebi

from random import randint, choice
import time
import matplotlib.pyplot as plt

class Graph:

    def __init__(self, size, edges = [], weights = []):

        self.size = size
        self.edges = edges if edges else [[] for _ in range(size)]
        self.weights = weights if weights else [[] for _ in range(size)]

    def __str__(self):
        return 'Graph:\nEdges: %s\nWeights: %s\n' % (self.edges, self.weights)

    @staticmethod
    def random(size = 5, degs = [1, 3], weights = [1, 5, 20]):

       g = Graph(size)

       # removing impossible degs
       tmp = []
       for deg in degs:
           if deg < size:
               tmp.append(deg)
       degs = tmp
       if not degs:
           g.size = -1
           return g

       # create one path to every vertex
       last = 0
       nexts = [i for i in range(1, size)]
       while nexts:
           r = randint(0, len(nexts) - 1)
           g.edges[last].append(nexts[r])
           last = nexts[r]
           del nexts[r]
       g.edges[last].append(randint(0, size - 1))

       # create extra veteces
       for n, e in enumerate(g.edges):
           nexts = []
           for i in range(size):
               if i not in e and n != i:
                   nexts.append(i)
           for i in range(1, choice(degs)):
               e.append(nexts.pop(randint(0, len(nexts) - 1)))

       # put weights
       for i in range(size):
           for _ in g.edges[i]:
               g.weights[i].append(choice(weights))

       return g

    def dijkstra(self):

        print('Dijkstra:')
        unvis = [i for i in range(self.size)]
        prev = [None] * self.size
        dist = [float('inf')] * self.size
        cur = dist[0] = 0
        while unvis:
            unvis.remove(cur)
            for i, v in enumerate(self.edges[cur]):
                if v in unvis:
                    new_dist = dist[cur] + self.weights[cur][i]
                    if new_dist < dist[v]:
                        dist[v] = new_dist
                        prev[v] = cur
            mini = float('inf')
            for i, d in enumerate(dist):
                if d < mini and i in unvis:
                    mini = d
                    cur = i
            print('Previous: %s\nDistances: %s\n' % (prev, dist))

    def bellmanford(self):

        print('Bellmanford:')
        prev = [None] * self.size
        dist = [float('inf')] * self.size
        dist[0] = 0
        for _ in range(self.size - 1):
            for i, e in enumerate(self.edges):
                for j, v in enumerate(e):
                    new_dist = dist[i] + self.weights[i][j]
                    if new_dist < dist[v]:
                        dist[v] = new_dist
                        prev[v] = i
            print('Previous: %s\nDistances: %s\n' % (prev, dist))

    def floydwarshall(self):

        print('Floydwarshall')
        dist = [[float('inf') for _ in range(self.size)][:] for _ in range(self.size)]

        for i, e in enumerate(self.edges):
            for j, v in enumerate(e):
                dist[i][v] = self.weights[i][j]

        for k in range(self.size):
            for i in range(self.size):
                for j in range(self.size):
                    new_dist = dist[i][k] + dist[k][j]
                    if new_dist < dist[i][j]:
                        dist[i][j] = new_dist
            
            print('matrix %d:' % k)
            for x in dist:
                for y in x:
                    print(('%3d\t' % y) if y < float('inf') else 'inf\t', end = '')
                print('\n')


    def compare(self):
        if self.size  == -1:
            return 0, 0, 0

        t = time.time()
        self.dijkstra()
        td = time.time() - t

        t = time.time()
        self.bellmanford()
        tb = time.time() - t

        t = time.time()
        self.floydwarshall()
        tf = time.time() - t
        
        return td, tb, tf

def main(max_size, degs, weights):

    graphs = [Graph.random(i, degs, weights) for i in range(1, max_size)]
    yd, yb, yf = [], [], []
    x = [i+1 for i in range(1, max_size)]
    for g in graphs:
        print(g)
        td, tb, tf = g.compare()
        yd.append(td)
        yb.append(tb)
        yf.append(tf)
    plt.plot(x, yd, label = 'Dijkstra')
    plt.plot(x, yb, label = 'Bellman-ford')
    plt.plot(x, yf, label = 'Floyd-warshal')
    plt.legend(loc='upper center')
    plt.xlabel('Size')
    plt.ylabel('Time')
    plt.show()

main(int(input('Write number of verteces of bigges graph: ')),
     [int(d) for d in input('Write posdible degrees of each vertex: ').split(' ')],
     [int(w) for w in input('Write weights of each vertex: ').split(' ')])