#!/usr/bin/env python3

import random


class Graph(object):

    INFINITY = 32767

    __name = "Graph"
    __first_vertex = None
    __info = 0

    def __init__(self, name):
        self.__name = name

    def get_name(self):
        return self.__name

    def set_name(self, name):
        self.__name = name

    def get_first_vertex(self):
        return self.__first_vertex

    def set_first_vertex(self, vertex):
        self.__first_vertex = vertex

    def get_info(self):
        return self.__info

    def set_info(self, info):
        self.__info = info

    def __str__(self):
        nl = "\n"
        res = nl + self.get_name()
        v = self.get_first_vertex()
        while v:
            res += nl + str(v) + " -->"
            a = v.get_first_out_arc()
            while a:
                res += " " + str(a)
                res += "(" + v.get_name() + "->" + a.get_target(). \
                    get_name() + ") "
                a = a.get_next()
            v = v.get_next()
        return res

    def matrix(self):
        v = self.get_first_vertex()
        n = 0
        while v:
            v.set_info(n)
            n += 1
            v = v.get_next()
        res = [[0] * n for row in range(n)]
        v = self.get_first_vertex()
        while v:
            a = v.get_first_out_arc()
            while a:
                i = v.get_info()
                j = a.get_target().get_info()
                res[i][j] += 1
                a = a.get_next()
            v = v.get_next()
        return res

    def create_vertex(self, name):
        res = Vertex(name)
        res.set_next(self.get_first_vertex())
        self.set_first_vertex(res)
        return res

    def create_arc(self, name, fr, to):
        res = Arc(name)
        res.set_next(fr.get_first_out_arc())
        fr.set_first_out_arc(res)
        res.set_target(to)
        return res

    def create_random_tree(self, number_of_vertices):
        if number_of_vertices < 1:
            return
        vlist = []
        for from_i in range(number_of_vertices):
            name = "v" + str(number_of_vertices - from_i)
            vlist.append(self.create_vertex(name))
            if from_i > 0:
                to_i = random.randint(0, from_i - 1)
                from_v = vlist[from_i]
                to_v = vlist[to_i]
                self.create_arc("a" + to_v.get_name() +
                                "_" + from_v.get_name(), to_v, from_v)
                self.create_arc("a" + from_v.get_name() +
                                "_" + to_v.get_name(), from_v, to_v)

    def create_random_simplegraph(self, number_of_vertices, number_of_edges):
        self.set_first_vertex(None)
        if number_of_vertices < 1:
            return
        if (number_of_edges < number_of_vertices - 1) or \
                (number_of_edges > number_of_vertices * (number_of_vertices - 1) / 2):
            raise ValueError("Wrong number of edges: " + str(number_of_edges))
        self.create_random_tree(number_of_vertices)
        connected = self.matrix()
        vlist = []
        v = self.get_first_vertex()
        while v:
            vlist.append(v)
            v = v.get_next()
        remaining_edges = number_of_edges - number_of_vertices + 1
        while remaining_edges > 0:
            i_v1 = random.randint(0, number_of_vertices - 1)
            i_v2 = random.randint(0, number_of_vertices - 1)
            if i_v1 == i_v2:
                continue
            if (connected[i_v1][i_v2] > 0) or (connected[i_v2][i_v1] > 0):
                continue
            v1 = vlist[i_v1]
            v2 = vlist[i_v2]
            self.create_arc("a" + v1.get_name() +
                            "_" + v2.get_name(), v1, v2)
            self.create_arc("a" + v2.get_name() +
                            "_" + v1.get_name(), v2, v1)
            connected[i_v1][i_v2] = 1
            connected[i_v2][i_v1] = 1
            remaining_edges -= 1

    def create_random_acyclic(self, number_of_vertices):
        if number_of_vertices < 1:
            return
        vlist = []
        for from_i in range(number_of_vertices):
            name = "v" + str(number_of_vertices - from_i)
            vlist.append(self.create_vertex(name))
            if from_i > 0:
                to_i = random.randint(0, from_i - 1)
                from_v = vlist[from_i]
                to_v = vlist[to_i]
                if random.random() < 0.5:
                    self.create_arc("a" + to_v.get_name() +
                                    "_" + from_v.get_name(), to_v, from_v)
                else:
                    self.create_arc("a" + from_v.get_name() +
                                    "_" + to_v.get_name(), from_v, to_v)

    def generate_lengths(self, minlen, maxlen):
        v = self.get_first_vertex()
        while v:
            a = v.get_first_out_arc()
            while a:
                lg = random.randint(minlen, maxlen)
                a.set_info(lg)
                a = a.get_next()
            v = v.get_next()

    def dist_matrix(self):
        v = self.get_first_vertex()
        n = 0
        while v:
            v.set_info(n)
            n += 1
            v = v.get_next()
        res = [[0] * n for row in range(n)]
        v = self.get_first_vertex()
        max_len = 0
        while v:
            a = v.get_first_out_arc()
            while a:
                i = v.get_info()
                j = a.get_target().get_info()
                res[i][j] = a.get_info()
                max_len = max(max_len, res[i][j])
                a = a.get_next()
            v = v.get_next()
        n = len(res)
        Graph.INFINITY = max_len * n + 1
        for i in range(0, n):
            for j in range(0, n):
                if res[i][j] <= 0:
                    res[i][j] = Graph.INFINITY
            res[i][i] = 0
        return res

    @staticmethod
    def floyd_warshall(m):
        n = len(m)
        if n > 0:
            for k in range(0, n):
                for i in range(0, n):
                    for j in range(0, n):
                        new = m[i][k] + m[k][j]
                        if new < m[i][j]:
                            m[i][j] = new

    def topol_sort(self):
        cycle_found = False
        order = []
        n = 0
        v = self.get_first_vertex()
        while v:
            v.set_info(0)
            n = n + 1
            v = v.get_next()
        v = self.get_first_vertex()
        while v:
            a = v.get_first_out_arc()
            while a:
                to = a.get_target()
                to.set_info(to.get_info()+1)
                a = a.get_next()
            v = v.get_next()
        start = []
        v = self.get_first_vertex()
        while v:
            if v.get_info() == 0:
                start.append(v)
            v = v.get_next()
        if len(start) == 0:
            cycle_found = True
        while not cycle_found and len(start) > 0:
            cur = start.pop()
            order.append(cur)
            aout = cur.get_first_out_arc()
            while aout:
                ato = aout.get_target()
                ato.set_info(ato.get_info()-1)
                if ato.get_info() <= 0:
                    start.append(ato)
                aout = aout.get_next()
        if len(order) != n:
            cycle_found = True
        if cycle_found:
            v = self.get_first_vertex()
            while v:
                v.set_info(0)
                v = v.get_next()
        else:
            i = 0
            for v1 in order:
                i = i + 1
                v1.set_info(i)

    def traverse(self, source):
        v = self.get_first_vertex()
        source_exists = False
        while v:
            v.set_info(0)  # white
            if v == source:
                source_exists = True
            v = v.get_next()
        vq = []
        if source_exists:
            vq.append(source)
            source.set_info(1)  # gray
        else:
            raise ValueError("Wrong source vertex")
        while vq:
            vert = vq.pop()  # LIFO (DFS) pop()  vs. FIFO (BFS) pop(0)
            print(vert.get_name(), end=' ')  # process vert
            vert.set_info(2)  # black
            a = vert.get_first_out_arc()
            while a:
                w = a.get_target()
                if w.get_info() == 0:  # white?
                    vq.append(w)
                    w.set_info(1)  # gray
                a = a.get_next()

    def shortest_paths_from(self, source):
        n = 0
        maxlen = 0
        source_found = False
        v = self.get_first_vertex()
        while v:
            if v == source:
                source_found = True
            n = n + 1
            a = v.get_first_out_arc()
            while a:
                maxlen = max(maxlen, a.get_info())
                a = a.get_next()
            v = v.get_next()
        Graph.INFINITY = n * maxlen + 1
        if source_found:
            v = self.get_first_vertex()
            while v:
                v.set_previous(None)
                v.set_info(Graph.INFINITY)
                v = v.get_next()
            source.set_info(0)
            vq = [source]
            while vq:
                minv = None
                minlen = Graph.INFINITY
                for vert in vq:
                    if vert.get_info() < minlen:
                        minv = vert
                        minlen = minv.get_info()
                vq.remove(minv)
                a = minv.get_first_out_arc()
                while a:
                    to = a.get_target()
                    newlen = minlen + a.get_info()
                    if to.get_info() >= Graph.INFINITY:
                        vq.append(to)
                    if newlen < to.get_info():
                        to.set_info(newlen)
                        to.set_previous(minv)
                    a = a.get_next()
            # display the result
            v = self.get_first_vertex()
            print('shortest paths:')
            while v:
                print(str(v.get_info()) + ' ' + v.get_name(), end=' ')
                bv = v.get_previous()
                while bv:
                    print(bv.get_name(), end=' ')
                    bv = bv.get_previous()
                print()
                v = v.get_next()
        else:
            raise ValueError("Source vertex not found:", source)

    def from_matrix(self, mat):
        n = len(mat)
        if n > 0:
            vlist = []
            for k in range(n-1, -1, -1):  # create_vertex reverses list
                vk = self.create_vertex("v" + str(k+1))
                vlist.insert(0, vk)
            for i in range(0, n):
                for j in range(n-1, -1, -1):  # create_arc reverses list
                    for d in range(0, mat[i][j]):  # duplicate arcs possible
                        fromv = vlist[i]
                        tov = vlist[j]
                        aname = "a" + fromv.get_name() + "_" + tov.get_name()
                        if d > 0:  # duplicate arc
                            aname = aname + "_" + str(mat[i][j] - d)
                        self.create_arc(aname, fromv, tov)


