graph

Documentation

Index

• Variables
• type Graph
  • func New() *Graph
  • func (g *Graph) AddEdge(node *Node, edges ...*Node)
  • func (g *Graph) AddNode(nodes ...*Node)
  • func (g *Graph) AsDot(name string, w io.Writer)
  • func (g *Graph) GetNode(name string) (*Node, bool)
  • func (g *Graph) Reversed() *Graph
  • func (g *Graph) Sort() ([]*Node, error)
• type Node
  • func NewNode(name string) *Node

Variables

var ErrCircularDependency = errors.New("Circular dependency found in graph")

ErrCircularDependency is returned when the graph cannot be topologically sorted because of circular dependencies

Types

type Graph

type Graph struct {
	Nodes map[string]*Node
}

Graph represents a DAG graph

func New

func New() *Graph

New creates a new DAG graph

func (*Graph) AddEdge

func (g *Graph) AddEdge(node *Node, edges ...*Node)

AddEdge connects a node with other nodes in the graph

func (*Graph) AddNode

func (g *Graph) AddNode(nodes ...*Node)

AddNode adds nodes to the graph

func (*Graph) AsDot

func (g *Graph) AsDot(name string, w io.Writer)

AsDot generates a DOT representation for the graph https://en.wikipedia.org/wiki/DOT_(graph_description_language)

func (*Graph) GetNode

func (g *Graph) GetNode(name string) (*Node, bool)

GetNode retrieves the node from the graph with the given name

func (*Graph) Reversed

func (g *Graph) Reversed() *Graph

Reversed creates the reversed representation of the graph

func (*Graph) Sort

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

Sort performs a topological sort of the graph https://en.wikipedia.org/wiki/Topological_sorting

If the graph can be topologically sorted the result will contain the sorted nodes.

If the graph cannot be sorted in case of circular dependencies, then the result will contain the remaining nodes from the graph, which are the ones causing the circular dependency.

type Node

type Node struct {
	// Name of the node
	Name string

	// Edges to other nodes in the graph
	Edges []*Node
}

Node represents a single node in the graph

func NewNode

func NewNode(name string) *Node

NewNode creates a new node with the given name