topsort

README

topsort

Topological Sorting for Golang

Topological sorting algorithms are especially useful for dependency calculation, and so this particular implementation is mainly intended for this purpose. As a result, the direction of edges and the order of the results may seem reversed compared to other implementations of topological sorting.

For example, if:

• A depends on B
• B depends on C

The graph is represented as:

A -> B -> C

Where -> represents a directed edge from one node to another.

The topological ordering of dependencies results in:

[C, B, A]

The code for this example would look something like:

// Initialize the graph.
graph := topsort.NewGraph()
graph.AddNode("A")
graph.AddNode("B")
graph.AddNode("C")

// Add edges.
graph.AddEdge("A", "B")
graph.AddEdge("B", "C")

// Topologically sort node A.
graph.TopSort("A")  // => [C, B, A]

Documentation

Index

• type Graph
  • func NewGraph() *Graph
  • func (g *Graph) AddEdge(from string, to string) error
  • func (g *Graph) AddNode(name string)
  • func (g *Graph) ContainsNode(name string) bool
  • func (g *Graph) GetOrAddNode(name string) node
  • func (g *Graph) TopSort(name string) ([]string, error)

Types

type Graph

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

func NewGraph

func NewGraph() *Graph

func (*Graph) AddEdge

func (g *Graph) AddEdge(from string, to string) error

func (*Graph) AddNode

func (g *Graph) AddNode(name string)

func (*Graph) ContainsNode

func (g *Graph) ContainsNode(name string) bool

func (*Graph) GetOrAddNode

func (g *Graph) GetOrAddNode(name string) node

func (*Graph) TopSort

func (g *Graph) TopSort(name string) ([]string, error)