Algorithm for Finding Redundant Edges in a Graph o

Question

Is there an established algorithm for finding redundant edges in a graph?

For example, I'd like to find that a->d and a->e are redundant, and then get rid of them, like this:

=>

Edit: Strilanc was nice enough to read my mind for me. "Redundant" was too strong of a word, since in the example above, neither a->b or a->c is considered redundant, but a->d is.

Answer 1

You want to compute the smallest graph which maintains vertex reachability.

This is called the transitive reduction of a graph. The wikipedia article should get you started down the right road.

Answer 2

Several ways to attack this, but first you're going to need to define the problem a little more precisely. First, the graph you have here is acyclic and directed: will this always be true?

Next, you need to define what you mean by a "redundant edge". In this case, you start with a graph which has two paths a->c: one via b and one direct one. From this I infer that by "redundant" you mean something like this. Let G=< V, E > be a graph, with V the set of vertices and E ⊆ V×V the set of edges. It kinda looks like you're defining all edges from v_i to v_j shorter than the longest edge as "redundant". So the easiest thing would be to use depth first search, enumerate the paths, and when you find a new one that's longer, save it as the best candidate.

I can't imagine what you want it for, though. Can you tell?

Answer 3

A sub-graph of a given graph which contains no "redundant edges" is called a 'spanning tree' of that graph. For any given graph, multiple spanning trees are possible.

So, in order to get rid of redundant edges, all you need to do is find any one spanning tree of your graph. You can use any depth-first-search or breadth-first-search algorithm and continue searching till you have visited every vertex in the graph.

Answer 4

I think the easiest way to do that, actually imagine how it would look in the real work, imagine if you have joints, Like

(A->B)(B->C)(A->C), imagine if distance between near graphs is equals 1, so

(A->B) = 1, (B->C) = 1, (A->C) = 2.

So you can remove joint (A->C).

In other words, minimize.

This is just my idea how I would think about it at start. There are various articles and sources on the net, you can look at them and go deeper.

Resources, that Will help you:

Algorithm for Removing Redundant Edges in the Dual Graph of a Non-Binary CSP

Graph Data Structure and Basic Graph Algorithms

Google Books, On finding minimal two connected Subgraphs

Graph Reduction

Redundant trees for preplanned recovery in arbitraryvertex-redundant or edge-redundant graphs

Answer 5

Check this: Minimum Spanning Tree

Answer 6

I had a similar problem and 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). Note it works only for a DAG - that is directed, acyclic graph.

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)]