An efficient algorithm to compute a line digraph from a digraph

2
votes

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.

2
algorithmgraph-theorylinegraph
I'm guessing the best way to go about this is to change the second step "iterate through all pairs of nodes (uv, wc) in L(G)...)" so that its instead "iterate through all nodes v in G". - stonea
Then for every incoming edge uv and outgoing edge vx there will be an edge in L(G) (between nodes uv and vx). Although that still sounds like an O(n^2) algorithm. Maybe there's some kind of amortized analysis for this? - stonea

2 Answers

1
votes

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.

1
votes

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);
  }
}