tsort

README

A golang implementation of topographical sort using Tarjan's algorithm.

There is also a command line utility to perform topographical sorting of input from stdin.

Documentation

Overview

Example

package main

import (
	"bufio"
	"fmt"
	"os"

	"github.com/danos/utils/tsort"
)

func main() {
	var e error

	f := os.Stdin
	n := os.Args[0]
	if len(os.Args) > 1 {
		fname := os.Args[1]
		f, e = os.Open(fname)
		if e != nil {
			fmt.Fprintf(os.Stderr, "%s: %s\n", n, e)
			os.Exit(1)
		}
	}
	g := tsort.New()

	scanner := bufio.NewScanner(bufio.NewReader(f))
	scanner.Split(bufio.ScanWords)

	var v, w string
	elems := make([]string, 0)

	for scanner.Scan() {
		t := scanner.Text()
		elems = append(elems, t)
	}
	if len(elems)%2 != 0 {
		fmt.Fprintf(os.Stderr, "%s: odd data count\n", n)
		os.Exit(1)
	}
	for i := 0; i < len(elems); i++ {
		v = elems[i]
		i += 1
		w = elems[i]
		g.AddEdge(v, w)
	}
	out, err := g.Sort()
	if err != nil {
		fmt.Fprintln(os.Stderr, err)
		os.Exit(1)
	}
	for _, s := range out {
		fmt.Println(s)
	}
}

Index

• type Graph
  • func New() *Graph
  • func (g *Graph) AddEdge(v, w string)
  • func (g *Graph) AddVertex(v string) *vertex
  • func (g *Graph) Dot() string
  • func (g *Graph) HasEdge(v, w string) bool
  • func (g *Graph) Sort() ([]string, error)
  • func (g *Graph) SortDot() string
  • func (g *Graph) String() string

Examples

• Package

Types

type Graph

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

func New

func New() *Graph

func (*Graph) AddEdge

func (g *Graph) AddEdge(v, w string)

func (*Graph) AddVertex

func (g *Graph) AddVertex(v string) *vertex

func (*Graph) Dot

func (g *Graph) Dot() string

func (*Graph) HasEdge

func (g *Graph) HasEdge(v, w string) bool

func (*Graph) Sort

func (g *Graph) Sort() ([]string, error)

func (*Graph) SortDot

func (g *Graph) SortDot() string

func (*Graph) String

func (g *Graph) String() string