graph

package
v2.15.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jun 3, 2024 License: MIT Imports: 5 Imported by: 0

Documentation

Overview

Package graph implements general-purpose graph algorithms.

This package does not implement any specific graph data structures: bring your own implementation!

Many of the algorithms and definitions are thanks to CLRS "Introduction to Algorithms", 3rd edition.

In general, this package is written & composed in such a way as to reduce runtime memory (re)allocations by encouraging the caller to reuse buffers.

Example (SolarSystem) 
package main

import (
	"fmt"
	stdslices "slices"
	"strings"

	"github.com/tawesoft/golib/v2/ds/graph"
	"github.com/tawesoft/golib/v2/fun/slices"
	"github.com/tawesoft/golib/v2/iter"
	"github.com/tawesoft/golib/v2/must"
)

type Distance int

type Body struct {
	Name   string
	Orbits map[graph.VertexIndex]Distance
}

// Universe is a multigraph.
type Universe struct {
	Bodies map[graph.VertexIndex]Body
}

// Vertexes implements the graph.Iterator interface.
func (u Universe) Vertexes() func() (graph.VertexIndex, bool) {
	return iter.Keys(iter.FromMap(u.Bodies))
}

// Edges implements the graph.Iterator interface.
func (u Universe) Edges(source graph.VertexIndex) func() (target graph.VertexIndex, count int, ok bool) {
	vertex := u.Bodies[source]
	it := iter.Keys(iter.FromMap(vertex.Orbits))
	return func() (_ graph.VertexIndex, _ int, _ bool) {
		target, ok := it()
		if !ok {
			return
		}
		return target, 1, true
	}
}

// AddVertex implements the graph.Builder interface
func (u *Universe) AddVertex() graph.VertexIndex {
	index := graph.VertexIndex(len(u.Bodies))
	if u.Bodies == nil {
		u.Bodies = make(map[graph.VertexIndex]Body)
	}
	u.Bodies[index] = Body{}
	return index
}

// AddEdge implements the graph.Builder interface
func (u *Universe) AddEdge(from graph.VertexIndex, to graph.VertexIndex) {
	u.Bodies[from].Orbits[to] = Distance(0)
}

func (u *Universe) AddBody(name string) graph.VertexIndex {
	index := u.AddVertex()
	u.Bodies[index] = Body{
		Name:   name,
		Orbits: make(map[graph.VertexIndex]Distance),
	}
	return index
}

func (u *Universe) AddOrbit(center graph.VertexIndex, body graph.VertexIndex, distance Distance) {
	u.AddEdge(center, body)
	u.Bodies[center].Orbits[body] = distance
}

