使用networkX查找节点前辈的最优雅的方式

Question

我正在使用 NetworkX 使用 python 开发图形模型项目。 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 {}

我想使用有向图，因为我正在编码具有方向的依赖项（在上面的示例中，我有以“a”为条件的“b”的封闭形式，而不是相反）。

对于给定的节点，我想找到该节点的前辈。对于上面的示例，par('b') 应返回 ['a']。 NetworkX 确实有一个后继函数，可以查找任何节点的子节点。显然，通过遍历所有节点并找到那些具有“b”作为子节点的节点是可行的，但节点数量将是 Ω(n)（这对于我的应用程序来说太昂贵了）。

我无法想象这么简单的东西会被排除在这个制作精良的包之外，但找不到任何东西。

一种有效的选择是存储图的有向版本和无向版本；所有无向边本质上都是通过添加两个有向边来实现的，因此可以采用相邻节点和子节点（这将是前驱节点）之间的集合差异。

问题是我不确定包装现有的 networkx DiGraph 和 Graph 类来完成此操作的最 Pythonic 方法。实际上，我只想得到一个类 PGraph，其行为与 networkx DiGraph 类完全相同，但除了 successors(node) 函数之外，还有一个 predecessors(node) 函数。

PGraph是否应该继承DiGraph并封装Graph（用于前辈函数中）？那么我应该如何强制将所有节点和边添加到它包含的有向图和无向图中？我是否应该重新实现在 PGraph 中添加和删除节点和边的函数（以便在有向和无向版本中添加和删除它们）？我担心如果我错过了一些晦涩难懂的东西，我以后会头疼，这可能并不意味着好的设计。

或者（请让这是True）是否有一种简单的方法可以在 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

有一个前驱（和前驱_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': {}}

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

图并不总是树，因此“父”的概念通常没有意义。因此，我认为这没有实施。

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

Answer 4

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

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

Answer 5

一般来说，如果您尝试创建一个与现有图相比边缘方向相反的有向图（您对 PGraph 类所做的操作），转置邻接矩阵 应该可以解决问题。

具体来说，在 NetworkX 中，可以使用 DiGraph.reverse 方法用于此目的。

（如果由于某种原因您被迫使用没有 predecessors 或 pred 的非常旧的 NetworkX 版本 - 反转图表并使用 successors< /代码>。）