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']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(10)+1 if i==j: f[i][j]=0 return f def simplexNewPaths (G, old_paths,edge,points,capacity,V): # G.remove_edge (edge[0],edge[1]) w = G[edge[0]][edge[1]] G.remove_edge (edge[0],edge[1]) new_paths = [] k = [] for p in old_paths: new_paths.append (Path(nx.shortest_path(G,p.C[0],p.C[-1]),None)) k.append(p.getK(points)) # print ("Change paths",new_paths) 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].C[0]][old_paths[i].C[-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] 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) 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() #Создание случайной матрциы перевозок V = builtRandomTransit(N) shed.pprint (V) result_flows = [[[] for i in range(N)] for j in range(N)] #Поиск всех кратчайших путей 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]]['flow'].append(Path(path[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['flow'],d['capacity'], d['problem']) for i in range(N): for j in range(N): if i==j: result_flows[i][j]=Path([i,i],0) else: tmp_path = Path(path[i][j],None) if tmp_path.complete(V[i][j],G): result_flows[i][j]=Path(path[i][j],V[i][j]) for k in range(len(tmp_path.C)-1): G[tmp_path.C[k]][tmp_path.C[k+1]]['capacity']-=V[i][j] if G[tmp_path.C[k]][tmp_path.C[k+1]]['capacity']==0: G.remove_edge([tmp_path.C[k]][tmp_path.C[k+1]]) else: G[tmp_path.C[k]][tmp_path.C[k+1]]['flow'].remove(tmp_path) shed.pprint(result_flows) for u,v,d in G.edges(data=True): print (u,v,d['flow'],d['capacity'], d['problem']) for i in range(2): flag = False for u,v,d in G.edges(data=True): if d['problem']: print (u,v,d['capacity']) oldPaths, newPaths= simplexNewPaths(G,d['flow'],(u,v),p, d['capacity'],V) print (oldPaths,newPaths) for oP in oldPaths: if oP.flow == 0.0: for j in range(len(oP.C)-1): G[oP.C[j]][oP.C[j+1]]['flow'].remove(oP) else: for j in range(len(oP.C)-1): index = G[oP.C[j]][oP.C[j+1]]['flow'].index(oP) G[oP.C[j]][oP.C[j+1]]['flow'][index].flow = oP.flow for nP in newPaths: if nP.flow != 0.0: for j in range(len(nP.C)-1): G[nP.C[j]][nP.C[j+1]]['flow'].append(nP) else: d['problem'] = False 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['flow'],d['capacity'], d['problem']) ost_paths = {} for u,v,d in G.edges(data=True): for f in d['flow']: if ost_paths.get((f.C[0],f.C[-1])) is None: ost_paths[(f.C[0],f.C[-1])] = [f] else: if f not in ost_paths[(f.C[0],f.C[-1])]: ost_paths[(f.C[0],f.C[-1])].append(f) for i in ost_paths: result_flows[i[0]][i[1]] = ost_paths[i] shed.pprint (result_flows)