dag

package module
v0.10.1 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Dec 19, 2020 License: BSD-3-Clause Imports: 3 Imported by: 58

README

dag

run tests PkgGoDev Go Report Card

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}

Documentation

Overview

Package dag implements directed acyclic graphs (DAGs).

Example 
// 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())

Output:

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

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type DAG 

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

DAG implements the data structure of the DAG.

func NewDAG 

func NewDAG() *DAG

NewDAG creates / initializes a new DAG.

func (*DAG) AddEdge 

func (d *DAG) AddEdge(srcID, dstID string) error

AddEdge adds an edge between srcID and dstID. AddEdge returns an error, if srcID or dstID are empty strings or unknown, if the edge already exists, or if the new edge would create a loop.

func (*DAG) AddVertex 

func (d *DAG) AddVertex(v interface{}) (string, error)

AddVertex adds the vertex v to the DAG. AddVertex returns an error, if v is nil, v is already part of the graph, or the id of v is already part of the graph.

func (*DAG) AncestorsWalker added in v0.9.9 

func (d *DAG) AncestorsWalker(id string) (chan string, chan bool, error)

AncestorsWalker returns a channel and subsequently returns / walks all ancestors of the vertex with id id in a breath first order. The second channel returned may be used to stop further walking. AncestorsWalker returns an error, if id is empty or unknown.

Note, there is no order between sibling vertices. Two consecutive runs of AncestorsWalker may return different results.

Example 
dag := NewDAG()

v1, _ := dag.AddVertex(iVertex{1})
v2, _ := dag.AddVertex(iVertex{2})
v3, _ := dag.AddVertex(iVertex{3})
v4, _ := dag.AddVertex(iVertex{4})
v5, _ := dag.AddVertex(iVertex{5})
_ = dag.AddEdge(v1, v2)
_ = dag.AddEdge(v2, v3)
_ = dag.AddEdge(v2, v4)
_ = dag.AddEdge(v4, v5)

var ancestors []interface{}
vertices, signal, _ := dag.AncestorsWalker(v5)
for v := range vertices {
	ancestors = append(ancestors, v)
	if v == v2 {
		signal <- true
		break
	}
}
fmt.Printf("%v", ancestors)

Output:

  [4 2]

func (*DAG) DeleteEdge 

func (d *DAG) DeleteEdge(srcID, dstID string) error

DeleteEdge deletes the edge between srcID and dstID. DeleteEdge returns an error, if srcID or dstID are empty or unknown, or if, there is no edge between srcID and dstID.

func (*DAG) DeleteVertex 

func (d *DAG) DeleteVertex(id string) error

DeleteVertex deletes the vertex with the given id. DeleteVertex also deletes all attached edges (inbound and outbound). DeleteVertex returns an error, if id is empty or unknown.

func (*DAG) DescendantsWalker added in v0.9.9 

func (d *DAG) DescendantsWalker(id string) (chan string, chan bool, error)

DescendantsWalker returns a channel and subsequently returns / walks all descendants of the vertex with id id in a breath first order. The second channel returned may be used to stop further walking. DescendantsWalker returns an error, if id is empty or unknown.

Note, there is no order between sibling vertices. Two consecutive runs of DescendantsWalker may return different results.

func (*DAG) FlushCaches added in v0.9.12 

func (d *DAG) FlushCaches()

FlushCaches completely flushes the descendants- and ancestor cache.

Note, the only reason to call this method is to free up memory. Otherwise the caches are automatically maintained.

func (*DAG) GetAncestors 

func (d *DAG) GetAncestors(id string) (map[string]interface{}, error)

GetAncestors return all ancestors of the vertex with the id id. GetAncestors returns an error, if id is empty or unknown.

Note, in order to get the ancestors, GetAncestors populates the ancestor- cache as needed. Depending on order and size of the sub-graph of the vertex with id id this may take a long time and consume a lot of memory.

func (*DAG) GetChildren 

func (d *DAG) GetChildren(id string) (map[string]interface{}, error)

GetChildren returns all children of the vertex with the id id. GetChildren returns an error, if id is empty or unknown.

func (*DAG) GetDescendants 

func (d *DAG) GetDescendants(id string) (map[string]interface{}, error)

GetDescendants return all ancestors of the vertex with id id. GetDescendants returns an error, if id is empty or unknown.

Note, in order to get the descendants, GetDescendants populates the descendants-cache as needed. Depending on order and size of the sub-graph of the vertex with id id this may take a long time and consume a lot of memory.

func (*DAG) GetLeaves added in v0.10.0 

func (d *DAG) GetLeaves() map[string]interface{}

GetLeaves returns all vertices without children.

func (*DAG) GetOrder 

func (d *DAG) GetOrder() int

GetOrder returns the number of vertices in the graph.

func (*DAG) GetOrderedAncestors added in v0.9.9 

func (d *DAG) GetOrderedAncestors(id string) ([]string, error)