class Vertex(object):

    __name = "Vertex"
    __first_out_arc = None
    __next = None
    __previous = None
    __info = 0

    def __init__(self, name):
        self.set_name(name)

    def get_name(self):
        return self.__name

    def set_name(self, name):
        self.__name = name

    def get_first_out_arc(self):
        return self.__first_out_arc

    def set_first_out_arc(self, arc):
        self.__first_out_arc = arc

    def get_next(self):
        return self.__next

    def set_next(self, next_vertex):
        self.__next = next_vertex

    def get_previous(self):
        return self.__previous

    def set_previous(self, previous_vertex):
        self.__previous = previous_vertex

    def get_info(self):
        return self.__info

    def set_info(self, info):
        self.__info = info

    def __str__(self):
        return self.get_name() + " " + str(self.get_info())


class Arc(object):

    __name = "Arc"
    __next = None
    __target = None
    __info = 0

    def __init__(self, name):
        self.set_name(name)

    def get_name(self):
        return self.__name

    def set_name(self, name):
        self.__name = name

    def get_next(self):
        return self.__next

    def set_next(self, next_arc):
        self.__next = next_arc

    def get_target(self):
        return self.__target

    def set_target(self, target):
        self.__target = target

    def get_info(self):
        return self.__info

    def set_info(self, info):
        self.__info = info

    def __str__(self):
        return self.get_name() + " " + str(self.get_info())


def main():
    """
    Main method.
    """
    g1 = Graph("G")
    g1.create_random_simplegraph(9, 15)
    g1.generate_lengths(1, 1)
    g1.shortest_paths_from(g1.get_first_vertex())
    print(g1)


if __name__ == '__main__':
    main()