topological

Documentation

Index

• type Node
  • func NodesFromEdges(edges [][]int) []*Node
  • func TopoOrder(g []*Node) []*Node

Types

type Node

type Node struct {
	ID int
	//outbound edges
	Outbound []*Node
	Indegree int
}

Node is a simple node for a digraph

func NodesFromEdges

func NodesFromEdges(edges [][]int) []*Node

NodesFromEdges make a Node based adjacency list from edges calculating the heads' indegree.

func TopoOrder

func TopoOrder(g []*Node) []*Node

TopoOrder takes an adjacency list and returns nodes in topological order iterate over node list, finding all with indegree zero.

• calculate the indegree while building the adjacency list from the edge list, every time you connect a tail, to a head, increment the indegree of the head.

add them to a stack. While the stack is not empty pop a node of the stack and conceptually remove it from the graph. for every outbound node, decrement that node's indegree and if that node then has indegree zero, add it to the stack append the node to order.