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}