<p>I ended up solving it this way:</p>

<p>My data structure is made of <code>dependends</code> dictionary, from a node id to a list of nodes that depend on it (ie. its followers in the DAG).</p>

<p>I haven't calculated the exact complexity of it, but it swallowed my graph of several thousands in a split second.</p>

<pre><code>_transitive_closure_cache = {}
def transitive_closure(self, node_id):
    """returns a set of all the nodes (ids) reachable from given node(_id)"""
    global _transitive_closure_cache
    if node_id in _transitive_closure_cache:
        return _transitive_closure_cache[node_id]
    c = set(d.id for d in dependents[node_id])
    for d in dependents[node_id]:
        c.update(transitive_closure(d.id))  # for the non-pythonists - update is update self to Union result
    _transitive_closure_cache[node_id] = c
    return c

def can_reduce(self, source_id, dest_id):
    """returns True if the edge (source_id, dest_id) is redundant (can reach from source_id to dest_id without it)"""
    for d in dependents[source_id]:
        if d.id == dest_id:
            continue
        if dest_id in transitive_closure(d.id):
            return True # the dest node can be reached in a less direct path, then this link is redundant
    return False

# Reduce redundant edges:
for node in nodes:      
    dependents[node.id] = [d for d in dependents[node.id] if not can_reduce(node.id, d.id)]
</code></pre>

CC BY-SA 3.0
2011-06-29T07:26:55.317Z
2011-06-29T07:26:55.317Z
Iftah
<p><a href="http://epubs.siam.org/sicomp/resource/1/smjcat/v1/i2/p131_s1?isAuthorized=no" rel="nofollow noreferrer">The Transitive Reduction of a Directed Graph
A. V. Aho, M. R. Garey, and J. D. Ullman</a></p>

<p>According to <a href="http://en.wikipedia.org/wiki/Transitive_reduction#Graph_algorithms_for_transitive_reduction" rel="nofollow noreferrer">wikipedia</a>, this algorithm is used by <code>tred</code> which is tool for transitive reduction available in GraphViz package. You can run it on your graph and get reduced graph. </p>

<p>This question is duplicate of <a href="https://stackoverflow.com/q/510277/58737">this stackoverflow question</a>.</p>

<p><a href="http://www.google.com/codesearch#pFm0LxzAWvs/darwinsource/tarballs/other/graphviz-622.tar.gz%7C8x16qTtM0ig/graphviz-622/graphviz/tools/src/tred.c&amp;type=cs&amp;l=49" rel="nofollow noreferrer">code here</a> <code>graphviz/tools/src/tred.c</code> <strong>does</strong> use DFS. ;-)</p>

CC BY-SA 3.0
2011-06-27T09:36:20.910Z
I didn't know about `tred`, thanks.
Anthony Labarre
CC BY-SA 3.0
2011-06-27T12:00:52.663Z
Thank you MachineCharmer.
I am outside a university and cannot download the paper without paying 25$... is there a free online source that describes this algorithm?
The tred source is small and readable, but without explanations.
Iftah
CC BY-SA 3.0
2011-06-27T13:45:50.863Z
No. There is no free download link for that paper. But you might have *friends* at some university :)
Pratik Deoghare
CC BY-SA 3.0
2011-06-27T09:19:58.270Z
2011-06-27T09:52:25.683Z
2017-05-23T11:33:33.907Z
Pratik Deoghare
<p>I have a DAG of dependencies that contains lots of redundant edges (see example below). I want a "quick" algorithm (ie. can handle a graph with several thousands of nodes/edges) that finds a minimal sub graph. </p>

<p>For example:</p>

<pre><code>A -&gt; B -&gt; C
A -&gt; C
</code></pre>

<p>in words A is prerequisite to B, and B is prerequisite to C, and also A is prerequisite to C. In this case A -> C is redundant (since B is already necessary to reach C, and A is necessary to reach B).</p>

<p>Its been a while since I studied algorithms, and I'm not sure where to start.</p>

<p>By the way, its not critical that the algorithm finds the global minimum, local minimum is fine (the edge reduction is only a runtime optimization for next stage of processing).</p>

<p>Also, I realize this is a CS QA and not programming, but my program is written in Python, so I would be extra happy to learn of a python module or open source for doing this reduction, just in case you know of it.</p>

<p>thanks in advance!</p>

