graph

package
v2.16.0 Latest Latest
Warning

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

 Go to latest Published: Jul 24, 2024 License: MIT Imports: 5 Imported by: 0

Documentation

Overview

Package graph implements general-purpose graph algorithms.

This includes some "online algorithms" for dynamic graphs i.e. algorithms that can efficiently give new results as a graph changes.

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

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.

References

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

The slides from Danupon Nanongkai (KTH, Sweden)'s ADFOCS 2018 talk, "Introduction to Dynamic Graph Algorithms", were also helpful.

The dynamic BFS algorithm is from "Semi-dynamic breadth-first search in digraphs", Franciosa, Frigioni & Giaccio, Theoretical Computer Science, Vol. 250, Issue 1-2, Jan 6 2001, pp 201–217.

To do

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
	}
}

func (u Universe) Weight(source, target graph.VertexIndex) graph.Weight {
	return graph.Weight(u.Bodies[source].Orbits[target])
}

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
}

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()
	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

This section is empty.

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. As it can be updated incrementally, AdjacencyMatrix also implements the Dynamic interface.

func NewAdjacencyMatrix 

func NewAdjacencyMatrix() AdjacencyMatrix

NewAdjacencyMatrix returns an AdjacencyMatrix. Each vertex pair can only have one edge. For a multigraph, where vertex pairs can store a count of multiple edges, use NewMultiAdjacencyMatrix.

func NewMultiAdjacencyMatrix added in v2.16.0 

func NewMultiAdjacencyMatrix() AdjacencyMatrix

NewMultiAdjacencyMatrix returns an AdjacencyMatrix. Each vertex pair can have a count of multiple edges. For a simple graph, where each vertex pair can have at most one edge, use NewAdjacencyMatrix.

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 Iterator and Dynamic, 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.M[int]

Matrix returns a pointer to the underlying matrix.M (of type int). Note that if the matrix is resized, this value may become an old reference.

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.

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).

THe matrix is automatically resized, if necessary.

func (AdjacencyMatrix) Vertexes 

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

Vertexes implements the graph Iterator Vertexes method. An AdjacencyMatrix is a graph of every vertex that has at least one edge (in either direction).

func (AdjacencyMatrix) Weight added in v2.16.0 

func (m AdjacencyMatrix) Weight(source, target VertexIndex) Weight

Weight implements the graph Iterator Weight method. The weight of each edge in an adjacency matrix is defined as the number of edges from source to target in the input matrix (including self-loops, if any). If the graph is not a multigraph, this is always exactly one for any existing edge in the matrix.

type BfsTree added in v2.14.0 

type BfsTree 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

NewBfsTree returns a new (empty) breadth-first search tree object for storing results.

func (*BfsTree) CalculateUnweighted added in v2.15.0 

func (t *BfsTree) 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) CalculateWeightedGeneral added in v2.15.0 

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

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) Clear added in v2.14.0 

func (t *BfsTree) Clear()

func (BfsTree) Distance added in v2.14.0 

func (t BfsTree) Distance(vertex VertexIndex) (Weight, 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) Edges added in v2.15.0 

func (t BfsTree) 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) Predecessor added in v2.14.0 

func (t BfsTree) 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) Reachable added in v2.14.0 

func (t BfsTree) Reachable(vertex VertexIndex) bool

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

func (*BfsTree) Resize added in v2.14.0 

func (t *BfsTree) 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) Vertexes added in v2.14.0 

func (t BfsTree) Vertexes() VertexIterator

Vertexes implements the graph Iterator Vertexes method.

type Decremental added in v2.16.0 

type Decremental interface {
	RemoveVertex(VertexIndex)
	RemoveEdge(source VertexIndex, target VertexIndex)
	IncreaseWeight(source VertexIndex, weight Weight)
}

Decremental is an interface for any dynamic graph implementation or online algorithm that can efficiently update to give a useful result if a graph changes by the removal of a vertex or edge, or if an edge weight increases.

Multiple related graph representations can be kept in-sync with TeeDecremental.

func TeeDecremental added in v2.16.0 

func TeeDecremental(a, b Decremental) Decremental

TeeDecremental returns a new Decremental interface whose methods, when called, are also called on `a` and `b`. This can be used to keep two related graph implementations in sync with each-other.

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.M[int]

Matrix returns a pointer to the underlying matrix.M (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.

func (*DegreeMatrix) Set 

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

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

type Dynamic added in v2.16.0 

type Dynamic interface {
	Incremental
	Decremental
}

Dynamic is an interface for any dynamic graph implementation or online algorithm that can efficiently update to give a useful result if a graph changes.

Multiple related graph representations can be kept in-sync with TeeDynamic.

func TeeDynamic added in v2.16.0 

func TeeDynamic[W Weight](a, b Dynamic) Dynamic

TeeDynamic returns a new Dynamic interface whose methods, when called, are also called on `a` and `b`. This can be used to keep two related graph implementations in-sync with each-other.

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 Incremental added in v2.16.0 

type Incremental interface {
	AddVertex(VertexIndex)
	AddEdge(source VertexIndex, target VertexIndex)
	DecreaseWeight(source VertexIndex, weight Weight)
}

Incremental is an interface for any dynamic graph implementation or online algorithm that can efficiently update to give a useful result if a graph changes by the addition of a vertex or edge, or if an edge weight decreases.

Multiple related graph representations can be kept in-sync with TeeIncremental.

func TeeIncremental added in v2.16.0 

func TeeIncremental(a, b Incremental) Incremental

TeeIncremental returns a new Incremental interface whose methods, when called, are also called on `a` and `b`. This can be used to keep two related graph implementations in sync with each-other.

Multiple related graph representations can be kept in-sync with TeeIncremental.

type Iterator 

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

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, etc. without restriction except where noted. In general, algorithms in this package operate on finite graphs only.

Edges are directed, but an undirected graph can always be implemented efficiently from a directed graph - e.g. from its adjacency matrix.

The Weight method calculates a weight of the edge between source and target. In the case of a multigraph, multiple edges must be reduced by some appropriate method e.g. by picking the minimum edge weight, by calculating the sum of edge weights, or by the count of edges, etc. Algorithms will only call Weight if a directed edge already exists from the source to the target vertex, so it is not necessary to validate the arguments again. If the graph is unweighted, you can return a unit Weight of 1.

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.

The optimum assignment of a VertexIndex to each vertex is called the Minimum Linear Arrangement, but in the general case this is NP-Hard and even an approximation has quadratic complexity. You can get decent results just using the indexes of a generational array (see the `genarray` sibling package).

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 int

Weight represents the "cost" of a weighted edge from one vertex to another. Weights may be negative, except where indicated by certain algorithms.

Real number (floating point) weights should be scaled to an integer range, for example by multiplying by some constant and rounding.

type WeightFunc added in v2.15.0 

type WeightFunc func(source, target VertexIndex) Weight

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 again.

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.