Line graph of a multigraph

Question

I have a weighted directed multigraph and I would like to make a line graph from it. That is replace each edge by a node and connect two nodes if there is a directed path with a common node between the two edges in the original multigraph. However, in my case I only say there is a path between two edges if the weight of the second is greater than the first.

There is an implementation of a basic line graph algorithm in networkx http://networkx.github.io/documentation/latest/reference/generated/networkx.generators.line.line_graph.html . However this does not support multigraphs.

Is there a nice way to do this in networkx or igraph?

Tamás Tamás · Accepted Answer · 2013-08-03T08:18:14

igraph solution (yet untested because I don't have much time now) - assumes that the weights are stored in the weight edge attribute:

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)

Line graph of a multigraph

1 Answers