使用networkX查找节点前驱的最优雅方法

Question

我正在用Python做一个图形模型项目，使用的是NetworkX库。NetworkX提供了一些简单好用的功能，主要是通过字典来实现的。

import networkx as nx
G = nx.DiGraph() # a directed graph
G.add_edge('a', 'b')
print G['a'] # prints {'b': {}}
print G['b'] # prints {}

我想使用有向图，因为我在编写一些有方向的依赖关系（在上面的例子中，我有'b'在'a'的条件下的闭合形式，而不是反过来）。

对于给定的节点，我想找到这个节点的前驱节点。比如在上面的例子中，par('b')应该返回['a']。NetworkX确实有一个后继函数，可以找到任何节点的子节点。显然，通过遍历所有节点并找到那些以'b'为子节点的节点是可行的，但这样做的复杂度是Ω(n)，对于我的应用来说，这样的开销太大了。

我无法想象这么简单的功能会在这个做得很好的库中被遗漏，但我找不到相关的内容。

一个有效的选择是同时存储一个有向图和一个无向图；所有的无向边实际上是通过添加两个有向边来实现的，因此可以通过相邻节点和子节点之间的集合差来找到前驱节点。

问题是我不确定用最“Pythonic”的方式来封装现有的networkx DiGraph和Graph类，以实现这个功能。其实我只想得到一个名为PGraph的类，它的行为和networkx的DiGraph类完全一样，但除了successors(node)函数外，还要有一个predecessors(node)函数。

PGraph应该继承自DiGraph，并封装Graph（用于前驱函数）吗？那么我该如何确保所有节点和边都被添加到它包含的有向图和无向图中呢？我是否应该在PGraph中重新实现添加和移除节点和边的函数（这样它们就会同时被添加和移除到有向和无向版本中）？我担心如果我漏掉了什么细节，以后会很麻烦，这可能不是一个好的设计。

或者（希望真的是这样）在networkx.DiGraph中是否有简单的方法可以获取一个节点的前驱节点，而我完全错过了？

非常感谢你的帮助。

---

编辑：

我觉得这个方法可以解决问题。PGraph继承自DiGraph，并封装了另一个反向的DiGraph。我重写了添加和移除节点及边的方法。

import networkx as nx

class PGraph(nx.DiGraph):
    def __init__(self):
        nx.DiGraph.__init__(self)
        self.reversed_graph = nx.DiGraph()
    def add_node(self, n, attr_dict=None, **attr):
        nx.DiGraph.add_node(self, n, attr_dict, **attr)
        self.reversed_graph.add_node(n, attr_dict, **attr)
    def add_nodes_from(self, ns, attr_dict=None, **attr):
        nx.DiGraph.add_nodes_from(self, ns, attr_dict, **attr)
        self.reversed_graph.add_nodes_from(ns, attr_dict, **attr)
    def add_edge(self, a, b, attr_dict=None, **attr):
        nx.DiGraph.add_edge(self, a, b, attr_dict, **attr)
        self.reversed_graph.add_edge(b, a, attr_dict, **attr)
    def add_edges_from(self, es, attr_dict=None, **attr):
        nx.DiGraph.add_edges_from(self, es, attr_dict, **attr)
        self.reversed_graph.add_edges_from(es, attr_dict, **attr)
    def remove_node(self, n):
        nx.DiGraph.remove_node(self, n)
        self.reversed_graph.remove_node(n)
    def remove_nodes_from(self, ns):
        nx.DiGraph.remove_nodes_from(self, ns)
        self.reversed_graph.remove_nodes_from(ns)
    def remove_edge(self, a, b):
        nx.DiGraph.remove_edge(self, b, a)
        self.reversed_graph.remove_edge(a, b)
    def remove_edges_from(self, es):
        nx.DiGraph.remove_edges_from(self, es)
        self.reversed_graph.remove_edges_from([ (b,a) for a,b in es])
# the predecessors function I wanted
    def predecessors(self, n):
        return self.reversed_graph.successors(n)

你觉得这个解决方案怎么样？这可能会使内存使用量翻倍，但我觉得这是可以接受的。这样做会不会太复杂？这是一个好的设计吗？

Answer 1

图（graph）不一定是树（tree），所以“父节点”（parent）这个概念有时候是没意义的。因此，我猜这个功能可能没有被实现。

如果你想实现你需要的功能，可以从 DiGraph 这个类继承，并重写所有可以添加节点的方法。然后根据这些信息来构建树的数据结构。

Answer 2

另一种实现这个功能的方法如下：

创建基本图形

import networkx as nx
import matplotlib.pyplot as plt

G = nx.DiGraph()
G.add_edges_from([('A', 'B'), ('A', 'C'), ('D', 'B'), ('E', 'C'), ('E','F'), ('B', 'H'), ('B', 'G'), ('B', 'F'), ('C', 'G'), ('Q', 'D')])

pos = nx.spring_layout(G)
nx.draw_networkx_nodes(G, pos, cmap=plt.get_cmap('jet'),node_size = 50)
nx.draw_networkx_edges(G, pos, edge_color='r', arrows=True)
nx.draw_networkx_labels(G, pos)
plt.show()

查找下游边

print("Downstream Edges of 'B' (just example)-->")
print(list(nx.dfs_edges(G,'B')))

查找上游边

print("Upstream Edges of 'B' (just example)-->")
print(list(nx.edge_dfs(G,'B', orientation='reverse')))

更多细节可以在这个 博客 中找到

Answer 3

这里有一个叫做前驱（predecessor）的方法，还有一个叫做前驱迭代器（predecessor_iter）的方法：

你可以在这里查看详细信息：http://networkx.lanl.gov/reference/generated/networkx.DiGraph.predecessors.html#networkx.DiGraph.predecessors

另外，你也可以直接访问数据结构，比如用 G.pred。

 In [1]: import networkx as nx
 In [2]: G = nx.DiGraph() # a directed graph
 In [3]: G.add_edge('a', 'b')
 In [4]: G.predecessors('b')
 Out[4]: ['a']
 In [5]: G.pred['b']
 Out[5]: {'a': {}}