45

I have been looking for an algorithm to perform a transitive reduction on a graph, but without success. There's nothing in my algorithms bible (Introduction To Algorithms by Cormen et al) and whilst I've seen plenty of transitive closure pseudocode, I haven't been able to track down anything for a reduction. The closest I've got is that there is one in "Algorithmische Graphentheorie" by Volker Turau (ISBN:978-3-486-59057-9), but unfortunately I don't have access to this book! Wikipedia is unhelpful and Google is yet to turn up anything. :^(

Does anyone know of an algorithm for performing a transitive reduction?

0

8 Answers 8

21

See Harry Hsu. "An algorithm for finding a minimal equivalent graph of a digraph.", Journal of the ACM, 22(1):11-16, January 1975. The simple cubic algorithm below (using an N x N path matrix) suffices for DAGs, but Hsu generalizes it to cyclic graphs.

// reflexive reduction
for (int i = 0; i < N; ++i)
  m[i][i] = false;

// transitive reduction
for (int j = 0; j < N; ++j)
  for (int i = 0; i < N; ++i)
    if (m[i][j])
      for (int k = 0; k < N; ++k)
        if (m[j][k])
          m[i][k] = false;
4
  • (for DAGs) In other words: look at each edge (i,j), remove it if there is a reason for not being in the transitive reduction. The edges not removed must be inside the transitive reduction.
    – galath
    Commented Sep 10, 2011 at 20:26
  • 7
    According to the reference you cite, you should be starting from the path matrix, not the adjacency matrix Commented May 3, 2013 at 11:09
  • 6
    This does not work for all cases. In a graph with edges (A,B), (B,C), (C,D) and (A,D) the last edge (A,D) should be deleted. It is not, because there is no combination of two edges (m[i][j] and m[j][k]) that leads from A to D. Commented Jul 30, 2013 at 9:28
  • 1
    @MichaelClerx quite right, I meant path matrix. Thanks for pointing out the error. If you have an adjacency matrix, apply Warshal's algorithm first to transitively close it. Commented Nov 24, 2014 at 21:42
8

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
6
  • 1
    You need to add if (x,z) != (x,y) && (x,z) != (y,z) before delete edge... to avoid incorrect deletions in the event of cycles. Other than that, and although it'd be better to have a faster linear-time algorithm, I like this answer: nice and simple.
    – Joey Adams
    Commented Jun 6, 2010 at 8:20
  • 1
    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
    Commented Jun 7, 2010 at 5:30
  • 2
    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. Commented Jun 10, 2010 at 18:04
  • Are you sure of your algorithm for the transitive closure? For that task I would use Floyd-Warshall's algorithm, which is foreach y in graph.vertices: foreach x in graph.vertices: foreach z in graph.vertices: add edge xz if edges xy and yz exist OR edge xz exist. Note the different order in x and y. I thought the order mattered. It doesn't?
    – galath
    Commented Sep 10, 2011 at 20:16
  • 8
    As noted by cmn, thi algorithm does clear edges that connect nodes that are also connected through a path that has more than two edges. Example: A -> B -> C -> D; A -> C; A-> D. The algorithm would clear A -> C, but not A -> D.
    – Penz
    Commented Jun 28, 2012 at 1:53
6

Based on the reference provided by Alan Donovan, which says you should use the path matrix (which has a 1 if there is a path from node i to node j) instead of the adjacency matrix (which has a 1 only if there is an edge from node i to node j).

Some sample python code follows below to show the differences between the solutions

def prima(m, title=None):
    """ Prints a matrix to the terminal """
    if title:
        print title
    for row in m:
        print ', '.join([str(x) for x in row])
    print ''

def path(m):
    """ Returns a path matrix """
    p = [list(row) for row in m]
    n = len(p)
    for i in xrange(0, n):
        for j in xrange(0, n):
            if i == j:
                continue
            if p[j][i]:
                for k in xrange(0, n):
                    if p[j][k] == 0:
                        p[j][k] = p[i][k]
    return p

def hsu(m):
    """ Transforms a given directed acyclic graph into its minimal equivalent """
    n = len(m)
    for j in xrange(n):
        for i in xrange(n):
            if m[i][j]:
                for k in xrange(n):
                    if m[j][k]:
                        m[i][k] = 0

