zadanie10.py

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)

zadanie5.py

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)

zadanie6a.py

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])

zadanie7.py

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)

zadanie8a.py

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)

zadanie9.py

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)