Seeking algorithm to invert (reverse? mirror? turn inside-out) a DAG

Question

I'm looking for an algorithm to "invert" (reverse? turn inside-out?) a DAG:

       A*      # I can't ascii-art the arrows, so just
      / \      # pretend the slashes are all pointing
     B   C     # "down" (south-east or south-west)
    /   / \    # e.g. 
   G   E   D   # A -> (B -> G, C -> (E -> F, D -> F))
        \ /
         F

The representation I'm using is immutable truly a DAG (there are no "parent" pointers). I'd like to traverse the graph in some fashion while building a "mirror image" graph with equivalent nodes, but with the direction of relations between nodes inverted.

         F*
        / \
   G*  E   D   # F -> (E -> C -> A, D -> C -> A), G -> B -> A
    \   \ /    # 
     B   C     # Again, arrows point "down"
      \ /      # 
       A       # 

So the input is a set of "roots" (here, {A}). The output should be a set of "roots" in the result graph: {G, F}. (By root I mean a node with no incoming references. A leaf is a node with no outgoing references.)

The roots of the input become the leaves of the output and visa versa. The transformation should be an inverse of itself.

(For the curious, I'd like to add a feature to a library I'm using to represent XML for structural querying by which I can map each node in the first tree to its "mirror image" in the second tree (and back again) to provide more navigational flexibility for my query rules.)

Answer 1

Traverse the graph building a set of reversed edges and a list of leaf nodes.

Perform a topological sort of the reversed edges using the leaf (which are now root) nodes to start with.

Construct the reversed graph based on the reversed edges starting from the end of the sorted list. As the nodes are constructed in reverse topological order, you are guaranteed to have constructed the children of a given node before constructing the node, so creating an immutable representation is possible.

This is either O(N) if you use structures for your intermediate representation which track all links in both directions associated with a node, or O(NlnN) if you use sorting to find all the links of a node. For small graphs, or languages which don't suffer from stack overflows, you can just construct the graph lazily rather than explicitly performing the topological sort. So it depends a little what you're implementing it all in how different this would be.

A -> (B -> G, C -> (E -> F, D -> F))

original roots: [ A ]
original links: [ AB, BG, AC, CE, EF, CD, DF ] 
reversed links: [ BA, GB, CA, EC, FE, DC, FD ]
reversed roots: [ G, F ]
reversed links: [ BA, CA, DC, EC, FE, FD, GB ] (in order of source)
topologically sorted: [ G, B, F, E, D, C, A ]
construction order : A, C->A, D->C, E->C, F->(D,E), B->A, G->B

Answer 2

Just do a depth-first search marking where you have already been, and each time you traverse an arrow you add the reverse to your result DAG. Add the leaves as roots.

Answer 3

My intuitive suggestion would be to perform a Depth First traversal of your graph, and construct your mirrored graph simultaneously.

When traversing each node, create a new node in the mirrored graph, and create an edge between it and its predecessor in the new graph.

If at any point you reach a node which has no children, mark it as a root.

Answer 4

I solved this with a simple graph traversal. Keep in mind topological sorting will only be useful for directed acyclic graphs.

I used an adjacency list, but you can do a similar thing with an adjacency matrix.

In Python it looks like this:

# Basic Graph Structure
g = {}
g[vertex] = [v1, v2, v3] # Each vertex contains a lists of its edges

To find all the edges for v, you then traverse the list g[v] and that will give you all (v, u) edges.

To build the reversed graph make a new dictionary and build it something like this:

    reversed = {}
    for v in g:
        for e in g[v]:
            if e not in reversed:
                reversed[e] = []
            reversed[e].append(v)

This is very memory intensive for large graphs (doubling your memory usage), but it is a very easy way to work with them and quite quick. There may be more clever solutions out there involving building a generator and using a dfs algorithm of some sort, but I have not put a lot of thought into it.

Answer 5

Depth-first search might be able to generate what you're after: Note your path through the tree and each time you traverse add the reverse to the resulting DAG (leaves are roots).