使用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（用于predecessors函数）吗？然后，我应该如何强制所有节点和边缘都添加到它包含的有向和无向图中？我应该重新实现添加和删除节点和边缘的函数，以便将它们添加和删除到有向和无向版本中吗？我担心如果我错过了一些模糊的东西，那么以后可能会遇到头疼的问题，这可能不意味着良好的设计。或者（请让这是真的）在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)

你对这个解决方案有什么看法？它可能会使内存使用量增加一倍，但我认为这是可以接受的。它是否过于复杂？这是一个好的设计吗？

- user

Answer 1

有一个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': {}}

- Aric

---

谢谢您发布这篇文章——我不久前发现了pred[...]。我之前没有使用它们，然后在另一台电脑上安装了networkx。也许它们不在我曾经使用的版本中？或者第一次可能只是打错字了？ - user

我在networkx中没有可用的前任节点，但我有前驱节点。 - Rotail

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

更多细节请参见博客

- KuboAndTwoStrings

Answer 3

图不总是一棵树，因此“父节点”的概念通常没有意义。因此，我认为这并没有被实现。

要实现您需要的内容，请从DiGraph继承并重载所有允许添加节点的方法。从该信息构建树形数据结构。

- Aaron Digulla

---

啊，对不起，更正式地说，前驱节点是我想要的更好的描述。我肯定是在处理一般图，而不仅仅是树。我担心我还需要重载删除节点的方法，因为我需要在有向图和无向图中保持相同的节点集合。然后还有批量添加节点的方法。此外，我不确定这些方法在哪里被称为“底层实现”，所以我担心即使我没有自己调用它们，我也可能会错过一些重要的东西。 - user

我怀疑 DiGraph 中的任何方法都不会添加或删除节点，除非你告诉它们这样做。话虽如此，只需查看类的源代码。毕竟这是 Python。代码可能足够简单易懂。也许所有调用都会汇聚到 2-3 个需要重载的方法。 - Aaron Digulla

谢谢你的帮助 - 我已经发布了对应于该解决方案的代码。你觉得怎么样？我不得不覆盖 DiGraph 中的 8 个函数。看完后，你认为这是一个好的设计吗？ - user

@starghost：我喜欢这个解决方案。它简单、明显、紧凑。在性能或内存成为问题之前，不必担心。 - Aaron Digulla

Answer 4

如果G是nx.DiGraph()的实例，并且node是您要搜索前驱节点的源节点，则以下内容将为您提供前驱节点列表："如果G是nx.DiGraph（）的实例，而node是您搜索其前驱节点的源节点，则以下内容将为您提供前驱节点列表："

predecessors = [pred for pred in G.predecessors(node)]

- dopexxx

---

不错。使用 + [node]，这是一个很好的一行代码来处理异常。 - xtian

Answer 5

通常情况下，如果您想创建一个有向图，其中边的方向与现有图相反（就像您使用PGraph类所做的那样），则应该使用转置邻接矩阵来解决问题。

具体而言，在NetworkX中，可以使用DiGraph.reverse方法来实现这一点。

（如果由于某种原因您被迫使用非常旧的NetworkX版本，没有predecessors或pred - 可以反转图形并使用successors。）

- Dev-iL