dag

package module
v0.0.0-...-360dd84 Latest Latest
Warning

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

 Go to latest Published: Mar 2, 2026 License: BSD-3-Clause Imports: 10 Imported by: 0

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/JodeZer/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}

Serialization

DAGs can be serialized to and deserialized from JSON.

For most use cases, use UnmarshalFromJSON which provides a simple API:

// Simple string type
var vertexType string
dag, err := dag.UnmarshalFromJSON(data, &vertexType, dag.DefaultAcyclic())

// Complex custom type
type Person struct {
    Name string `json:"name"`
    Age  int    `json:"age"`
}
var vertexType Person
dag, err := dag.UnmarshalFromJSON(data, &vertexType, dag.DefaultAcyclic())

// Integer type
var vertexType int
dag, err := dag.UnmarshalFromJSON(data, &vertexType, dag.DefaultAcyclic())
Advanced Deserialization

For complete control over vertex types, implement the StorableDAG interface and use UnmarshalJSON:

type MyVertex struct {
    WID string `json:"i"`
    Val string `json:"v"`
}

func (v MyVertex) Vertex() (string, interface{}) {
    return v.WID, v.Val
}

type MyStorableDAG struct {
    StorableVertices []MyVertex     `json:"vs"`
    StorableEdges    []storableEdge `json:"es"`
}

func (g MyStorableDAG) Vertices() []Vertexer {
    l := make([]Vertexer, 0, len(g.StorableVertices))
    for _, v := range g.StorableVertices {
        l = append(l, v)
    }
    return l
}

func (g MyStorableDAG) Edges() []Edger {
    l := make([]Edger, 0, len(g.StorableEdges))
    for _, e := range g.StorableEdges {
        l = append(l, e)
    }
    return l
}

// Usage
var wd MyStorableDAG
dag, err := dag.UnmarshalJSON(data, &wd, dag.DefaultAcyclic())
Serialization

To serialize a DAG to JSON:

d := NewDAG()
// ... add vertices and edges ...

data, err := d.MarshalJSON()
if err != nil {
    panic(err)
}

Documentation

Overview

Package dag implements directed acyclic graphs (DAGs).

Example 
package main

