python - 在图形或森林中提取不同的树
问题描述
我在图中有多个独立的树。我想分别提取它们。我正在使用 pydot 来绘制图表。我分别想要父 1 图表和父 2 图表。在我的用例中,树会随机生长(不是一棵一棵)。
graph = pydot.Dot(graph_type="digraph")
parent_node_1 = pydot.Node(name='Parent_1', style='filled', fillcolor='yellow')
parent_node_2 = pydot.Node(name='Parent_2', style='filled', fillcolor='yellow')
child_node_1 = pydot.Node(name='Child 1', style='filled', fillcolor='yellow')
child_node_2 = pydot.Node(name='Child 2', style='filled', fillcolor='yellow')
e1 = pydot.Edge('Parent_1', 'Child 1')
e2 = pydot.Edge('Parent_2', 'Child 2')
graph.add_node(parent_node_1)
graph.add_node(parent_node_2)
graph.add_node(child_node_1)
graph.add_node(child_node_2)
graph.add_edge(e1)
graph.add_edge(e2)
graph.write_png('dummy_graph.png')
解决方案
这在 pydot 中是一个麻烦的问题,因为您需要能够以简单的方式遍历图。这是可能的,但我不会推荐它。在您的测试用例中工作的简单代码在下面的代码段中。我敢打赌它在某个地方有一些错误,所以请谨慎使用。
def get_out_edges_and_children(g, node):
out_edges = {e for e in g.get_edges() if e.get_source() == node.get_name()}
children_names = {e.get_destination() for e in out_edges}
children = [n for n in graph.get_nodes() if n.get_name() in children_names]
return out_edges, children
all_node_names = {n.get_name() for n in graph.get_nodes()}
all_children_names = {e.get_destination() for e in graph.get_edges()}
all_roots = all_node_names - all_children_names #roots are children to noone
trees = []
for r in all_roots:
nodes_to_process= graph.get_node(r)
t = pydot.Dot()
t.add_node(nodes_to_process[0])
i = 0
while i < len(nodes_to_process):
current_node=nodes_to_process[i]
edges,children = get_out_edges_and_children(graph,current_node)
for c in children: t.add_node(c)
for e in edges: t.add_edge(e)
nodes_to_process += children
i += 1
trees.append(t)
查看其他图形库以获得更强大的解决方案,例如networkx。它还可以导入 pydot 对象,所以过渡应该是平滑的!
推荐阅读
- php - Heroku HTTP 响应代码 200,应该是 404
- c++ - 寻找最小编号。可以用来给 x 找零的面额
- javascript - ([JavaScript) 我无法使用对象的整数键访问值
- c# - 具有多部分的图表线
- linux - 使用 GNU Make 分叉错误
- r - 在 Plotly 动画中更改“框架”标签
- mongodb - 我直到今天才使用 $gte 在 mongodb 中获取数据
- node.js - MongoError: pool is draining, 在集成测试中使用 MongoMemoryServer 时禁止新操作
- java - 如何在抽象测试类中模拟自动装配的实例?
- python - Plotly:如何在桑基图中设置节点位置?