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


def builtRandomTransit (n):
    f = []
    for i in range(n):
        f.append([0] * n)
   
    for i in range(n):
        for j in range(n):
            f[i][j]=np.random.randint(10)+1
            if i==j:
                f[i][j]=0
    return f

def getMinFlow (C):
    if len(C)==1:
        return 0
    min_flow = np.inf
    for i in range(len(C)-1):
        if G[C[i]][C[i+1]]['capacity']<min_flow:
            min_flow = G[C[i]][C[i+1]]['capacity']
    return min_flow

def getKPath (C,p):
    d = 0
    for i in range(len(C)-1):
        d += distance.euclidean(p[C[i]],p[C[i+1]])
    return d/distance.euclidean(p[C[0]],p[C[-1]])
    
def new_paths(G,edge):
    for u,v,d in G.edges(data=True):
        if d['capacity']<=0:
            G.remove_edge(G[u][v])

def simplexNewPaths (G, old_paths,edge,points,capacity,V):
    G.remove_edge (edge[0],edge[1])
    new_paths = []
    k = []
    for p in old_paths:
        new_paths.append (nx.shortest_path(G,p[0],p[-1]))
        k.append(getKPath(p,points))
    print ("Change paths",new_paths)
    for p in new_paths:
        k.append(getKPath(p,points))
    size = len(old_paths)
    A_e = []
    A_u = [[]]
    b_u = [capacity]
    b_e = []
    for i in range(size):
        A_e.append([])
        b_e.append(V[old_paths[i][0]][old_paths[i][-1]])
        for j in range(size*2):
            if j==2*i or j==2*i+1:
                A_e[i].append(1)
            else:
                A_e[i].append(0)
    for j in range(size*2):
        if j%2==0:
            A_u[0].append(1)
        else:
            A_u[0].append(0)
    res = linprog(k, A_ub=A_u, b_ub=b_u, A_eq = A_e, b_eq=b_e,bounds=(0, None))
    print('Optimal value:', res.fun, '\nX:', res.x)
 
#Создание и отрисовка случайного графа при помощи триангуляции Делоне
N = 6
p = shed.builtPoints(N,10,10)
tri = Delaunay(p)
e,f = shed.getEdgesDelaunay(tri)

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(50)+1,flow=[],problem = True)   
           
positions_vertexes = [(p[i][0], p[i][1]) for i in range(N)]
edge_labels=dict([((u,v,),(d['capacity'])) for u,v,d in G.edges(data=True)])
nx.draw_networkx_edge_labels(G,positions_vertexes,edge_labels=edge_labels,label_pos=0.75)
nx.draw_networkx(G, positions_vertexes, with_labels=True, arrows=True, node_color='Red')
plt.show()

#Создание случайной матрциы перевозок
V = builtRandomTransit(N)
shed.pprint (V)

#Поиск всех кратчайших путей
path = nx.all_pairs_dijkstra_path(G)
print (path)
#for i, u in path.items():
#    for j, v in u.items():
#        path[i][j]=(path[i][j], getMinFlow(path[i][j]),getKPath(path[i][j],p))

for i in range(N):   
    for j in range(N):
        for k in range(len(path[i][j])-1):
#            G[path[i][j][k]][path[i][j][k+1]]['capacity'] -= V[i][j]
            G[path[i][j][k]][path[i][j][k+1]]['flow'].append(path[i][j])

edge_labels=dict([((u,v,),(d['capacity'])) for u,v,d in G.edges(data=True)])
nx.draw_networkx_edge_labels(G,positions_vertexes,edge_labels=edge_labels,label_pos=0.75)
nx.draw_networkx(G, positions_vertexes, with_labels=True, arrows=True, node_color='Red')
plt.show()
#
#for i, u in path.items():
#    for j, v in u.items():
#        print (path[i][j], getMinFlow(path[i][j]), V[i][j])

for u,v,d in G.edges(data=True):
    sum_flow = sum([V[paths_edge[0]][paths_edge[-1]] for paths_edge in d['flow'] ])
    if sum_flow>d['capacity']:
        print (u,v,d['capacity'],d['flow'],sum_flow)
        simplexNewPaths(G,d['flow'],(u,v),p, d['capacity'],V)