networkx 中的分组节点

Question

我不知道正确的术语，但我在 networkx 中有一个有向图，我想使用映射函数合并相关节点，维护 link 到原始节点

例如，如果我有这张图：

a1 -> b1
a2 -> b2
a1 -> c1
a2 -> d2
b1 -> d2
c1 -> f1
c2 -> f2
b1 -> c2

和这个函数

def mymap(node):
    return node[0]

那么我想得到这张图作为结果：

a -> b
a -> c
a -> d
b -> d
c -> f
b -> c

有节点数据

a: original_nodes = [a1, a2]
b: original_nodes = [b1, b2]
c: original_nodes = [c1, c2]
d: original_nodes = [d2]
f: original_nodes = [f1, f2]

有办法吗？（无需手动遍历节点和边缘；我可以做到，但我认为这将是一项常见任务）

Answer 1

嗯，我想我以前记得这样做过，只是在我的一个 Python 脚本中发现了这个：

def supergraph(g1, keyfunc, allow_selfloops=True):
    g2 = nx.DiGraph()
    for (a,b,d) in g1.edges_iter(data=True):
        result = keyfunc(g1,a,b,d)
        if result is not None:
            a2,b2,w = result
            if a2 != b2 or allow_selfloops:
                g2.add_edge(a2,b2)
                try:
                    g2[a2][b2]['weight'] += w
                except:
                    g2[a2][b2]['weight'] = w

            for u2,u in [(a2,a),(b2,b)]:
                if not u2 in g2:
                    g2.add_node(u2, original_nodes=set([u]))
                else:
                    try:
                        g2.node[u2]['original_nodes'].add(u)
                    except:
                        g2.node[u2]['original_nodes'] = set([u])
    return g2

其中 keyfunc(g,a,b,d) 具有图 g、节点 a 和 b 以及边数据 d，是一个映射函数，应该 return 或者 None（忽略该边）或具有新节点 a2 和 b2 以及权重 w.

的元组 (a2, b2, w)

networkx 中的分组节点

grouping nodes in networkx

python

graph

networkx