# 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