Mewakili grafik (struktur data) dengan Python

Bagaimana seseorang bisa rapi mewakili grafik di Python ? (Mulai dari awal yaitu tidak ada perpustakaan!)
Apa struktur data (misalnya dicts / tuple / dict (tuple)) yang akan cepat tetapi juga efisien dalam memori?
Seseorang harus dapat melakukan berbagai operasi grafik di atasnya.

Seperti yang ditunjukkan, berbagai representasi grafik mungkin membantu. Bagaimana cara menerapkannya dengan Python?

Mengenai perpustakaan, pertanyaan ini memiliki jawaban yang cukup bagus.

Meskipun ini adalah pertanyaan yang agak lama, saya pikir saya akan memberikan jawaban praktis bagi siapa pun yang tersandung ini.

Katakanlah Anda mendapatkan data masukan untuk koneksi Anda sebagai daftar tupel seperti:

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

Struktur data yang menurut saya paling berguna dan efisien untuk grafik dengan Python adalah diktik set . Ini akan menjadi struktur yang mendasari Graphkelas kita . Anda juga harus tahu apakah koneksi ini busur (diarahkan, terhubung satu arah) atau tepi (tidak diarahkan, terhubung dua arah). Kami akan menanganinya dengan menambahkan directedparameter ke Graph.__init__metode. Kami juga akan menambahkan beberapa metode bermanfaat lainnya.

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))

Saya akan meninggalkannya sebagai "latihan untuk pembaca" untuk membuat find_shortest_pathdan metode lainnya.

Mari kita lihat ini beraksi ...

>>> 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 adalah pustaka grafik Python yang mengagumkan. Anda akan kesulitan menemukan sesuatu yang Anda butuhkan yang belum dilakukannya.

Dan ini open source sehingga Anda dapat melihat bagaimana mereka menerapkan algoritme mereka. Anda juga dapat menambahkan algoritme tambahan.

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

Pertama, pilihan representasi daftar vs. matriks bergantung pada tujuan (pada apa yang ingin Anda lakukan dengan representasi tersebut). Masalah dan algoritma terkenal terkait dengan pilihan. Pilihan jenis representasi abstrak menentukan bagaimana hal itu harus dilaksanakan.

Kedua, pertanyaannya adalah apakah simpul dan tepi harus diekspresikan hanya dalam bentuk keberadaan, atau apakah mereka membawa beberapa informasi tambahan.

Dari sudut pandang tipe data bawaan Python, nilai apa pun yang terkandung di tempat lain diekspresikan sebagai referensi (tersembunyi) ke objek target. Jika ini adalah variabel (yaitu referensi bernama), maka nama dan referensi selalu disimpan dalam kamus (internal). Jika Anda tidak membutuhkan nama, maka referensi dapat disimpan di wadah Anda sendiri - di sini mungkin daftar Python akan selalu digunakan untuk daftar sebagai abstraksi.

Daftar Python diimplementasikan sebagai array referensi dinamis, Python tuple diimplementasikan sebagai array statis referensi dengan konten konstan (nilai referensi tidak dapat diubah). Karena itu mereka dapat dengan mudah diindeks. Dengan cara ini, daftar tersebut dapat digunakan juga untuk implementasi matriks.

Cara lain untuk merepresentasikan matriks adalah array yang diimplementasikan oleh modul standar array- lebih dibatasi sehubungan dengan tipe yang disimpan, nilai homogen. Elemen menyimpan nilainya secara langsung. (Daftar menyimpan referensi ke objek nilai sebagai gantinya). Dengan cara ini, memori lebih efisien dan akses ke nilai lebih cepat.

Terkadang, Anda mungkin menemukan representasi yang lebih terbatas seperti bytearray.

Ada dua pustaka grafik NetworkX dan igraph yang sangat baik . Anda dapat menemukan kedua kode sumber pustaka di GitHub. Anda selalu dapat melihat bagaimana fungsi ditulis. Tapi saya lebih suka NetworkX karena mudah dimengerti.
Lihat kode mereka untuk mengetahui bagaimana mereka membuat fungsinya. Anda akan mendapatkan banyak ide dan kemudian dapat memilih bagaimana Anda ingin membuat grafik menggunakan struktur data.