Grafy z wagami w Pythonie (dict+list)

WPROWADZENIE

Graf będzie słownikiem, w którym kluczami będą wierzchołki (liczby, napisy, itp.). Każdemu kluczowi będzie odpowiadać lista krotek, zawierająca 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 listę sąsiedztwa. 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, weight) not in graph[source]:
        graph[source].append((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, weight) not in graph[source]:
        graph[source].append((target, weight))
    if (source, weight) not in graph[target]:
        graph[target].append((source, weight))

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

def iternodes(graph):
    """Zwraca iterator po wierzchołkach grafu."""
    #return graph.keys()   # Py3 widok na wierzchołki grafu
    return iter(graph)

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

def iteradjacent(graph, source):
    """Zwraca iterator po sąsiadach danego wierzchołka w grafie ważonym."""
    for (target, weight) in graph[source]:
        yield target

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