Reducing Graph Complexity Using Go and Transitive Reduction

Directed acyclic graphs (DAGs) serve a wide variety of applications in computer science, biology, sociology, and other fields that involve complex networks. While these graphs often contain a large number of edges, some of the edges might be redundant, making computations unnecessarily expensive and the graph structure harder to understand.

This article demonstrates how a DAG can be built in Go using the graph library and describes the algorithm to remove these redundant edges in detail.

Transitive Reduction

"Redundant" does not mean that an edge between two vertices exists twice. It means that there is an edge joining a vertex u and a vertex w, but w would be reachable from u even without that edge. The so-called transitive reduction of a DAG is a graph with the exact same vertices and the same reachability relation as the original graph, but with as few edges as possible.

In the graph on the top, the edge (u,w) can be removed without changing the reachability relation, because when traversing the graph from u, w would inevitably be reached through v. Therefore, its transitive reduction on the bottom only consists of the edges (u,v), (v,w).

Getting Started

If you want to try this demo yourself, you can do so by setting up an example project:

1. Install Go 1.18.
2. Initialize a Go module in a new directory, for example go mod init transitive-reduction.
3. Get the library using go get github.com/dominikbraun/graph.
4. Create a file called main.go.

Building the DAG

The first step is to create a DAG of integers that contains some unnecessary edges to build a foundation for the ensuing transitive reduction.

The following code in main.go will initialize a directed acyclic graph with integer vertices, add all five vertices, and add the edges joining the vertices:

package main

import "github.com/dominikbraun/graph"

func main() {
    g := graph.New(graph.IntHash, graph.Directed(), graph.Acyclic())

    _ = g.AddVertex(1)
    _ = g.AddVertex(2)
    _ = g.AddVertex(3)
    _ = g.AddVertex(4)
    _ = g.AddVertex(5)

    _ = g.AddEdge(1, 2)
    _ = g.AddEdge(1, 3)
    _ = g.AddEdge(1, 4)
    _ = g.AddEdge(1, 5)
    _ = g.AddEdge(2, 4)
    _ = g.AddEdge(3, 4)
    _ = g.AddEdge(3, 5)
    _ = g.AddEdge(4, 5)
}

To identify each vertex by its hash value, the library needs a hashing function which is passed to New. For this example, we're using the predefined IntHash function which takes an integer and returns that integer as a hash value at the same time.

Computing the Transitive Reduction

The algorithm for computing the transitive reduction for a graph, introduced by A. Aho, M. Garey, and J. Ullman in 1972, is based on a simple idea: When you traverse the graph and encounter an edge joining a neighbor of the current vertex and the starting vertex, the edge is redundant because you would reach the neighbor through the current vertex anyway.

A pseudo-code implementation of this fundamental idea could look as follows:

for each vertex u in G:
  for each successor v of u:
    DFS(w):
      for each successor x of w:
        if there is an edge (u,x):
          remove edge (u,x)

Expressed in words – iterate over all direct successors of all vertices in the graph, and start a depth-first search from each successor. For each vertex visited in the DFS, take a look at its direct successors. If there is an edge between the top-level iteration vertex and the successor of the current node, this edge can be removed.

Implementing the Algorithm

Using the graph library, this algorithm is comparably easy to implement. The AdjacencyMap method creates an adjacency map for the entire graph, providing all vertices and their direct successors. A depth-first search can be performed using the DFS function.

The adjacency map has an entry for each vertex, and each of the entries is a map with the successors of that vertex. For example, adjacencyMap[3] is a map containing 4 and 5.

package main

import "github.com/dominikbraun/graph"

func main() {
    g := graph.New(graph.IntHash, graph.Directed(), graph.Acyclic())

    // Add the vertices and edges as shown above.

    adjacencyMap, _ := g.AdjacencyMap()

    for vertex, successors := range adjacencyMap {
        for successor := range successors {
            _ := DFS(g, successor, func(current K) bool {
                for _, edge := range adjacencyMap[current] {
                    if _, ok := adjacencyMap[vertex][edge.Target]; ok {
                        _ = g.RemoveEdge(vertex, edge.Target)
                    }
                }
                return false
            })
        }
    }
}

This code transforms g into its transitive reduction and greatly simplifies the entire graph. You can prove this by appending a new AdjacencyMap call to the end and verifying that the redundant edges have been removed:

transformedGraph, _ := g.AdjacencyMap()
fmt.Println(transformedGraph)

Using Transitive Reduction in Your Application

Fortunately, graph already provides the well-tested TransitiveReduction function for performing a transitive reduction, so in reality, running the algorithm is more straightforward:

 _ = graph.TransitiveReduction(g)

This will transform g into its own transitive reduction. If you want to retain the original graph, you can clone it first and run the algorithm on the cloned graph.