8
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ I was wondering if DFS could help here? $\endgroup$ – Pratik Deoghare Jun 27 '11 at 8:58
  • 3
    $\begingroup$ You are looking for the "transitive reduction" of your dependency graph. $\endgroup$ – Dave Clarke Jun 27 '11 at 9:02
  • $\begingroup$ 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. $\endgroup$ – Kaveh Jul 13 '11 at 0:27
13
$\begingroup$

The Transitive Reduction of a Directed Graph A. V. Aho, M. R. Garey, and J. D. Ullman

According to wikipedia, 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.

code here graphviz/tools/src/tred.c does use DFS. ;-)

$\endgroup$
  • 2
    $\begingroup$ I didn't know about tred, thanks. $\endgroup$ – Anthony Labarre Jun 27 '11 at 9:36
  • 1
    $\begingroup$ 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. $\endgroup$ – Iftah Jun 27 '11 at 12:00
  • $\begingroup$ No. There is no free download link for that paper. But you might have friends at some university :) $\endgroup$ – Pratik Deoghare Jun 27 '11 at 13:45
-1
$\begingroup$

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)]
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.