graph

Documentation

Overview

Package graph contains type definitions for graphs and algorithms that operate on them.

This package is used in service maps logic.

Index

• Variables
• func EdgeSetsEqual(lhs, rhs map[Edge]bool) bool
• type Edge
• type Graph
  • func NewGraph(edges ...Edge) *Graph
  • func (graph *Graph) NumNodes() int
• type GraphNode
  • func (n *GraphNode) GetLabel() int64
  • func (n *GraphNode) InNode(i int) Node
  • func (n *GraphNode) NumInNodes() int
  • func (n *GraphNode) NumOutNodes() int
  • func (n *GraphNode) OutNode(i int) Node
• type Node
  • func DepthFirstTraverse(root Node, t TraversalType) []Node
  • func SortBasic(graph *Graph) ([]Node, error)
  • func SortTree(root *TreeNode) []Node
• type TraversalType
• type Tree
  • func NewTreeFromGraph(graph *Graph) (*Tree, bool)
• type TreeNode
  • func (n *TreeNode) GetLabel() int64
  • func (n *TreeNode) InNode(i int) Node
  • func (n *TreeNode) NumInNodes() int
  • func (n *TreeNode) NumOutNodes() int
  • func (n *TreeNode) OutNode(i int) Node

Variables

var (
	ErrGraphNotSortable = fmt.Errorf("the provided graph is not topologically sortable because it contains a cycle")
)

Functions

func EdgeSetsEqual

func EdgeSetsEqual(lhs, rhs map[Edge]bool) bool

EdgeSetsEqual returns whether the provided sets of edges have the same elements.

Types

type Edge

type Edge struct {
	FromLabel int64
	ToLabel   int64
}

type Graph

type Graph struct {
	LabelToNode map[int64]*GraphNode
}

func NewGraph

func NewGraph(edges ...Edge) *Graph

func (*Graph) NumNodes

func (graph *Graph) NumNodes() int

type GraphNode

type GraphNode struct {
	Label    int64
	InNodes  []*GraphNode
	OutNodes []*GraphNode
}

func (*GraphNode) GetLabel

func (n *GraphNode) GetLabel() int64

func (*GraphNode) InNode

func (n *GraphNode) InNode(i int) Node

func (*GraphNode) NumInNodes

func (n *GraphNode) NumInNodes() int

func (*GraphNode) NumOutNodes

func (n *GraphNode) NumOutNodes() int

func (*GraphNode) OutNode

func (n *GraphNode) OutNode(i int) Node

type Node

type Node interface {
	GetLabel() int64
	NumInNodes() int
	InNode(i int) Node
	NumOutNodes() int
	OutNode(i int) Node
}

func DepthFirstTraverse

func DepthFirstTraverse(root Node, t TraversalType) []Node

DepthFirstTraverse performs a depth first traversal with the given root as the starting point.

func SortBasic

func SortBasic(graph *Graph) ([]Node, error)

func SortTree

func SortTree(root *TreeNode) []Node

SortTree topologically sorts the provided tree.

The algorithm minimizes the total length of the edges.

type TraversalType

type TraversalType bool

const (
	PreOrder  TraversalType = true
	PostOrder TraversalType = false
)

type Tree

type Tree struct {
	Root        *TreeNode
	LabelToNode map[int64]*TreeNode
}

func NewTreeFromGraph

func NewTreeFromGraph(graph *Graph) (*Tree, bool)

NewTreeFromGraph attempts to convert the provided graph to a tree.

The second return value is true if and only if this conversion is possible.

type TreeNode

type TreeNode struct {
	Label    int64
	Parent   *TreeNode
	Children []*TreeNode
}

func (*TreeNode) GetLabel

func (n *TreeNode) GetLabel() int64

func (*TreeNode) InNode

func (n *TreeNode) InNode(i int) Node

func (*TreeNode) NumInNodes

func (n *TreeNode) NumInNodes() int

func (*TreeNode) NumOutNodes

func (n *TreeNode) NumOutNodes() int

func (*TreeNode) OutNode

func (n *TreeNode) OutNode(i int) Node