groph

README

groph

import "git.fractalqb.de/fractalqb/groph"

---

A pure Go library of graphs and their algorithms.

The library is currently rewritten for Go generics.

Graph implementations:

• Adjacency matrix: Uses a continuous region of memory, i.e. a slice
• Adjacency list: Uses a slice of slices
• Edgelist: A slice of {u, v, w}
• Euclidean: Computes the euclidean distance as weight for each edge where vertices have to implement the Distancer interface
• Forest: A compact representation for trees and forests

Algorithms

Computing Paths

• Floyd Warshall for shortest paths
• Dijkstra's Algorithm for shortest paths
• A greedy implementation for the TSP
• A 2-opt based implementation for the TSP
• A* algorithm for undirected graphs

Documentation

Overview

Package groph is a pure Go library for graph data and algorithms.

It provides an abstract graph model through some interfaces described below, a set of different implementations for those graph models—there is no one-size-fits-all implementation—and graph algorithms provided in sub packages.

Vertices are always represented by an integer value of type VIdx ranging from 0 to n-1 for graphs with n vertices. Mapping different vertex types to the VIdx values for groph is currently left to the user. Edges are associated with values called “weights” which is a useful feature for most graph algorithms. A simple, unweighted graph can be considered to have weights of type bool that represent whether an edged is in the graph.

The graph interfaces

The graph interfaces are grouped by some specific aspects:

- Graph implementations can be read-only and read-write.

- Graph implementations are for directed or undirected graphs.

- Values associated with edges can be general, i.e. of type interface{}, or have some specific type.

The most basic is the RGraph interface that allows read-only access to directed and undirected graphs with no specific edge type. The WGraph interface extends RGraph with methods to change edges in the graph.

The variants of RGraph and WGraph for undirected graphs are RUndirected and WUndirected. Any specific graph that does not implement RUndirected is considered to be a directed graph. One can use the Directed() function to just distinguish directed and undirected at runtime. To also downcast to undirected graphs use standard Go features.

More specific interfaces are derived from these interfaces and adhere to the following naming convention. The first letter is either 'R' or 'W' to indicate read-only respectively read-write graphs. The second letter is either 'G' or 'U' to distinguish general graph interfaces from undirected interfaces. Finally comes an indicator for the edge weights, e.g. “i32” for int32 or “f32” for float32 or “bool” for just bool.

Index

• Constants
• func Clipped(err error) int
• func Copy[W any](dst WGraph[W], src RGraph[W]) error
• func CopyX[V, W any](dst WGraph[V], src RGraph[W], x func(W) (V, error)) error
• func Del[W any](g WGraph[W], vs ...VIdx)
• func Set[W any](g WGraph[W], w W, vs ...VIdx)
• type ClipError
  • func (err ClipError) Error() string
• type RDirected
• type RGraph
• type RUndirected
• type SrcDstError
  • func (err SrcDstError) Error() string
• type UVError
  • func (e UVError) Error() string
  • func (e UVError) Unwrap() error
• type VIdx
• type VisitEdge
• type VisitEdgeW
• type VisitVertex
• type WDirected
• type WGraph
• type WUndirected

Constants

const (
	IntNoEdge int = minInt
)

const Stopped stop = 0

Functions

func Clipped

func Clipped(err error) int

Clipped returns the clipping if err is a ClipError. Otherwise it returns 0.

func Copy

func Copy[W any](dst WGraph[W], src RGraph[W]) error

TODO What to do with w → !g.IsEdge(w) ??? Use CopyX ???

func CopyX

func CopyX[V, W any](dst WGraph[V], src RGraph[W], x func(W) (V, error)) error

func Del

func Del[W any](g WGraph[W], vs ...VIdx)

func Set

func Set[W any](g WGraph[W], w W, vs ...VIdx)

Types

type ClipError

type ClipError int

ClipError is returned when the order of src and dst in Cp*Weights does not match. If err is < 0 there were -err vertices ignored from src. If err > 0 then err vertices in dst were not covered.

func (ClipError) Error

func (err ClipError) Error() string

type RDirected

