Линейный график мультиграфа

У меня есть взвешенный ориентированный мультиграф, и я хотел бы сделать из него линейный график. То есть заменить каждое ребро на узел и соединить два узла, если существует направленный путь с общим узлом между двумя ребрами в исходном мультиграфе. Однако в моем случае я только говорю, что существует путь между двумя ребрами, если вес второго больше, чем вес первого.

В networkx http://networkx.github.io/documentation/latest/reference/generated/networkx.generators.line.line_graph.html. Однако это не поддерживает мультиграфы.

Есть ли хороший способ сделать это в networkx или igraph?


python igraph networkx
person Anush    schedule 02.08.2013    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Решение igraph (пока не протестировано, потому что у меня мало времени) - предполагает, что веса хранятся в атрибуте weight edge:

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)
person Tamás    schedule 03.08.2013