ADT dla grafów

WPROWADZENIE

Poniżej podana jest propozycja interfejsu ADT dla grafu z wagami, skierowanego lub nieskierowanego. W implementacji macierzy sąsiedztwa wierzchołkami grafu są liczby od 0 do n-1 i właściwie wierzchołki już są utworzone (zwykle się ich nie usuwa). W innych implementacjach pythonowych wierzchołki mogą być liczbami, stringami, czy innymi obiektami hashowalnymi, z porządkiem liniowym. Tutaj pojawia się problem z kompatybilnością różnych implementacji, jeżeli przewidujemy usuwanie wierzchołków.

Interfejs korzysta z obiektów krawędzi, które odpowiadają krawędziom skierowanym ważonym. Jeżeli graf jest nieskierowany, to krawędzie o przeciwnych kierunkach są równoważne.

class Edge:
    """Klasa dla krawędzi skierowanej z wagą."""

    def __init__(self, source, target, weight=1):
        """Konstruktor krawędzi."""
        self.source = source
        self.target = target
        self.weight = weight

    def __repr__(self):
        """Zwraca reprezentację napisową krawędzi."""
        if self.weight == 1:
            return "Edge({}, {})".format(repr(self.source), repr(self.target))
        else:
            return "Edge({}, {}, {})".format(
                repr(self.source), repr(self.target), repr(self.weight))

    def __eq__(self, other):
        """Porównywanie krawędzi (e1 == e2)."""
        return (self.source, self.target, self.weight) == (
            other.source, other.target, other.weight)

    def __ne__(self, other):
        """Porównywanie krawędzi (e1 != e2)."""
        return not self == other

    def __lt__(self, other):
        """Porównywanie krawędzi (e1 < e2)."""
        return (self.weight, self.source, self.target) < (
            other.weight, other.source, other.target)

    def __le__(self, other):
        """Porównywanie krawędzi (e1 <= e2)."""
        return (self.weight, self.source, self.target) <= (
            other.weight, other.source, other.target)

    def __hash__(self):
        """Krawędzie są hashowalne."""
        return hash((self.source, self.target, self.weight))

    def __invert__(self):   # przydatne dla grafu nieskierowanego
        """Zwraca krawędź o przeciwnym kierunku (~edge)."""
        return Edge(self.target, self.source, self.weight)

class Graph:
    """Klasa dla grafu ważonego, skierowanego lub nieskierowanego."""

    def __init__(self, n=0, directed=False):
        self.n = n                      # kompatybilność
        self.directed = directed        # bool, czy graf skierowany

    def v(self): pass                   # zwraca liczbę wierzchołków

    def e(self): pass                   # zwraca liczbę krawędzi

    def is_directed(self):              # bool, czy graf skierowany
        return self.directed

    def add_node(self, node): pass      # dodaje wierzchołek

    def has_node(self, node): pass      # bool

    def del_node(self, node): pass      # usuwa wierzchołek z krawędziami incydentnymi

    def add_edge(self, edge): pass      # wstawienie krawędzi

    def has_edge(self, edge): pass      # bool
    #def has_edge(self, source, target): pass   # bool

    def del_edge(self, edge): pass      # usunięcie krawędzi
    #def del_edge(self, source, target): pass   # usunięcie krawędzi

    def weight(self, edge): pass        # zwraca wagę krawędzi
    #def weight(self, source, target): pass   # zwraca wagę krawędzi

    def iternodes(self): pass           # iterator po wierzchołkach

    def iteradjacent(self, node): pass  # iterator po wierzchołkach sąsiednich

    def iteroutedges(self, node): pass  # iterator po krawędziach wychodzących

    def iterinedges(self, node): pass   # iterator po krawędziach przychodzących

    def iteredges(self): pass           # iterator po krawędziach
    # w grafie nieskierowanym można przyjąć, że edge.source < edge.target

    def copy(self): pass                # zwraca kopię grafu

PROSTY ADT DLA GRAFÓW DO WYKŁADU

Mogą być implementacje dict+list (graf bez wag), dict+set (graf bez wag), dict+dict (graf ważony).

Krawędź to będzie 2-krotka (source, target) lub 3-krotka z wagą (source, target, weight).

node_list = list(graph)

node in graph   # bool, czy wierzchołek należy do grafu

len(graph)    # liczba wierzchołków grafu

len(graph[node])   # stopień wierzchołka (graf nieskierowany)

for node in graph:   # iteracja po wierzchołkach
    print("wierzchołek {}".format(node))

for target in graph[source]:   # iteracja po sąsiadach wierzchołka source
    print("{} sąsiaduje z {}".format(source, target))

target in graph[source]   # bool, czy jest sąsiadem

for source in graph:   # iteracja po krawędziach bez wag
    for target in graph[source]:
        print("krawędź {} {}".format(source, target))

sum(len(graph[node]) for node in graph)
# liczba krawędzi dla grafu skierowanego

graph[source][target]   # waga dla implementacji dict+dict

[node for node in graph if not graph[node]]
# lista wierzcholkow izolowanych

sorted(len(graph[node]) for node in graph)
# posortowana lista stopni wierzcholkow grafu nieskierowanego