How to remove invalid edges in a graded graph of a directed acyclig?

Question

The following sample graph is part of a directional acyclic graph that must be layered and cleaned so that only the edges connecting successive layers are preserved.

So, I need to eliminate the edges that form the "shortcuts", i.e. jump between endless layers.

The following considerations apply:

• The bluish cut of the ring is valid because, starting from 83140 and ending at 29518, both branches have the same number of (3) intermediate nodes, and there is no path that is longer between the beginning and end of the node;
• The green ring starting at 94347 and ending at 107263 has an invalid edge (already with red cross), since the left branch includes only one intermediary node, while the right branch includes three intermediate nodes; In addition, since the first edge of this branch is already valid - we know that this refers to a real blue ring - it is possible to know which one is the right edge for the strikeout - otherwise it would be impossible to know which layer should be assigned to node 94030 and therefore it must be eliminated;
• If we look at the pink ring after looking at the green, we know that the bottom red-crossed edge should be removed.
• BUT, if we consider only the yellow ring, both branches seem correct (they contain the same number of internal nodes), but in fact they seem correct, because they contain symmetrical errors (shortcuts jumping with the same number of nodes on both branches). If we take this ring locally, at least one of the branches will be in the wrong layers, so more global data must be used to prevent this error.

My questions:

• What typical concepts and operations are involved in the formulation and possible solution of this problem?
• Is there an algorithm for this?

Answer 1

First, topologically sort the graph.

Now, starting from the beginning of the sorted array, start the width of the first search and try to find the desired "depth" (that is, the distance from the root) of each node. Since a node can have several parents, for node x , depth[x] is the maximum depth of all parents, plus one. We initialize depth for all nodes as -1 .

Now, bypassing bfs, when we encounter node p , we try to update the depth of all its children c , where depth[c] = max(depth[c],depth[p]+1) . Now there are two ways to detect a child using a shortcut.

• if depth[p]+1 < depth[c] , this means that c has a parent with a greater depth than p . Therefore, edge p to c should be a shortcut.
• if depth[p]+1 > depth[c] and depth[c]!=-1 , this means that c has a parent with less depth than p . Therefore, p is the best parent, and the other parent of c must have a label with p .

In both cases, we mark c as problematic.

Now our goal is for each "problem" node x , we check all its parents, the depth of which should be depth[x]-1 . If any of them have a depth that is lower than this, she has a short belt with x that needs to be removed.

Since the graph can have several roots, we must have a variable to mark the visited nodes and repeat the above thing for all that remained inaccessible.

This sorts the problem with the yellow ring, because before we visit any node, all of its predecessors were already visited and correctly ranked. This is provided by topological sorting.

(Note: we can do this in just one pass. Instead of marking the problem nodes, we can maintain the parent variable for all nodes and remove the edge with the old parent whenever case 2 happens. Case 1 should be obvious)