Reprezentowanie wykresów (struktury danych) w Pythonie


105

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.



1
Aby zaimplementować wykres, spójrz na artykuł w Wikipedii, w którym wymieniono typowe implementacje i ich wydajność zarówno pod względem pamięci, jak i szybkości: en.wikipedia.org/wiki/ ...
Kassym Dorsel

Możesz spróbować GitHub.com/thePastor/pangaia. Wymaga trochę przepisania, aby użyć domyślnego słownika biblioteki standardowej (którego nie było, gdy kod został napisany). Używa rekurencyjnej struktury danych, aby uczynić ją bardziej elegancką niż inne implementacje.
theDoctor

1
W przypadku wykresów ukierunkowanych ten esej z python.org sugeruje a dictz lists. Zasadniczo coś w rodzaju {<parent>: [<child>, ...], ...}.
djvg

Możesz zaimplementować użycie słownika jako listy przylegania z kluczami jako węzłami i wartościami jako listą sąsiednich węzłów dla każdego klucza.
Shahrukh khan

Odpowiedzi:


140

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']

6
Chociaż to pytanie jest bardzo stare, myślę, że dokładnie takiej odpowiedzi oczekiwałem w tamtym czasie. Przykład naprawdę pomaga wyjaśnić, jak można przejść do implementacji, a jednocześnie jest naprawdę prosty. Można znaleźć implementacje z różnych bibliotek open source, ale wyjaśnienie nie byłoby na równi. Dzięki!
shad0w_wa1k3r

2
jaki rodzaj modyfikacji jest wymagany, aby zwiększyć wagę krawędzi?
pshirishreddy

3
@pshirishreddy Ciekawe pytanie! Nie myślałem o tym, ale odruchowo chciałem używać heapqbiblioteki do układania list krotek zamiast zbiorów. Na przykład wykres składałby się ze stosów, takich jak: _graph = {'A': heapify([(0.3, 'D'), (0.5, 'B'), (0.75, 'A'), (0.9, 'C')])}(uwaga: nie używałbyś heapifytego w ten sposób, przeczytaj pomoc do biblioteki), wtedy możesz użyć heapqfunkcji do wstawienia i uzyskania ważonych krawędzi.
mVChr

@mVChr to oznaczałoby logdostęp czasowy. Ale jak rozszerzyć słownik używany do mapowania zarówno nodeID, jak i weight?
orezvani

Miły ! Funkcja nazywa się rekurencyjnie i wydaje się być DFS, ponieważ rozwija węzły. Dla najkrótszej ścieżki możemy porównać długość ścieżek i zwrócić tylko najkrótszą na końcu.
Jwalant Bhatt,

36

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


7
Dlatego NetworkX jest fantastycznym źródłem informacji. Jest to oprogramowanie typu open source, więc możesz zobaczyć, jak zaimplementowali swoje algorytmy. Możesz także dodać dodatkowe algorytmy.
jterrace

2
Około 2000 linii kodu dla graph.py --> class Graph. Chcę tylko zobaczyć, jak używają __iter__.
T.Woody

8

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.


7

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.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.