Search for an algorithm for inverting (reverse? Mirror? Turn inside out) DAG

Question

Am I looking for an invert algorithm (reverse? Turn inside out)? a DAG:

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

The view that I use is invariably a DAG (no "parent" pointers). I would like to somehow cross the graph when plotting the “mirror image” with equivalent nodes, but with the direction of the relationship between the inverted nodes.

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

Thus, the input is a collection of "roots" (here {{A}). The output should be a set of "roots" in the graph of results: {G, F}. (By the root, I mean node without inbound links. Leaf node without outbound links.)

The roots of input become the leaves of the exit and the visa vice versa. The transformation should be the reverse of itself.

(For the curious, I would like to add a function to the library that I use to represent XML for a structural query, with 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

Rotate the graph by constructing a set of back edges and a list of leaf nodes.

Perform a topological view of the reversed edges using the starting nodes of the leaf (which are now the root nodes).

Build the inverse graph based on the inverse edges, starting at the end of the sorted list. Since the nodes are built in the reverse topological order, you are guaranteed to create children of this node before building the node, so it is possible to create an immutable representation.

This is either O (N) if you use structures for an intermediate view that track all links in both directions associated with a node, or O (NlnN) if you use sorting to find all node links. For small graphs or languages ​​that do not suffer from, you can simply construct the graph lazily, rather than explicitly performing topological sorting. So it depends a little on what you implement all this in how much it 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 deep search marking where you have already been, and each time you go through the arrow, you add a link back to your result in the DAG. Add leaves as roots.

Answer 3

My intuitive suggestion was to do the depth of the first crawl of your chart and build your mirror chart at the same time.

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

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

Answer 4

I solved this with a simple graph traversal. Keep in mind that topological sorting will only be useful for oriented 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 go over the list g [v] and this will give you all (v, u) edges.

To build a reverse graph, create 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 a very intensive amount of memory for large graphs (doubling the memory usage), but it is a very simple way to work with them rather quickly. There may be smarter decisions related to building a generator and using some kind of dfs algorithm, but I have not thought about that.

Answer 5

A deep search could generate what you need: Pay attention to your path through the tree and each time you go add the inverse to the resulting DAG (leaves are the roots).