An efficient algorithm to compute a line digraph from a digraph

Question

Does anyone know an efficient algorithm to compute a line digraph from a digraph? See http://en.wikipedia.org/wiki/Line_graph (The Wikipedia article mentions the digraph case near the bottom (in the Generalizations sections). Ideally I would like to do this in linear time.

From that section:

• If G is a directed graph, its directed line graph or line digraph has one vertex for each edge of G.
• Two vertices representing directed edges from u to v and from w to x in G are connected by an edge from uv to wx in the line digraph when v = w.

Let G be the directed graph Let L(G) be the directed line graph

The algorithm I can come up with to produce L(G) given G is:

• Iterate through all edges of G to produce the nodes of L(G)
• Iterate through all pairs of nodes (uv, wx) in L(G) and connect if v = w

This is an O(n^2) algorithm.

Seems like there should be a way to get this down to O(n) time. I'm going to go think about this, but I figured I'd ask stack overflow just in case there's some famous (or not so famous) algorithm for doing this that I don't know of.

Answer 1

Hmm... I think there may be a more time-efficient algorithm after some thought too... but it would require a fair amount of book-keeping and a chunk of extra memory to do so.

My basic thoughts are that you loop over all the nodes in G and create connected nodes from the edges connected to each node. With an extra link to keep track of G(edge) to L(G)(node) you may be able to get away with just one loop through the nodes on G.

Answer 2

You can't exape from O(n^2), because there are some graph with a linear graph with a cardinality of the edges equals to the square of the cardinality of the the vertices of the original one: think, for example, at a graph with n+1 vertices, with a single vertex connected to other all vertices: you have then to build a clique with n vertices, so with (n-1)^2 edges.

The complexity of an algorithm is bounded from the bottom by the size of the output it produces.

This, of course, doesn't mean we don't have to find smart algorithms. I've thinked at that:

LG(LN,LE) getLinearGraph(G(N,E)) {
  LN = EmptySet();
  LE = EmptySet();
  for (Vertex v : N) {
    verticesToAdd = EmptySet()
    for (Vertex i : out-degree(v) {
      toAdd += textual-rep((v,i));
    }
    LN += toAdd;
    LE += make-clique(toAdd);
  }
}