func main() {
	// define a custom multigraph of orbit distances and solar irradiation
	var d Universe

	// Alpha Centuri is trinary star system with a binary star center
	alphaCentauri := d.AddBody("Alpha Centauri")     // Alpha Centauri AB barycenter
	proximaCentauri := d.AddBody("Proxima Centauri") // Alpha Centauri C

	sun := d.AddBody("Sol")

	mercury := d.AddBody("Mercury")
	venus := d.AddBody("Venus")
	earth := d.AddBody("The Earth")
	mars := d.AddBody("Mars")
	jupiter := d.AddBody("Jupiter")
	saturn := d.AddBody("Saturn")
	uranus := d.AddBody("Uranus")
	neptune := d.AddBody("Neptune")

	moon := d.AddBody("The Moon")
	demos := d.AddBody("Demos")
	phobos := d.AddBody("Phobos")

	// Average orbit distance (kilometres)
	// (figures from NASA)
	d.AddOrbit(alphaCentauri, proximaCentauri, 1_937_292_425_565)
	d.AddOrbit(sun, mercury, 57_000_000)
	d.AddOrbit(sun, venus, 108_000_000)
	d.AddOrbit(sun, earth, 149_000_000)
	d.AddOrbit(sun, mars, 228_000_000)
	d.AddOrbit(sun, jupiter, 780_000_000)
	d.AddOrbit(sun, saturn, 1_437_000_000)
	d.AddOrbit(sun, uranus, 2_871_000_000)
	d.AddOrbit(sun, neptune, 4_530_000_000)
	d.AddOrbit(earth, moon, 384_400)
	d.AddOrbit(mars, demos, 23_460)
	d.AddOrbit(mars, phobos, 6_000)

	// construct an adjacency matrix for efficient adjacency lookup
	orbitMatrix := graph.NewAdjacencyMatrix(nil)
	orbitMatrix.Calculate(d)

	// construct degree matrices for efficient in-/out- degree lookup
	indegreeMatrix := graph.NewDegreeMatrix()
	outdegreeMatrix := graph.NewDegreeMatrix()
	indegreeMatrix.Calculate(d.Vertexes, orbitMatrix.Indegree)
	outdegreeMatrix.Calculate(d.Vertexes, orbitMatrix.Outdegree)

	// construct a breadth-first search tree of everything reachable from the
	// sun i.e. all the solar system planets, and all their moons.
	solSystem := graph.NewBfsTree()
	solSystem.CalculateUnweighted(d, sun)

	// efficiently returns true iff a orbits b
	orbits := func(a graph.VertexIndex, b graph.VertexIndex) bool {
		return orbitMatrix.Get(b, a) > 0
	}

	// efficiently returns the number of satellites orbiting a
	numSatellites := func(a graph.VertexIndex) int {
		return outdegreeMatrix.Get(a)
	}

	// produces target vertexes from orbit edges
	satellites := func(source graph.VertexIndex) func() (graph.VertexIndex, bool) {
		edges := d.Edges(source)
		return func() (graph.VertexIndex, bool) {
			for {
				targetIdx, _, ok := edges()
				return targetIdx, ok
			}
		}
	}

	must.Truef(orbits(earth, sun), "expected: earth orbits the sun")
	must.Truef(orbits(moon, earth), "expected: moon orbits the earth")
	must.Falsef(orbits(sun, earth), "expected: sun does not orbit the earth")

	// efficiently find all graph roots
	roots := iter.ToSlice(graph.Roots(orbitMatrix.Vertexes, indegreeMatrix.Get))

	vertexName := func(x graph.VertexIndex) string {
		vertex := d.Bodies[x]
		return vertex.Name
	}

	sorted := func(xs []string) []string {
		stdslices.Sort(xs)
		return xs
	}

	fmt.Printf("The graph contains data for %d solar systems: %s.\n",
		len(roots),
		strings.Join(sorted(slices.Map(vertexName, roots)), " and "))
	fmt.Printf("The sun is orbited by %d satellites.\n",
		numSatellites(sun))
	fmt.Printf("Mars is orbited by %d satellites: %s.\n",
		numSatellites(mars),
		strings.Join(sorted(slices.Map(vertexName, iter.ToSlice(satellites(mars)))), " and "))

	if solSystem.Reachable(phobos) {
		fmt.Println("The solar system contains Phobos.")
	}
	if !solSystem.Reachable(proximaCentauri) {
		fmt.Println("The solar system does not contain Proxima Centauri.")
	}
	fmt.Printf("Phobos orbits %s.\n",
		vertexName(must.Ok(solSystem.Predecessor(phobos))))

}

Output:

The graph contains data for 2 solar systems: Alpha Centauri and Sol.
The sun is orbited by 8 satellites.
Mars is orbited by 2 satellites: Demos and Phobos.
The solar system contains Phobos.
The solar system does not contain Proxima Centauri.
Phobos orbits Mars.

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

func UnitWeightFunc added in v2.15.0 

func UnitWeightFunc(_, _ VertexIndex) int

UnitWeightFunc implements a WeightFunc that gives every existing edge an int-typed weight of 1.

Types

type AdjacencyMatrix 

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

AdjacencyMatrix represents the number of directed edges from a source vertex (along the x-axis) to a target vertex (along the y-axis), including self-loops, if any.

As a representation of a graph itself, AdjacencyMatrix implements the graph Iterator interface.

func NewAdjacencyMatrix 

func NewAdjacencyMatrix(m matrix.Constructor[int]) AdjacencyMatrix

NewAdjacencyMatrix returns an AdjacencyMatrix backed by the specified matrix implementation. If nil, defaults to matrix.NewBit.

A matrix implementation with a wider data type is needed to implement an AdjacencyMatrix for a multigraph e.g. matrix.NewGrid.

func (AdjacencyMatrix) Calculate 

func (m AdjacencyMatrix) Calculate(g Iterator)

Calculate computes the adjacency matrix for a finite graph g. The created adjacency matrix is itself a graph implementing [Interface] containing only the vertexes of g with at least one inward or outward edge.

