dag

Implementation of directed acyclic graphs (DAGs).

The implementation is fast and thread-safe. It prevents adding cycles or duplicates and thereby always maintains a valid DAG. The implementation caches descendants and ancestors to speed up subsequent calls.

Quickstart

Running:

package main

import (
	"fmt"
	"github.com/heimdalr/dag"
)

func main() {

	// initialize a new graph
	d := NewDAG()

	// init three vertices
	v1, _ := d.AddVertex(1)
	v2, _ := d.AddVertex(2)
	v3, _ := d.AddVertex(struct{a string; b string}{a: "foo", b: "bar"})

	// add the above vertices and connect them with two edges
	_ = d.AddEdge(v1, v2)
	_ = d.AddEdge(v1, v3)

	// describe the graph
	fmt.Print(d.String())
}

will result in something like:

DAG Vertices: 3 - Edges: 2
Vertices:
  1
  2
  {foo bar}
Edges:
  1 -> 2
  1 -> {foo bar}