What algorithm can I apply to this DAG?

Question

I have a DAG representing a list of properties. These properties are such that if a> b, then a has a directed edge to b. This is also transitive, so if a> b and b> c, then a has a directed edge to c.

However, the directional edge from a to c is redundant, since a has a directed edge to b and b has a directed edge to c. How can I crop all these excess edges? I was thinking about using a minimal spanning tree algorithm, but I'm not quite sure which algorithm is appropriate in this situation.

Suppose I could do a first depth search from each node and all its outgoing edges and compare if it can reach certain nodes without using certain edges, but this seems terribly inefficient and slow.

After completion of the algorithm, the output will be a linear list of all nodes in the order agreed with the schedule. So, if a has three directed edges to b, c and d. b and c, each of which has a directed edge to d, the output can be either abcd or acbd.

Answer 1

This is called a transitional recovery problem . Formally speaking, you are looking for a minimal (least edge) directed graph whose transitive closure is equal to the transitive closure of the input graph. (The diagram on the above link on Wikipedia makes it clear.)

Apparently, there is an effective algorithm for solving this problem, which takes the same time as for creating a transitive closure (i.e., the more general inverse problem of adding transitive connections instead of removing them), however, a link to a 1972 article by Aho, Gary and Ullman costs $ 25 to download, and some quick searches did not display any nice descriptions.

EDIT: Scott Cotton graphlib contains a Java implementation ! . This Java library looks very well organized.

Answer 2

In fact, looking around a bit more, I think Topologicalsort is what I'm really here for.

Answer 3

If it is already n nodes with directed edges:

• Starting at any point M, collapse all its child edges, select the largest child (for example, N), remove other edges, the complexity should be o (n). If N does not exist (without a child edge, go to step 3).
• start with N, repeat step 1.
• start at point M, select the smallest parent node (e.g. T), remove the other edges.
• start with T, repeat step 3 .....

---

This is actually just an ordering algorithm, and the total complexity should be o (0.5n ^ 2).

---

One of the problems is that if we want the parent nodes to loop one node, we need more memory to register the edge so that we can track back from the child to the parent. This can be improved in step 3, where we select one node from the left nodes, large M, which means that we need to save the list of nodes to find out which nodes remain.