import numpy as np
import shed
import pylab
from mpl_toolkits.mplot3d import Axes3D
import matplotlib.pyplot as plt
from scipy.spatial import Delaunay
import networkx as nx
from scipy.spatial import distance
def builtRandomFlow (mA):
f = []
for i in range(len(mA)):
f.append([0] * len(mA))
for i in range(len(mA)):
for j in range(len(mA)):
if mA[i][j]!=np.inf and i!=j:
f[i][j]=np.random.randint(20)+1
if i==j:
f[i][j]=0
return f
def length (path):
l = 0
for i in range(len(path)-1):
l+=G[path[i]][path[i+1]]['weight']
return l
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(10)+1)
H = G.copy()
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()
#for u,v,d in G.edges(data=True):
# print (u,v,d)
path = nx.all_pairs_dijkstra_path(G)
print ("Изначальные пути",path)
#shed.pprint(path)
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'] -= 1
for u,v,d in G.edges(data=True):
if d['capacity']==0:
G.remove_edge(u,v)
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()
#print ("Потоки после дейсктры")
#shed.pprint (flow)
#
flow_edge = [[[] for j in range(N)] for i in range(N)]
for i in range(N):
for j in range(N):
if len(path[i][j])!=1:
for k in range(len(path[i][j])-1):
flow_edge[int(path[i][j][k])][int(path[i][j][k+1])].append(path[i][j])
shed.pprint(flow_edge)
for u,v,d in G.edges(data=True):
if d['capacity']<0:
print (flow_edge[u][v],d['capacity'])
d['weight'] = np.inf
for r_flow in range(d['capacity']*(-1)):
new_path = []
new_k = np.inf
for i in flow_edge[u][v]:
try:
tmp_path = nx.shortest_path(G,i[0],i[-1],weight = 'weight')
tmp_k = length(tmp_path)/round(distance.euclidean(p[i[0]],p[i[-1]]))
if (tmp_k<new_k):
new_k = tmp_k
new_path = tmp_path
except nx.NetworkXNoPath:
continue
print ( new_path)
for vertrex_new_path in range(len(new_path)-1):
flow_edge[new_path[vertrex_new_path]][new_path[vertrex_new_path+1]].append(new_path)
G[new_path[vertrex_new_path]][new_path[vertrex_new_path+1]]['capacity']-=1
if G[new_path[vertrex_new_path]][new_path[vertrex_new_path+1]]['capacity']==0:
G.remove_edge(new_path[vertrex_new_path],new_path[vertrex_new_path+1])
for vertrex_new_path in range(len(path[u][v])-1):
flow_edge[path[u][v][vertrex_new_path]][path[u][v][vertrex_new_path+1]].remove(path[u][v])
G[path[u][v][vertrex_new_path]][path[u][v][vertrex_new_path+1]]['capacity']+=1
path[u][v] = new_path
G.remove_edge(u,v)
#
#for i in range(N):
# for j in range(N):
# if flow[i][j]<=0:
# if G.has_edge(i,j):
# G.remove_edge(i, j)
#
#flag = True
#
#while flag:
# flag = False
# for i in range(N):
# for j in range(N):
# if flow[i][j]<=0:
#
# if G.has_edge(i,j):
# flag = True
# G.remove_edge(i, j)
# if flow[i][j]<0:
#
# new_path = ""
# old_path = ""
# len_new_path = np.inf
# for p in flow_edge[i][j]:
# if nx.has_path(G,int(p[0]),int(p[-1])) == False:
# path[int(p[0])][int(p[-1])]=[]
# else:
# tmp = nx.dijkstra_path(G,int(p[0]),int(p[-1]))
# len_tmp = nx.dijkstra_path_length(G,int(p[0]),int(p[-1]))
# if len_tmp<len_new_path:
# len_new_path = len_tmp
# new_path = tmp
# old_path = p
# if new_path!="":
# for old_edge in range(len(old_path)-1):
# flow[old_path[old_edge]][old_path[old_edge+1]]+=1
## print ("del",old_path[old_edge], old_path[old_edge+1], old_path)
# flow_edge[old_path[old_edge]][old_path[old_edge+1]].remove(old_path)
# flag = True
# path[new_path[0]][new_path[-1]]=new_path
#
# for t in range(len(new_path)-1):
# flow[new_path[t]][new_path[t+1]]-=1
## print ("add",new_path[t], new_path[t+1], new_path)
# flow_edge[new_path[t]][new_path[t+1]].append(new_path)
# path[new_path[t]][new_path[t+1]]=new_path
# print (old_path,"->",new_path)
#
#edge_labels=dict([((u,v,),(flow[u][v])) 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')
#shed.pprint(path)
#shed.pprint(flow)