graphlib

README

graphlib

A Topological sort lib.

Sorting and pruning of DAG graphs.

Ideas borrowed from python graphlib

How to install

go get -u github.com/aio-arch/graphlib

How to use

    import "github.com/aio-arch/graphlib"

    // New A graph

	// for string type
	g1 := graphlib.NewGraph[string]()

	// for int type
	g2 := graphlib.NewGraph[int]()

	// for add node and add edge
	g1.AddNode("A1")
	g1.AddNode("B2")
	g1.AddEdge("A1", "B2") // edge: A1 -> B2

	// for add mulit edge,add node inline
	g2.Add(10, 1, 9)    // edge: 1 -> 10 and 9 -> 10
	g2.Add(100, 10, 90) // edge: 10 -> 100 and 90 -> 100

	// topological order
	topo, err := graphlib.TopologicalOrder(g1)
	if err != nil {
		fmt.Println(err.Error())
	}
	fmt.Printf("Topological Order:%v\n", topo)

	// topological prune
	g3, err := graphlib.TopologicalPrune(g2, []int{10, 90})
	if err != nil {
		fmt.Println(err.Error())
	}
	_ = g3

Documentation

Index

• func TopologicalOrder[V comparable](digraph *Graph[V]) ([]V, error)
• type ErrCycle
  • func (e *ErrCycle[V]) Error() string
• type ErrUnknownNode
  • func (e *ErrUnknownNode[V]) Error() string
• type Graph
  • func NewGraph[V comparable]() *Graph[V]
  • func TopologicalPrune[V comparable](digraph *Graph[V], nodes []V) (*Graph[V], error)
  • func (g *Graph[V]) Add(node V, predecessors ...V)
  • func (g *Graph[V]) AddEdge(from, to V)
  • func (g *Graph[V]) AddNode(node V) *nodeInfo[V]
  • func (g *Graph[V]) IsAcyclic() ([]V, bool)
  • func (g *Graph[V]) NodeSortSet() []V

Functions

func TopologicalOrder

func TopologicalOrder[V comparable](digraph *Graph[V]) ([]V, error)

Types

type ErrCycle

type ErrCycle[V comparable] struct {
	// contains filtered or unexported fields
}

func (*ErrCycle[V]) Error

func (e *ErrCycle[V]) Error() string

type ErrUnknownNode

type ErrUnknownNode[V comparable] struct {
	// contains filtered or unexported fields
}

func (*ErrUnknownNode[V]) Error

func (e *ErrUnknownNode[V]) Error() string

type Graph

type Graph[V comparable] struct {
	// contains filtered or unexported fields
}

func NewGraph

func NewGraph[V comparable]() *Graph[V]

func TopologicalPrune

func TopologicalPrune[V comparable](digraph *Graph[V], nodes []V) (*Graph[V], error)

func (*Graph[V]) Add

func (g *Graph[V]) Add(node V, predecessors ...V)

func (*Graph[V]) AddEdge

func (g *Graph[V]) AddEdge(from, to V)

func (*Graph[V]) AddNode

func (g *Graph[V]) AddNode(node V) *nodeInfo[V]

func (*Graph[V]) IsAcyclic

func (g *Graph[V]) IsAcyclic() ([]V, bool)

IsAcyclic checks if the graph is acyclic. If not, return the first detected cycle. it using https://github.com/python/cpython/blob/3.14/Lib/graphlib.py#L202 _find_cycle method

func (*Graph[V]) NodeSortSet

func (g *Graph[V]) NodeSortSet() []V