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

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

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

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

4 65
python data-structures core-graphics

4 ответа:

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

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

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

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

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.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)
>>> pprint(g._graph)
{'A': {'B'},
 'B': {'D', 'C'},
 'C': {'D'},
 'E': {'F'},
 'F': {'C'}}

>>> g = Graph(connections)  # undirected
>>> 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')
>>> 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')
>>> pprint(g._graph)
{'B': {'D', 'C'},
 'C': {'D', 'F', 'B'},
 'D': {'C', 'E', 'B'},
 'E': {'D', 'F'},
 'F': {'E', 'C'}}

>>> g.add('G', 'B')
>>> 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']
95

NetworkX - это потрясающая библиотека графов Python. Вам будет трудно найти то, что вам нужно, что он еще не делает.

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

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

23

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

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

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

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

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

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

6

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

4