graph

Documentation

Overview

Package graph contains a simple graph data structure. It contains a topological sorting function for ordering nodes in a DAG.

Index

• type Edge
  • func (e Edge) String() string
• type Graph
  • func New(nodes []Node, edges []Edge) *Graph
  • func (g *Graph) Edge(m, n Node) *Edge
  • func (g *Graph) IncomingNodesTo(n Node) []Node
  • func (g *Graph) Nodes() []Node
  • func (g *Graph) OutgoingNodesFrom(n Node) []Node
  • func (g *Graph) String() string
• type Node
  • func TopologicalSort(g *Graph) ([]Node, error)

Types

type Edge

type Edge struct {
	From, To Node
}

func (Edge) String

func (e Edge) String() string

type Graph

type Graph struct {
	// contains filtered or unexported fields
}

func New

func New(nodes []Node, edges []Edge) *Graph

func (*Graph) Edge

func (g *Graph) Edge(m, n Node) *Edge

Edge returns the edge from m to n if it exists, otherwise nil is returned.

func (*Graph) IncomingNodesTo

func (g *Graph) IncomingNodesTo(n Node) []Node

IncomingNodesTo returns all nodes that have an edge leading to n.

func (*Graph) Nodes

func (g *Graph) Nodes() []Node

Nodes returns all the nodes in the graph.

func (*Graph) OutgoingNodesFrom

func (g *Graph) OutgoingNodesFrom(n Node) []Node

OutgoingNodesFrom returns all nodes that have an edge leading from n.

func (*Graph) String

func (g *Graph) String() string

String generates a graphviz representation of the graph. You can write the output to a .dot file and generate a visualization with:

dot -Tsvg deps.dot

type Node

type Node interface {
	ID() string
}

func TopologicalSort

func TopologicalSort(g *Graph) ([]Node, error)

TopologicalSort sorts the nodes in the graph topologically using Kahn's algorithm. If the graph contains any cycles, then an error will be returned.