CC BY-SA 3.0
2011-06-27T08:58:47.477Z
I was wondering if DFS could help here?
Pratik Deoghare
CC BY-SA 3.0
2011-06-27T09:02:02.237Z
You are looking for the "transitive reduction" of your dependency graph.
Dave Clarke
CC BY-SA 3.0
2011-07-13T00:27:34.557Z
Find the strongly connected components. Only leave one edge between each pair of components. For each strongly connected component, you need to find a minimal number of cycles that would cover it. Finding a minimum number of cycles seems to be NP-complete since it will decide the Hamiltonicity, but since you only need a local minimal just remove edges from each component till it looses its strong connectivity.
Kaveh
<ds.algorithms><graph-algorithms><transitive-reduction>
Reducing redundant edges from a dependency graph
Iftah
# Reducing redundant edges from a dependency graph

(Asked by: username_0 on 2011-06-27)

I have a DAG of dependencies that contains lots of redundant edges (see example below). I want a "quick" algorithm (ie. can handle a graph with several thousands of nodes/edges) that finds a minimal sub graph. 
For example:
A -> B -> C
A -> C

in words A is prerequisite to B, and B is prerequisite to C, and also A is prerequisite to C. In this case A -> C is redundant (since B is already necessary to reach C, and A is necessary to reach B).
Its been a while since I studied algorithms, and I'm not sure where to start.
By the way, its not critical that the algorithm finds the global minimum, local minimum is fine (the edge reduction is only a runtime optimization for next stage of processing).
Also, I realize this is a CS QA and not programming, but my program is written in Python, so I would be extra happy to learn of a python module or open source for doing this reduction, just in case you know of it.
thanks in advance!

**Tags:** ds.algorithms, graph-algorithms, transitive-reduction

> **Comments:**
> **username_1**: I was wondering if DFS could help here?  
> **username_2**: You are looking for the "transitive reduction" of your dependency graph.  
> **username_3**: Find the strongly connected components. Only leave one edge between each pair of components. For each strongly connected component, you need to find a minimal number of cycles that would cover it. Finding a minimum number of cycles seems to be NP-complete since it will decide the Hamiltonicity, but since you only need a local minimal just remove edges from each component till it looses its strong connectivity.  

---

## 2 answers

### Answer by username_1 on 2011-06-27. Score: 13 | Accepted answer

[The Transitive Reduction of a Directed Graph
A. V. Aho, M. R. Garey, and J. D. Ullman](http://epubs.siam.org/sicomp/resource/1/smjcat/v1/i2/p131_s1?isAuthorized=no)

According to [wikipedia](http://en.wikipedia.org/wiki/Transitive_reduction#Graph_algorithms_for_transitive_reduction), this algorithm is used by `tred` which is tool for transitive reduction available in GraphViz package. You can run it on your graph and get reduced graph.

This question is duplicate of [this stackoverflow question](https://stackoverflow.com/q/510277/58737).

[code here](http://www.google.com/codesearch#pFm0LxzAWvs/darwinsource/tarballs/other/graphviz-622.tar.gz%7C8x16qTtM0ig/graphviz-622/graphviz/tools/src/tred.c&type=cs&l=49) `graphviz/tools/src/tred.c` **does** use DFS. ;-)

> **Comments:**
> **username_4**: I didn't know about `tred`, thanks.  
> **username_0**: Thank you MachineCharmer. I am outside a university and cannot download the paper without paying 25$... is there a free online source that describes this algorithm? The tred source is small and readable, but without explanations.  
> **username_1**: No. There is no free download link for that paper. But you might have *friends* at some university :)  

---

### Answer by username_0 on 2011-06-29. Score: -1

I ended up solving it this way:
My data structure is made of dependends dictionary, from a node id to a list of nodes that depend on it (ie. its followers in the DAG).
I haven't calculated the exact complexity of it, but it swallowed my graph of several thousands in a split second.
_transitive_closure_cache = {}
def transitive_closure(self, node_id):
    """returns a set of all the nodes (ids) reachable from given node(_id)"""
    global _transitive_closure_cache
    if node_id in _transitive_closure_cache:
        return _transitive_closure_cache[node_id]
    c = set(d.id for d in dependents[node_id])
    for d in dependents[node_id]:
        c.update(transitive_closure(d.id))  # for the non-pythonists - update is update self to Union result
    _transitive_closure_cache[node_id] = c
    return c

def can_reduce(self, source_id, dest_id):
    """returns True if the edge (source_id, dest_id) is redundant (can reach from source_id to dest_id without it)"""
    for d in dependents[source_id]:
        if d.id == dest_id:
            continue
        if dest_id in transitive_closure(d.id):
            return True # the dest node can be reached in a less direct path, then this link is redundant
    return False

# Reduce redundant edges:
for node in nodes:      
    dependents[node.id] = [d for d in dependents[node.id] if not can_reduce(node.id, d.id)]


---

