graphutil

Documentation

Overview

Package graphutil contains utility functions for manipulating graphs.

Index

• func Label[T any](t *Tree[T]) T
• func StronglyConnectedComponents[T comparable](nodes []T, successors func(T) []T) (sccs [][]T)
• type Tree
  • func NewTree[T any](rootLabel T) *Tree[T]
  • func (t *Tree[T]) AddChild(label T) *Tree[T]
  • func (t *Tree[T]) Ancestors(n int) []*Tree[T]

Functions

func Label

func Label[T any](t *Tree[T]) T

Label returns the label of its argument

func StronglyConnectedComponents

func StronglyConnectedComponents[T comparable](nodes []T, successors func(T) []T) (sccs [][]T)

StronglyConnectedComponents is an implementation of Tarjan's strongly connected component (SCC) algorithm for generic nodes T. Successors returns a slice containing the targets of directed edges out from the given node. sccs is a slice of slices containing the nodes in each SCC. The order within the SCC is arbitrary. The order of SCCs is toposorted so that successors appear first; i.e. if the graph is a tree then in order from leaves towards the root. For summary-based bottom-up algorithms, the result is in the desired order to minimize recomputation.

Types

type Tree

type Tree[T any] struct {
	Parent   *Tree[T]
	Children []*Tree[T]
	Label    T
}

Tree is a simple generic implementation of a tree

func NewTree

func NewTree[T any](rootLabel T) *Tree[T]

NewTree returns a new tree with the labels of the type provided

func (*Tree[T]) AddChild

func (t *Tree[T]) AddChild(label T) *Tree[T]

func (*Tree[T]) Ancestors

func (t *Tree[T]) Ancestors(n int) []*Tree[T]

Ancestors returns the chain of the n closest ancestors of t. If n < 0, then it returns the chain up to the root of the tree