Each vertex index in the adjacency matrix corresponds to a matching index in graph g. Once an adjacency matrix has been constructed, it is not affected by future changes to graph g.

func (AdjacencyMatrix) Clear 

func (m AdjacencyMatrix) Clear()

func (AdjacencyMatrix) CountEdges 

func (m AdjacencyMatrix) CountEdges() int

CountEdges returns the total number of edges in the adjacency matrix.

func (AdjacencyMatrix) Degree 

func (m AdjacencyMatrix) Degree(source VertexIndex) int

Degree returns the number of edges either to or from a specific vertex, including self-loops which are counted (by definition) as two edges.

This is computed with O(n) complexity; construct a DegreeMatrix for constant time.

func (AdjacencyMatrix) Edges 

func (m AdjacencyMatrix) Edges(source VertexIndex) func() (VertexIndex, int, bool)

Edges implements the graph Iterator Edges method.

func (AdjacencyMatrix) Get 

func (m AdjacencyMatrix) Get(source, target VertexIndex) int

Get returns the number of directed edges from a source vertex to a target vertex (including self-loops, if any).

func (AdjacencyMatrix) Indegree 

func (m AdjacencyMatrix) Indegree(target VertexIndex) int

Indegree returns the number of directed edges from any vertex to the specific target vertex (including self-loops from the target to itself).

This is computed with O(n) complexity; construct a DegreeMatrix for constant time.

func (AdjacencyMatrix) Matrix 

func (m AdjacencyMatrix) Matrix() matrix.Interface[int]

Matrix returns a pointer to the underlying matrix.Interface (of type int).

func (AdjacencyMatrix) Outdegree 

func (m AdjacencyMatrix) Outdegree(source VertexIndex) int

Outdegree returns the number of directed edges from a specific source vertex to any other vertex (including self-loops from the source to itself).

This is computed with O(n) complexity; construct a DegreeMatrix for constant time.

func (AdjacencyMatrix) Resize 

func (m AdjacencyMatrix) Resize(width int)

Resize updates the adjacency matrix, if necessary, so that it has at least capacity for width elements in each dimension. It reuses underlying memory from the existing matrix where possible. Note that this will clear the matrix.

func (AdjacencyMatrix) Set 

func (m AdjacencyMatrix) Set(source, target VertexIndex, count int)

Set stores the number of directed edges from a source vertex to a target vertex (including self-loops, if any).

func (AdjacencyMatrix) Vertexes 

func (m AdjacencyMatrix) Vertexes() func() (VertexIndex, bool)

Vertexes implements the graph Iterator Vertexes method. Every vertex will have at least one edge (in either direction).

func (AdjacencyMatrix) Width 

func (m AdjacencyMatrix) Width() int

Width returns the width of the adjacency matrix. Note that if VertexIndexes are sparsely distributed, width may be greater the number of vertexes produced by iteration.

type BfsTree added in v2.14.0 

type BfsTree[W Weight] struct {
	// contains filtered or unexported fields
}

BfsTree represents a (unweighted) breadth-first tree of the reachable graph from a given start vertex, taking the shortest number of edges.

A BfsTree is itself a graph (the predecessor subgraph of the graph it was constructed from), and implements the Iterator interface.

func NewBfsTree added in v2.14.0 

func NewBfsTree() *BfsTree[int]

NewBfsTree returns a new (empty) breadth-first search tree object for storing results. Distances are typed as integers.

func NewWeightedBfsTree added in v2.15.0 

func NewWeightedBfsTree[W Weight]() *BfsTree[W]

NewWeightedBfsTree returns a new (empty) breadth-first search tree object for storing results, with a specified Weight type.

func (*BfsTree[W]) CalculateUnweighted added in v2.15.0 

func (t *BfsTree[W]) CalculateUnweighted(graph Iterator, start VertexIndex)

CalculateUnweighted computes an unweighted breadth-first tree of the reachable graph from a given start vertex, taking the shortest number of edges. This is equivalent to a weighted search where every edge has a unit weight of one. The resulting search tree has useful properties.

The search stores a result in the provided result object, resizing its underlying buffer if necessary.

There may be many possible breadth-first trees of an input graph. This procedure always visits vertexes in the order given by a graph's EdgeIterator.

func (*BfsTree[W]) CalculateWeightedGeneral added in v2.15.0 

func (t *BfsTree[W]) CalculateWeightedGeneral(
	graph Iterator,
	start VertexIndex,
	weight WeightFunc[W],
)

