4

I have a large directed acyclic graph, and I'd like to compute the transitive reduction of that graph.

I'm currently computing the transitive reduction using a naive depth-first search, but that algorithm is too slow for my use case. However, the efficient algorithms I've been able to find work on an adjacency matrix representation, whereas my representation is roughly equivalent to an adjacency list. (It's actually represented as a set of C++ objects, each with pointers to their children and parents).

I obviously could transform my DAG into an adjacency matrix, do the reduction, and transform it back; but that seems a bit wasteful, and I'd like a simpler algorithm if possible.

My graph contains ~100,000 nodes.

NathanOliver
  • 171,901
  • 28
  • 288
  • 402
IanPudney
  • 5,941
  • 1
  • 24
  • 39
  • I'm removing the C++ tag as right now this is about an algorithm, not actual code. – NathanOliver Sep 17 '18 at 18:28
  • I'm not very familiar with the names of graph algorithms, but it looks like [`boost::transitive_closure`](https://www.boost.org/doc/libs/1_68_0/libs/graph/doc/transitive_closure.html) from [Boost Graph](https://www.boost.org/doc/libs/1_68_0/libs/graph/doc/table_of_contents.html) – Justin Sep 17 '18 at 18:34
  • Transitive closure is actually the opposite of a transitive reduction. Computing the closure means "if there exists an indirect path from A to B, add a direct path" whereas a transitive reduction means "remove all edges that can be removed without actually changing the DAG." (So, if you have edges A->B, B->C, and A->C, you can remove the A->C edge, since it's implied by A->B and B->C). – IanPudney Sep 17 '18 at 18:40
  • @IanPudney There's an undocumented [`boost::transitive_reduction`](https://www.boost.org/doc/libs/1_68_0/boost/graph/transitive_reduction.hpp): https://stackoverflow.com/a/29200511/1896169 – Justin Sep 17 '18 at 18:46

0 Answers0