graph

README

What is graph?

graph is golang package with graph algorithms and data structures.

What is special?

All algorithms and data structures in this package are based on a simple abstraction that contains only one method:

type Graph[K comparable] interface {
	Adjacency(vertex K) []K
}

As you might have guessed, this allows us to treat a wide variety of data structures as graphs without extra boilerplate.

Data structures

There are several graph implementations in this package with unique data storing mechanisms. The most universal are Mapped and Indexed, that store vertices in map and slice respectively.

But there are also much more specific structures. One of them is Grid which is an infinite grid in where each vertex has only four neighbors. Newly created grid takes up almost no space since all neighbors are calculated based on the input vertex, but any modifications to the graph force affected vertices to be stored in memory.

Showcase

Iterating over tree using BFS:

g := graph.NewIndexed[uint]()
g.AddVertices(7)
g.AddEdges([][2]uint{{0, 1}, {0, 2}, {2, 3}, {2, 4}, {3, 5}, {3, 6}}...)

err := graph.BFS(g, 0, func(vertex, depth uint) bool {
	if depth > 2 {
		return false
	}
	fmt.Printf("%d: depth: %d, neighbors: %v\n", vertex, depth, g.Adjacency(vertex))
	return true
})

0: depth: 0, neighbors: [1 2]
1: depth: 1, neighbors: []
2: depth: 1, neighbors: [3 4]
3: depth: 2, neighbors: [5 6]
4: depth: 2, neighbors: []

Documentation

Index

• Variables
• func BFS[K comparable](g Graph[K], entry K, while func(vertex K, depth uint) bool) error
• func DFS[K comparable](g Graph[K], entry K, while func(vertex K) bool) error
• type Graph
• type GraphReadWriter
• type Grid
  • func NewGrid() *Grid
  • func (g *Grid) AddEdges(edges ...[2][2]int) error
  • func (g *Grid) AddVertices(vertices ...[2]int) error
  • func (g *Grid) Adjacency(vertex [2]int) [][2]int
  • func (g *Grid) DeleteEdges(edges ...[2][2]int)
  • func (g *Grid) DeleteVertices(vertices ...[2]int)
  • func (g *Grid) Order() int
  • func (g *Grid) Vertices() [][2]int
• type Indexed
  • func NewIndexed[U unsigned]() *Indexed[U]
  • func (g *Indexed[U]) AddEdges(edges ...[2]U) error
  • func (g *Indexed[U]) AddVertices(vertices ...U) error
  • func (g *Indexed[U]) Adjacency(vertex U) []U
  • func (g *Indexed[U]) DeleteEdges(edges ...[2]U)
  • func (g *Indexed[U]) DeleteVertices(vertices ...U)
  • func (g *Indexed[U]) Order() int
  • func (g *Indexed[U]) Vertices() []U
• type Mapped
  • func NewMapped[K comparable]() *Mapped[K]
  • func (g *Mapped[K]) AddEdges(edges ...[2]K) error
  • func (g *Mapped[K]) AddVertices(vertices ...K) error
  • func (g *Mapped[K]) Adjacency(vertex K) []K
  • func (g *Mapped[K]) DeleteEdges(edges ...[2]K)
  • func (g *Mapped[K]) DeleteVertices(vertices ...K)
  • func (g *Mapped[K]) Vertices() []K
• type Number
• type Reader
• type WeightedGraph
• type Writer

Variables

var ErrLoop = errors.New("simple graph can't contain loops")

var ErrNilVertex = errors.New("nil vertex")

var ErrVertexExists = errors.New("vertex already exists")

Functions

func BFS

func BFS[K comparable](g Graph[K], entry K, while func(vertex K, depth uint) bool) error

Each time a vertex is visited, the while function is triggered. The function exits if while returns false or there are no more vertices.

func DFS

func DFS[K comparable](g Graph[K], entry K, while func(vertex K) bool) error

Each time a vertex is visited, the while function is triggered. The function exits if while returns false or there are no more vertices.

Types

type Graph

