views:

600

answers:

4

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.)

A: 

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).

Nerdling
How and why? You need to expand on this answer for it to be any use.
SpoonMeiser
Seems pretty clear to me. +1.
j_random_hacker
Especially with a link provided to how DFS works ...
Nerdling
How does knowing how to perform a depth first search help solve this problem?
SpoonMeiser
Quoting starblue: "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."
Nerdling
+1  A: 

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.

starblue
+2  A: 

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.

sykora
The difficult bit is that the nodes are *immutable* once created. so when I create a node i need to know all its children and they must be complete. I can't add stuff incrementally.
bendin
@bendin: During the DFS, you'll need to create a second DAG using a mutable datatype for nodes. Afterwards, use a subsequent DFS over this new DAG to produce nodes of the desired immutable datatype.
j_random_hacker
Like j_random_hacker said, you'll probably need a mutable node type to serve as intermediate. In order to know all a nodes children during creation, you must know all of its parents in the original graph, the first time you see it. That could get a bit difficult.
sykora
+2  A: 

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
Pete Kirkham
Yes, this is basically what I spent the afternoon coding up except that I'm not actually explicitly doing a topological sort. I'm looping over the nodes picking those next whose children have already been mirrored. The effect is the same.
bendin
(It's a shame there's no clever recursive solution that doesn't require so many intermediate data structures.)
bendin