type RDirected[W any] interface {
	RGraph[W]

	// OutDegree returns the number of outgoing edges of vertex v in graph
	// g. Note that for undirected graphs each edge is also considered to
	// be an outgoing edge.
	OutDegree(v VIdx) int

	EachOut(from VIdx, onDest VisitVertex) error

	// InDegree returns the number of incoming edges of vertex v in graph
	// g. Note that for undirected graphs each edge is also considered to
	// be an incoming edge.
	InDegree(v VIdx) int

	EachIn(to VIdx, onSource VisitVertex) error

	RootCount() int

	EachRoot(onEdge VisitVertex) error

	LeafCount() int

	EachLeaf(onEdge VisitVertex) error
}

type RGraph

type RGraph[W any] interface {
	// Order return the numer of vertices in the graph.
	Order() int

	// Returns the weight of the edge that connects the vertex with index
	// u with the vertex with index v. If there is no such edge it returns nil.
	Edge(u, v VIdx) (weight W)

	// IsEdge returns true if and only if weight denotes an existing edge.
	IsEdge(weight W) bool

	// NotEdge return a W typed value that denotes a non-existing edge, i.e.
	// IsEdge(NotEdge()) == false.
	NotEdge() W

	// Size returns the number of edges of the graph.
	Size() int

	// EachEdge calls onEdge for each edge in the graph. When onEdge returns
	// true EachEdge stops immediately and returns true. Otherwise EachEdge
	// returns false.
	EachEdge(onEdge VisitEdgeW[W]) error
}

RGraph represents graph that allows read only access to the egde weights.

For graphs that can change be modified see WGraph. For undirected graphs see also RUndirected.

type RUndirected

type RUndirected[W any] interface {
	RGraph[W]
	// Weight must only be called when u ≥ v.  Otherwise WeightU's
	// behaviour is unspecified, it even might crash.  In many
	// implementations this can be way more efficient than the
	// general case, see method Weight().
	EdgeU(u, v VIdx) (weight W)

	Degree(v VIdx) int

	EachAdjacent(of VIdx, onNeighbour VisitVertex) error
}

RUndirected represents an undirected graph that allows read only access to the edge weights. For undirected graphs each edge (u,v) is considered outgiong as well as incoming for both, vertex u and vertext v.

type SrcDstError

type SrcDstError struct {
	Src error
	Dst error
}

SrcDstError is returned when an error occurred in the src or dst graph during Cp*Weights.

func (SrcDstError) Error

func (err SrcDstError) Error() string

type UVError

type UVError struct {
	U, V VIdx
	// contains filtered or unexported fields
}

func (UVError) Error

func (e UVError) Error() string

func (UVError) Unwrap

func (e UVError) Unwrap() error

type VIdx

type VIdx = int

VIdx is the type used to represent vertices in the graph implementations provided by the groph package.

type VisitEdge

type VisitEdge = func(u, v VIdx) error

type VisitEdgeW

type VisitEdgeW[W any] func(u, v VIdx, w W) error

type VisitVertex

type VisitVertex = func(v VIdx) error

type WDirected

type WDirected[W any] interface {
	WGraph[W]
	RDirected[W]
}

type WGraph

type WGraph[W any] interface {
	RGraph[W]
	// Reset resizes the graph to order and reinitializes it. Implementations
	// are expected to reuse memory.
	Reset(order int)
	// SetWeight sets the edge weight for the edge starting at vertex u and
	// ending at vertex v. Passing w==nil removes the edge.
	SetEdge(u, v VIdx, weight W)

	DelEdge(u, v VIdx)
}

WGraph represents graph that allows read and write access to the egde weights.

For undirected graphs see also WUndirected.

type WUndirected

type WUndirected[W any] interface {
	WGraph[W]
	RUndirected[W]

	// SetWeightU must only be called when u ≥ v.  Otherwise
	// SetWeightU's behaviour is unspecified, it even might crash.
	//
	// See also RUndirected.WeightU
	SetEdgeU(u, v VIdx, w W)

	DelEdgeU(u, v VIdx)
}

WUndirected represents an undirected graph that allows read and write access to the egde weights.