import (
	"fmt"
	"github.com/JodeZer/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

func MarshalGeneric 

func MarshalGeneric[T any](d *DAG) ([]byte, error)

MarshalGeneric returns the JSON encoding of DAG with typed vertex values.

The generic parameter T specifies the type of vertex values. This is the recommended method for serialization when using the generic API.

Example usage: 

// Simple type
data, err := dag.MarshalGeneric[string](d)

// Complex custom type
type Person struct { Name string; Age int }
data, err := dag.MarshalGeneric[Person](d)

Types

type CopyOption 

type CopyOption int

CopyOption defines data copying options for edge and node list retrieval. 

const (
	// ShareData indicates that the returned data should share references
	// with the source DAG. This is more efficient but modifications to the
	// shared data may affect the DAG.
	ShareData CopyOption = iota

	// CopyData indicates that the returned data should be a deep copy.
	// This is safer but uses more memory.
	CopyData
)

type DAG deprecated 

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

DAG implements the data structure of the DAG.

Deprecated: Use GenericDAG[T] for type-safe operations and better performance. GenericDAG[T] eliminates type conversion overhead by storing vertex values directly as type T instead of interface{}. Use TypedDAG[T] for a convenient type-safe wrapper.

func NewDAG deprecated 

func NewDAG() *DAG

NewDAG creates / initializes a new DAG.

Deprecated: Use NewGenericDAG[T] for type-safe operations and better performance, or use New[T]() for a convenient type-safe wrapper.

func UnmarshalJSONGeneric 

func UnmarshalJSONGeneric[T any](data []byte, options Options) (*DAG, error)

UnmarshalJSONGeneric parses JSON-encoded data and returns a new DAG. This is the legacy generic function kept for backward compatibility.

The generic parameter T specifies the type of vertex values. It can be any type that json.Unmarshal can handle, including complex nested structs.

For new code, consider using the TypedDAG[T] API with UnmarshalJSON[T] instead.

Example usage: 

// Simple type
dag, err := dag.UnmarshalJSONGeneric[string](data, opts)

// Complex custom type
type Person struct {
    Name string `json:"name"`
    Age  int    `json:"age"`
}
dag, err := dag.UnmarshalJSONGeneric[Person](data, opts)

// Pointer to struct type
dag, err := dag.UnmarshalJSONGeneric[*Person](data, opts)

func UnmarshalJSONLegacy deprecated 

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

UnmarshalJSONLegacy parses the JSON-encoded data that defined by StorableDAG. This is the legacy function kept for backward compatibility. 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 := UnmarshalJSONLegacy(data, &wd) 

if err != nil {
    panic(err)
}

For more specific information please read the test code.

Deprecated: Use the generic UnmarshalJSON[T] function instead.

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(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 (
	"fmt"
	"github.com/JodeZer/dag"
	"sort"
)

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

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.

Deprecated: Use MarshalGeneric[T] for better performance with typed data.

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 EdgeList 

type EdgeList struct {
	Edges []GenericEdge
}

EdgeList represents a list of edges in the DAG.

func NewEdgeList 

func NewEdgeList(capacity int) *EdgeList

NewEdgeList creates a new EdgeList with the given capacity.

func (*EdgeList) AddEdge 

func (el *EdgeList) AddEdge(srcID, dstID string)

AddEdge adds an edge to the list.

func (*EdgeList) Copy 

func (el *EdgeList) Copy() *EdgeList

Copy creates a deep copy of the EdgeList.

func (*EdgeList) Count 

func (el *EdgeList) Count() int

Count returns the number of edges in the list.

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

type GenericDAG[T any] struct {
	// contains filtered or unexported fields
}

GenericDAG implements the data structure of the DAG with typed vertex values. This is the new generic implementation that eliminates type conversion overhead by storing vertex values directly as type T instead of interface{}.

Example usage: 

type Person struct {
    Name string `json:"name"`
    Age  int    `json:"age"`
}

// Create a DAG with string vertices
dag := NewGenericDAG[string]()
dag.AddVertex("value")

// Create a DAG with custom type vertices
personDAG := NewGenericDAG[Person]()
personDAG.AddVertex(Person{Name: "Alice", Age: 30})

func NewGenericDAG 

func NewGenericDAG[T any]() *GenericDAG[T]

NewGenericDAG creates / initializes a new generic DAG.

func UnmarshalGenericJSON 

func UnmarshalGenericJSON[T any](data []byte, options Options) (*GenericDAG[T], error)

UnmarshalGenericJSON parses JSON-encoded data and returns a new GenericDAG. This is the recommended function for unmarshaling GenericDAGs from JSON.

The generic parameter T specifies the type of vertex values. It can be any type that json.Unmarshal can handle, including complex nested structs.

Example usage: 

// Simple type
dag, err := dag.UnmarshalGenericJSON[string](data, dag.Options{})

// Complex custom type
type Person struct {
    Name string `json:"name"`
    Age  int    `json:"age"`
}
dag, err := dag.UnmarshalGenericJSON[Person](data, dag.Options{})

func (*GenericDAG[T]) AddEdge 

func (d *GenericDAG[T]) 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 (*GenericDAG[T]) AddVertex 

func (d *GenericDAG[T]) AddVertex(v T) (string, error)

AddVertex adds the vertex v to the DAG. AddVertex returns the generated id and an error if v is already part of the graph.

func (*GenericDAG[T]) AddVertexByID 

func (d *GenericDAG[T]) AddVertexByID(id string, v T) error

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

func (*GenericDAG[T]) AncestorsWalker 

func (d *GenericDAG[T]) AncestorsWalker(id string) (chan string, chan bool, error)

AncestorsWalker returns a channel and subsequently walks all ancestors of the vertex with 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.

func (*GenericDAG[T]) Copy 

func (d *GenericDAG[T]) Copy() (*GenericDAG[T], error)

Copy returns a copy of the GenericDAG.

func (*GenericDAG[T]) DeleteEdge 

func (d *GenericDAG[T]) 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 (*GenericDAG[T]) DeleteVertex 

func (d *GenericDAG[T]) 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 (*GenericDAG[T]) DescendantsWalker 

func (d *GenericDAG[T]) DescendantsWalker(id string) (chan string, chan bool, error)

DescendantsWalker returns a channel and subsequently 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.

func (*GenericDAG[T]) FlushCaches 

func (d *GenericDAG[T]) FlushCaches()

FlushCaches completely flushes the descendants- and ancestor cache.

func (*GenericDAG[T]) GenericBFSWalk 

func (d *GenericDAG[T]) GenericBFSWalk(visitor GenericVisitor[T])

GenericBFSWalk implements the Breadth-First-Search algorithm to traverse the entire GenericDAG. 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 (*GenericDAG[T]) GenericDFSWalk 

func (d *GenericDAG[T]) GenericDFSWalk(visitor GenericVisitor[T])

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

func (*GenericDAG[T]) GenericOrderedWalk 

func (d *GenericDAG[T]) GenericOrderedWalk(visitor GenericVisitor[T])

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

func (*GenericDAG[T]) GetAncestors 

func (d *GenericDAG[T]) GetAncestors(id string) (map[string]T, error)

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

func (*GenericDAG[T]) GetAncestorsGraph 

func (d *GenericDAG[T]) GetAncestorsGraph(id string) (*GenericDAG[T], string, error)

GetAncestorsGraph returns a new GenericDAG consisting of the vertex with 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.

func (*GenericDAG[T]) GetAncestorsGraphByDepth 

func (d *GenericDAG[T]) GetAncestorsGraphByDepth(leafID string, maxDepth int) (*GenericDAG[T], string, error)

GetAncestorsGraphByDepth returns a new GenericDAG consisting of the vertex with leafID and its ancestors, limited to maxDepth levels. Depth starts at 0 for the leaf node, 1 for its direct parents, and so on. Returns the new DAG, the id of the leaf node in the new graph, and an error.

func (*GenericDAG[T]) GetChildren 

func (d *GenericDAG[T]) GetChildren(id string) (map[string]T, error)

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

func (*GenericDAG[T]) GetDescendants 

func (d *GenericDAG[T]) GetDescendants(id string) (map[string]T, error)

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

func (*GenericDAG[T]) GetDescendantsGraph 

func (d *GenericDAG[T]) GetDescendantsGraph(id string) (*GenericDAG[T], string, error)

GetDescendantsGraph returns a new GenericDAG consisting of the vertex with 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.

func (*GenericDAG[T]) GetDescendantsGraphByDepth 

func (d *GenericDAG[T]) GetDescendantsGraphByDepth(rootID string, maxDepth int) (*GenericDAG[T], string, error)

GetDescendantsGraphByDepth returns a new GenericDAG consisting of the vertex with rootID and its descendants, limited to maxDepth levels. Depth starts at 0 for the root node, 1 for its direct children, and so on. Returns the new DAG, the id of the root node in the new graph, and an error.

func (*GenericDAG[T]) GetEdges 

func (d *GenericDAG[T]) GetEdges() EdgeList

GetEdges returns a list of all edges in the DAG. The returned edge list shares data with the DAG for better performance. Use GetEdgesWithOption(CopyData) for a safe, independent copy.

func (*GenericDAG[T]) GetEdgesByDepth 

func (d *GenericDAG[T]) GetEdgesByDepth(rootID string, minDepth, maxDepth int) (EdgeList, error)

GetEdgesByDepth returns edges within the specified depth range from the root node. The depth of an edge is determined by the depth of its target vertex. For example, root->child edges are at depth 1 (child is at depth 1). minDepth and maxDepth are inclusive. Use maxDepth = -1 for unlimited depth.

func (*GenericDAG[T]) GetEdgesWithOption 

func (d *GenericDAG[T]) GetEdgesWithOption(option CopyOption) EdgeList

GetEdgesWithOption returns a list of all edges in the DAG. The option parameter determines whether the data is shared or copied.

func (*GenericDAG[T]) GetLeaves 

func (d *GenericDAG[T]) GetLeaves() map[string]T

GetLeaves returns all vertices without children.

func (*GenericDAG[T]) GetOrder 

func (d *GenericDAG[T]) GetOrder() int

GetOrder returns the number of vertices in the graph.

func (*GenericDAG[T]) GetOrderedAncestors 

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

GetOrderedAncestors returns all ancestors of the vertex with 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.

func (*GenericDAG[T]) GetOrderedDescendants 

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

GetOrderedDescendants returns all descendants of the vertex with 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.

func (*GenericDAG[T]) GetParents 

func (d *GenericDAG[T]) GetParents(id string) (map[string]T, error)

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

func (*GenericDAG[T]) GetRoots 

func (d *GenericDAG[T]) GetRoots() map[string]T

GetRoots returns all vertices without parents.

func (*GenericDAG[T]) GetSize 

func (d *GenericDAG[T]) GetSize() int

GetSize returns the number of edges in the graph.

func (*GenericDAG[T]) GetVertex 

func (d *GenericDAG[T]) GetVertex(id string) (T, error)

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

func (*GenericDAG[T]) GetVertices 

func (d *GenericDAG[T]) GetVertices() map[string]T

GetVertices returns all vertices as a map of id to value.

func (*GenericDAG[T]) GetVerticesList 

func (d *GenericDAG[T]) GetVerticesList() NodeList[T]

GetVerticesList returns a list of all vertices in the DAG. The returned node list shares data with the DAG for better performance. Use GetVerticesListWithOption(CopyData) for a safe, independent copy.

func (*GenericDAG[T]) GetVerticesListWithOption 

func (d *GenericDAG[T]) GetVerticesListWithOption(option CopyOption) NodeList[T]

GetVerticesListWithOption returns a list of all vertices in the DAG. The option parameter determines whether the data is shared or copied.

func (*GenericDAG[T]) IsEdge 

func (d *GenericDAG[T]) 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 (*GenericDAG[T]) IsLeaf 

func (d *GenericDAG[T]) 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 (*GenericDAG[T]) IsRoot 

func (d *GenericDAG[T]) 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 (*GenericDAG[T]) MarshalJSON 

func (d *GenericDAG[T]) MarshalJSON() ([]byte, error)

MarshalJSON returns the JSON encoding of the GenericDAG.

func (*GenericDAG[T]) Options 

func (d *GenericDAG[T]) Options(options Options)

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

func (*GenericDAG[T]) ReduceTransitively 

func (d *GenericDAG[T]) ReduceTransitively()

ReduceTransitively transitively reduces the graph.

func (*GenericDAG[T]) String 

func (d *GenericDAG[T]) String() string

String returns a textual representation of the graph.

type GenericDFSVisitor 

type GenericDFSVisitor[T any] struct {
	// contains filtered or unexported fields
}

GenericDFSVisitor implements the DFS traversal for GenericDAG.

func NewGenericDFSVisitor 

func NewGenericDFSVisitor[T any](visitor GenericVisitor[T]) *GenericDFSVisitor[T]

NewGenericDFSVisitor creates a new DFS visitor.

func (*GenericDFSVisitor[T]) Visit 

func (gv *GenericDFSVisitor[T]) Visit(v Vertexer)

Visit implements the Visitor interface for DFS walk compatibility.

type GenericEdge 

type GenericEdge struct {
	SrcID string `json:"s"`
	DstID string `json:"d"`
}

GenericEdge represents an edge for serialization.

type GenericMarshalVisitor 

type GenericMarshalVisitor[T any] struct {
	// contains filtered or unexported fields
}

GenericMarshalVisitor implements GenericVisitor for marshaling.

func NewGenericMarshalVisitor 

func NewGenericMarshalVisitor[T any](order, size int) *GenericMarshalVisitor[T]

NewGenericMarshalVisitor creates a new marshal visitor for GenericDAG.

func (*GenericMarshalVisitor[T]) AddEdges 

func (mv *GenericMarshalVisitor[T]) AddEdges(parentID string, children map[string]interface{})

AddEdges adds edges from a parent to its children.

func (*GenericMarshalVisitor[T]) Visit 

func (mv *GenericMarshalVisitor[T]) Visit(value T, id string)

Visit implements GenericVisitor interface.

type GenericStorableDAG 

type GenericStorableDAG[T any] struct {
	Vertices []GenericStorableVertex[T] `json:"vs"`
	Edges    []GenericEdge              `json:"es"`
}

GenericStorableDAG represents a DAG for serialization.

type GenericStorableVertex 

type GenericStorableVertex[T any] struct {
	ID    string `json:"i"`
	Value T      `json:"v"`
}

GenericStorableVertex represents a vertex for serialization.

type GenericVisitor 

type GenericVisitor[T any] interface {
	Visit(value T, id string)
}

GenericVisitor is the interface for visiting generic DAG vertices.

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/JodeZer/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 NodeList 

type NodeList[T any] struct {
	Nodes []GenericStorableVertex[T]
}

NodeList represents a list of vertices in the DAG.

func NewNodeList 

func NewNodeList[T any](capacity int) *NodeList[T]

NewNodeList creates a new NodeList with the given capacity.

func (*NodeList[T]) AddNode 

func (nl *NodeList[T]) AddNode(id string, value T)

AddNode adds a node to the list.

func (*NodeList[T]) Copy 

func (nl *NodeList[T]) Copy() *NodeList[T]

Copy creates a deep copy of the NodeList. Note: This creates a shallow copy of the vertex values.

func (*NodeList[T]) Count 

func (nl *NodeList[T]) Count() int

Count returns the number of nodes in the list.

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 TestVertex 

type TestVertex struct {
	VertexID string
	Name     string
}

TestVertex is a simple vertex type for testing.

func (TestVertex) ID 

func (tv TestVertex) ID() string

ID implements the IDInterface for TestVertex.

type TypedDAG 

type TypedDAG[T any] struct {
	// contains filtered or unexported fields
}

TypedDAG is a type-safe directed acyclic graph with vertex values of type T. It provides compile-time type checking for vertex values and eliminates the need for type assertions when working with vertices.

Internally, TypedDAG uses GenericDAG[T] for optimal performance without type conversion overhead.

Example usage: 

type Person struct {
    Name string `json:"name"`
    Age  int    `json:"age"`
}

dag := dag.New[Person]()
dag.AddVertexByID("p1", Person{Name: "Alice", Age: 30})
dag.AddVertexByID("p2", Person{Name: "Bob", Age: 25})
dag.AddEdge("p1", "p2")

// Type-safe vertex access
person, err := dag.GetVertex("p1")
if err == nil {
    fmt.Printf("%s is %d years old\n", person.Name, person.Age)
}

// Auto-infer serialization - no generic parameter needed
data, err := dag.MarshalJSON()

// Deserialize with type parameter (reasonable - need to know the type)
restored, err := dag.UnmarshalJSON[Person](data, dag.Options{})

func New 

func New[T any]() *TypedDAG[T]

New creates a new type-safe DAG with vertex values of type T.

func NewWithOptions 

func NewWithOptions[T any](options Options) *TypedDAG[T]

NewWithOptions creates a new type-safe DAG with vertex values of type T and custom options.

func UnmarshalJSON 

func UnmarshalJSON[T any](data []byte, options Options) (*TypedDAG[T], error)

UnmarshalJSON parses JSON-encoded data and returns a new TypedDAG[T]. This is the recommended function for unmarshaling TypedDAGs from JSON.

The generic parameter T specifies the type of vertex values. It can be any type that json.Unmarshal can handle, including complex nested structs.

Example usage: 

// Simple type
dag, err := dag.UnmarshalJSON[string](data, dag.Options{})

// Complex custom type
type Person struct {
    Name string `json:"name"`
    Age  int    `json:"age"`
}
dag, err := dag.UnmarshalJSON[Person](data, dag.Options{})

func (*TypedDAG[T]) AddEdge 

func (d *TypedDAG[T]) 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 (*TypedDAG[T]) AddVertex 

func (d *TypedDAG[T]) AddVertex(v T) (string, error)

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

func (*TypedDAG[T]) AddVertexByID 

func (d *TypedDAG[T]) AddVertexByID(id string, v T) 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 (*TypedDAG[T]) AncestorsWalker 

func (d *TypedDAG[T]) AncestorsWalker(id string) (chan string, chan bool, error)

AncestorsWalker returns a channel and subsequently walks all ancestors of the vertex with 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.

func (*TypedDAG[T]) Copy 

func (d *TypedDAG[T]) Copy() (*TypedDAG[T], error)

Copy returns a copy of the TypedDAG.

func (*TypedDAG[T]) DeleteEdge 

func (d *TypedDAG[T]) 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 (*TypedDAG[T]) DeleteVertex 

func (d *TypedDAG[T]) 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 (*TypedDAG[T]) DescendantsFlow 

func (d *TypedDAG[T]) DescendantsFlow(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.

func (*TypedDAG[T]) DescendantsWalker 

func (d *TypedDAG[T]) DescendantsWalker(id string) (chan string, chan bool, error)

DescendantsWalker returns a channel and subsequently 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.

func (*TypedDAG[T]) FlushCaches 

func (d *TypedDAG[T]) FlushCaches()

FlushCaches completely flushes the descendants- and ancestor cache.

func (*TypedDAG[T]) GetAncestors 

func (d *TypedDAG[T]) GetAncestors(id string) (map[string]T, error)

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

func (*TypedDAG[T]) GetAncestorsGraph 

func (d *TypedDAG[T]) GetAncestorsGraph(id string) (*TypedDAG[T], string, error)

GetAncestorsGraph returns a new TypedDAG consisting of the vertex with 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.

func (*TypedDAG[T]) GetAncestorsGraphByDepth 

func (d *TypedDAG[T]) GetAncestorsGraphByDepth(leafID string, maxDepth int) (*TypedDAG[T], string, error)

GetAncestorsGraphByDepth returns a new TypedDAG consisting of the vertex with leafID and its ancestors, limited to maxDepth levels. Depth starts at 0 for the leaf node, 1 for its direct parents, and so on. Returns the new DAG, the id of the leaf node in the new graph, and an error.

func (*TypedDAG[T]) GetChildren 

func (d *TypedDAG[T]) GetChildren(id string) (map[string]T, error)

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

func (*TypedDAG[T]) GetDescendants 

func (d *TypedDAG[T]) GetDescendants(id string) (map[string]T, error)

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

func (*TypedDAG[T]) GetDescendantsGraph 

func (d *TypedDAG[T]) GetDescendantsGraph(id string) (*TypedDAG[T], string, error)

GetDescendantsGraph returns a new TypedDAG consisting of the vertex with 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.

func (*TypedDAG[T]) GetDescendantsGraphByDepth 

func (d *TypedDAG[T]) GetDescendantsGraphByDepth(rootID string, maxDepth int) (*TypedDAG[T], string, error)

GetDescendantsGraphByDepth returns a new TypedDAG consisting of the vertex with rootID and its descendants, limited to maxDepth levels. Depth starts at 0 for the root node, 1 for its direct children, and so on. Returns the new DAG, the id of the root node in the new graph, and an error.

func (*TypedDAG[T]) GetEdges 

func (d *TypedDAG[T]) GetEdges() EdgeList

GetEdges returns a list of all edges in the DAG. The returned edge list shares data with the DAG for better performance. Use GetEdgesWithOption(CopyData) for a safe, independent copy.

func (*TypedDAG[T]) GetEdgesWithOption 

func (d *TypedDAG[T]) GetEdgesWithOption(option CopyOption) EdgeList

GetEdgesWithOption returns a list of all edges in the DAG. The option parameter determines whether the data is shared or copied.

func (*TypedDAG[T]) GetLeaves 

func (d *TypedDAG[T]) GetLeaves() map[string]T

GetLeaves returns all vertices without children.

func (*TypedDAG[T]) GetOrder 

func (d *TypedDAG[T]) GetOrder() int

GetOrder returns the number of vertices in the graph.

func (*TypedDAG[T]) GetOrderedAncestors 

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

GetOrderedAncestors returns all ancestors of the vertex with 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.

func (*TypedDAG[T]) GetOrderedDescendants 

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

GetOrderedDescendants returns all descendants of the vertex with 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.

func (*TypedDAG[T]) GetParents 

func (d *TypedDAG[T]) GetParents(id string) (map[string]T, error)

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

func (*TypedDAG[T]) GetRoots 

func (d *TypedDAG[T]) GetRoots() map[string]T

GetRoots returns all vertices without parents.

func (*TypedDAG[T]) GetSize 

func (d *TypedDAG[T]) GetSize() int

GetSize returns the number of edges in the graph.

func (*TypedDAG[T]) GetVertex 

func (d *TypedDAG[T]) GetVertex(id string) (T, error)

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

func (*TypedDAG[T]) GetVertices 

func (d *TypedDAG[T]) GetVertices() map[string]T

GetVertices returns all vertices as a map of id to value.

func (*TypedDAG[T]) GetVerticesList 

func (d *TypedDAG[T]) GetVerticesList() NodeList[T]

GetVerticesList returns a list of all vertices in the DAG. The returned node list shares data with the DAG for better performance. Use GetVerticesListWithOption(CopyData) for a safe, independent copy.

func (*TypedDAG[T]) GetVerticesListWithOption 

func (d *TypedDAG[T]) GetVerticesListWithOption(option CopyOption) NodeList[T]

GetVerticesListWithOption returns a list of all vertices in the DAG. The option parameter determines whether the data is shared or copied.

func (*TypedDAG[T]) IsEdge 

func (d *TypedDAG[T]) 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 (*TypedDAG[T]) IsEmpty 

func (d *TypedDAG[T]) IsEmpty() bool

IsEmpty returns true if the graph has no vertices.

func (*TypedDAG[T]) IsLeaf 

func (d *TypedDAG[T]) 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 (*TypedDAG[T]) IsRoot 

func (d *TypedDAG[T]) 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 (*TypedDAG[T]) MarshalJSON 

func (d *TypedDAG[T]) MarshalJSON() ([]byte, error)

MarshalJSON returns the JSON encoding of the TypedDAG. This method automatically uses the GenericDAG implementation for optimal performance, eliminating the type conversion overhead of the old implementation.

func (*TypedDAG[T]) Options 

func (d *TypedDAG[T]) Options(options Options)

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

func (*TypedDAG[T]) ReduceTransitively 

func (d *TypedDAG[T]) ReduceTransitively()

ReduceTransitively transitively reduces the graph.

func (*TypedDAG[T]) ToDAG 

func (d *TypedDAG[T]) ToDAG() *GenericDAG[T]

ToDAG returns the underlying *GenericDAG for advanced usage. This is a convenience method for users who need direct access to the generic implementation.

func (*TypedDAG[T]) ToLegacyDAG 

func (d *TypedDAG[T]) ToLegacyDAG() *DAG

ToLegacyDAG returns a legacy *DAG for backward compatibility. This is a convenience method for migrating from the non-typed API. Deprecated: Use ToDAG instead for better performance.

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