dag

README

go-dag

Minimalistic DAG utility with concurrent scheduler

Example

See scheduler/scheduler_test.go.

  0      1
  |      |
  2      3
  |
 / \
4   5

import (
    "github.com/AkihiroSuda/go-dag"
    "github.com/AkihiroSuda/go-dag/scheduler"
)

g := &dag.Graph{
	Nodes: []dag.Node{0, 1, 2, 3, 4, 5},
	Edges: []dag.Edge{
		{Depender: 2, Dependee: 0},
		{Depender: 3, Dependee: 1},
		{Depender: 4, Dependee: 2},
		{Depender: 5, Dependee: 2},
	},
}
concurrency := 0
scheduler.Execute(g, concurrency, func(n dag.Node) { appendTo(got, n) })
assert(t, indexOf(got, 0) < indexOf(got, 2))
assert(t, indexOf(got, 2) < indexOf(got, 4))
assert(t, indexOf(got, 2) < indexOf(got, 5))
assert(t, indexOf(got, 1) < indexOf(got, 3))

Documentation

Overview

Package dag provides dag

Index

• type Edge
• type EdgesSorter
  • func (x EdgesSorter) Len() int
  • func (x EdgesSorter) Less(i, j int) bool
  • func (x EdgesSorter) Swap(i, j int)
• type Graph
  • func (g *Graph) AddEdge(e Edge)
  • func (g *Graph) AddNode(n Node)
  • func (g *Graph) ConnectedComponentRoots() []Node
  • func (g *Graph) DirectDependees(depender Node) []Node
  • func (g *Graph) DirectDependers(dependee Node) []Node
  • func (g *Graph) HasEdge(e Edge) bool
  • func (g *Graph) HasNode(n Node) bool
  • func (g *Graph) VerifyAcyclicity() bool
• type Node
• type NodesSorter
  • func (x NodesSorter) Len() int
  • func (x NodesSorter) Less(i, j int) bool
  • func (x NodesSorter) Swap(i, j int)

Types

type Edge

type Edge struct {
	Depender Node
	Dependee Node
}

Edge is a pair of depender node and dependee node.

type EdgesSorter

type EdgesSorter []Edge

EdgesSorter sorts edges

func (EdgesSorter) Len

func (x EdgesSorter) Len() int

Len implements sorter

func (EdgesSorter) Less

func (x EdgesSorter) Less(i, j int) bool

Less implements sorter

func (EdgesSorter) Swap

func (x EdgesSorter) Swap(i, j int)

Swap implements sorter

type Graph

type Graph struct {
	// Nodes SHOULD be sorted but not needed
	Nodes []Node
	// Edges SHOULD be sorted but not needed
	Edges []Edge
}

Graph is SUPPOSED to be a DAG, but there is no guarantee. Graph MAY be disconnected graph.

func (*Graph) AddEdge

func (g *Graph) AddEdge(e Edge)

AddEdge adds an edge if not existed

func (*Graph) AddNode

func (g *Graph) AddNode(n Node)

AddNode adds a node if not existed

func (*Graph) ConnectedComponentRoots

func (g *Graph) ConnectedComponentRoots() []Node

ConnectedComponentRoots returns nodes with no dependee See also https://en.wikipedia.org/wiki/Connected_component_(graph_theory)

func (*Graph) DirectDependees

func (g *Graph) DirectDependees(depender Node) []Node

DirectDependees returns direct dependees, not indirect ones

func (*Graph) DirectDependers

func (g *Graph) DirectDependers(dependee Node) []Node

DirectDependers returns direct dependers, not indirect ones

func (*Graph) HasEdge

func (g *Graph) HasEdge(e Edge) bool

HasEdge returns true if the graph has the node

func (*Graph) HasNode

func (g *Graph) HasNode(n Node) bool

HasNode returns true if the graph has the node

func (*Graph) VerifyAcyclicity

func (g *Graph) VerifyAcyclicity() bool

VerifyAcyclicity returns true if the graph is DAG

type Node

type Node int

Node is an integer that denotes Node.

type NodesSorter

type NodesSorter []Node

NodesSorter sorts nodes

func (NodesSorter) Len

func (x NodesSorter) Len() int

Len implements sorter

func (NodesSorter) Less

func (x NodesSorter) Less(i, j int) bool

Less implements sorter

func (NodesSorter) Swap

func (x NodesSorter) Swap(i, j int)

Swap implements sorter