Представление графиков (структуры данных) в Python

Как можно аккуратно изобразить граф на Python ? (Начиная с нуля, т.е. без библиотек!)
Какая структура данных (например, dicts / tuples / dict (кортежи)) будет быстрой, но при этом эффективной с точки зрения памяти?
Над ним нужно уметь выполнять различные операции с графом .

Как уже отмечалось, могут помочь различные представления графов . Как их реализовать на Python?

Что касается библиотек, то на этот вопрос есть неплохие ответы.

Несмотря на то, что это несколько старый вопрос, я подумал, что дам практический ответ любому, кто наткнется на него.

Допустим, вы получаете входные данные для своих подключений в виде списка кортежей, например:

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

Структура данных, которую я считаю наиболее полезной и эффективной для графиков в Python, - это набор наборов . Это будет основная структура нашего Graphкласса. Вы также должны знать, являются ли эти соединения дугами (направленные, соединяются в одну сторону) или ребрами (неориентированные, соединяются в обе стороны). Мы справимся с этим, добавив directedпараметр в Graph.__init__метод. Мы также добавим несколько других полезных методов.

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

Я оставлю это как "упражнение для читателя" по созданию find_shortest_path и других методов.

Но давайте посмотрим на это в действии ...

>>> 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 - потрясающая библиотека графов Python. Вам будет сложно найти то, что вам нужно, чего еще не было.

И это открытый исходный код, поэтому вы можете увидеть, как они реализовали свои алгоритмы. Вы также можете добавить дополнительные алгоритмы.

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

Во-первых, выбор классического списка или матрицы зависит от цели (от того, что вы хотите делать с представлением). С выбором связаны известные проблемы и алгоритмы. Выбор вида абстрактного представления диктует, как его следует реализовать.

Во-вторых, вопрос в том, должны ли вершины и ребра выражаться только в терминах существования, или они несут дополнительную информацию.

С точки зрения встроенных типов данных Python, любое значение, содержащееся в другом месте, выражается как (скрытая) ссылка на целевой объект. Если это переменная (т.е. именованная ссылка), тогда имя и ссылка всегда хранятся во (внутреннем) словаре. Если вам не нужны имена, тогда ссылку можно сохранить в вашем собственном контейнере - здесь, вероятно, список Python всегда будет использоваться для списка как абстракция.

Список Python реализован как динамический массив ссылок, кортеж Python реализован как статический массив ссылок с постоянным содержимым (значение ссылок не может быть изменено). Благодаря этому их легко индексировать. Таким образом, список можно использовать также для реализации матриц.

Другой способ представления матриц - это массивы, реализованные стандартным модулем array- более ограниченные по отношению к хранимому типу, однородное значение. Элементы сохраняют значение напрямую. (Вместо этого в списке хранятся ссылки на объекты значений). Таким образом, это более эффективно использует память, а также ускоряется доступ к значению.

Иногда может оказаться полезным даже более ограниченное представление, например bytearray.

Есть два отличных графа библиотеки NetworkX и igraph . Вы можете найти исходные коды обеих библиотек на GitHub. Всегда можно посмотреть, как написаны функции. Но я предпочитаю NetworkX, потому что его легко понять.
Посмотрите их коды, чтобы узнать, как они выполняют функции. Вы получите несколько идей, а затем сможете выбрать, как вы хотите построить график с использованием структур данных.