Reprezentowanie wykresów (struktury danych) w Pythonie

Jak można ładnie przedstawić wykres w Pythonie ? (Zaczynając od zera, tj. Bez bibliotek!)
Jaka struktura danych (np. Dykty / krotki / dyktowanie (krotki)) będzie szybka, ale także wydajna pod względem pamięci?
Trzeba umieć wykonywać na nim różne operacje na grafach.

Jak wskazano, pomocne mogą być różne reprezentacje wykresów . Jak się zabrać za implementację ich w Pythonie?

Jeśli chodzi o biblioteki, to pytanie ma całkiem dobre odpowiedzi.

Chociaż jest to dość stare pytanie, pomyślałem, że dam praktyczną odpowiedź każdemu, kto się na to natknie.

Załóżmy, że otrzymujesz dane wejściowe dla swoich połączeń jako listę krotek, takich jak:

[('A', 'B'), ('B', 'C'), ('B', 'D'), ('C', 'D'), ('E', 'F'), ('F', 'C')]

Struktura danych, którą uważam za najbardziej użyteczną i wydajną dla wykresów w Pythonie, jest dyktatem zbiorów . Będzie to podstawowa struktura naszej Graphklasy. Musisz również wiedzieć, czy te połączenia są łukami (skierowane, łączą w jedną stronę) czy krawędziami (niekierowane, łączą w obie strony). Zajmiemy się tym, dodając directedparametr do Graph.__init__metody. Dodamy również kilka innych pomocnych metod.

import pprint
from collections import defaultdict


class Graph(object):
    """ Graph data structure, undirected by default. """

    def __init__(self, connections, directed=False):
        self._graph = defaultdict(set)
        self._directed = directed
        self.add_connections(connections)

    def add_connections(self, connections):
        """ Add connections (list of tuple pairs) to graph """

        for node1, node2 in connections:
            self.add(node1, node2)

    def add(self, node1, node2):
        """ Add connection between node1 and node2 """

        self._graph[node1].add(node2)
        if not self._directed:
            self._graph[node2].add(node1)

    def remove(self, node):
        """ Remove all references to node """

        for n, cxns in self._graph.items():  # python3: items(); python2: iteritems()
            try:
                cxns.remove(node)
            except KeyError:
                pass
        try:
            del self._graph[node]
        except KeyError:
            pass

    def is_connected(self, node1, node2):
        """ Is node1 directly connected to node2 """

        return node1 in self._graph and node2 in self._graph[node1]

    def find_path(self, node1, node2, path=[]):
        """ Find any path between node1 and node2 (may not be shortest) """

        path = path + [node1]
        if node1 == node2:
            return path
        if node1 not in self._graph:
            return None
        for node in self._graph[node1]:
            if node not in path:
                new_path = self.find_path(node, node2, path)
                if new_path:
                    return new_path
        return None

    def __str__(self):
        return '{}({})'.format(self.__class__.__name__, dict(self._graph))

Zostawię to jako „ćwiczenie dla czytelnika” do stworzenia find_shortest_pathi innych metod.

Zobaczmy to jednak w akcji ...

>>> connections = [('A', 'B'), ('B', 'C'), ('B', 'D'),
                   ('C', 'D'), ('E', 'F'), ('F', 'C')]
>>> g = Graph(connections, directed=True)
>>> pretty_print = pprint.PrettyPrinter()
>>> pretty_print.pprint(g._graph)
{'A': {'B'},
 'B': {'D', 'C'},
 'C': {'D'},
 'E': {'F'},
 'F': {'C'}}

>>> g = Graph(connections)  # undirected
>>> pretty_print = pprint.PrettyPrinter()
>>> pretty_print.pprint(g._graph)
{'A': {'B'},
 'B': {'D', 'A', 'C'},
 'C': {'D', 'F', 'B'},
 'D': {'C', 'B'},
 'E': {'F'},
 'F': {'E', 'C'}}

>>> g.add('E', 'D')
>>> pretty_print.pprint(g._graph)
{'A': {'B'},
 'B': {'D', 'A', 'C'},
 'C': {'D', 'F', 'B'},
 'D': {'C', 'E', 'B'},
 'E': {'D', 'F'},
 'F': {'E', 'C'}}

>>> g.remove('A')
>>> pretty_print.pprint(g._graph)
{'B': {'D', 'C'},
 'C': {'D', 'F', 'B'},
 'D': {'C', 'E', 'B'},
 'E': {'D', 'F'},
 'F': {'E', 'C'}}

>>> g.add('G', 'B')
>>> pretty_print.pprint(g._graph)
{'B': {'D', 'G', 'C'},
 'C': {'D', 'F', 'B'},
 'D': {'C', 'E', 'B'},
 'E': {'D', 'F'},
 'F': {'E', 'C'},
 'G': {'B'}}

>>> g.find_path('G', 'E')
['G', 'B', 'D', 'C', 'F', 'E']

NetworkX to niesamowita biblioteka grafów Pythona. Trudno będzie znaleźć coś, czego potrzebujesz, czego jeszcze nie jest.

Jest to oprogramowanie typu open source, więc możesz zobaczyć, jak zaimplementowali swoje algorytmy. Możesz także dodać dodatkowe algorytmy.

https://github.com/networkx/networkx/tree/master/networkx/algorithms

Po pierwsze, wybór klasycznej reprezentacji list i macierzy zależy od celu (od tego, co chcesz zrobić z reprezentacją). Z wyborem są związane dobrze znane problemy i algorytmy. Wybór abstrakcyjnego rodzaju reprezentacji decyduje o sposobie jej realizacji.

Po drugie, pytanie brzmi, czy wierzchołki i krawędzie powinny być wyrażone tylko w kategoriach istnienia, czy też zawierają dodatkowe informacje.

Z punktu widzenia wbudowanych typów danych Pythona każda wartość zawarta w innym miejscu jest wyrażana jako (ukryte) odniesienie do obiektu docelowego. Jeśli jest to zmienna (tj. Nazwane odniesienie), to nazwa i odniesienie są zawsze przechowywane w (wewnętrznym) słowniku. Jeśli nie potrzebujemy nazwy, wówczas odniesienia może być przechowywany w swoim własnym pojemniku - tu prawdopodobnie lista Python zawsze będą wykorzystywane do listy jako abstrakcji.

Lista Pythona jest zaimplementowana jako dynamiczna tablica referencji, krotka Pythona jest zaimplementowana jako statyczna tablica referencji o stałej zawartości (wartości referencji nie można zmienić). Dzięki temu można je łatwo indeksować. W ten sposób lista może być wykorzystana również do implementacji macierzy.

Innym sposobem reprezentacji macierzy są tablice zaimplementowane przez standardowy moduł array- bardziej ograniczone względem przechowywanego typu, jednorodna wartość. Elementy przechowują wartość bezpośrednio. (Lista zawiera zamiast tego odniesienia do obiektów wartości). W ten sposób jest bardziej wydajny w pamięci, a także dostęp do wartości jest szybszy.

Czasami przydatna może być nawet bardziej ograniczona reprezentacja, taka jak bytearray.

Istnieją dwie doskonałe biblioteki grafów NetworkX i igraph . Kody źródłowe obu bibliotek można znaleźć w serwisie GitHub. Zawsze możesz zobaczyć, jak napisane są funkcje. Ale wolę NetworkX, ponieważ jest łatwy do zrozumienia.
Zobacz ich kody, aby dowiedzieć się, jak tworzą funkcje. Otrzymasz wiele pomysłów, a następnie możesz wybrać, w jaki sposób chcesz utworzyć wykres przy użyciu struktur danych.