import numpy as np import shed import matplotlib pyplot as plt from sc

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


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 getMinFlow(self):
        if len(self.C)==1:
            return 0
        min_flow = np.inf
        for i in range(len(self.C)-1):
            if G[self.C[i]][self.C[i+1]]['capacity']<min_flow:
                min_flow = G[self.C[i]][self.C[i+1]]['capacity']
        return min_flow
    
    def complete(self,v,G):
        for i in range(len(self.C)-1):
            if G[self.C[i]][self.C[i+1]]['problem']:
                return False
        if self.getMinFlow()>v:
            return True
        else:
            return False
 

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(5)+1
            if i==j:
                f[i][j]=0
    return f

def check(lst, sub):
   for i in range(0, len(lst)):
       if lst[i:i+len(sub)] == sub:
           return True
   return False
    
def simplexNewPaths (G, loupe_paths,  loupe_edges, V, capacity):
    print ("*"*45)
    
    loupe_paths = [i.C for i in loupe_paths]
    print(loupe_paths, loupe_edges)
    size = len(loupe_paths)
    A_e = []
    A_u = []
   
    b_e = []
    d = {}
    
    for i in loupe_paths:
        if d.get((i[0],i[-1])) is None:
            d[(i[0],i[-1])] = []
        if i not in d[(i[0],i[-1])]:
            d[(i[0],i[-1])].append(i)
            
    print ("+"*50)
    new_paths = []
    new_d = {}
    for key, value in d.items():
        if len(value)>1:
            new_d[key] = value

            print("{0}: {1}".format(key,value))  
            A_e.append([0]*size)
            for j in value:
                new_paths.append(j)
                xxx = list(new_d.keys()).index(key)
                yyy = new_paths.index(j)
                A_e[xxx][yyy] = 1
                   
            b_e.append(V[key[0]][key[1]])
    
    shed.ppprint(A_e, len(A_e), size)
    print(b_e)      
    
    for i in loupe_edges:
        A_u.append([0]*size)
        for j in new_paths:
            if check(j,i):
                A_u[-1][new_paths.index(j)]=1
    shed.ppprint(A_u, len(A_u), size)           
  
    k = [np.random.random()+1 for i in range(size)]
    print(k)
    res = linprog(k, A_ub=A_e, b_ub=b_e, A_eq = A_u, b_eq=capacity,bounds=(0, None))
    print(res.x)
#    return old_paths, new_paths
 
#Создание и отрисовка случайного графа при помощи триангуляции Делоне
N = 6
#p = shed.builtPoints(N,10,10)
#print(p)
p = [[9 ,0], [8 ,2], [9, 6], [9, 7], [3, 5], [6, 1]]
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)   
    G.add_edge(edge[1],edge[0],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)]

#Создание случайной матрциы перевозок
# V = builtRandomTransit(N)
# print (V)
V = [[0, 5, 4, 5, 3, 1], [2, 0, 1, 2, 4, 4], [4, 3, 0, 5, 3, 3], [2, 5, 5, 0, 3, 2], [2, 5, 1, 2, 0, 2], [1, 4, 1, 1, 4, 0]]
# shed.pprint (V)
result_flows = [[[] for i in range(N)] for j in range(N)]
#Поиск всех кратчайших путей
path = nx.all_pairs_shortest_path(G)
print (path)

result_paths = []

for i in range(N):   
    for j in range(N):
        if path[i][j] is not None:
           for k in range(len(path[i][j])-1):
               result_paths.append(Path(path[i][j],V[i][j]))
               G[path[i][j][k]][path[i][j][k+1]]['flow'].append(result_paths[-1])

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 u,v,d in G.edges(data=True):
    sum_flow = sum([paths_edge.flow for paths_edge in d['flow'] ])
    if sum_flow<=d['capacity']:
        d['problem']=False

for u,v,d in G.edges(data=True):
    print (d['problem'], u,v,d['flow'],d['capacity'])   
 
print (result_paths)    
print("="*15)    
simplex_result_paths = []
problem_edges = []
capacities = []
for u,v,d in G.edges(data=True):
    if d['problem']==True:
        G.remove_edge (u,v) 
        for pa in d['flow']:
            simplex_result_paths.append(Path(nx.shortest_path(G,pa.C[0],pa.C[-1]),None))
            simplex_result_paths.append(pa)
        G.add_edge(u,v,d)
        problem_edges.append([u,v])
        capacities.append(d['capacity'])
        

simplexNewPaths(G,simplex_result_paths,problem_edges, V, capacities)