import numpy as np
import shed
import path
import sys
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 simplexNewPaths (G,edge,points,V):
print ("Вход в фунцкию с ",edge,G[edge[0]][edge[1]]['flow'],G[edge[0]][edge[1]]['capacity'])
old_paths = G[edge[0]][edge[1]]['flow']
w = G[edge[0]][edge[1]]
capacity = w['capacity']
G.remove_edge (edge[0],edge[1])
new_paths = []
k = []
for p in old_paths:
try:
new_paths.append (path.Path(nx.shortest_path(G,p[0],p[-1]),None))
k.append(p.getK(points))
except nx.NetworkXNoPath as e:
print(e)
return None,None
for p in new_paths:
k.append(p.getK(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))
G.add_edge(edge[0],edge[1],w)
for i in range(size):
new_paths[i].flow = res.x[i*2+1]
old_paths[i].flow = res.x[i*2]
print (old_paths[i],"---->",new_paths[i])
# G.remove_edge (edge[0],edge[1])
print ("o"*25)
return old_paths, new_paths
#Создание и отрисовка случайного графа при помощи триангуляции Делоне
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)
#Создание случайной матрциы перевозок
V = shed.builtRandomTransit(N,10)
shed.pprint (V)
result_flows = [[[] for i in range(N)] for j in range(N)]
#Поиск всех кратчайших путей
paths = nx.all_pairs_dijkstra_path(G)
shed.pprint (paths)
for i in range(N):
for j in range(N):
for k in range(len(paths[i][j])-1):
G[paths[i][j][k]][paths[i][j][k+1]]['flow'].append(path.Path(paths[i][j],V[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 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 (u,v, d['problem'],d['flow'],d['capacity'])
for i in range(N):
for j in range(N):
if i==j:
result_flows[i][j]=path.Path([i],0)
else:
tmp_path = path.Path(paths[i][j],None)
if tmp_path.complete(V[i][j],G):
result_flows[i][j]=path.Path(paths[i][j],V[i][j])
V[i][j] = 0
for k in range(len(tmp_path.chain)-1):
G[tmp_path[k]][tmp_path[k+1]]['capacity']-=V[i][j]
if G[tmp_path[k]][tmp_path[k+1]]['capacity']==0:
G.remove_edge([tmp_path[k]][tmp_path[k+1]])
else:
G[tmp_path[k]][tmp_path[k+1]]['flow'].remove(tmp_path)
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()
shed.ppprint(result_flows)
problem_edges = []
for u,v,d in G.edges(data=True):
if d['problem']:
problem_edges.append((u,v,d))
#flag = True
#while flag:
# flag = False
while (len(problem_edges)!=0):
print ("Проблемные ребра", problem_edges)
for u,v,d in problem_edges:
print (u,v,d)
if d['problem']:
old_paths, new_paths = simplexNewPaths(G,(u,v),p,V)
if old_paths is None:
sys.exit("Задача неразрешима. Нет пути")
for oP in old_paths:
if oP.flow == 0.0:
for j in range(len(oP.chain)-1):
if (oP[j],oP[j+1]) not in nx.non_edges(G):
G[oP[j]][oP[j+1]]['flow'].remove(oP)
print ("Удалил",oP[j],oP[j+1],oP)
if sum([paths_edge.flow for paths_edge in G[oP[j]][oP[j+1]]['flow']])<=G[oP[j]][oP[j+1]]['capacity']:
G[oP[j]][oP[j+1]]['problem']=False
# G[oP[j]][oP[j+1]]['capacity']+=oP.flow
else:
for j in range(len(oP.chain)-1):
if (oP[j],oP[j+1]) not in nx.non_edges(G):
index = G[oP[j]][oP[j+1]]['flow'].index(oP)
print ("Изменил поток",oP[j],oP[j+1],oP)
G[oP[j]][oP[j+1]]['flow'][index].flow = oP.flow
if sum([paths_edge.flow for paths_edge in G[oP[j]][oP[j+1]]['flow']])<=G[oP[j]][oP[j+1]]['capacity']:
G[oP[j]][oP[j+1]]['problem']=False
# G[oP[j]][oP[j+1]]['capacity'] = old_old_paths[old_paths.index(oP)] - oP.flow
for nP in new_paths:
if nP.flow != 0.0:
print (nP)
for j in range(len(nP.chain)-1):
if nP not in G[nP[j]][nP[j+1]]['flow']:
G[nP[j]][nP[j+1]]['flow'].append(path.Path(nP.chain, nP.flow))
print ("Прибавил",nP[j],nP[j+1],nP.chain, nP.flow)
if sum([paths_edge.flow for paths_edge in G[nP[j]][nP[j+1]]['flow']])>G[nP[j]][nP[j+1]]['capacity']:
G[nP[j]][nP[j+1]]['problem']=True
else:
G[nP[j]][nP[j+1]]['problem']=False
#
# if sum([paths_edge.flow for paths_edge in G[nP[j]][nP[j+1]]['flow']])==G[nP[j]][nP[j+1]]['capacity']:
# G.remove_edge(nP[j],nP[j+1])
# else:
# G[nP[j]][nP[j+1]]['problem']=False
for i in d['flow']:
result_flows[i[0]][i[-1]].append(i)
V[i[0]][i[-1]]-=i.flow
G.remove_edge(u,v)
problem_edges = []
for u,v,d in G.edges(data=True):
if d['problem']:
problem_edges.append((u,v,d))
for u,v,d in G.edges(data=True):
print (u,v, d['problem'],d['flow'],d['capacity'])
ost_paths = {}
for u,v,d in G.edges(data=True):
for f in d['flow']:
if ost_paths.get((f[0],f[-1])) is None:
ost_paths[(f[0],f[-1])] = [f]
else:
if f not in ost_paths[(f[0],f[-1])]:
ost_paths[(f[0],f[-1])].append(f)
print (ost_paths)
for i in ost_paths:
sum_flow = sum([ip.flow for ip in ost_paths[i]])
result_flows[i[0]][i[1]] = ost_paths[i]
V[i[0]][i[1]]-= sum_flow
print ("Edges")
for u,v,d in G.edges(data=True):
print (u,v, d['problem'],d['flow'],d['capacity'])
shed.ppprint (result_flows)
shed.pprint (V)