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']<min_flow:
min_flow = G[self.C[i]][self.C[i+1]]['capacity']
return min_flow
def complete(self,v,G):
for i in range(len(self.C)-1):
if G[self.C[i]][self.C[i+1]]['problem']:
return False
if self.getMinFlow()>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)