dgorder

package
Version: v0.0.0-...-e504d38 Latest Latest
Warning

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

Go to latest
Published: Aug 8, 2021 License: MIT Imports: 2 Imported by: 0

README

dgorder - dependency graph order

GoDoc

Install:

go get github.com/muir/libschema

Dependency graph order

Dgorder provides a simple dependency graph ordering function.

The big design decision with such a library is to choose an API. The API for dgorder is an array of nodes that express dependencies on other nodes based on the node index position in the array.

While this API is never going to match the caller's data structures, it should be easy to transform data to this format.

import "github.com/muir/libschema/dgorder"

nodes := make([]dgorder.Node, len(myThings))
for i, thing := range myThings {
	for _, blockedThing := range myThings.BlockedByMything {
		nodes[i].Blocking = append(nodes[i].Blocking, getIndex(blockedThing))
	}
	for _, blockingThing := range myThings.ThingsBlockingMyThing {
		j := getIndex(blockingThing)
		nodes[j].Blocking = append(nodes[j].Blocking, i)
	}
}
ordering, err := dgorder.Order(nodes, func(i int) string {
	return descriptionOfMyThingByIndex(i)
})
if err != nil {
	panic("Dependency cycle! " + err.Error())
}
myThingsInOrder := make([]MyThingType, len(myThings))
for i, e := range ordering {
	myThingsInOrder[i] = myThings[e]
}

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func Order

func Order(nodes []Node, describe func(int) string) ([]int, error)

Order returns a list of the indexes of the nodes in the order in which they can be acted upon so that no blocked node comes before a node that blocks it. Additionally, to the extent possible nodes will be returned in-order. If this is not possible, an error will be returned and the describe function will be used to help generate the error so that it is human-readable.

Types

type IntHeap

type IntHeap []int

The following is lifted directly from the examples provided with container/heap

func (IntHeap) Len

func (h IntHeap) Len() int

func (IntHeap) Less

func (h IntHeap) Less(i, j int) bool

func (*IntHeap) Pop

func (h *IntHeap) Pop() interface{}

func (*IntHeap) Push

func (h *IntHeap) Push(x interface{})

func (IntHeap) Swap

func (h IntHeap) Swap(i, j int)

type Node

type Node struct {
	Blocking []int // values are the indexes of nodes in the list of nodes
	// contains filtered or unexported fields
}

Source Files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
t or T : Toggle theme light dark auto
y or Y : Canonical URL