GetOrderedAncestors returns all ancestors of the vertex with id id in a breath-first order. Only the first occurrence of each vertex is returned. GetOrderedAncestors returns an error, if id is empty or unknown.

Note, there is no order between sibling vertices. Two consecutive runs of GetOrderedAncestors may return different results.

func (*DAG) GetOrderedDescendants added in v0.9.9 

func (d *DAG) GetOrderedDescendants(id string) ([]string, error)

GetOrderedDescendants returns all descendants of the vertex with id id in a breath-first order. Only the first occurrence of each vertex is returned. GetOrderedDescendants returns an error, if id is empty or unknown.

Note, there is no order between sibling vertices. Two consecutive runs of GetOrderedDescendants may return different results.

func (*DAG) GetParents 

func (d *DAG) GetParents(id string) (map[string]interface{}, error)

GetParents returns the all parents of the vertex with the id id. GetParents returns an error, if id is empty or unknown.

func (*DAG) GetRoots 

func (d *DAG) GetRoots() map[string]interface{}

GetRoots returns all vertices without parents.

func (*DAG) GetSize 

func (d *DAG) GetSize() int

GetSize returns the number of edges in the graph.

func (*DAG) GetVertex added in v0.9.10 

func (d *DAG) GetVertex(id string) (interface{}, error)

GetVertex returns a vertex by its id. GetVertex returns an error, if id is the empty string or unknown.

func (*DAG) GetVertices 

func (d *DAG) GetVertices() map[string]interface{}

GetVertices returns all vertices.

func (*DAG) IsEdge added in v0.9.11 

func (d *DAG) IsEdge(srcID, dstID string) (bool, error)

IsEdge returns true, if there exists an edge between srcID and dstID. IsEdge returns false, if there is no such edge. IsEdge returns an error, if srcID or dstID are empty, unknown, or the same.

func (*DAG) ReduceTransitively added in v0.9.11 

func (d *DAG) ReduceTransitively()

ReduceTransitively transitively reduce the graph.

Note, in order to do the reduction the descendant-cache of all vertices is populated (i.e. the transitive closure). Depending on order and size of DAG this may take a long time and consume a lot of memory.

func (*DAG) String 

func (d *DAG) String() string

String returns a textual representation of the graph.

type EdgeDuplicateError added in v0.9.3 

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

EdgeDuplicateError is the error type to describe the situation, that an edge already exists in the graph.

func (EdgeDuplicateError) Error added in v0.9.3 

func (e EdgeDuplicateError) Error() string

Implements the error interface.

type EdgeLoopError added in v0.9.3 

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

EdgeLoopError is the error type to describe loop errors (i.e. errors that where raised to prevent establishing loops in the graph).

func (EdgeLoopError) Error added in v0.9.3 

func (e EdgeLoopError) Error() string

Implements the error interface.

type EdgeUnknownError added in v0.9.3 

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

EdgeUnknownError is the error type to describe the situation, that a given edge does not exit in the graph.

func (EdgeUnknownError) Error added in v0.9.3 

func (e EdgeUnknownError) Error() string

Implements the error interface.

type IDDuplicateError added in v0.10.0 

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

IDDuplicateError is the error type to describe the situation, that a given vertex id already exists in the graph.

func (IDDuplicateError) Error added in v0.10.0 

func (e IDDuplicateError) Error() string

Implements the error interface.

type IDEmptyError added in v0.10.0 

type IDEmptyError struct{}

IDEmptyError is the error type to describe the situation, that a an empty string is given instead of a valid id.

func (IDEmptyError) Error added in v0.10.0 

func (e IDEmptyError) Error() string

Implements the error interface.

type IDInterface added in v0.10.0 

type IDInterface interface {
	ID() string
}

IDInterface describes the interface a type must implement in order to explicitly specify vertex id.

Objects of types not implementing this interface will receive automatically generated ids (as of adding them to the graph).

type IDUnknownError added in v0.10.0 

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

IDUnknownError is the error type to describe the situation, that a given vertex does not exit in the graph.

func (IDUnknownError) Error added in v0.10.0 

func (e IDUnknownError) Error() string

Implements the error interface.

type SrcDstEqualError added in v0.9.11 

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

SrcDstEqualError is the error type to describe the situation, that src and dst are equal.

func (SrcDstEqualError) Error added in v0.9.11 

func (e SrcDstEqualError) Error() string

Implements the error interface.

type VertexDuplicateError added in v0.9.3 

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

VertexDuplicateError is the error type to describe the situation, that a given vertex already exists in the graph.

func (VertexDuplicateError) Error added in v0.9.3 

func (e VertexDuplicateError) Error() string

Implements the error interface.

type VertexNilError added in v0.9.3 

type VertexNilError struct{}

VertexNilError is the error type to describe the situation, that a nil is given instead of a vertex.

func (VertexNilError) Error added in v0.9.3 

func (e VertexNilError) Error() string

Implements the error interface.

Source Files

View all Source files

Directories

Path Synopsis
cmd
basic command
terraform command
timing command

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.