提问者:小点点

在igraph [python]中将两条有向边折叠成一条


我有一个有向图,在许多情况下,两个节点之间有双向的边,权重不同。例如,一个-

我已经看过 g.simplify(),但是我如何让它组合相反的边缘?


共1个答案

匿名用户

假设在相同的两个顶点之间可以有多条相同方向的边,如果是这样的话,您希望将它们的权重相加,可以从

g.simplify(combine_edges='sum')

然后,对于每对顶点 a 和 b,最多一条边从 a 到 b。

要将这些相对的边组合成一条边,您可以使用实例方法to_undirected,它将g转换为无向图。在第一步之后,每对顶点之间最多应该有两条边,总是相对的。所以如果你想从另一个方向减去一个方向上的权重,你可以这样做:

def subwt(attrs):
     if len(attrs) == 1:
         return attrs[0]
     assert len(attrs) == 2
     return attrs[0] - attrs[1]

g.to_undirected(combine_edges=subwt)

但这给了你一个无向图,边的权重是否应该从a到b,还是从b到a,是不可能说的。

如果你想要一个有向图,你如何选择是从a到b,权重为2,还是从b到a,权重为-2?

这里有一个函数,它将产生这样一个有向图;输出图中每条边的方向由输入图中顶点之间遇到的第一条边确定。此外,除了“权重”之外的任何边属性都会从第一条边复制,而忽略任何其他边。

def combine_edges(graph):
    combe = graph.copy() # copies graph attributes, vertex attributes
    combe.delete_edges(None) # removes all edges
    for e in graph.es:
        src, targ = e.tuple
        if combe.are_connected(src, targ):
            ced = combe.es(_source=src, _target=targ)[0]
            ced['weight'] += e['weight']
        elif combe.are_connected(targ, src):
            ced = combe.es(_source=targ, _target=src)[0]
            ced['weight'] -= e['weight']
        else:
            combe.add_edge(src, targ, **e.attributes())
    return combe