Grafy bez wag w Pythonie (dict+list)

http://www.python.org/doc/essays/graphs/

WPROWADZENIE

W języku Python grafy możemy wygodnie przedstawić za pomocą słowników i list. Graf będzie słownikiem, w którym kluczami będą wierzchołki (liczby, napisy, itp.). Każdemu kluczowi będzie odpowiadać lista zawierająca wierzchołki połączone krawędzią z danym wierzchołkiem. 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), (A,C), (B,C), (B,D), (C,D), (D,C), (E,C). Możemy go zapisać jako słownik

graph = {"A":["B","C"], "B":["C","D"], "C":["D"], "D":["C"], "E":["C"], "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 2-krotkę.

def add_edge_directed(graph, edge):
    """Dodaje krawędź do grafu skierowanego."""
    source, target = 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].append(target)

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 = 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].append(target)
    if source not in graph[target]:
        graph[target].append(source)

Iterowanie 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 (2-krotki) grafu skierowanego bez wag.
    Dla grafu nieskierowanego należy zwrócić tylko jedną krawędź z pary
    dwóch krawędzi skierowanych, np. edge.source < edge.target.
    """
    for source in graph:
        for target in graph[source]:
            yield (source, target)

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

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