ansaurus

Question

transitive reduction algorithm: pseudocode?

Answer 1

+1 A:

The Wikipedia article on transitive reduction points to an implementation within GraphViz (which is open source). Not exactly pseudocode, but maybe someplace to start?

LEDA includes a transitive reduction algorithm. I don't have a copy of the LEDA book anymore, and this function might have been added after the book was published. But if it's in there, then there will be a good description of the algorithm.

Google points to an algorithm that somebody suggested for inclusion in Boost. I didn't try to read it, so maybe not correct?

Also, this might be worth a look.

Eric 2009-11-07 15:42:18

Thanks (belatedly!) for your response. In the end, I emailed the author of an algorithms book and asked him to verify whether some pseudocode I'd written was correct, which he kindly did.

girlwithglasses 2010-03-03 14:42:43

Answer 2

A:

The basic gist of the transitive reduction algorithm I used is


foreach x in graph.vertices
   foreach y in graph.vertices
      foreach z in graph.vertices
         delete edge xz if edges xy and yz exist

The transitive closure algorithm I used in the same script is very similar but the last line is


         add edge xz if edges xy and yz OR edge xz exist

girlwithglasses 2010-03-03 14:49:42

Joey Adams 2010-06-06 08:20:39

Also, if the graph has cycles, this algorithm won't always produce the *minimal* transitive reduction. For instance, try it on `[0,1,2,3,4,5]` where A points to B for all A and B (even when they're the same). It should produce something like 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 0, but running this algorithm (with my tweak) brings in 5 -> 2 and 5 -> 4 in addition to 0 -> ... -> 5 -> 0. Running it without my tweak produces no edges at all.

Joey Adams 2010-06-07 05:30:52

I should have stated that my code included checks for the identical edges you mentioned, and also that I'm working solely with DAGs, so the cycles aren't an issue.

girlwithglasses 2010-06-10 18:04:40

ansaurus

tags:

views:

answers:

transitive reduction algorithm: pseudocode?

related questions