我正在用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)(这对我的应用程序来说太贵了)。
我无法想象这么简单的东西会从这个精心制作的包裹中被遗漏,但却找不到任何东西。
一个有效的选择是存储图的有向和无向版本;所有无向边本质上都是通过添加两个有向边来实现的,因此可以在相邻节点和子节点(将是前一个节点)之间取得按集的差异。
问题是,我不确定用什么方法来包装现有的networkx有向图和Graph类来实现这一点。实际上,我只想得到一个PGraph类,它的行为与networkx有向图类完全相同,但是除了successors(node)
函数之外还有一个predecessors(node)
函数。
PGraph是否应该继承有向图并封装图(用于precedes函数)?那么,我应该如何强制将所有节点和边添加到它包含的有向图和无向图中?我是否应该重新实现在pggraph中添加和删除节点和边的函数(以便在有向和无向版本中添加和删除节点和边)?我担心,如果我错过了一些晦涩难懂的东西,我会在以后头痛,这可能并不意味着良好的设计。
或者(请将其设为True
)有没有简单的方法可以在networkx.DiGraph中获取节点的前导,而我完全错过了它?
非常感谢你的帮助。
编辑:
我想这就行了。pggraph从有向图继承并封装另一个有向图(此图相反)。我重写了添加和删除节点和边的方法。
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)
你觉得这个办法怎么样?它可能会使内存使用量加倍,但我认为这是可以接受的。是不是太复杂了?这个设计好吗?
一个图并不总是一棵树,所以“父”的概念通常没有意义。因此,我假设这没有实现。
要实现所需功能,请从
DiGraph
继承并重载所有允许添加节点的方法。根据这些信息构建树数据结构。另一种实现方法如下:
创建基本图形
寻找下游边缘
寻找上游边缘
更多详细信息请参见blog
有一种前置(和前置)方法: http://networkx.lanl.gov/reference/generated/networkx.DiGraph.predecessors.html#networkx.DiGraph.predecessors
同样,没有什么可以阻止您像G.pred那样直接访问数据结构
相关问题 更多 >
编程相关推荐