# Reducing graph complexity using Go and transitive reduction

Adding numerous edges to a DAG can make the graph unnecessarily complex. However, these graphs can be simplified using a technique called transitive reduction.

Posted on September 12, 2022

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.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` 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.

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.