dag

README

dag

dag is an implementation of a directed acyclic graph in Go. It is a simple and easy-to-use package that allows you to create and manipulate directed acyclic graphs.

Installation

go get github.com/aacanakin/dag

Usage

package main

import (
	"fmt"

	"github.com/aacanakin/dag"
)

/*
A -> B -> C
|    |
v    v
D -> E -> F
*/
func main() {
	// Let's create a directed acyclic graph that looks like the following:
	//
	// A -> B -> C
	// |    |
	// v    v
	// D -> E -> F

	// Create an empty directed acyclic graph
	var err error
	g, err := dag.New(
		dag.WithVertices([]dag.Vertex{"A", "B", "C", "D", "E", "F"}),
		dag.WithEdges(dag.Edges{
			"A": []dag.Vertex{"B", "D"},
			"B": []dag.Vertex{"C", "E"},
			"D": []dag.Vertex{"E"},
			"E": []dag.Vertex{"F"},
		}),
	)

	if err != nil {
		panic(errors.Wrap(err, "could not create sample graph"))
	}

	// Get the topological order
	sorted, _ := graph.TopSort()

	// Print the topological order
	for _, vertex := range sorted {
		fmt.Println(vertex)
	}

	// Output:
	// A
	// B
	// D
	// C
	// E
	// F
}

More examples can be found in the godoc examples.

Roadmap

• Generic vertex types

Documentation

Overview

Package dag provides a simple directed acyclic graph (DAG) implementation. It is a simple graph data structure that uses a map to store the vertices and edges. The package provides methods to add and remove vertices and edges, as well as methods to traverse the graph.

Index

• type Edges
• type Graph
  • func New(opts ...GraphOptions) (*Graph, error)
  • func (g *Graph) Add(vertices ...Vertex) error
  • func (g *Graph) Append(v Vertex, prevVertices []Vertex) error
  • func (g *Graph) BFS(start Vertex) (result []Vertex, err error)
  • func (g *Graph) Connect(from Vertex, to Vertex) error
  • func (g *Graph) DFS(start Vertex) (result []Vertex, err error)
  • func (g *Graph) DeepCopy() (*Graph, error)
  • func (g *Graph) Deps(vertex string) (result []Vertex, err error)
  • func (g *Graph) Disconnect(v Vertex) error
  • func (g *Graph) DisconnectEdge(from Vertex, to Vertex) error
  • func (g *Graph) Edges() Edges
  • func (g *Graph) Exists(vertex Vertex) bool
  • func (g *Graph) Leaves() (leaves []Vertex, err error)
  • func (g *Graph) Next(vertex Vertex) ([]Vertex, error)
  • func (g *Graph) Prev(vertex Vertex) (prev []Vertex, err error)
  • func (g *Graph) Remove(v Vertex) (removed []Vertex, err error)
  • func (g *Graph) Reverse() (*Graph, error)
  • func (g *Graph) ReverseDeps(vertex Vertex) (result []Vertex, err error)
  • func (g *Graph) ReverseEdges() (Edges, error)
  • func (g *Graph) Roots() ([]Vertex, error)
  • func (g *Graph) SubGraph(vertices []Vertex) (graph *Graph, err error)
  • func (g *Graph) TopSort() (result []Vertex, err error)
  • func (g *Graph) Vertices() []Vertex
• type GraphOptions
  • func WithEdges(edges Edges) GraphOptions
  • func WithVertices(vertices []Vertex) GraphOptions
• type Vertex

Examples

• Graph
• Graph.Append
• Graph.Deps
• Graph.Disconnect

Types

type Edges

type Edges map[Vertex][]Vertex

keys represent vertex & values are direct edges to vertices Edges represents the edges of the graph

type Graph

type Graph struct {
	// contains filtered or unexported fields
}

Graph represents a directed asyclic graph

Example

package main

import (
	"fmt"

	"github.com/aacanakin/dag"
)

func main() {
	// Create a new directed acyclic graph
	// A -> B -> C
	// |    |
	// v    v
	// D -> E -> F

	// Create an empty directed acyclic graph
	graph, _ := dag.New()

	// Add some vertices
	graph.Add("A", "B", "C", "D", "E", "F")

	// Add some edges
	graph.Connect("A", "B")
	graph.Connect("B", "C")
	graph.Connect("A", "D")
	graph.Connect("D", "E")
	graph.Connect("B", "E")
	graph.Connect("E", "F")

	// Get the topological order
	sorted, _ := graph.TopSort()

	// Print the topological order
	for _, vertex := range sorted {
		fmt.Println(vertex)
	}

}

Output:

A
B
D
C
E
F

func New

func New(opts ...GraphOptions) (*Graph, error)

New creates an empty graph with no vertices & edges and returns it

func (*Graph) Add

func (g *Graph) Add(vertices ...Vertex) error

Add appends an unconnected node to the graph

func (*Graph) Append

func (g *Graph) Append(v Vertex, prevVertices []Vertex) error

Append adds a new vertex to graph given vertex and previous vertices, returns error if any of the previous vertices is not present in graph

Example

graph := createGraph()

var err error
// Append some vertices
err = graph.Append("G", []dag.Vertex{"F"})
if err != nil {
	fmt.Println(err)
	return
}

err = graph.Append("H", []dag.Vertex{"G", "F"})
if err != nil {
	fmt.Println(err)
	return
}

sorted, _ := graph.TopSort()

// Print the topological order
for _, vertex := range sorted {
	fmt.Println(vertex)
}

Output:

A
B
D
C
E
F
G
H

func (*Graph) BFS

func (g *Graph) BFS(start Vertex) (result []Vertex, err error)

