在Python中表示图(数据结构)

问题:在Python中表示图(数据结构)

如何用Python巧妙地表示图形?(从头开始,即没有库!)哪种数据结构(例如dicts / tuples / dict(tuples))既快速又具有存储效率?必须能够对它执行各种图形操作。 如前所述,各种图形表示可能会有所帮助。如何在Python中实现它们?至于图书馆,这个问题有很好的答案。





How can one neatly represent a graph in Python? (Starting from scratch i.e. no libraries!)
What data structure (e.g. dicts/tuples/dict(tuples)) will be fast but also memory efficient?
One must be able to do various graph operations on it.

As pointed out, the various graph representations might help. How does one go about implementing them in Python?

As for the libraries, this question has quite good answers.


回答 0

即使这是一个有点老的问题,我还是想为遇到问题的任何人提供一个切实可行的答案。

假设您以元组列表的形式获取连接的输入数据,如下所示:

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

我发现对于Python中的图形最有用和最有效的数据结构是集合的决定。这将是我们GraphClass的基础结构。您还必须知道这些连接是弧形(定向,以一种方式连接)还是边缘(无定向,以两种方式连接)。我们将通过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']

Even though this is a somewhat old question, I thought I’d give a practical answer for anyone stumbling across this.

Let’s say you get your input data for your connections as a list of tuples like so:

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

The data structure I’ve found to be most useful and efficient for graphs in Python is a dict of sets. This will be the underlying structure for our Graph class. You also have to know if these connections are arcs (directed, connect one way) or edges (undirected, connect both ways). We’ll handle that by adding a directed parameter to the Graph.__init__ method. We’ll also add some other helpful methods.

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

I’ll leave it as an “exercise for the reader” to create a find_shortest_path and other methods.

Let’s see this in action though…

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

回答 1

NetworkX是一个很棒的Python图形库。您将很难找到尚未需要的东西。

而且它是开源的,因此您可以了解他们如何实现算法。您还可以添加其他算法。

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

NetworkX is an awesome Python graph library. You’ll be hard pressed to find something you need that it doesn’t already do.

And it’s open source so you can see how they implemented their algorithms. You can also add additional algorithms.

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


回答 2

首先,经典列表矩阵表示形式的选择取决于目的(取决于您要如何使用表示形式)。众所周知的问题和算法与选择有关。对抽象表示类型的选择决定了应如何实现它。

其次,问题是顶点和边缘是否应该仅根据存在性来表达,或者它们是否携带一些额外的信息。

从Python内置数据类型的角度来看,其他任何地方包含的任何值都表示为对目标对象的(隐藏)引用。如果它是变量(即命名引用),则名称和引用始终存储在(内部)字典中。如果你不需要名字,则引用可以存储在自己的容器-在这里大概Python列表会一直被用于列表的抽象。

Python列表实现为动态引用数组,Python元组实现为具有恒定内容的静态引用数组(不能更改引用的值)。因此,它们可以很容易地被索引。这样,该列表也可以用于矩阵的实现。

表示矩阵的另一种方法是由标准模块实现的数组array-相对于存储的类型(均值)更受限制。元素直接存储值。(该列表将存储对值对象的引用)。这样,它可以提高内存效率,并且对值的访问也更快。

有时,您可能会发现有用的甚至更受限制的表示形式,例如bytearray

First, the choice of classical list vs. matrix representations depends on the purpose (on what do you want to do with the representation). The well-known problems and algorithms are related to the choice. The choice of the abstract representation kind of dictates how it should be implemented.

Second, the question is whether the vertices and edges should be expressed only in terms of existence, or whether they carry some extra information.

From Python built-in data types point-of-view, any value contained elsewhere is expressed as a (hidden) reference to the target object. If it is a variable (i.e. named reference), then the name and the reference is always stored in (an internal) dictionary. If you do not need names, then the reference can be stored in your own container — here probably Python list will always be used for the list as abstraction.

Python list is implemented as a dynamic array of references, Python tuple is implemented as static array of references with constant content (the value of references cannot be changed). Because of that they can be easily indexed. This way, the list can be used also for implementation of matrices.

Another way to represent matrices are the arrays implemented by the standard module array — more constrained with respect to the stored type, homogeneous value. The elements store the value directly. (The list stores the references to the value objects instead). This way, it is more memory efficient and also the access to the value is faster.

Sometimes, you may find useful even more restricted representation like bytearray.


回答 3

有两个出色的图形库 NetworkXigraph。您可以在GitHub上找到这两个库源代码。您始终可以看到函数的编写方式。但是我更喜欢NetworkX,因为它易于理解。
查看其代码以了解其功能。您将获得多个想法,然后可以选择如何使用数据结构制作图形。

There are two excellent graph libraries NetworkX and igraph. You can find both library source codes on GitHub. You can always see how the functions are written. But I prefer NetworkX because its easy to understand.
See their codes to know how they make the functions. You will get multiple ideas and then can choose how you want to make a graph using data structures.