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(5) + 1
if i == j:
f[i][j] = 0
return f
def check(lst, sub):
for i in range(0, len(lst)):
if lst[i:i + len(sub)] == sub:
return True
return False
def simplexNewPaths(G, p, V):
loupe_paths = []
k = []
for u, v, d in G.edges(data=True):
for j in d['flow']:
if j.C not in loupe_paths:
k.append(j.getK(p))
loupe_paths.append(j.C)
size = len(loupe_paths)
A_e = [[0 for i in range(size)] for j in range(len(p)*len(p))]
A_u = []*len(G.edges(data=True))
b_e = [0] * (len(p)*len(p))
b_u = [d['capacity'] for u, v, d in G.edges(data=True)]
for ii in range(size):
A_e[loupe_paths[ii][0]*len(p)+loupe_paths[ii][-1]][ii] = 1
for ii in range(len(p)):
for jj in range(len(p)):
b_e[ii*len(p)+jj] = V[ii][jj]
# d = {}
#
# for i in loupe_paths:
# if d.get((i[0], i[-1])) is None:
# d[(i[0], i[-1])] = []
# if i not in d[(i[0], i[-1])]:
# d[(i[0], i[-1])].append(i)
#
# for key, value in d.items():
# if len(value) > 1:
# print("{0}: {1}".format(key, value))
# A_e.append([0] * size)
# for j in value:
# xxx = list(d.keys()).index(key)
# yyy = loupe_paths.index(j)
# A_e[xxx][yyy] = 1
#
# b_e.append(V[key[0]][key[1]])
# print(loupe_paths)
# shed.ppprint(A_e, len(A_e), size)
# print(b_e)
#
# for i in loupe_edges:
# A_u.append([0] * size)
# for j in loupe_paths:
# if check(j, [i[0], i[1]]):
# A_u[-1][loupe_paths.index(j)] = 1
# shed.ppprint(A_u, len(A_u), size)
res = linprog(k, A_ub=A_u, b_ub=b_u, A_eq=A_e, b_eq=b_e, bounds=(0, None))
print(res.x)
return res.x
# Создание и отрисовка случайного графа при помощи триангуляции Делоне
N = 6
p = shed.builtPoints(N, 10, 10)
# print(p)
# p = [[6, 6], [8, 4], [2, 1], [1, 6], [1, 9], [4, 2]]
# 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(30) + 1, flow=[], problem=True)
# G.add_edge(edge[1], edge[0], weight=round(distance.euclidean(p[edge[0]], p[edge[1]]), 3),
# capacity=np.random.randint(30) + 1, flow=[], problem=True)
G.add_edge(2,5,weight = round(distance.euclidean(p[2],p[5]),3), capacity = 9,flow=[], problem = True)
G.add_edge(2,3,weight = round(distance.euclidean(p[2],p[3]),3), capacity = 6,flow=[], problem = True)
G.add_edge(5,2,weight = round(distance.euclidean(p[5],p[2]),3), capacity = 46,flow=[], problem = True)
G.add_edge(5,3,weight = round(distance.euclidean(p[5],p[3]),3), capacity = 2,flow=[], problem = True)
G.add_edge(5,0,weight = round(distance.euclidean(p[5],p[0]),3), capacity = 50,flow=[], problem = True)
G.add_edge(5,1,weight = round(distance.euclidean(p[5],p[1]),3), capacity = 42,flow=[], problem = True)
G.add_edge(3,2,weight = round(distance.euclidean(p[3],p[2]),3), capacity = 19,flow=[], problem = True)
G.add_edge(3,5,weight = round(distance.euclidean(p[3],p[5]),3), capacity = 24,flow=[], problem = True)
G.add_edge(3,0,weight = round(distance.euclidean(p[3],p[0]),3), capacity = 3,flow=[], problem = True)
G.add_edge(3,4,weight = round(distance.euclidean(p[3],p[4]),3), capacity = 34,flow=[], problem = True)
G.add_edge(0,5,weight = round(distance.euclidean(p[0],p[5]),3), capacity = 16,flow=[], problem = True)
G.add_edge(0,3,weight = round(distance.euclidean(p[0],p[3]),3), capacity = 9,flow=[], problem = True)
G.add_edge(0,1,weight = round(distance.euclidean(p[0],p[1]),3), capacity = 28,flow=[], problem = True)
G.add_edge(0,4,weight = round(distance.euclidean(p[0],p[4]),3), capacity = 7,flow=[], problem = True)
G.add_edge(1,0,weight = round(distance.euclidean(p[1],p[0]),3), capacity = 3,flow=[], problem = True)
G.add_edge(1,5,weight = round(distance.euclidean(p[1],p[5]),3), capacity = 23,flow=[], problem = True)
G.add_edge(4,0,weight = round(distance.euclidean(p[4],p[0]),3), capacity = 21,flow=[], problem = True)
G.add_edge(4,3,weight = round(distance.euclidean(p[4],p[3]),3), capacity = 44,flow=[], problem = True)
positions_vertexes = [(p[i][0], p[i][1]) for i in range(N)]
V = [[0, 1, 3, 3, 5, 3], [5, 0, 3, 3, 4, 5], [2, 4, 0, 4, 1, 3], [3, 3, 5, 0, 3, 2], [3, 3, 5, 4, 0, 1], [3, 3, 4, 1, 5, 0]]
path = nx.all_pairs_shortest_path(G)
W = []
for i in range(N):
for j in range(N):
if path[i][j] is not None:
new_path = Path(path[i][j], V[i][j])
for k in range(len(path[i][j]) - 1):
G[path[i][j][k]][path[i][j][k + 1]]['flow'].append(new_path)
else:
if V[i][j] > 0:
print('Задача неразрешима. Нет ни одного пути из', i, 'в', j)
exit(1)
problem_edges = []
find_paths = [[[] for i in range(N)] for j in range(N)]
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
else:
problem_edges.append([u, v, d])
if len(problem_edges) == 0:
print("Решение получено")
exit(1)
no_new_path = True
for u, v, d in problem_edges:
old_paths = d['flow']
for pa in old_paths:
for deleted_edge in find_paths[pa.C[0]][pa.C[-1]]:
if G.has_edge(deleted_edge[0], deleted_edge[1]):
G.remove_edge(deleted_edge[0], deleted_edge[1])
if nx.has_path(G, pa.C[0], pa.C[-1]):
tmp_pp = Path(nx.shortest_path(G, pa.C[0], pa.C[-1]), None)
no_new_path = False
for j in range(len(tmp_pp.C) - 1):
G[tmp_pp.C[j]][tmp_pp.C[j+1]]['flow'].append(tmp_pp)
for deleted_paths in find_paths[pa.C[0]][pa.C[-1]]:
G.add_edge(deleted_paths[0], deleted_paths[1], deleted_paths[2])
find_paths[pa.C[0]][pa.C[-1]].append([u, v, d])
G.add_edge(u, v, d)
if no_new_path:
print("Нет больше путей. Конец алгоритма")
exit(1)
simplexNewPaths(G, p, V)
# capacities = []
#
# flag = True
#
# while (flag):
# flag = False
# simplex_result_paths = []
# for u, v, d in problem_edges:
# G.remove_edge(u, v)
#
# for u, v, d in problem_edges:
#
# for pa in d['flow']:
# if pa not in simplex_result_paths:
# simplex_result_paths.append(pa)
# tmp_pp = Path(nx.shortest_path(G, pa.C[0], pa.C[-1]), None)
# if tmp_pp not in simplex_result_paths:
# simplex_result_paths.append(tmp_pp)
#
# for u, v, d in problem_edges:
# G.add_edge(u, v, d)
#
# resx = simplexNewPaths(G, simplex_result_paths, problem_edges, V, p)
#
# for i in range(len(resx)):
# simplex_result_paths[i].flow = resx[i]
#
# for i in range(len(resx)):
# if i % 2 == 0:
# if simplex_result_paths[i].flow > 0.0:
# for j in range(len(simplex_result_paths[i].C) - 1):
# if simplex_result_paths[i] in G[simplex_result_paths[i].C[j]][simplex_result_paths[i].C[j + 1]][
# 'flow']:
# index = G[simplex_result_paths[i].C[j]][simplex_result_paths[i].C[j + 1]]['flow'].index(
# simplex_result_paths[i])
# G[simplex_result_paths[i].C[j]][simplex_result_paths[i].C[j + 1]]['flow'][index].flow = \
# simplex_result_paths[i].flow
# else:
# for j in range(len(simplex_result_paths[i].C) - 1):
# if simplex_result_paths[i] in G[simplex_result_paths[i].C[j]][simplex_result_paths[i].C[j + 1]][
# 'flow']:
# G[simplex_result_paths[i].C[j]][simplex_result_paths[i].C[j + 1]]['flow'].remove(
# simplex_result_paths[i])
# else:
# if simplex_result_paths[i].flow != 0.0:
# for j in range(len(simplex_result_paths[i].C) - 1):
# if simplex_result_paths[i] not in G[simplex_result_paths[i].C[j]][simplex_result_paths[i].C[j + 1]][
# 'flow']:
# G[simplex_result_paths[i].C[j]][simplex_result_paths[i].C[j + 1]]['flow'].append(
# simplex_result_paths[i])
#
# 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
# else:
# d['problem'] = True
# problem_edges.append([u, v, d])
# flag = True
#
# print("\nВсе ребра")
# for u, v, d in G.edges(data=True):
# print(d['problem'], u, v, d['flow'], d['capacity'])
#
#