Remove unnecessary dependencies in a task graph? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T05:53:03Z http://mathoverflow.net/feeds/question/25176 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/25176/remove-unnecessary-dependencies-in-a-task-graph Remove unnecessary dependencies in a task graph? Kip 2010-05-18T21:12:02Z 2010-05-18T22:26:40Z <p>I'm modeling a game tech/build tree as a directed acyclic graph with a .dot file for visualization use in Graphviz. </p> <p>Some of the dependencies discovered are redundant in the sense that while they are dependencies, they are satisfied via a longer yet required path.</p> <pre><code>a -&gt; b b -&gt; c a -&gt; c // Unnecessary because we have to do b first. </code></pre> <p>And a longer example</p> <pre><code>a -&gt; b b -&gt; c c -&gt; d a -&gt; d // Unnecessary between we have to do both b and c first. </code></pre> <p>Is there an algorithm to testing a graph for these unnecessary paths so that I could trim them from the .dot file? Perhaps this is more appropriately a programming question, but I'm guessing some use of graph theory applies here.</p> http://mathoverflow.net/questions/25176/remove-unnecessary-dependencies-in-a-task-graph/25177#25177 Answer by mathy for Remove unnecessary dependencies in a task graph? mathy 2010-05-18T21:35:45Z 2010-05-18T21:35:45Z <p>AFAICT, what you want is called a <a href="http://en.wikipedia.org/wiki/Transitive_reduction" rel="nofollow">transitive reduction</a> of the graph. La Wik claims that Graphviz can do the job somehow; consult its documentation.</p> http://mathoverflow.net/questions/25176/remove-unnecessary-dependencies-in-a-task-graph/25182#25182 Answer by Lucas K. for Remove unnecessary dependencies in a task graph? Lucas K. 2010-05-18T22:26:40Z 2010-05-18T22:26:40Z <p>For each vertex x, make a set that contain each vertex y that can reach x. This sets also includes x.</p> <p>If you have two edges b -> a and c -> a, then if the set associated with b is a subset of the set associated with c, then the edge b -> a can be removed.</p> <p>Example:</p> <p>a -> b<br> b -> c<br> a -> c</p> <p>The set are:<br> a: { a }<br> b: { a, b } // Can be reached from a and b<br> c: { a, b, c}</p> <p>If you look at the edges:<br> b -> c<br> a -> c</p> <p>Then you see that the set of a is a subset of b. So, the edge a -> c can be removed.</p> <p>Lucas</p>