daggo

README

dag-go

A DAG, Directed acyclic graph implementation in golang.

https://en.wikipedia.org/wiki/Directed_acyclic_graph

Documentation

https://pkg.go.dev/github.com/open-trust/dag-go

Package

Import

import (
	daggo "github.com/open-trust/dag-go"
)

Example

package main

import (
	"encoding/json"
	"fmt"
	"time"

	otgo "github.com/open-trust/ot-go-lib"
)

type V string

func (v V) ID() string {
	return string(v)
}
func (v V) Attrs() daggo.Attrs {
	return daggo.Attrs{A(v)}
}

type A string

func (a A) ID() string {
	return string(a)
}

func main() {
  d := daggo.New()
  _ = d.AddEdge(V("a"), V("b"), 10)
  _ = d.AddEdge(V("a"), V("c"), 3)
  _ = d.AddEdge(V("a"), V("d"), 10)
  _ = d.AddEdge(V("a"), V("e"), 10)
  _ = d.AddEdge(V("b"), V("d"), 10)
  _ = d.AddEdge(V("c"), V("d"), 100)
  _ = d.AddEdge(V("c"), V("e"), 3)
  _ = d.AddEdge(V("d"), V("e"), 10)
  _ = d.AddEdge(V("x"), V("b"), 10)
  _ = d.AddEdge(V("d"), V("y"), 10)

  fmt.Println(d.Vertices()) // a, b, c, d, e, x, y
  fmt.Println(d.StartingVertices()) // x, a
  fmt.Println(d.EndingVertices()) // e, y
  fmt.Println(d.ToVertices(V("a"))) // b, c, e
  fmt.Println(d.FromVertices(V("e"))) // a, c, d
  fmt.Println(d.ReachDAG(V("a")))
  fmt.Println(d.CloseDAG(V("a"), V("e")))
  fmt.Println(d.ReduceDAG(V("a"), V("e")))
  fmt.Println(d.Reverse())
  fmt.Println(d.Shortest(V("a"), V("e"), false)) // a, e
  fmt.Println(d.Shortest(V("a"), V("e"), true)) // a, c, e
  fmt.Println(d.Longest(V("a"), V("e"), false)) // [a, c, d, e] or [a, b, d, e]
  fmt.Println(d.Longest(V("a"), V("e"), true)) // a, c, d, e

  fmt.Println(d.CloseDAG(V("a"), V("e")).
    Iterate(V("a"), nil, func(v daggo.Vertice, w int, acc daggo.Attrs) daggo.Attrs {
      return append(acc, v.Attrs()...)
    }))
}

Documentation

Index

• type DAG
  • func FromJSON(j *JSON) *DAG
  • func New() *DAG
  • func (d *DAG) AddEdge(start, end Vertice, weight int) error
  • func (d *DAG) Clone() *DAG
  • func (d *DAG) CloseDAG(start, end Vertice) *DAG
  • func (d *DAG) EndingVertices() Vertices
  • func (d *DAG) Equal(a *DAG) bool
  • func (d *DAG) FromVertices(v Vertice) Vertices
  • func (d *DAG) GetVertice(ty, id string) Vertice
  • func (d *DAG) Iterate(start Vertice, init []interface{}, fn IterateFn) []interface{}
  • func (d *DAG) JSON() *JSON
  • func (d *DAG) Len() int
  • func (d *DAG) Longest(start, end Vertice, withWeight bool) Vertices
  • func (d *DAG) Merge(a *DAG) error
  • func (d *DAG) ReachDAG(start Vertice) *DAG
  • func (d *DAG) ReduceDAG(start, end Vertice) *DAG
  • func (d *DAG) RemoveEdge(start, end Vertice)
  • func (d *DAG) Reverse() *DAG
  • func (d *DAG) Shortest(start, end Vertice, withWeight bool) Vertices
  • func (d *DAG) StartingVertices() Vertices
  • func (d *DAG) ToVertices(v Vertice) Vertices
  • func (d *DAG) Vertices(ty string) Vertices
• type IterateFn
• type JSON
• type Vertice
• type Vertices
  • func (s Vertices) Filter(fn func(v Vertice) bool) Vertices
  • func (s Vertices) IDs() []string
  • func (s Vertices) Len() int
  • func (s Vertices) Less(i, j int) bool
  • func (s Vertices) Sort() Vertices
  • func (s Vertices) Swap(i, j int)

Types

type DAG

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

