SHARE
TWEET

Untitled

a guest Jun 25th, 2019 60 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import sys
  2. import networkx as nx
  3.  
  4. """
  5. Algorytm znajdowania trasy Chińskiego Listonosza opiera się na rozszerzeniu
  6. grafu wejściowego o dodatkowe krawędzie (co robi z niego multigraf) i odszukanie
  7. w tak spreparowanym grafie ścieżki Eulera. Metoda doboru takich krawędzi
  8. zapewnia optymalność łącznej sumy długości ścieżek.
  9. """
  10.  
  11. def extract_odd_vertices(G):
  12.     """
  13.     Znajduje wszystkie wierzchołki o nieparzystym stopniu (a więc takie, które
  14.     przeszkadzają w utworzeniu cyklu Eulera).
  15.     """
  16.     degrees = nx.degree(G)
  17.     return {node for node in G if degrees[node] % 2 == 1}
  18.  
  19. def path_length(G, path):
  20.     """
  21.     Wyznacza długość ścieżki oznaczonej przez ciąg wierzchołków.
  22.     """
  23.     return sum(G[u][v]['weight'] for u, v in zip(path, path[1:]))
  24.  
  25. def make_complete_graph(G, node_set, shortest_paths):
  26.     """
  27.     Tworzy nowy graf, który zawiera wszystkie wierzchołki z node_set, jest
  28.     pełny, oraz waga krawędzi pomiędzy dowolnymi dwoma wierzchołkami, to wartość
  29.     przeciwna długości najkrótszej ścieżki między nimi w oryginalnym grafie G (w
  30.     ten sposób, dzięki metodzie, która wyciąga skojarzenie o największej wadze,
  31.     uzyskamy skojarzenie o wadze najmniejszej).
  32.     """
  33.     new_graph_data = {}
  34.     for u in node_set:
  35.         new_graph_data[u] = {}
  36.         for v in node_set:
  37.             if u == v:
  38.                 continue
  39.             new_graph_data[u][v] = {'weight' : -path_length(G, shortest_paths[u][v])}
  40.     return nx.Graph(new_graph_data)
  41.  
  42. def select_best_matching(G):
  43.     """
  44.     Funkcja znajduje skojarzenie doskonałe o największej sumarycznej wadze (a
  45.     skoro wagi są ujemne, to znajdzie takie, gdzie suma jest najmniejsza).
  46.     """
  47.     return nx.max_weight_matching(G, maxcardinality=True, weight='weight')
  48.  
  49. def make_eulerian_multigraph(G):
  50.     """
  51.     Funkcja tworzy minimalny (w sensie sumy wag) multigraf graf Eulerowski.
  52.     """
  53.     multigraph = nx.MultiGraph(G)
  54.  
  55.     odd_nodes = extract_odd_vertices(G)
  56.  
  57.     shortest_paths = nx.shortest_path(G, weight='weight')
  58.     complete_graph = make_complete_graph(G, odd_nodes, shortest_paths)
  59.     best_matching = select_best_matching(complete_graph)
  60.  
  61.     for u, v in best_matching:
  62.         path = shortest_paths[u][v]
  63.         for x, y in zip(path[1:], path):
  64.             multigraph.add_edge(x, y, weight=G[x][y]['weight'])
  65.  
  66.     return multigraph
  67.  
  68. def read_graph(file_name):
  69.     with open(file_name) as f:
  70.         edges = f.readlines()[1:]
  71.     G = nx.parse_edgelist(edges, nodetype=int, data=(('weight', int),))
  72.     return G
  73.  
  74. def serialize(G, eulerian_path, f=sys.stdout):
  75.     print('graph {', file=f)
  76.     for node in G:
  77.         print(node, ';', file=f)
  78.     for i, (u, v) in enumerate(eulerian_path):
  79.         print(u, ' -- ', v, ' [color=red,penwidth=3.0,key=', i, ',weight=',G[u][v]['weight'], ',label=', i, '];', file=f, sep='')
  80.     print('}', file=f)
  81.  
  82.  
  83. if __name__ == '__main__':
  84.     G = read_graph(input('Podaj ścieżkę do pliku z opisem grafu: '))
  85.     multigraph = make_eulerian_multigraph(G)
  86.     sciezka_listonosza = nx.eulerian_circuit(multigraph)
  87.     output = input('Podaj nazwę pliku wynikowego (.dot)')
  88.     with open(output, 'w') as f:
  89.         serialize(G, sciezka_listonosza, f)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top