BFS performs breadth first search on the graph starting from the given vertex

func (*Graph) Connect

func (g *Graph) Connect(from Vertex, to Vertex) error

Connect connects two vertices in the graph

returns error if;

the edge already exists or if the edge creates a cycle

the from vertex is not found in the graph

the to vertex is not found in the graph

the from vertex is the same as the to vertex

it can be used to lazily initialize vertice connections

func (*Graph) DFS

func (g *Graph) DFS(start Vertex) (result []Vertex, err error)

DFS performs depth first search on the graph starting from the given vertex

func (*Graph) DeepCopy

func (g *Graph) DeepCopy() (*Graph, error)

DeepCopy creates a deep copy of the graph

func (*Graph) Deps

func (g *Graph) Deps(vertex string) (result []Vertex, err error)

Deps returns the dependencies of a vertex given vertex, in topological order

Example

package main

import (
	"fmt"

	"github.com/aacanakin/dag"
)

func main() {
	// Create a new directed acyclic graph
	// A -> B -> C
	// |    |
	// v    v
	// D -> E -> F

	// Create an empty directed acyclic graph
	graph, _ := dag.New()

	// Add some vertices
	graph.Add("A", "B", "C", "D", "E", "F")

	// Add some edges
	graph.Connect("A", "B")
	graph.Connect("B", "C")
	graph.Connect("A", "D")
	graph.Connect("D", "E")
	graph.Connect("B", "E")
	graph.Connect("E", "F")

	// Get the dependencies of vertex E
	deps, err := graph.Deps("E")

	if err != nil {
		fmt.Println(err)
		return
	}

	for _, vertex := range deps {
		fmt.Println(vertex)
	}

}

Output:

A
B
D

func (*Graph) Disconnect

func (g *Graph) Disconnect(v Vertex) error

Disconnect disconnects all edges from and to a vertex returns error if the vertex is not found in the graph

Example

package main

import (
	"fmt"

	"github.com/aacanakin/dag"
)

func main() {
	// Create a new directed acyclic graph
	// A -> B -> C
	// |    |
	// v    v
	// D -> E -> F

	// Create an empty directed acyclic graph
	graph, _ := dag.New()

	// Add some vertices
	graph.Add("A", "B", "C", "D", "E", "F")

	// Add some edges
	graph.Connect("A", "B")
	graph.Connect("B", "C")
	graph.Connect("A", "D")
	graph.Connect("D", "E")
	graph.Connect("B", "E")
	graph.Connect("E", "F")

	fmt.Println("disconnecting E")
	err := graph.Disconnect("E")
	if err != nil {
		fmt.Println(err)
		return
	}

	prev, err := graph.Prev("E")
	if err != nil {
		fmt.Println(err)
		return
	}

	for _, prevVertex := range prev {
		fmt.Println(prevVertex)
	}

	next, err := graph.Next("E")
	if err != nil {
		fmt.Println(err)
		return
	}

	for _, nextVertex := range next {
		fmt.Println(nextVertex)
	}

	// here, E is disconnected from all vertices, so, it should not have any dependencies or dependants
	

func (*Graph) DisconnectEdge

func (g *Graph) DisconnectEdge(from Vertex, to Vertex) error

DisconnectEdge disconnects two vertices in the graph returns error if the edge does not exist

func (*Graph) Edges

func (g *Graph) Edges() Edges

Edges returns the edges of the graph

func (*Graph) Exists

func (g *Graph) Exists(vertex Vertex) bool

Exists checks if a vertex exists in the graph

func (*Graph) Leaves

func (g *Graph) Leaves() (leaves []Vertex, err error)

Leaves returns the leaf vertices of the graph

func (*Graph) Next

func (g *Graph) Next(vertex Vertex) ([]Vertex, error)

Next returns the next vertices of a given vertex

func (*Graph) Prev

func (g *Graph) Prev(vertex Vertex) (prev []Vertex, err error)

Prev returns the previous vertices of a given vertex

func (*Graph) Remove

func (g *Graph) Remove(v Vertex) (removed []Vertex, err error)

Remove removes node, all next nodes that are connected to that node & clears all edges that are related to node & deps

func (*Graph) Reverse

func (g *Graph) Reverse() (*Graph, error)

Reverse returns the reverse graph of the graph with reversed edges

func (*Graph) ReverseDeps

func (g *Graph) ReverseDeps(vertex Vertex) (result []Vertex, err error)

ReverseDeps returns the reverse dependencies of a vertex given vertex, in topological order

func (*Graph) ReverseEdges

func (g *Graph) ReverseEdges() (Edges, error)

ReverseEdges returns the reverse edges of the graph example: {a: [b, c], b: [c], c: []} -> {a: [], b: [a], c: [a, b]}

func (*Graph) Roots

func (g *Graph) Roots() ([]Vertex, error)

Roots returns the root vertices of the graph

func (*Graph) SubGraph

func (g *Graph) SubGraph(vertices []Vertex) (graph *Graph, err error)

SubGraph returns a subgraph of existing graph that includes input vertices, clips out vertices & non connected edges

func (*Graph) TopSort

func (g *Graph) TopSort() (result []Vertex, err error)

TopSort applies topological sort algorithm to graph and returns vertices slice

func (*Graph) Vertices

func (g *Graph) Vertices() []Vertex

Vertices returns the vertices of the graph

type GraphOptions

type GraphOptions func(*Graph) error

func WithEdges

func WithEdges(edges Edges) GraphOptions

WithEdges sets the edges of the graph

func WithVertices

func WithVertices(vertices []Vertex) GraphOptions

type Vertex

type Vertex = string

Vertex represents a vertex or node in the graph