topsort

README

go-topsort

Topological Sorting for Golang

It's fork of stevenle/topsort.

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
• B depends on D
• E depends on D

The graph is represented as:

INSTALLATION

go get -u github.com/moisespsena-go/topsort/topsort

CLI

$GOPATH/bin/topsort -h

# or

export PATH=$GOPATH/bin:$PATH
topsort -h

Output:

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.

Home Page: https://github.com/moisespsena-go/topsort

EXAMPLES
--------

$ echo "A-B,B-C,B-D,E-D,F" | topsort
$ echo "A-B:B-C:B-D:E-D,F" | topsort -p :
$ topsort pairs.txt

Ordered input files including STDIN (file name is '-')
$ echo "A-B,B-C,B-D,E-D,F" | topsort pairs1.txt pairs2.txt - pairs3.txt

Usage:
  topsort [flags] [file...]

Flags:
  -e, --edge-sep string   Set the edge separator (default "-")
  -h, --help              help for topsort
  -p, --pair-sep string   Set the pairs separator (default ",")
  -t, --toggle            Help message for toggle
  -T, --top-sort          Use Topological node classifier, otherwise, Depth-first classifier.

How To

The code for previous example would look something like:

import fmt
// Initialize the graph
graph := topsort.NewGraph()

// Add nodes
graph.AddNode("A", "B", "C", "D", "E")

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

// Topologically sort only node A in dependency order and your edges, but not sort D and E.
results, err := graph.TopSort("A")
if err != nil {
    panic(err)
}
fmt.Println(results) // => [C D B A]

// in depth-first order
results, err = graph.DepthFirst("A")
if err != nil {
    panic(err)
}
fmt.Println(results) // => [A B D C]

Sort all nodes:

// Topologically sort all nodes in the graph
results, err := graph.TopSort()
if err != nil {
    panic(err)
}
fmt.Println(results) // => [B C D B A E]

// all nodes in depth-first order
results, err = graph.DepthFirst()
if err != nil {
    panic(err)
}
fmt.Println(results) // => [E A B D C]

See Examples Test for more examples.

Documentation

Index

• Constants
• func Reverse(a []string)
• type Graph
  • func NewGraph() *Graph
  • func (g *Graph) AddEdge(from string, to string) error
  • func (g *Graph) AddEdgeTuple(fromTo ...[2]string) (err error)
  • func (g *Graph) AddNode(names ...string)
  • func (g *Graph) ContainsNode(name string) bool
  • func (g *Graph) DOTString() string
  • func (g *Graph) DepthFirst(names ...string) ([]string, error)
  • func (g *Graph) ParseLines(edgeSep, pairSep string, lineReader func() (string, error)) (err error)
  • func (g *Graph) ParseString(data, edgeSep, pairSep string)
  • func (g *Graph) TopSort(names ...string) ([]string, error)

Examples

• Graph.AddEdgeTuple
• Graph.DOTString
• Graph.DepthFirst
• Graph.ParseLines
• Graph.ParseString
• Graph.TopSort

Constants

const EDGE_SEP = ">"

const PAIR_SEP = ","

Functions

func Reverse

func Reverse(a []string)

Reverse Reverse the slice items.

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) AddEdgeTuple

func (g *Graph) AddEdgeTuple(fromTo ...[2]string) (err error)

Example

fmt.Println(`
import fmt
// Initialize the graph
graph := topsort.NewGraph()

// Add nodes
graph.AddNode("A", "B")

// Add edges: A -> B and B -> C
graph.AddEdgeEdgeTuple([2]string{"A", "B"}, [2]string{"B", "C"})
	`)

func (*Graph) AddNode

func (g *Graph) AddNode(names ...string)

func (*Graph) ContainsNode

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

func (*Graph) DOTString

func (g *Graph) DOTString() string

DOTString Generate GraphViz DOT string

Example

data := `// digraph G {
//  "A" -> "B";
//  "B" -> "C";
//  "B" -> "D";
//  "C"
//  "D"
//  "E" -> "D";
// }`
fmt.Println(`
import fmt
// Initialize the graph
graph := topsort.NewGraph()
graph := NewGraph()
graph.ParseString("A>B,E,B>C,B>D,E>D", "", "")
println(graph.DOTString())
` + data)

func (*Graph) DepthFirst

func (g *Graph) DepthFirst(names ...string) ([]string, error)

DepthFirst Depth-first classifier. The order is defined by the default ordering of the key in the edges map and edges of edges. If `names` is empty, classify all nodes in the graph.

Example

fmt.Println(`
import fmt
// Initialize the graph
graph := topsort.NewGraph()

// Add nodes
graph.AddNode("A", "B", "C", "D", "E")

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

// in depth-first order
results, err = graph.DepthFirst("A")
if err != nil {
    panic(err)
}
fmt.Println(results) // => [A B D C]

// all nodes in depth-first order
results, err = graph.DepthFirst()
if err != nil {
    panic(err)
}
fmt.Println(results) // => [E A B D C]
	`)

func (*Graph) ParseLines

func (g *Graph) ParseLines(edgeSep, pairSep string, lineReader func() (string, error)) (err error)

ParseLines Parse nodes and egdes from lines

Example

fmt.Println(`
import fmt
// Initialize the graph
graph := topsort.NewGraph()

lines := []string{"A>B", "B>C,C>D", ""}
i := -1
lineReader := func() string {
	i++
	return lines[i]
}

// default separators
graph.ParseLines("", "", lineReader)

// custom separators
lines := []string{"A-B", "B-C|C-D", ""}
i = -1
graph.ParseLines("-", "|", lineReader)
	`)

func (*Graph) ParseString

func (g *Graph) ParseString(data, edgeSep, pairSep string)

ParseString Parse nodes and egdes from string

Example

fmt.Println(`
import fmt
// Initialize the graph
graph := topsort.NewGraph()

// default separators
graph.ParseString("A>B,B>C", "", "")
// custom separators
graph.ParseString("A-B|B-C", "-", "|")
	`)

func (*Graph) TopSort

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

TopSort Topological node classifier. The order is defined by the default ordering of the key in the edges map and edges of edges. If `names` is empty, sort all nodes in the graph.

Example

fmt.Println(`
import fmt
// Initialize the graph
graph := topsort.NewGraph()

// Add nodes
graph.AddNode("A", "B", "C", "D", "E")

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

// Topologically sort only node A in dependency order and your edges, but not sort D and E.
results, err := graph.TopSort("A")
if err != nil {
    panic(err)
}
fmt.Println(results) // => [C D B A]

// Topologically sort all nodes in the graph
results, err := graph.TopSort()
if err != nil {
    panic(err)
}
fmt.Println(results) // => [B C D B A E]
	`)