toposort

README

go-toposort

deterministic topological sort implementation for golang

Example

package main

import (
	"fmt"

	toposort "github.com/philopon/go-toposort"
)

func main() {
	graph := toposort.NewGraph(8)
	graph.AddNodes("2", "3", "5", "7", "8", "9", "10", "11")

	graph.AddEdge("7", "8")
	graph.AddEdge("7", "11")

	graph.AddEdge("5", "11")

	graph.AddEdge("3", "8")
	graph.AddEdge("3", "10")

	graph.AddEdge("11", "2")
	graph.AddEdge("11", "9")
	graph.AddEdge("11", "10")

	graph.AddEdge("8", "9")

	result, ok := graph.Toposort()
	if !ok {
		panic("cycle detected")
	}

	fmt.Println(result)
}

[3 5 7 8 11 2 9 10]

License

MIT

Documentation

Index

• type Graph
  • func NewGraph(cap int) *Graph
  • func (g *Graph) AddEdge(from, to string) bool
  • func (g *Graph) AddNode(name string) bool
  • func (g *Graph) AddNodes(names ...string) bool
  • func (g *Graph) RemoveEdge(from, to string) bool
  • func (g *Graph) Toposort() ([]string, bool)

Types

type Graph

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

func NewGraph

func NewGraph(cap int) *Graph

func (*Graph) AddEdge

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

func (*Graph) AddNode

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

func (*Graph) AddNodes

func (g *Graph) AddNodes(names ...string) bool

func (*Graph) RemoveEdge

func (g *Graph) RemoveEdge(from, to string) bool

func (*Graph) Toposort

func (g *Graph) Toposort() ([]string, bool)