dag

package module
v0.0.0-...-9f658dd Latest Latest
Warning

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

 Go to latest Published: Oct 18, 2024 License: BSD-3-Clause Imports: 9 Imported by: 1

README

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}

Documentation

Overview

Package dag implements directed acyclic graphs (DAGs).

Example 
package main

import (
	"fmt"

	"github.com/ishumei/dag"
)

type foobar struct {
	a string
	b string
}

func main() {

	// initialize a new graph
	d := dag.NewDAG()

	// init three vertices
	v1, _ := d.AddVertex(1)
	v2, _ := d.AddVertex(2)
	v3, _ := d.AddVertex(foobar{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 UnmarshalJSON 

func UnmarshalJSON(data []byte, wd StorableDAG, options Options) (*DAG, error)

UnmarshalJSON parses the JSON-encoded data that defined by StorableDAG. It returns a new DAG defined by the vertices and edges of wd. If the internal structure of data and wd do not match, then deserialization will fail and return json error.

Because the vertex data passed in by the user is an interface{}, it does not indicate a specific structure, so it cannot be deserialized. And this function needs to pass in a clear DAG structure.

Example: dag := NewDAG() data, err := json.Marshal(d) 

if err != nil {
    panic(err)
}

var wd YourStorableDAG restoredDag, err := UnmarshalJSON(data, &wd) 

if err != nil {
    panic(err)
}

For more specific information please read the test code.

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) AddVertexByID 

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

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

func (*DAG) AncestorsWalker 

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) BFSWalk 

func (d *DAG) BFSWalk(visitor Visitor)

BFSWalk implements the Breadth-First-Search algorithm to traverse the entire DAG. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next depth level.

func (*DAG) Copy 

func (d *DAG) Copy() (newDAG *DAG, err error)

Copy returns a copy of the DAG.

func (*DAG) DFSWalk 

func (d *DAG) DFSWalk(visitor Visitor)

DFSWalk implements the Depth-First-Search algorithm to traverse the entire DAG. The algorithm starts at the root node and explores as far as possible along each branch before backtracking.

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) DescendantsFlow 

func (d *DAG) DescendantsFlow(ctx context.Context, startID string, inputs []FlowResult, callback FlowCallback) ([]FlowResult, error)

DescendantsFlow traverses descendants of the vertex with the ID startID. For the vertex itself and each of its descendant it executes the given (callback-) function providing it the results of its respective parents. The (callback-) function is only executed after all parents have finished their work.

Example 
package main

import (
	"context"
	"fmt"
	"sort"

	"github.com/ishumei/dag"
)

func main() {
	// Initialize a new graph.
	d := dag.NewDAG()

	// Init vertices.
	v0, _ := d.AddVertex(0)
	v1, _ := d.AddVertex(1)
	v2, _ := d.AddVertex(2)
	v3, _ := d.AddVertex(3)
	v4, _ := d.AddVertex(4)

	// Add the above vertices and connect them.
	_ = d.AddEdge(v0, v1)
	_ = d.AddEdge(v0, v3)
	_ = d.AddEdge(v1, v2)
	_ = d.AddEdge(v2, v4)
	_ = d.AddEdge(v3, v4)

	//   0
	// ┌─┴─┐
	// 1   │
	// │   3
	// 2   │
	// └─┬─┘
	//   4

	// The callback function adds its own value (ID) to the sum of parent results.
	flowCallback := func(ctx context.Context, d *dag.DAG, id string, parentResults []dag.FlowResult) (interface{}, error) {

		v, _ := d.GetVertex(id)
		result, _ := v.(int)
		var parents []int
		for _, r := range parentResults {
			p, _ := d.GetVertex(r.ID)
			parents = append(parents, p.(int))
			result += r.Result.(int)
		}
		sort.Ints(parents)
		fmt.Printf("%v based on: %+v returns: %d\n", v, parents, result)
		return result, nil
	}

	_, _ = d.DescendantsFlow(context.Background(), v0, nil, flowCallback)

}

Output:

0 based on: [] returns: 0
1 based on: [0] returns: 1
3 based on: [0] returns: 3
2 based on: [1] returns: 3
4 based on: [2 3] returns: 10

func (*DAG) DescendantsWalker 

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 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 

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. Normally 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) GetAncestorsGraph 

func (d *DAG) GetAncestorsGraph(id string) (*DAG, string, error)

GetAncestorsGraph returns a new DAG consisting of the vertex with id id and all its ancestors (i.e. the subgraph). GetAncestorsGraph also returns the id of the (copy of the) given vertex within the new graph (i.e. the id of the single leaf of the new graph). GetAncestorsGraph returns an error, if id is empty or unknown.

Note, the new graph is a copy of the relevant part of the original graph.

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 descendants 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) GetDescendantsGraph 

func (d *DAG) GetDescendantsGraph(id string) (*DAG, string, error)

GetDescendantsGraph returns a new DAG consisting of the vertex with id id and all its descendants (i.e. the subgraph). GetDescendantsGraph also returns the id of the (copy of the) given vertex within the new graph (i.e. the id of the single root of the new graph). GetDescendantsGraph returns an error, if id is empty or unknown.

Note, the new graph is a copy of the relevant part of the original graph.

