gnetdag

Documentation

Overview

Package gnetdag (Gordian NETwork Directed Acyclic Graph) contains types for determining directional flow of network traffic.

Types in this package are focused on int values, so that they remain decoupled from any concrete implementations of validators, network addresses, and so on. Callers may simply use the int values as indices into slices of the actual type needing the directed graph.

This package currently contains the FixedTree type, which effectively maps indices in a slice such that every non-root node contains a fixed number of children. This package will be expanded with more types as deemed necessary.

Index

• type FixedTree
  • func (t FixedTree) FirstChild(entryIdx int) int
  • func (t FixedTree) Layer(entryIdx int) int
  • func (t FixedTree) Parent(entryIdx int) int

Types

type FixedTree

type FixedTree struct {
	// The width of the layer at index 1.
	BranchFactor int
}

FixedTree represents a tree where each non-leaf node has a fixed number of children. With BranchFactor=3, the entries are arranged in layers like:

0 (L0)
1 2 3 (L1)
4 5 6 7 8 9 10 11 12 (L2)

The entryIdx parameter used in methods on FixedTree are intended to be used as indices into an existing ordered slice that is to be treated as a tree.

Methods on FixedTree use unchecked math, so invalid values, such as negative entry indices or branch factors, or branch factor so large that bf^2 overflows an int, result in undefined behavior.

func (FixedTree) FirstChild

func (t FixedTree) FirstChild(entryIdx int) int

FirstChild returns the entry index of the first child of the given entry index. Every parent contains t.BranchFactor children, but the FixedTree type does not track number of entries, so it is the caller's responsibility to confirm that there are at least t.BranchFactor children available.

func (FixedTree) Layer

func (t FixedTree) Layer(entryIdx int) int

Layer returns the layer that would contain the given entry index.

func (FixedTree) Parent

func (t FixedTree) Parent(entryIdx int) int

Parent returns the "parent" index of the given entry index. It returns -1 for entryIdx = 0.