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)