Skip to content
Advertisement

I’m trying to perform the transitive reduction of directed graph in Python

As a warning, I’m still a bit inexperienced in python

I’m trying to perform the transitive reduction of directed graph using the networkx library. I’ve figured out an algorithm but I’m having trouble implementing it. After a quick search, I found algorithms similar to mine in other stack exchange questions but no demonstrations of how to actually code the algorithm.

Here’s my algorthm:

JavaScript

Here’s my attempt at expressing this in python :

JavaScript

I don’t think I’m properly calling every permutation of edges in the network and was thinking of trying to use itertools. Even if I had every possible permutation, I don’t know how to implement the algorithm with that information.

Any help would be wonderful. Thanks!

Advertisement

Answer

The following seems to work, at least for the sample data I provided. If you have a specific case that doesn’t it’d be helpful to see it.

JavaScript

Output:

JavaScript
User contributions licensed under: CC BY-SA
9 People found this is helpful
Advertisement