import numpy as np
import matplotlib.pyplot as plt
from scipy.spatial import Delaunay
import networkx as nx
from scipy.spatial import distance
from scipy.optimize import linprog
from functools import cmp_to_key
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 koefficient(path, points):
d = 0
for i in range(len(path) - 1):
d += distance.euclidean(points[path[i]], points[path[i + 1]])
return d / distance.euclidean(points[path[0]], points[path[-1]])
def compare(p1, p2):
return koefficient(p1, p) - koefficient(p2, p)
def simplexNewPaths(G, loupe_paths, V, p):
print("\n Work simplex method")
N = len(p)
k = [i.getK(p) for i in loupe_paths]
size = len(loupe_paths)
A_V = [[0 for j in range(size)] for i in range(N * N)]
for lp in range(len(loupe_paths)):
i = loupe_paths[lp].C[0]
j = loupe_paths[lp].C[-1]
A_V[N * i + j][lp] = 1
b_V = []
for i in range(len(V)):
for j in range(len(V)):
b_V.append(V[i][j])
A_e = []
b_e = []
for u, v, d in G.edges(data=True):
A_e_list = list(d['flow'])
A_e.append([0 for i in range(size)])
for i in A_e_list:
A_e[-1][i] = 1
b_e.append(d['capacity'])
res = linprog(k, A_ub=A_e, b_ub=b_e, A_eq=A_V, b_eq=b_V, bounds=(0, None))
print(res.x)
if res.success is False:
return None
return res.x
N = 4
p = []
while len(p) < N:
x = np.random.randint(0, 10)
y = np.random.randint(0, 10)
if [x, y] not in p:
p.append([x, y])
tri = Delaunay(p)
sim = tri.simplices
edges_of_tri = [[[min(s[i], s[i + 1]), max(s[i], s[i + 1])] for i in range(-1, 2)] for s in sim]
e = []
for et in edges_of_tri:
for r in et:
if r not in e:
e.append(r)
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, flow=set())
G.add_edge(edge[1], edge[0], weight=round(distance.euclidean(p[edge[0]], p[edge[1]]), 3),
capacity=np.random.randint(10) + 1, flow=set())
positions_vertexes = [(p[i][0], p[i][1]) for i in range(N)]
V = np.random.randint(0, 5, (N, N))
for i in range(N):
V[i][i] = 0
nx.draw_networkx(G, positions_vertexes, with_labels=True, arrows=True, node_color='Red')
plt.savefig("mygraph.png")
paths = []
all_paths = []
for i in range(N):
all_paths.append([])
for j in range(N):
if not nx.has_path(G, i, j) and V[i][j] > 0:
print("Задача не разрешима")
exit(1)
else:
all_paths[i].append(sorted(list(nx.all_simple_paths(G, i, j)), key=cmp_to_key(compare)))
if i != j:
paths.append(Path(all_paths[i][j][0], V[i][j]))
del all_paths[i][j][0]
for i in range(len(paths)):
for k in range(len(paths[i].C) - 1):
G[paths[i].C[k]][paths[i].C[k + 1]]['flow'].add(i)
flag_change = True
flag_problem = True
while flag_change and flag_problem:
resx = simplexNewPaths(G, paths, V, p)
if resx is not None:
for i in range(len(resx)):
paths[i].flow = resx[i]
flag_change = False
flag_problem = False
for u, v, d in G.edges(data=True):
sum_flow = sum([paths[paths_edge].flow for paths_edge in d['flow']])
if sum_flow > d['capacity']:
flag_problem = True
current_paths = list(d['flow'])
for route in current_paths:
if len(all_paths[paths[route].C[0]][paths[route].C[-1]]) > 0:
flag_change = True
new_path = all_paths[paths[route].C[0]][paths[route].C[-1]][0]
del all_paths[paths[route].C[0]][paths[route].C[-1]][0]
paths.append(Path(new_path, 0))
for i in range(len(new_path) - 1):
G[new_path[i]][new_path[i + 1]]['flow'].add(len(paths) - 1)
if not flag_problem:
print("Задача решена")
print(V)
result_paths = [[[] for i in range(N)] for j in range(N)]
for i in paths:
if i.flow > 0:
result_paths[i.C[0]][i.C[-1]].append(i)
print(result_paths)
exit(0)
else:
if not flag_change:
print("Задача не разрешима, кончились пути")