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