在 Python 中表示图(数据结构) [英] Representing graphs (data structure) in Python

问题描述

如何在 图表://en.wikipedia.org/wiki/Python_(programming_language)" rel="noreferrer">Python?(从头开始，即没有库！)
什么数据结构(例如dicts/tuples/dict(tuples))既快速又节省内存?
必须能够做各种图形操作.

正如所指出的，各种图形表示可能会有所帮助.如何在 Python 中实现它们?

至于库，这个问题 有很好的答案.

解决方案

尽管这是一个有点老的问题，但我想我会为任何遇到此问题的人提供实用的答案.

假设您将连接的输入数据作为元组列表获取，如下所示:

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

我发现对 Python 中的图形最有用和最有效的数据结构是集合字典.这将是我们的 Graph 类的底层结构.您还必须知道这些连接是弧线(有向，单向连接)还是边(无向，双向连接).我们将通过向 Graph.__init__ 方法添加一个 directed 参数来处理这个问题.我们还将添加一些其他有用的方法.

导入pprint从集合导入 defaultdict类图(对象):"""图数据结构，默认无向."""def __init__(self,connections,directed=False):self._graph = defaultdict(set)self._directed = 定向self.add_connections(连接)def add_connections(self, connection):""" 将连接(元组对列表)添加到图形 """对于连接中的节点 1、节点 2:self.add(node1, node2)def add(self, node1, node2):"""在node1和node2之间添加连接"""self._graph[node1].add(node2)如果不是 self._directed:self._graph[node2].add(node1)def删除(自我，节点):""" 删除对节点 """ 的所有引用对于 n, cxns in self._graph.items(): # python3: items();python2: iteritems()尝试:cxns.remove(节点)除了 KeyError:经过尝试:del self._graph[节点]除了 KeyError:经过def is_connected(self, node1, node2):""" node1 是否直接连接到 node2 """在 self._graph 中返回 node1，在 self._graph[node1] 中返回 node2def find_path(self, node1, node2, path=[]):"""查找node1和node2之间的任意路径(可能不是最短的)"""路径 = 路径 + [节点 1]如果节点 1 == 节点 2:返回路径如果 node1 不在 self._graph 中:返回无对于 self._graph[node1] 中的节点:如果节点不在路径中:new_path = self.find_path(node, node2, path)如果新路径:返回新路径返回无def __str__(self):返回 '​​{}({})'.format(self.__class__.__name__, dict(self._graph))

我将把它作为读者练习"来创建find_shortest_path 和其他方法.

让我们看看它的实际效果...

<预><代码>>>>连接 = [('A', 'B'), ('B', 'C'), ('B', 'D'),('C', 'D'), ('E', 'F'), ('F', 'C')]>>>g = Graph(连接，有向=真)>>>Pretty_print = pprint.PrettyPrinter()>>>Pretty_print.pprint(g._graph){'A':{'B'}，'B': {'D', 'C'},'C':{'D'}，'E':{'F'}，'F':{'C'}}>>>g = Graph(connections) # 无向>>>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']

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.

解决方案

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

这篇关于在 Python 中表示图(数据结构)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！