Grafy z wagami w Pythonie (dict+dict)

WPROWADZENIE

Graf będzie słownikiem, w którym kluczami będą wierzchołki (liczby, napisy, itp.). Każdemu kluczowi będzie odpowiadać słownik, zawierający wierzchołki połączone krawędzią z danym wierzchołkiem, oraz wagi krawędzi prowadzących do danego wierzchołka. Pusty graf będzie reprezentowany przez pusty słownik. W podanej implementacji graf nieskierowany możemy potraktować jak graf skierowany, ale nie na odwrót. Dlatego tam, gdzie to jest istotne, będziemy zaznaczać, że graf jest nieskierowany.

PRZYKŁAD. Rozważmy graf skierowany o wierzchołkach od A do F i krawędziach (A, B, 1), (A, C, 2), (B, C, 3), (B, D, 4), (C, D, 5), (D, C, 6), (E, C, 7). Możemy go zapisać jako słownik.

graph = {
    "A" : {"B":1, "C":2}, 
    "B" : {"C":3, "D":4}, 
    "C" : {"D":5}, 
    "D" : {"C":6}, 
    "E" : {"C":7}, 
    "F" : {}}

POMOCNICZE FUNKCJE

Określamy funkcje pomagające we właściwej budowie grafu w Pythonie.

graph = {}                    # pusty graf (dowolny)
directed_graph = {}           # pusty graf skierowany
undirected_graph = {}         # pusty graf nieskierowany

Dodawanie wierzchołka do grafu bez duplikatów.

def add_node(graph, node):
    """Wstawia wierzchołek do grafu."""
    if node not in graph:
        graph[node] = {}

Dodawanie krawędzi do grafu skierowanego bez duplikatów. Na początku próbujemy uzupełniać brakujące wierzchołki. Następnie uzupełniamy krawędzie. Krawędź grafu przedstawiamy jako 3-krotkę.

def add_edge_directed(graph, edge):
    """Dodaje krawędź do grafu skierowanego."""
    source, target, weight = edge
    add_node(graph, source)
    add_node(graph, target)
    # Możemy wykluczyć pętle.
    if source == target:
        raise ValueError("pętle są zabronione")
    if target not in graph[source]:
        graph[source][target] = weight

Dodawanie krawędzi do grafu nieskierowanego bez duplikatów. Krawędź nieskierowana występuje jako dwie krawędzie skierowane.

def add_edge_undirected(graph, edge):
    """Dodaje krawędź do grafu nieskierowanego."""
    source, target, weight = edge
    add_node(graph, source)
    add_node(graph, target)
    # Możemy wykluczyć pętle.
    if source == target:
        raise ValueError("pętle są zabronione")
    if target not in graph[source]:
        graph[source][target] = weight
    if source not in graph[target]:
        graph[target][source] = weight

Iteracja po wierzchołkach, krawędziach i sąsiadach.

def iternodes(graph):
    """Zwraca iterator po wierzchołkach grafu."""
    return iter(graph)

def iteredges(graph):
    """Zwraca iterator po krawędziach (3-krotki) grafu skierowanego ważonego."""
    for source in graph:
        for target in graph[source]:
            yield (source, target, graph[source][target])

def iteradjacent(graph, source):
    """Zwraca iterator po sąsiadach danego wierzchołka w grafie ważonym."""
    return iter(graph[source])

def print_graph(graph):
    """Wypisuje postać grafu skierowanego ważonego na ekranie."""
    L = []
    for source in graph:
        L.append("{} : ".format(source))
        for target in graph[source]:
            L.append("{}({}) ".format(target, graph[source][target]))
        L.append("\n")
    print("".join(L))