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

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
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
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(15)+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,paths = [])
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()
path = nx.all_pairs_dijkstra_path(G)
print ("Изначальные пути",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)
if d['capacity']<0:
d['weight'] = np.inf
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()
flag = True
for u,v,d in G.edges(data=True):
if d['capacity']<0:
print (d['paths'],d['capacity'])
while d['capacity']!=0 and flag:
new_path = []
new_k = np.inf
for i in d['paths']:
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
if len(new_path)==0 or new_path==path[new_path[0]][new_path[-1]]:
flag = False
else:
print ("Старый путь",path[new_path[0]][new_path[-1]])
print ("Новый путь",new_path)
for vertrex_new_path in range(len(path[new_path[0]][new_path[-1]])-1):
G[path[new_path[0]][new_path[-1]][vertrex_new_path]][path[new_path[0]][new_path[-1]][vertrex_new_path+1]]['capacity']+=1
G[path[new_path[0]][new_path[-1]][vertrex_new_path]][path[new_path[0]][new_path[-1]][vertrex_new_path+1]]['paths'].remove(path[new_path[0]][new_path[-1]])
for vertrex_new_path in range(len(new_path)-1):
G[new_path[vertrex_new_path]][new_path[vertrex_new_path+1]]['capacity']-=1
G[new_path[vertrex_new_path]][new_path[vertrex_new_path+1]]['paths'].append(new_path)
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])
path[new_path[0]][new_path[-1]] = new_path
print (d['paths'],d['capacity'])
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['capacity'])
print ("Конечные пути",path)