m = [   [0, 1, 1, 0, 0],
        [0, 0, 0, 0, 0],
        [0, 0, 0, 1, 1],
        [0, 0, 0, 0, 1],
        [0, 1, 0, 0, 0]]

prima(m, 'Original matrix')
hsu(m)
prima(m, 'After Hsu')

p = path(m)
prima(p, 'Path matrix')
hsu(p)
prima(p, 'After Hsu')

Output:

Adjacency matrix
0, 1, 1, 0, 0
0, 0, 0, 0, 0
0, 0, 0, 1, 1
0, 0, 0, 0, 1
0, 1, 0, 0, 0

After Hsu
0, 1, 1, 0, 0
0, 0, 0, 0, 0
0, 0, 0, 1, 0
0, 0, 0, 0, 1
0, 1, 0, 0, 0

Path matrix
0, 1, 1, 1, 1
0, 0, 0, 0, 0
0, 1, 0, 1, 1
0, 1, 0, 0, 1
0, 1, 0, 0, 0

After Hsu
0, 0, 1, 0, 0
0, 0, 0, 0, 0
0, 0, 0, 1, 0
0, 0, 0, 0, 1
0, 1, 0, 0, 0
5
  • I'm puzzled because it seems that, if you removed the edges in the right order, you could get right back to the original (redundant) adjacency matrix by applying the algorithm to the path matrix. So basically you've gotten nowhere. See this example: i.imgur.com/fbt6oK1.png Say you start with just the black edges, and of course you want to eliminate the dotted black/green edge. So you add the red edges to get the path matrix. Then you remove the red edges because they can both be removed by the algorithm. And now you're stuck.
    – Rag
    Commented Jul 1, 2013 at 18:41
  • Using m = [[0, 1, 0, 1], [0, 0, 1, 0], [0, 0, 0, 1], [0, 0, 0, 0]] as input works fine :) Commented Jul 1, 2013 at 20:55
  • I think that It can work as long as you're not unlucky about which edges are removed first.
    – Rag
    Commented Jul 2, 2013 at 15:54
  • Try it, the order makes no difference. Commented Jul 2, 2013 at 17:19
  • OK, sorry, you're right, I can't find any case where the dotted black/green edge is removed before the two red eges. When I get home tonight I'll try to figure out why this happens.
    – Rag
    Commented Jul 2, 2013 at 20:14
4

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.

2
  • 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. Commented Mar 3, 2010 at 14:42
  • 2
    The tred source code is barely readable thanks to the absence of any comment in the code. Commented Mar 16, 2012 at 12:02
3

Depth-first algorithm in pseudo-python:

for vertex0 in vertices:
    done = set()
    for child in vertex0.children:
        df(edges, vertex0, child, done)

df = function(edges, vertex0, child0, done)
    if child0 in done:
        return
    for child in child0.children:
        edge.discard((vertex0, child))
        df(edges, vertex0, child, done)
    done.add(child0)

The algorithm is sub-optimal, but deals with the multi-edge-span problem of the previous solutions. The results are very similar to what tred from graphviz produces.

2

The algorithm of "girlwithglasses" forgets that a redundant edge could span a chain of three edges. To correct, compute Q = R x R+ where R+ is the transitive closure and then delete all edges from R that show up in Q. See also the Wikipedia article.

2
  • 1
    Can you suggest some pseudocode for doing this? The transitive reduction algorithm posted below would run on the transitive closure graph, so for an edge x-y which could also be reached by x-A-B-y, you would also have x-A-y and x-B-y. Commented May 10, 2011 at 18:07
  • 1
    What is Q supposed to represent? What do you do with it?
    – Rag
    Commented Jul 1, 2013 at 19:55
1

ported to java / jgrapht, the python sample on this page from @Michael Clerx:

import java.util.ArrayList;
import java.util.List;
import java.util.Set;

import org.jgrapht.DirectedGraph;

public class TransitiveReduction<V, E> {

    final private List<V> vertices;
    final private int [][] pathMatrix;
    
    private final DirectedGraph<V, E> graph;
    
