CODEWITHSUNDEEP
algorithmgraph
SedriX
SedriX

Reputation: 510

Identify Redundant Dependence in Graph

I have a DIRECTED ACYCLIC GRAPH where each node stands for a task and each directed edge A -> B means task A should be done before task B starts

A simple illustration could be like this:

enter image description here

So this is actually a workflow. In this graph, edge A -> B is considered redundant because task B need task C done first, and task C needs task A done first. (not to mention another path A -> D -> E -> B which make A -> B unnecessary)

The problem is: I want to identify (say, just output) all the redundant dependence (edges) on the graph. My friend and I have got an idea like this: iterate through all edges on the graph, and for each edge say X -> Y, remove it and check the connectivity from X to Y (for example, run DFS/BFS), if there still exists a path (other than the removed one), then edge X -> Y is redundant and can be physically removed, otherwise just put it back. In this case, the complexity in the worst condition could be O(n^2) (DFS/BFS pass through approximately all edges every time), where n stands for the number of edges on the graph.

I wonder if there is any optimization about this?

Upvotes: 2

Views: 1003

Answers (2)

sunkuet02
sunkuet02

Reputation: 2442

Have you heard Transitive reduction? From Wikipedia

A transitive reduction of a directed graph is a graph with as few edges as possible that has the same reachability relation as the given graph. Equivalently, the given graph and its transitive reduction should have the same transitive closure as each other, and its transitive reduction should have as few edges as possible among all graphs with this property. Transitive reductions were introduced by Aho, Garey & Ullman (1972), who provided tight bounds on the computational complexity of constructing them.

You can get details from Transitive Reduction. If the number n of vertices and the number m of edges in a directed acyclic graph, then transitive reductions can be found in time O(nm).

Upvotes: 2

Techfist
Techfist

Reputation: 4344

Topological sorting using DFS with an stack can yield result in linear time, it can be done by starting with a vertex, marking it visited, then recursively performing topologic sorting to all its non visited adjacent edged, once all of them are explored push the vertex to stack.

then simply print from stack, it will generate result in linear time, for more you can refer to an algo explained in following link.

Topological sorting

Upvotes: 0

Related Questions