import numpy as np import matplotlib pyplot as plt from scipy spatial

import numpy as np
import matplotlib.pyplot as plt
from scipy.spatial import Delaunay
import networkx as nx
from scipy.spatial import distance
from scipy.optimize import linprog
from functools import cmp_to_key


class Path:

    def __init__(self, C, f):
        self.C = C
        self.flow = f

    def getK(self, p):
        d = 0
        for i in range(len(self.C) - 1):
            d += distance.euclidean(p[self.C[i]], p[self.C[i + 1]])
        return d / distance.euclidean(p[self.C[0]], p[self.C[-1]])

    def __repr__(self):
        return " %s<-%s " % (self.C, self.flow)

    def __str__(self):
        return "   %s<-%s   " % (self.C, self.flow)

    def __eq__(self, other):
        if len(self.C) != len(other.C):
            return False
        for i in range(len(self.C)):
            if self.C[i] != other.C[i]:
                return False
        return True


def koefficient(path, points):
    d = 0
    for i in range(len(path) - 1):
        d += distance.euclidean(points[path[i]], points[path[i + 1]])
    return d / distance.euclidean(points[path[0]], points[path[-1]])


def compare(p1, p2):
    return koefficient(p1, p) - koefficient(p2, p)


def simplexNewPaths(G, loupe_paths, V, p):
    print("\n Work simplex method")
    N = len(p)
    k = [i.getK(p) for i in loupe_paths]
    size = len(loupe_paths)
    A_V = [[0 for j in range(size)] for i in range(N * N)]
    for lp in range(len(loupe_paths)):
        i = loupe_paths[lp].C[0]
        j = loupe_paths[lp].C[-1]
        A_V[N * i + j][lp] = 1

    b_V = []
    for i in range(len(V)):
        for j in range(len(V)):
            b_V.append(V[i][j])

    A_e = []
    b_e = []
    for u, v, d in G.edges(data=True):
        A_e_list = list(d['flow'])
        A_e.append([0 for i in range(size)])
        for i in A_e_list:
            A_e[-1][i] = 1
        b_e.append(d['capacity'])

    res = linprog(k, A_ub=A_e, b_ub=b_e, A_eq=A_V, b_eq=b_V, bounds=(0, None))

    print(res.x)
    if res.success is False:
        return None
    return res.x


N = 4
p = []
while len(p) < N:
    x = np.random.randint(0, 10)
    y = np.random.randint(0, 10)
    if [x, y] not in p:
        p.append([x, y])

tri = Delaunay(p)

sim = tri.simplices
edges_of_tri = [[[min(s[i], s[i + 1]), max(s[i], s[i + 1])] for i in range(-1, 2)] for s in sim]
e = []
for et in edges_of_tri:
    for r in et:
        if r not in e:
            e.append(r)

G = nx.DiGraph()
for edge in e:
    G.add_edge(edge[0], edge[1], weight=round(distance.euclidean(p[edge[0]], p[edge[1]]), 3),
               capacity=np.random.randint(10) + 1, flow=set())
    G.add_edge(edge[1], edge[0], weight=round(distance.euclidean(p[edge[0]], p[edge[1]]), 3),
               capacity=np.random.randint(10) + 1, flow=set())

positions_vertexes = [(p[i][0], p[i][1]) for i in range(N)]
V = np.random.randint(0, 5, (N, N))
for i in range(N):
    V[i][i] = 0

nx.draw_networkx(G, positions_vertexes, with_labels=True, arrows=True, node_color='Red')
plt.savefig("mygraph.png")

paths = []
all_paths = []
for i in range(N):
    all_paths.append([])
    for j in range(N):
        if not nx.has_path(G, i, j) and V[i][j] > 0:
            print("Задача не разрешима")
            exit(1)
        else:
            all_paths[i].append(sorted(list(nx.all_simple_paths(G, i, j)), key=cmp_to_key(compare)))
            if i != j:
                paths.append(Path(all_paths[i][j][0], V[i][j]))
                del all_paths[i][j][0]

for i in range(len(paths)):
    for k in range(len(paths[i].C) - 1):
        G[paths[i].C[k]][paths[i].C[k + 1]]['flow'].add(i)

flag_change = True
flag_problem = True
while flag_change and flag_problem:
    resx = simplexNewPaths(G, paths, V, p)

    if resx is not None:
        for i in range(len(resx)):
            paths[i].flow = resx[i]

    flag_change = False
    flag_problem = False
    for u, v, d in G.edges(data=True):
        sum_flow = sum([paths[paths_edge].flow for paths_edge in d['flow']])
        if sum_flow > d['capacity']:
            flag_problem = True
            current_paths = list(d['flow'])
            for route in current_paths:
                if len(all_paths[paths[route].C[0]][paths[route].C[-1]]) > 0:
                    flag_change = True
                    new_path = all_paths[paths[route].C[0]][paths[route].C[-1]][0]
                    del all_paths[paths[route].C[0]][paths[route].C[-1]][0]
                    paths.append(Path(new_path, 0))
                    for i in range(len(new_path) - 1):
                        G[new_path[i]][new_path[i + 1]]['flow'].add(len(paths) - 1)

if not flag_problem:
    print("Задача решена")
    print(V)
    result_paths = [[[] for i in range(N)] for j in range(N)]
    for i in paths:
        if i.flow > 0:
            result_paths[i.C[0]][i.C[-1]].append(i)
    print(result_paths)
    exit(0)
else:
    if not flag_change:
        print("Задача не разрешима, кончились пути")