多圖的線圖

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)