CalculateWeightedGeneral computes a weighted breadth-first tree of the reachable graph from a given start vertex, taking the shortest distance calculated as a cumulative sum of weights along a path. The resulting search tree has useful properties.

This search is performed in the "general case" where edges may have negative weights, but not negative-weight cycles. [CalculateWeighted] is more efficient, but does not support negative edge weights.

The search stores a result in the provided result object, resizing its underlying buffer if necessary.

There may be many possible breadth-first trees of an input graph. The order taken by this procedure, when two paths have the same weight, is arbitrary and subject to change.

func (*BfsTree[W]) Clear added in v2.14.0 

func (t *BfsTree[W]) Clear()

func (BfsTree[W]) Distance added in v2.14.0 

func (t BfsTree[W]) Distance(vertex VertexIndex) (W, bool)

Distance returns the cumulative number of edges crossed from the search start vertex to the given target. If the vertex is not reachable, the boolean return value is false.

func (BfsTree[W]) Edges added in v2.15.0 

func (t BfsTree[W]) Edges(source VertexIndex) EdgeIterator

Edges implements the graph Iterator Edges method.

Each vertex has exactly one directed edge, to its predecessor, except the root vertex, which has none.

func (BfsTree[W]) Predecessor added in v2.14.0 

func (t BfsTree[W]) Predecessor(vertex VertexIndex) (VertexIndex, bool)

Predecessor returns the predecessor of the vertex in the search tree. If the vertex is not reachable, or if the vertex is the search start vertex, the boolean return value is false.

func (BfsTree[W]) Reachable added in v2.14.0 

func (t BfsTree[W]) Reachable(vertex VertexIndex) bool

Reachable returns true if the given vertex is reachable from the root of the BfsTree.

func (*BfsTree[W]) Resize added in v2.14.0 

func (t *BfsTree[W]) Resize(n int)

Resize updates the BfsTree, if necessary, so that it has at least capacity for n vertexes. It reuses underlying memory from the existing tree where possible. Note that this will clear the tree.

func (BfsTree[W]) Vertexes added in v2.14.0 

func (t BfsTree[W]) Vertexes() VertexIterator

Vertexes implements the graph Iterator Vertexes method.

type DegreeMatrix 

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

DegreeMatrix represents the number of edges on a vertex (to or from any other vertex in aggregate). This may be the in-, out-, or undirected-, degree.

Once built, a degree matrix can be queried in constant time.

Values are indexed by VertexIndex. A DegreeMatrix is a diagonal-matrix; values off the diagonal are zero.

func NewDegreeMatrix 

func NewDegreeMatrix() DegreeMatrix

NewDegreeMatrix returns a new degree matrix of undefined size.

func (DegreeMatrix) Calculate 

func (m DegreeMatrix) Calculate(g func() VertexIterator, degree func(index VertexIndex) int)

Calculate computes the degree matrix from any vertex iterator and any degree function.

For example, an in-, out-, or undirected degree matrix may be constructed from an AdjacencyMatrix using its Vertexes method and its Indegree, Outdegree, and Degree methods respectively.

Each vertex index in the degree matrix corresponds to the matching index in the input graph g. Once a degree matrix has been constructed, it is not affected by future changes to g.

func (DegreeMatrix) Clear 

func (m DegreeMatrix) Clear()

func (DegreeMatrix) CountEdges 

func (m DegreeMatrix) CountEdges() int

CountEdges returns the total number of edges in the degree matrix.

func (DegreeMatrix) Get 

func (m DegreeMatrix) Get(source VertexIndex) int

Get returns the (in-, out-, or undirected) degree of the given vertex.

func (DegreeMatrix) Matrix 

func (m DegreeMatrix) Matrix() matrix.Interface[int]

Matrix returns a pointer to the underlying matrix.Interface (of type int).

func (DegreeMatrix) Resize 

func (m DegreeMatrix) Resize(width int)

Resize updates the degree matrix, if necessary, so that it has at least capacity for width elements in each dimension. It reuses underlying memory from the existing matrix where possible. Note that this will clear the matrix.

func (DegreeMatrix) Set 

func (m DegreeMatrix) Set(source VertexIndex, count int)

Set stores the (in-, out-, or undirected) degree of the given vertex.

func (DegreeMatrix) Width 

func (m DegreeMatrix) Width() int