func (*DAG) GetLeaves 

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 

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 

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 

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 

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) IsLeaf 

func (d *DAG) IsLeaf(id string) (bool, error)

IsLeaf returns true, if the vertex with the given id has no children. IsLeaf returns an error, if id is empty or unknown.

func (*DAG) IsRoot 

func (d *DAG) IsRoot(id string) (bool, error)

IsRoot returns true, if the vertex with the given id has no parents. IsRoot returns an error, if id is empty or unknown.

func (*DAG) MarshalJSON 

func (d *DAG) MarshalJSON() ([]byte, error)

MarshalJSON returns the JSON encoding of DAG.

It traverses the DAG using the Depth-First-Search algorithm and uses an internal structure to store vertices and edges.

func (*DAG) Options 

func (d *DAG) Options(options Options)

Options sets the options for the DAG. Options must be called before any other method of the DAG is called.

func (*DAG) OrderedWalk 

func (d *DAG) OrderedWalk(visitor Visitor)

OrderedWalk implements the Topological Sort algorithm to traverse the entire DAG. This means that for any edge a -> b, node a will be visited before node b.

func (*DAG) ReduceTransitively 

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.

func (*DAG) UnmarshalJSON 

func (d *DAG) UnmarshalJSON(_ []byte) error

UnmarshalJSON is an informative method. See the UnmarshalJSON function below.

type EdgeDuplicateError 

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 

func (e EdgeDuplicateError) Error() string

Implements the error interface.

type EdgeLoopError 

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 

func (e EdgeLoopError) Error() string

Implements the error interface.

type EdgeUnknownError 

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 

func (e EdgeUnknownError) Error() string

Implements the error interface.

type Edger 

type Edger interface {
	Edge() (srcID, dstID string)
}

Edger is the interface that wraps the basic Edge method. Edge returns the ids of two vertices that connect an edge.

type FlowCallback 

type FlowCallback func(ctx context.Context, d *DAG, id string, parentResults []FlowResult) (interface{}, error)

FlowCallback is the signature of the (callback-) function to call for each vertex within a DescendantsFlow, after all its parents have finished their work. The parameters of the function are the (complete) DAG, the current vertex ID, and the results of all its parents. An instance of FlowCallback should return a result or an error.

type FlowResult 

type FlowResult struct {

	// The id of the vertex that produced this result.
	ID string

	// The actual result.
	Result interface{}

	// Any error. Note, DescendantsFlow does not care about this error. It is up to
	// the FlowCallback of downstream vertices to handle the error as needed - if
	// needed.
	Error error
}

FlowResult describes the data to be passed between vertices in a DescendantsFlow.

type IDDuplicateError 

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 

func (e IDDuplicateError) Error() string

Implements the error interface.

type IDEmptyError 

type IDEmptyError struct{}

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

func (IDEmptyError) Error 

func (e IDEmptyError) Error() string

Implements the error interface.

type IDInterface 

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).

Example 
package main

import (
	"fmt"

	"github.com/ishumei/dag"
)

type idVertex struct {
	id  string
	msg string
}

func (v idVertex) ID() string {
	return v.id
}

func main() {

	// initialize a new graph
	d := dag.NewDAG()

	// init three vertices
	id, _ := d.AddVertex(idVertex{id: "1", msg: "foo"})
	fmt.Printf("id of vertex is %s\n", id)
	v, _ := d.GetVertex(id)
	fmt.Printf("%s", v)

}

Output:

id of vertex is 1
{1 foo}

type IDUnknownError 

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 

func (e IDUnknownError) Error() string

Implements the error interface.

type Options 

type Options struct {
	// VertexHashFunc is the function that calculates the hash value of a vertex.
	// This can be useful when the vertex contains not comparable types such as maps.
	// If VertexHashFunc is nil, the defaultVertexHashFunc is used.
	VertexHashFunc func(v interface{}) interface{}
}

Options is the configuration for the DAG.

type SrcDstEqualError 

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 

func (e SrcDstEqualError) Error() string

Implements the error interface.

type StorableDAG 

type StorableDAG interface {
	Vertices() []Vertexer
	Edges() []Edger
}

StorableDAG is the interface that defines a DAG that can be stored. It provides methods to get all vertices and all edges of a DAG.

type VertexDuplicateError 

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 

func (e VertexDuplicateError) Error() string

Implements the error interface.

type VertexNilError 

type VertexNilError struct{}

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

func (VertexNilError) Error 

func (e VertexNilError) Error() string

Implements the error interface.

type Vertexer 

type Vertexer interface {
	Vertex() (id string, value interface{})
}

Vertexer is the interface that wraps the basic Vertex method. Vertex returns an id that identifies this vertex and the value of this vertex.

The reason for defining this new structure is that the vertex id may be automatically generated when the caller adds a vertex. At this time, the vertex structure added by the user does not contain id information.

type Visitor 

type Visitor interface {
	Visit(Vertexer)
}

Visitor is the interface that wraps the basic Visit method. It can use the Visitor and XXXWalk functions together to traverse the entire DAG. And access per-vertex information when traversing.

Source Files

View all Source files

Directories

Path Synopsis
cmd
basic
terraform
timing

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.