Topological Sort for arbitrary slices

Introduction

The topo package implements a topological sort algorithm to facilitate dependency resolution between elements of arbitrary data types. The topo/graph package provides a directed graph representation for arbitrary data types to perform the actual sort process by describing elements as nodes / vertices and dependencies as links / arcs between these elements.

Installation and usage

The import path for the package is github.com/fako1024/topo. To install it, run:

go get github.com/fako1024/topo

API summary

The API of the topo package is fairly straight-forward. The following generics-based types / methods are exposed:

// Dependency represents a dependency between one Type and another
type Dependency[T comparable] struct {
    Child  T
    Parent T
}

// Dependencies represents a list of dependencies
type Dependencies[T comparable] []Dependency[T]

// String tries to stringify a dependency. If the type of the dependency fulfills
// the Stringer interface, it will use its String() method, otherwise it will try
// to format the variable otherwise
func (d Dependency[T]) String() string

// Sort performs a topological sort on a slice and constructs a directed graph (using the
// dependency constraints) and finally converts back the resulting object list to the
// original slice (sort in place)
func Sort[T comparable](data graph.Objects[T], deps Dependencies[T]) (err error)

In order to perform a dependency resolution, first a slice or array containing all elements to be sorted and a list of all dependencies have to be created. Afterwards, the actual Sort() call can be performed, causing the original slice to be sorted in-place so as to satisfy all dependencies. Note: Sort() is a stable sort algorithm, hence the actual order of elements in the output will be deterministic. A detailed, yet simple example can be found below.

License

The topo and topo/graph packages are licensed under the Apache License 2.0. Please see the LICENSE file for details.

Example

package main

import (
    "fmt"
    "os"
    "github.com/fako1024/topo"
)

// List of all simple strings (to be sorted)
var stringsToSort = []string{
    "A", "B", "C", "D", "E", "F", "G", "H",
}

// List of dependencies
var stringDependencies = []topo.Dependency[string]{
    {Child: "B", Parent: "A"},
    {Child: "B", Parent: "C"},
    {Child: "B", Parent: "D"},
    {Child: "A", Parent: "E"},
    {Child: "D", Parent: "C"},
}

func main() {

    // Perform topological sort
    if err := topo.Sort(stringsToSort, stringDependencies); err != nil {
        fmt.Printf("Error performing topological sort on slice of strings: %s\n", err)
        os.Exit(1)
    }

    // Print resulting Slice in order
    fmt.Println("Sorted list of strings:", stringsToSort)
    fmt.Println("The following dependencies were taken into account:")
    for _, dep := range stringDependencies {
        fmt.Println(dep)
    }
}

This example will generate the following output:

Sorted list of strings: [E A C D B F G H]
The following dependencies were taken into account:
B depends upon A
B depends upon C
B depends upon D
A depends upon E
D depends upon C

Additional examples can be found in the *_example_test.go files.