DAG is a directed acyclic graph.

func FromJSON

func FromJSON(j *JSON) *DAG

FromJSON returns a DAG from JSON structured data, return nil if some data invalid.

func New

func New() *DAG

New returns a new DAG.

func (*DAG) AddEdge

func (d *DAG) AddEdge(start, end Vertice, weight int) error

AddEdge adds a connecting pairs of vertices into the DAG. the vertices should not be nil, not be equal, and not form a cyclic graph. the method can be called multiple times.

func (*DAG) Clone

func (d *DAG) Clone() *DAG

Clone returns a clone DAG.

func (*DAG) CloseDAG

func (d *DAG) CloseDAG(start, end Vertice) *DAG

CloseDAG returns a new transitive closure DAG with the most edges that represents the same reachability relation.

func (*DAG) EndingVertices

func (d *DAG) EndingVertices() Vertices

EndingVertices returns ending vertices in the DAG that don't connected to any other vertices.

func (*DAG) Equal

func (d *DAG) Equal(a *DAG) bool

Equal asserts that two DAG are equal.

func (*DAG) FromVertices

func (d *DAG) FromVertices(v Vertice) Vertices

FromVertices returns vertices in the DAG that connected to the vertice v.

func (*DAG) GetVertice

func (d *DAG) GetVertice(ty, id string) Vertice

GetVertice returns a vertice with type and id in the DAG, returns nil if not found.

func (*DAG) Iterate

func (d *DAG) Iterate(start Vertice, init []interface{}, fn IterateFn) []interface{}

Iterate iterate the DAG' vertices with the most reachability relation paths.

func (*DAG) JSON

func (d *DAG) JSON() *JSON

JSON ...

func (*DAG) Len

func (d *DAG) Len() int

Len returns vertices count in the DAG.

func (*DAG) Longest

func (d *DAG) Longest(start, end Vertice, withWeight bool) Vertices

Longest find a longest paths.

func (*DAG) Merge

func (d *DAG) Merge(a *DAG) error

Merge merge two DAG into one, return error if cyclic graph will come into being

func (*DAG) ReachDAG

func (d *DAG) ReachDAG(start Vertice) *DAG

ReachDAG returns a new sub DAG with the most edges that starting vertice may reach to.

func (*DAG) ReduceDAG

func (d *DAG) ReduceDAG(start, end Vertice) *DAG

ReduceDAG returns a new transitive reduction DAG with the fewest edges that represents the same reachability relation.

func (*DAG) RemoveEdge

func (d *DAG) RemoveEdge(start, end Vertice)

RemoveEdge remove the direct connecting in the vertices pair.

func (*DAG) Reverse

func (d *DAG) Reverse() *DAG

Reverse returns a new DAG that all edges relation reversed.

func (*DAG) Shortest

func (d *DAG) Shortest(start, end Vertice, withWeight bool) Vertices

Shortest find a shortest paths.

func (*DAG) StartingVertices

func (d *DAG) StartingVertices() Vertices

StartingVertices returns starting vertices in the DAG that have no other vertices connected to them.

func (*DAG) ToVertices

func (d *DAG) ToVertices(v Vertice) Vertices

ToVertices returns vertices in the DAG that the vertice v connected to them.

func (*DAG) Vertices

func (d *DAG) Vertices(ty string) Vertices

Vertices returns a type of vertices in the DAG, returns all if type is empty.

type IterateFn

type IterateFn func(cur Vertice, weight int, acc []interface{}) []interface{}

IterateFn ...

type JSON

type JSON struct {
	Vertices []Vertice                 `json:"vertices"`
	Edges    map[string]map[string]int `json:"edges"`
}

JSON ...

type Vertice

type Vertice interface {
	ID() string
	Type() string
}

Vertice is a vertice formed DAG.

type Vertices

type Vertices []Vertice

Vertices is a slice of vertices.

func (Vertices) Filter

func (s Vertices) Filter(fn func(v Vertice) bool) Vertices

Filter ...

func (Vertices) IDs

func (s Vertices) IDs() []string

IDs returns a slice of vertices' IDs

func (Vertices) Len

func (s Vertices) Len() int

func (Vertices) Less

func (s Vertices) Less(i, j int) bool

func (Vertices) Sort

func (s Vertices) Sort() Vertices

Sort returns a slice of vertices in increasing order by vertice ID.

func (Vertices) Swap

func (s Vertices) Swap(i, j int)