dag

Documentation

Index

• type Graph
  • func (g *Graph) MakeEdge(from, to Node) error
  • func (g *Graph) MakeEdgeWeight(from, to Node, weight int) error
  • func (g *Graph) MakeNode(value interface{}) Node
  • func (g *Graph) TopologicalSort() []Node
• type Node

Types

type Graph

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

Graph is an adjacency slice representation of a directed graph.

func (*Graph) MakeEdge

func (g *Graph) MakeEdge(from, to Node) error

MakeEdge calls MakeEdgeWeight with a weight of 0 and returns an error if either of the nodes do not belong in the graph. Calling MakeEdge multiple times on the same nodes will not create multiple edges.

func (*Graph) MakeEdgeWeight

func (g *Graph) MakeEdgeWeight(from, to Node, weight int) error

MakeEdgeWeight creates an edge in the graph with a corresponding weight. It returns an error if either of the nodes do not belong in the graph.

Calling MakeEdgeWeight multiple times on the same nodes will not create multiple edges; this function will update the weight on the node to the new value.

func (*Graph) MakeNode

func (g *Graph) MakeNode(value interface{}) Node

MakeNode creates a node, adds it to the graph and returns the new node.

func (*Graph) TopologicalSort

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

TopologicalSort topoligically sorts a directed acyclic graph. If the graph is cyclic, the sort order will change based on which node the sort starts on.

The StronglyConnectedComponents function can be used to determine if a graph has cycles.

type Node

type Node struct {

	// Value can be used to store information on the caller side.
	// Its use is optional. See the Topological Sort example for
	// a reason on why to use this pointer.
	// The reason it is a pointer is so that graph function calls
	// can test for equality on Nodes. The pointer wont change,
	// the value it points to will. If the pointer is explicitly changed,
	// graph functions that use Nodes will cease to work.
	Value *interface{}
	// contains filtered or unexported fields
}

Node connects to a backing node on the graph. It can safely be used in maps.