    public TransitiveReduction(DirectedGraph<V, E> graph) {
        super();
        this.graph = graph;
        this.vertices = new ArrayList<V>(graph.vertexSet());
        int n = vertices.size();
        int[][] original = new int[n][n];

        // initialize matrix with zeros
        // --> 0 is the default value for int arrays
        
        // initialize matrix with edges
        Set<E> edges = graph.edgeSet();
        for (E edge : edges) {
            V v1 = graph.getEdgeSource(edge);
            V v2 = graph.getEdgeTarget(edge);

            int v_1 = vertices.indexOf(v1);
            int v_2 = vertices.indexOf(v2);

            original[v_1][v_2] = 1;
        }
        
        this.pathMatrix = original;
        transformToPathMatrix(this.pathMatrix);
    }
    
    // (package visible for unit testing)
    static void transformToPathMatrix(int[][] matrix) {
        // compute path matrix 
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix.length; j++) { 
                if (i == j) {
                    continue;
                }
                if (matrix[j][i] > 0 ){
                    for (int k = 0; k < matrix.length; k++) {
                        if (matrix[j][k] == 0) {
                            matrix[j][k] = matrix[i][k];
                        }
                    }
                }
            }
        }
    }

    // (package visible for unit testing)
    static void transitiveReduction(int[][] pathMatrix) {
        // transitively reduce
        for (int j = 0; j < pathMatrix.length; j++) { 
            for (int i = 0; i < pathMatrix.length; i++) {
                if (pathMatrix[i][j] > 0){
                    for (int k = 0; k < pathMatrix.length; k++) {
                        if (pathMatrix[j][k] > 0) {
                            pathMatrix[i][k] = 0;
                        }
                    }
                }
            }
        }
    }

    public void reduce() {
        
        int n = pathMatrix.length;
        int[][] transitivelyReducedMatrix = new int[n][n];
        System.arraycopy(pathMatrix, 0, transitivelyReducedMatrix, 0, pathMatrix.length);
        transitiveReduction(transitivelyReducedMatrix);
        
        for (int i = 0; i <n; i++) {
            for (int j = 0; j < n; j++) { 
                if (transitivelyReducedMatrix[i][j] == 0) {
                    // System.out.println("removing "+vertices.get(i)+" -> "+vertices.get(j));
                    graph.removeEdge(graph.getEdge(vertices.get(i), vertices.get(j)));
                }
            }
        }
    }
}

unit test :

import java.util.Arrays;

import org.junit.Assert;
import org.junit.Test;

public class TransitiveReductionTest {

    @Test
    public void test() {

        int[][] matrix = new int[][] {
            {0, 1, 1, 0, 0},
            {0, 0, 0, 0, 0},
            {0, 0, 0, 1, 1},
            {0, 0, 0, 0, 1},
            {0, 1, 0, 0, 0}
        };
        
        int[][] expected_path_matrix = new int[][] {
            {0, 1, 1, 1, 1},
            {0, 0, 0, 0, 0},
            {0, 1, 0, 1, 1},
            {0, 1, 0, 0, 1},
            {0, 1, 0, 0, 0}
        };
        
        int[][] expected_transitively_reduced_matrix = new int[][] {
            {0, 0, 1, 0, 0},
            {0, 0, 0, 0, 0},
            {0, 0, 0, 1, 0},
            {0, 0, 0, 0, 1},
            {0, 1, 0, 0, 0}
        };
        
        System.out.println(Arrays.deepToString(matrix) + " original matrix");

        int n = matrix.length;

        // calc path matrix
        int[][] path_matrix = new int[n][n];
        {
            System.arraycopy(matrix, 0, path_matrix, 0, matrix.length);
            
            TransitiveReduction.transformToPathMatrix(path_matrix);
            System.out.println(Arrays.deepToString(path_matrix) + " path matrix");
            Assert.assertArrayEquals(expected_path_matrix, path_matrix);
        }

        // calc transitive reduction
        {
            int[][] transitively_reduced_matrix = new int[n][n];
            System.arraycopy(path_matrix, 0, transitively_reduced_matrix, 0, matrix.length);
            
            TransitiveReduction.transitiveReduction(transitively_reduced_matrix);
            System.out.println(Arrays.deepToString(transitively_reduced_matrix) + " transitive reduction");
            Assert.assertArrayEquals(expected_transitively_reduced_matrix, transitively_reduced_matrix);
        }
    }
}

test ouput

