Skip to content
/ dag Public

Yet another directed acyclic graph (DAG) implementation in golang.

License

Notifications You must be signed in to change notification settings

heimdalr/dag

Folders and files

NameName
Last commit message
Last commit date

Latest commit

5f5ea29 · Jul 26, 2024
Jul 26, 2024
Jan 5, 2022
Jan 5, 2022
Jan 15, 2021
Dec 27, 2019
Aug 29, 2022
Jul 22, 2024
Aug 21, 2023
Jan 5, 2022
Aug 21, 2023
Jan 5, 2022
Jul 26, 2024
Aug 21, 2023
Jul 22, 2024
Jul 22, 2024
Jul 21, 2024
Jul 26, 2024
May 1, 2022
Jul 22, 2024
Jul 22, 2024
Nov 30, 2023

Repository files navigation

dag

run tests PkgGoDev Go Report Card Gitpod ready-to-code CodeQL

CII Best Practices

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}