Skip to content

Instantly share code, notes, and snippets.

@enedil
Last active June 16, 2019 19:17
Show Gist options
  • Save enedil/c2f5c89ea34361ddf517192495b44274 to your computer and use it in GitHub Desktop.
Save enedil/c2f5c89ea34361ddf517192495b44274 to your computer and use it in GitHub Desktop.
import sys
import networkx as nx
"""
Algorytm znajdowania trasy Chińskiego Listonosza opiera się na rozszerzeniu
grafu wejściowego o dodatkowe krawędzie (co robi z niego multigraf) i odszukanie
w tak spreparowanym grafie ścieżki Eulera. Metoda doboru takich krawędzi
zapewnia optymalność łącznej sumy długości ścieżek.
"""
def extract_odd_vertices(G):
"""
Znajduje wszystkie wierzchołki o nieparzystym stopniu (a więc takie, które
przeszkadzają w utworzeniu cyklu Eulera).
"""
degrees = nx.degree(G)
return {node for node in G if degrees[node] % 2 == 1}
def path_length(G, path):
"""
Wyznacza długość ścieżki oznaczonej przez ciąg wierzchołków.
"""
return sum(G[u][v]['weight'] for u, v in zip(path, path[1:]))
def make_complete_graph(G, node_set, shortest_paths):
"""
Tworzy nowy graf, który zawiera wszystkie wierzchołki z node_set, jest
pełny, oraz waga krawędzi pomiędzy dowolnymi dwoma wierzchołkami, to wartość
przeciwna długości najkrótszej ścieżki między nimi w oryginalnym grafie G (w
ten sposób, dzięki metodzie, która wyciąga skojarzenie o największej wadze,
uzyskamy skojarzenie o wadze najmniejszej).
"""
new_graph_data = {}
for u in node_set:
new_graph_data[u] = {}
for v in node_set:
if u == v:
continue
new_graph_data[u][v] = {'weight' : -path_length(G, shortest_paths[u][v])}
return nx.Graph(new_graph_data)
def select_best_matching(G):
"""
Funkcja znajduje skojarzenie doskonałe o największej sumarycznej wadze (a
skoro wagi są ujemne, to znajdzie takie, gdzie suma jest najmniejsza).
"""
return nx.max_weight_matching(G, maxcardinality=True, weight='weight')
def make_eulerian_multigraph(G):
"""
Funkcja tworzy minimalny (w sensie sumy wag) multigraf graf Eulerowski.
"""
multigraph = nx.MultiGraph(G)
odd_nodes = extract_odd_vertices(G)
shortest_paths = nx.shortest_path(G, weight='weight')
complete_graph = make_complete_graph(G, odd_nodes, shortest_paths)
best_matching = select_best_matching(complete_graph)
for u, v in best_matching:
path = shortest_paths[u][v]
for x, y in zip(path[1:], path):
multigraph.add_edge(x, y, weight=G[x][y]['weight'])
return multigraph
def read_graph(file_name):
with open(file_name) as f:
edges = f.readlines()[1:]
G = nx.parse_edgelist(edges, nodetype=int, data=(('weight', int),))
return G
def serialize(G, eulerian_path, f=sys.stdout):
print('graph {', file=f)
for node in G:
print(node, ';', file=f)
for i, (u, v) in enumerate(eulerian_path):
print(u, ' -- ', v, ' [color=red,penwidth=3.0,key=', i, ',weight=',G[u][v]['weight'], ',label=', i, '];', file=f, sep='')
print('}', file=f)
if __name__ == '__main__':
G = read_graph(input('Podaj ścieżkę do pliku z opisem grafu: '))
multigraph = make_eulerian_multigraph(G)
sciezka_listonosza = nx.eulerian_circuit(multigraph)
output = input('Podaj nazwę pliku wynikowego (.dot)')
with open(output, 'w') as f:
serialize(G, sciezka_listonosza, f)
import networkx as nx
if __name__ == '__main__':
file_name = input('Podaj nazwę pliku z opisem: ')
with open(file_name) as f:
edges = f.readlines()[1:]
G = nx.parse_edgelist(edges, nodetype=int, data=(('weight', int),))
with open('output.txt', 'w') as f:
print('graph G {', file=f)
for edge in G.edges(data=True):
u, v, weight = edge
weight = weight['weight']
print(f' {u} -- {v} [label="{weight}"];', file=f)
print('}', file=f)
import networkx as nx
def BellmanFord(G, source):
distance = {v: float('inf') for v in G}
previous = {v: None for v in G}
distance[source] = 0
for _ in G:
for (u, v, data) in G.edges.data():
weight = data['weight']
if distance[u] + weight < distance[v]:
distance[v] = distance[u] + weight
previous[v] = u
if distance[v] + weight < distance[u]:
distance[u] = distance[v] + weight
previous[u] = v
return distance, previous
if __name__ == '__main__':
file_name = input('wprowadź nazwę pliku z opisem grafu: ')
with open(file_name) as f:
edges = f.readlines()[1:]
G = nx.parse_edgelist(edges, nodetype=int, data=(('weight', int),))
source = int(input('podaj pierwszy wierzchołek: '))
destination = int(input('podaj końcowy wierzchołek: '))
distances, _ = BellmanFord(G, source)
if distances[destination] == float('inf'):
print(f'Nie istnieje ścieżka pomiędzy {source} a {destination}')
else:
print(f'Najkrótsza droga pomiędzy {source} a {destination}: ', end='')
print(distances[destination])
import networkx as nx
def BellmanFord(G, source):
distance = {v: float('inf') for v in G}
previous = {v: None for v in G}
distance[source] = 0
for _ in G:
for (u, v, data) in G.edges.data():
weight = data['weight']
if distance[u] + weight < distance[v]:
distance[v] = distance[u] + weight
previous[v] = u
if distance[v] + weight < distance[u]:
distance[u] = distance[v] + weight
previous[u] = v
return distance, previous
def find_distances(G):
ret = {}
for v in G:
distance, _ = BellmanFord(G, v)
for u, dist in distance.items():
if u != v and (v, u) not in ret:
ret[(u, v)] = dist
return ret
if __name__ == '__main__':
file_name = input('wprowadź nazwę pliku z opisem grafu: ')
with open(file_name) as f:
edges = f.readlines()[1:]
G = nx.parse_edgelist(edges, nodetype=int, data=(('weight', int),))
distances = find_distances(G)
for (u, v), weight in distances.items():
l = sorted([u, v])
print(l[0], '-', l[1], '\t', weight)
from itertools import permutations
def travelling_salesman_problem(distances, n):
def path_cost(path):
return sum(distances[a][b] for a, b in zip(path, path[1:]+path[:1]))
def fix_first_elem(permutation):
return (0,) + permutation
return min(map(fix_first_elem, permutations(range(1, n))), key=path_cost)
odleglosci = [[0, 296, 133, 389, 311, 360, 558, 260, 168, 291],
[296, 0, 262, 272, 445, 564, 645, 450, 280, 82],
[133, 262, 0, 219, 201, 337, 449, 223, 287, 193],
[389, 272, 219, 0, 164, 459, 377, 277, 429, 194],
[311, 445, 201, 164, 0, 316, 243, 140, 467, 367],
[360, 564, 337, 459, 316, 0, 366, 170, 508, 531],
[558, 645, 449, 377, 243, 366, 0, 258, 711, 568],
[260, 450, 223, 277, 140, 170, 258, 0, 427, 416],
[168, 280, 287, 429, 467, 508, 711, 427, 0, 343],
[291, 82, 193, 194, 367, 531, 568, 416, 343, 0]]
miasta = ['Warszawa', 'Kraków', 'Łódź', 'Wrocław', 'Poznań',
'Gdańsk', 'Szczecin', 'Bydgoszcz','Lublin', 'Katowice']
sciezka = travelling_salesman_problem(odleglosci, len(odleglosci))
print(*[miasta[x] for x in sciezka], sep=' -> ')
koszt = sum(odleglosci[a][b] for a, b in zip(sciezka, sciezka[1:]+sciezka[:1]))
print('Łączny koszt: ', koszt)
from collections import defaultdict
from itertools import permutations
import networkx as nx
def travelling_salesman_problem(distances, n):
def path_cost(path):
return sum(distances[a][b] for a, b in zip(path, path[1:]+path[:1]))
def fix_first_elem(permutation):
return (0,) + permutation
return min(map(fix_first_elem, permutations(range(1, n))), key=path_cost)
if __name__ == '__main__':
file_name = input('Wprowadź nazwę pliku z opisem grafu pełnego: ')
with open(file_name) as f:
edges = f.readlines()[1:]
G = nx.parse_edgelist(edges, nodetype=int, data=(('weight', int),))
distances = {}
for edge in G.edges(data=True):
u, v, weight = edge
weight = weight['weight']
if u not in distances:
distances[u] = defaultdict(int)
if v not in distances:
distances[v] = defaultdict(int)
distances[u][v] = weight
path = travelling_salesman_problem(distances, len(G))
print('Droga: ')
print(*path)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment