Skip to content

Instantly share code, notes, and snippets.

@enedil
Last active Jun 16, 2019
Embed
What would you like to do?
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