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:

- Install Go 1.18.
- Initialize a Go module in a new directory, for example
`go mod init transitive-reduction`

. - Get the library using
`go get github.com/dominikbraun/graph`

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