Width returns the width of the degree matrix. Note that if VertexIndexes are sparsely distributed, width may be greater the number of vertexes produced by iteration.

type EdgeIterator 

type EdgeIterator = func() (target VertexIndex, count int, ok bool)

EdgeIterator is the type of a generator function that, for some particular source vertex, generates each target vertex connected by at least one directed edge, and a count of the number of edges between them. If the graph is not a multigraph, this count will always be one.

The last return value controls the iteration - if false, the iteration has finished and the other return values are not useful.

type FilterEdges 

type FilterEdges struct {
	Parent Iterator
	Filter func(source VertexIndex, target VertexIndex) bool
}

FilterEdges implements the graph Iterator interface and represents a subgraph of a parent graph of only edges that satisfy the given filter function.

The Iterator implemented by FilterEdges is only a view of the parent graph and is computed on-the-fly as the parent changes.

func (FilterEdges) Edges 

func (f FilterEdges) Edges(source VertexIndex) EdgeIterator

func (FilterEdges) Vertexes 

func (f FilterEdges) Vertexes() VertexIterator

type FilterVertexes 

type FilterVertexes struct {
	Parent Iterator
	Filter func(vertex VertexIndex) bool
}

FilterVertexes implements the graph Iterator interface and represents a subgraph of a parent graph of only vertexes that satisfy the given filter function.

The Iterator implemented by FilterVertexes is only a view of the parent graph and is computed on-the-fly as the parent changes.

func (FilterVertexes) Edges 

func (f FilterVertexes) Edges(source VertexIndex) EdgeIterator

func (FilterVertexes) Vertexes 

func (f FilterVertexes) Vertexes() VertexIterator

type Iterator 

type Iterator interface {
	Vertexes() VertexIterator
	Edges(source VertexIndex) EdgeIterator
}

Iterator is the basic interface that a graph data type must implement to be able to use many of the algorithms in this package.

A graph can have many equivalent implementations: a data structure, perhaps an adjacency list or an adjacency matrix; or an algorithm. The mapping between this general-purpose graph interface and a given graph implementation is achieved through two iterator-style functions.

Graphs may contain cycles, loops, be disjoint, be multigraphs, be infinite, etc. without restriction except where noted. These properties can be tested for by algorithms implemented in this package.

Edges are directed, but an undirected graph can always be implemented efficiently by defining an "undirected edge" as a directed edge from a lower VertexIndex to a higher VertexIndex.

type VertexIndex 

type VertexIndex int

VertexIndex is a non-negative index that uniquely identifies each vertex in a graph. Vertex indexes do not have to be consecutive or sorted, may be sparse, and do not have to start at zero, but it may be more efficient where that is the case.

Many algorithms in this package will have computational complexity proportionate to the maximum VertexIndex, and require memory proportionate to the maximum VertexIndex squared.

type VertexIterator 

type VertexIterator = func() (vertex VertexIndex, ok bool)

VertexIterator is the type of a generator function that, for some particular graph, generates a VertexIndex for each vertex in the graph.

The last return value controls the iteration - if false, the iteration has finished and the other return value is not useful.

func Leaves 

func Leaves(
	vertexes func() VertexIterator,
	indegree func(VertexIndex) int,
	outdegree func(VertexIndex) int,
) VertexIterator

Leaves returns an iterator that generates indexes of vertexes that have exactly one parent and exactly zero children in a directed graph.

A degree function can be made by passing an appropriate method from an AdjacencyMatrix or DegreeMatrix.

func Roots 

func Roots(
	vertexes func() VertexIterator,
	indegree func(VertexIndex) int,
) VertexIterator

Roots returns an iterator that generates only the indexes of vertexes that have no parents i.e. root vertexes in a directed graph.

A degree function can be made by passing an appropriate method from an AdjacencyMatrix or DegreeMatrix.

type Weight added in v2.15.0 

type Weight interface {
	constraints.Integer | constraints.Float
}

Weight represents the value of a weighted edge from one vertex to another. It can be any integer or float type. Weights may be negative, except where indicated by certain algorithms.

type WeightFunc added in v2.15.0 

type WeightFunc[W Weight] func(source, target VertexIndex) W

WeightFunc is the type of a function that gives a weight between two vertexes in a graph. Algorithms will only call this if a directed edge already exists from the source to the target vertex, so it is not necessary to validate the arguments.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.