graph

package
v0.5.0 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Nov 25, 2016 License: BSD-2-Clause Imports: 5 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

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

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

Functions

This section is empty.

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 added in v0.4.0

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

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL