dag

Documentation

Overview

Copyright 2021 Wim Henderickx.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

Index

• type DAG
  • func NewMapDag() DAG
• type MapDag
  • func (d *MapDag) AddEdge(from string, to Node) (bool, error)
  • func (d *MapDag) AddEdges(edges map[string][]Node) ([]Node, error)
  • func (d *MapDag) AddNode(node Node) error
  • func (d *MapDag) AddNodes(nodes ...Node) error
  • func (d *MapDag) AddOrUpdateNodes(nodes ...Node)
  • func (d *MapDag) GetNode(identifier string) (Node, error)
  • func (d *MapDag) Init(nodes []Node, fns ...NodeFn) ([]Node, error)
  • func (d *MapDag) NodeExists(identifier string) bool
  • func (d *MapDag) NodeNeighbors(identifier string) ([]Node, error)
  • func (d *MapDag) Sort() ([]string, error)
  • func (d *MapDag) TraceNode(identifier string) (map[string]Node, error)
• type NewDAGFn
• type Node
• type NodeFn
  • func FindIndex(identifier string, index *int) NodeFn

Types

type DAG

type DAG interface {
	Init(nodes []Node, fns ...NodeFn) ([]Node, error)
	AddNode(Node) error
	AddNodes(...Node) error
	AddOrUpdateNodes(...Node)
	GetNode(identifier string) (Node, error)
	AddEdge(from string, to Node) (bool, error)
	AddEdges(edges map[string][]Node) ([]Node, error)
	NodeExists(identifier string) bool
	NodeNeighbors(identifier string) ([]Node, error)
	TraceNode(identifier string) (map[string]Node, error)
	Sort() ([]string, error)
}

DAG is a Directed Acyclic Graph.

func NewMapDag

func NewMapDag() DAG

NewMapDag creates a new MapDag.

type MapDag

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

MapDag is a directed acyclic graph implementation that uses a map for its underlying data structure.

func (*MapDag) AddEdge

func (d *MapDag) AddEdge(from string, to Node) (bool, error)

AddEdge adds an edge to the graph.

func (*MapDag) AddEdges

func (d *MapDag) AddEdges(edges map[string][]Node) ([]Node, error)

AddEdges adds edges to the graph.

func (*MapDag) AddNode

func (d *MapDag) AddNode(node Node) error

AddNode adds a node to the graph.

func (*MapDag) AddNodes

func (d *MapDag) AddNodes(nodes ...Node) error

AddNodes adds nodes to the graph.

func (*MapDag) AddOrUpdateNodes

func (d *MapDag) AddOrUpdateNodes(nodes ...Node)

AddOrUpdateNodes adds new nodes or updates the existing ones with the same identifier.

func (*MapDag) GetNode

func (d *MapDag) GetNode(identifier string) (Node, error)

GetNode returns a node in the dag.

func (*MapDag) Init

func (d *MapDag) Init(nodes []Node, fns ...NodeFn) ([]Node, error)

Init initializes a MapDag and implies missing destination nodes. Any implied nodes are returned. Any existing nodes are cleared.

func (*MapDag) NodeExists

func (d *MapDag) NodeExists(identifier string) bool

NodeExists checks whether a node exists.

func (*MapDag) NodeNeighbors

func (d *MapDag) NodeNeighbors(identifier string) ([]Node, error)

NodeNeighbors returns a node's neighbors.

func (*MapDag) Sort

func (d *MapDag) Sort() ([]string, error)

Sort performs topological sort on the graph.

func (*MapDag) TraceNode

func (d *MapDag) TraceNode(identifier string) (map[string]Node, error)

TraceNode returns a node's neighbors and all transitive neighbors using depth first search.

type NewDAGFn

type NewDAGFn func() DAG

NewDAGFn is a function that returns a DAG.

type Node

type Node interface {
	Identifier() string
	Neighbors() []Node

	// Node implementations should be careful to establish uniqueness of
	// neighbors in their AddNeighbors method or risk counting a neighbor
	// multiple times.
	AddNeighbors(...Node) error
}

Node is a node in DAG.

type NodeFn

type NodeFn func(int, Node)

NodeFn performs executes a function on each node.

func FindIndex

func FindIndex(identifier string, index *int) NodeFn

FindIndex searches for the index of a specific node. The passed index parameter will be updated to the index of the node if found, or left unchanged if not.