多图的线图

Question

我有一个加权有向多图，我想从它做一个线图。如果在原始多图的两条边之间存在一个具有公共节点的有向路径，那么将替换每个边的节点并连接两个节点。然而，就我而言，我只说如果第二个的重量大于第一个，那么在两个边之间就有一条路径。

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

有没有一种很好的方式来做到这一点在networkx或igraph？

Answer 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)