1

我有一个加权有向多重图，我想从中制作一个折线图。如果在原始多重图中的两条边之间存在具有公共节点的有向路径，则将每个边替换为一个节点并连接两个节点。但是，在我的情况下，我只说如果第二个边的权重大于第一个边，则两条边之间有一条路径。

networkx http://networkx.github.io/documentation/latest/reference/generated/networkx.generators.line.line_graph.html中有一个基本线图算法的实现。但是，这不支持多重图。

在networkx或igraph中是否有一种很好的方法来做到这一点？

4

1 回答 1

1

igraph 解决方案（尚未经过测试，因为我现在没有太多时间） - 假设权重存储在weight边缘属性中：

weights = g.es["weight"]
line_graph_edges = []
for v in xrange(g.vcount()):
    incoming = g.incident(v, mode="in")
    outgoing = g.incident(v, mode="out")
    line_graph_edges.extend((e1, e2) for e1 in incoming for e2 in outgoing
        if weights[e1] < weights[e2])
line_graph = Graph(g.ecount(), line_graph_edges)
于 2013-08-03T08:18:14.280 回答