dag

package module
v0.9.11 Latest Latest
Warning

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

 Go to latest Published: Jan 28, 2020 License: BSD-3-Clause Imports: 2 Imported by: 58

README

dag

Build Status codecov GoDoc Go Report Card Nutrition Facts

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

Quickstart

Running:

package main

import (
	"fmt"
	"github.com/heimdalr/dag"
)

// data structure that will be used as vertex in the graph
type myVertex struct {
	Label string
}

// implement the Vertex interface
func (v myVertex) String() string {
	return v.Label
}

func main() {

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

	// init three vertices
	v1 := &myVertex{"1"}
	v2 := &myVertex{"2"}
	v3 := &myVertex{"3"}

	// 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:
  2
  3
  1
Edges:
  1 -> 2
  1 -> 3

Documentation

Overview

Package dag implements directed acyclic graphs (DAGs).

Example 
// initialize a new graph
d := NewDAG()

// init three vertices
v1 := &iVertex{1}
v2 := &iVertex{2}
v3 := &iVertex{3}

// 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:
  2
  3
  1
Edges:
  1 -> 2
  1 -> 3

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(src Vertex, dst Vertex) error

AddEdge adds an edge between src and dst. AddEdge returns an error, if src or dst are nil or if the edge would create a loop. AddEdge calls AddVertex, if src and/or dst are not yet known within the DAG.

func (*DAG) AddVertex 

func (d *DAG) AddVertex(v Vertex) 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(v Vertex) (chan Vertex, chan bool, error)

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

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

Example 
dag := NewDAG()

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

var ancestors []Vertex
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(src Vertex, dst Vertex) error

DeleteEdge deletes an edge. DeleteEdge also deletes ancestor- and descendant-caches of related vertices. DeleteEdge returns an error, if src or dst are nil or unknown, or if there is no edge between src and dst.

func (*DAG) DeleteVertex 

func (d *DAG) DeleteVertex(v Vertex) error

DeleteVertex deletes the vertex v. DeleteVertex also deletes all attached edges (inbound and outbound) as well as ancestor- and descendant-caches of related vertices. DeleteVertex returns an error, if v is nil or unknown.

func (*DAG) DescendantsWalker added in v0.9.9 

func (d *DAG) DescendantsWalker(v Vertex) (chan Vertex, chan bool, error)

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

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

func (*DAG) GetAncestors 

func (d *DAG) GetAncestors(v Vertex) (map[Vertex]bool, error)

GetAncestors return all ancestors of the vertex v. GetAncestors returns an error, if v is nil 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 v this may take a long time and consume a lot of memory.

func (*DAG) GetChildren 

func (d *DAG) GetChildren(v Vertex) (map[Vertex]bool, error)

GetChildren returns all children of vertex v. GetChildren returns an error, if v is nil or unknown.

func (*DAG) GetDescendants 

func (d *DAG) GetDescendants(v Vertex) (map[Vertex]bool, error)

GetDescendants return all ancestors of the vertex v. GetDescendants returns an error, if v is nil 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 v this may take a long time and consume a lot of memory.

func (*DAG) GetLeafs 

func (d *DAG) GetLeafs() map[Vertex]bool

GetLeafs 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(v Vertex) ([]Vertex, error)

GetOrderedAncestors returns all ancestors of the vertex v in a breath-first order. Only the first occurrence of each vertex is returned. GetOrderedAncestors returns an error, if v is nil 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(v Vertex) ([]Vertex, error)

GetOrderedDescendants returns all descendants of the vertex v in a breath- first order. Only the first occurrence of each vertex is returned. GetOrderedDescendants returns an error, if v is nil 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(v Vertex) (map[Vertex]bool, error)

GetParents returns all parents of vertex v. GetParents returns an error, if v is nil or unknown.

func (*DAG) GetRoots 

func (d *DAG) GetRoots() map[Vertex]bool

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) (Vertex, 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[Vertex]bool

GetVertices returns all vertices.

func (*DAG) IsEdge added in v0.9.11 

func (d *DAG) IsEdge(src Vertex, dst Vertex) (bool, error)

IsEdge returns true, if there exists an edge between src and dst. IsEdge returns false if there is no such edge. IsEdge returns an error, if src or dst are nil, 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 return 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.9.10 

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

func (e IdDuplicateError) Error() string

Implements the error interface.

type IdEmptyError added in v0.9.10 

type IdEmptyError struct{}

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

func (IdEmptyError) Error added in v0.9.10 

func (e IdEmptyError) Error() string

Implements the error interface.

type IdUnknownError added in v0.9.10 

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

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 Vertex 

type Vertex interface {

	// Return a string representation of the vertex.
	String() string

	// Return the id of this vertex. This id must be unique and never change.
	Id() string
}

Vertex is the interface to be implemented for the vertices of the DAG.

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.

type VertexUnknownError 

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

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

func (VertexUnknownError) Error 

func (e VertexUnknownError) Error() string

Implements the error interface.

Source Files

View all Source files

Directories

Path Synopsis
cmd
basic 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.