type Graph[K comparable] interface {
	// There are three possible outputs Adjacency method has:
	// Nil slice: there in no a such vertex in the graph;
	// Empty slice: given vertex does not have neighbors;
	// Slice with values: all neighbors of the vertex.
	Adjacency(vertex K) []K
}

Graph is the interface that wraps the basic Adjacency method.

type GraphReadWriter

type GraphReadWriter[K comparable] interface {
	Graph[K]
	Reader[K]
	Writer[K]
}

type Grid

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

func NewGrid

func NewGrid() *Grid

func (*Grid) AddEdges

func (g *Grid) AddEdges(edges ...[2][2]int) error

func (*Grid) AddVertices

func (g *Grid) AddVertices(vertices ...[2]int) error

func (*Grid) Adjacency

func (g *Grid) Adjacency(vertex [2]int) [][2]int

func (*Grid) DeleteEdges

func (g *Grid) DeleteEdges(edges ...[2][2]int)

func (*Grid) DeleteVertices

func (g *Grid) DeleteVertices(vertices ...[2]int)

func (*Grid) Order

func (g *Grid) Order() int

func (*Grid) Vertices

func (g *Grid) Vertices() [][2]int

type Indexed

type Indexed[U unsigned] struct {
	// contains filtered or unexported fields
}

Unstable - vertex deletion, moves the last vertex to the place of the deleted one.

func NewIndexed

func NewIndexed[U unsigned]() *Indexed[U]

func (*Indexed[U]) AddEdges

func (g *Indexed[U]) AddEdges(edges ...[2]U) error

func (*Indexed[U]) AddVertices

func (g *Indexed[U]) AddVertices(vertices ...U) error

If only one vertex passed, increases slice size by its value. If more than one passed, increases slice size by amount of vertices passed.

func (*Indexed[U]) Adjacency

func (g *Indexed[U]) Adjacency(vertex U) []U

func (*Indexed[U]) DeleteEdges

func (g *Indexed[U]) DeleteEdges(edges ...[2]U)

func (*Indexed[U]) DeleteVertices

func (g *Indexed[U]) DeleteVertices(vertices ...U)

Deleted vertices get replaced by last ones.

func (*Indexed[U]) Order

func (g *Indexed[U]) Order() int

func (*Indexed[U]) Vertices

func (g *Indexed[U]) Vertices() []U

type Mapped

type Mapped[K comparable] struct {
	// contains filtered or unexported fields
}

func NewMapped

func NewMapped[K comparable]() *Mapped[K]

func (*Mapped[K]) AddEdges

func (g *Mapped[K]) AddEdges(edges ...[2]K) error

func (*Mapped[K]) AddVertices

func (g *Mapped[K]) AddVertices(vertices ...K) error

func (*Mapped[K]) Adjacency

func (g *Mapped[K]) Adjacency(vertex K) []K

func (*Mapped[K]) DeleteEdges

func (g *Mapped[K]) DeleteEdges(edges ...[2]K)

func (*Mapped[K]) DeleteVertices

func (g *Mapped[K]) DeleteVertices(vertices ...K)

func (*Mapped[K]) Vertices

func (g *Mapped[K]) Vertices() []K

type Number

type Number interface {
	~int | ~int8 | ~int16 | ~int32 | ~int64 |
		~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr |
		~float32 | ~float64
}

type Reader

type Reader[K comparable] interface {
	// Returns all vertices in the graph.
	// Must not return nil.
	// Infinite graph should return vertices that can't be procedural calculated.
	Vertices() []K

	// Returns amount of vertices in graph.
	// Infinite graph should return -1.
	Order() int
}

Reader is the interface that defines graph data read methods.

type WeightedGraph

type WeightedGraph[K comparable, N Number] interface {
	Graph[K]
	VerticesValues(vertices ...K) []N
	EdgesValues(vertices ...[2]K) []N
}

type Writer

type Writer[K comparable] interface {
	AddVertices(vertices ...K) error
	DeleteVertices(vertices ...K)
	AddEdges(edges ...[2]K) error
	DeleteEdges(edges ...[2]K)
}

Reader is the interface that defines methods that allow modify graph data.