[[0, 1, 1, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 1, 1], [0, 0, 0, 0, 1], [0, 1, 0, 0, 0]] original matrix
[[0, 1, 1, 1, 1], [0, 0, 0, 0, 0], [0, 1, 0, 1, 1], [0, 1, 0, 0, 1], [0, 1, 0, 0, 0]] path matrix
[[0, 0, 1, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 1, 0], [0, 0, 0, 0, 1], [0, 1, 0, 0, 0]] transitive reduction
2
  • 1
    For your information, a pull request with a reworked version of this code has been submitted, accepted and merged into jgrapht. github.com/jgrapht/jgrapht/commit/…
    – cthiebaud
    Commented Aug 24, 2015 at 7:49
  • FYI, the algorithm in JGraphT does not work if the graph contains cycles, see issue #667. Could you maybe check what is wrong with it?
    – kriegaex
    Commented Nov 5, 2020 at 6:29
0

Here is a Python implementation that borrows from the NetworkX library. Two functions used in it are topological sort to detect cycles, and DFS to find all vertices reachable from a staring vertex. All of these can be implemented without any dependencies, I’ve a complete implementation on my GitHub. However, it’s in a private repo, so, I’m copy-pasting the complete content of the module here.

from __future__ import annotations
from collections import defaultdict, deque
from typing import TypeVar, NamedTuple

T = TypeVar('T')


class Edge(NamedTuple):
    src: T
    dest: T


class Graph:
    def __init__(self, vertices: set[T] = None, edges: set[Edge] = None):
        self.vertices = vertices or set()
        self.edges = edges or set()
        self.adj = defaultdict(set)
        self.indegrees = defaultdict(int)
        for u, v in self.edges:
            self.vertices.add(u)
            self.vertices.add(v)
            self.adj[u].add(v)
            self.indegrees[v] += 1
        self.indegrees.update({v: 0 for v in (self.vertices - self.indegrees.keys())})

    def add_edge(self, edge: Edge) -> None:
        u, v, = edge
        self.vertices.add(u)
        self.vertices.add(v)
        self.edges.add(edge)
        self.adj[u].add(v)
        self.indegrees[v] += 1

    # Kahn's Algorithm
    def topological_sort(self) -> list[T]:
        indegrees = self.indegrees.copy()
        q = deque(node for node, degree in indegrees.items() if degree == 0)
        result = []
        while q:
            u = q.popleft()
            result.append(u)
            if u not in self.adj:
                continue
            for v in self.adj[u]:
                indegrees[v] -= 1
                if indegrees[v] == 0:
                    q.append(v)

        if len(result) != len(self.vertices):
            raise ValueError('Graph has a cycle')
        return result

    def dfs(self, start: T) -> list[Edge]:
        stack = [(None, start)]
        result = []
        visited = set()
        while stack:
            u, v = stack.pop()
            if u is not None:
                result.append(Edge(u, v))
            if v in visited or v not in self.adj:
                continue
            visited.add(v)
            for k in self.adj[v]:
                if k not in visited:
                    stack.append((v, k))
        return result

    # Input: DAG G=(V,E)
    #
    # E2 = E
    # for edge (u,v) in E2 do
    #     if there is a path from u to v in G=(V,E2) that does not use edge (u,v) then
    #         E2 = E2 - {(u,v)}   // remove edge (u,v) from E2
    #     end if
    # end for
    #
    # Output: G2=(V,E2) is the transitive reduction of G
    def transitive_reduction(self) -> Graph:
        # Throws exception if graph has a cycle.
        _ = self.topological_sort()

        tr = Graph(self.vertices)
        # descendants[v] is the list of all vertices reachable from v.
        descendants = {}
        indegrees = self.indegrees.copy()
        for u in self.vertices:
            if u not in self.adj:
                continue
            u_neighbors = self.adj[u].copy()
            for v in self.adj[u]:
                if v in u_neighbors:
                    if v not in descendants:
                        descendants[v] = {y for x, y in self.dfs(v)}
                    u_neighbors -= descendants[v]
                indegrees[v] -= 1
                if indegrees[v] == 0:
                    del indegrees[v]
            for v in u_neighbors:
                tr.add_edge(Edge(u, v))
        return tr

For a detailed discussion of improving the efficiency of the algorithm, see this.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.