graph

README

中文版 | English Version

A library for creating generic graph data structures and modifying, analyzing, and visualizing them.

Are you using graph? Check out the graph user survey.

Features

• Generic vertices of any type, such as int or City.
• Graph traits with corresponding validations, such as cycle checks in acyclic graphs.
• Algorithms for finding paths or components, such as shortest paths or strongly connected components.
• Algorithms for transformations and representations, such as transitive reduction or topological order.
• Algorithms for non-recursive graph traversal, such as DFS or BFS.
• Vertices and edges with optional metadata, such as weights or custom attributes.
• Visualization of graphs using the DOT language and Graphviz.
• Integrate any storage backend by using your own Store implementation.
• Extensive tests with ~90% coverage, and zero dependencies.

Status: Because graph is in version 0, the public API shouldn't be considered stable.

This README may contain unreleased changes. Check out the latest documentation.

Getting started

go get github.com/dominikbraun/graph

Quick examples

Create a graph of integers

g := graph.New(graph.IntHash)

_ = g.AddVertex(1)
_ = g.AddVertex(2)
_ = g.AddVertex(3)
_ = g.AddVertex(4)
_ = g.AddVertex(5)

_ = g.AddEdge(1, 2)
_ = g.AddEdge(1, 4)
_ = g.AddEdge(2, 3)
_ = g.AddEdge(2, 4)
_ = g.AddEdge(2, 5)
_ = g.AddEdge(3, 5)

Create a directed acyclic graph of integers

g := graph.New(graph.IntHash, graph.Directed(), graph.Acyclic())

_ = g.AddVertex(1)
_ = g.AddVertex(2)
_ = g.AddVertex(3)
_ = g.AddVertex(4)

_ = g.AddEdge(1, 2)
_ = g.AddEdge(1, 3)
_ = g.AddEdge(2, 3)
_ = g.AddEdge(2, 4)
_ = g.AddEdge(3, 4)

Create a graph of a custom type

To understand this example in detail, see the concept of hashes.

type City struct {
    Name string
}

cityHash := func(c City) string {
    return c.Name
}

g := graph.New(cityHash)

_ = g.AddVertex(london)

Create a weighted graph

g := graph.New(cityHash, graph.Weighted())

_ = g.AddVertex(london)
_ = g.AddVertex(munich)
_ = g.AddVertex(paris)
_ = g.AddVertex(madrid)

_ = g.AddEdge("london", "munich", graph.EdgeWeight(3))
_ = g.AddEdge("london", "paris", graph.EdgeWeight(2))
_ = g.AddEdge("london", "madrid", graph.EdgeWeight(5))
_ = g.AddEdge("munich", "madrid", graph.EdgeWeight(6))
_ = g.AddEdge("munich", "paris", graph.EdgeWeight(2))
_ = g.AddEdge("paris", "madrid", graph.EdgeWeight(4))

Perform a Depth-First Search

This example traverses and prints all vertices in the graph in DFS order.

g := graph.New(graph.IntHash, graph.Directed())

_ = g.AddVertex(1)
_ = g.AddVertex(2)
_ = g.AddVertex(3)
_ = g.AddVertex(4)

_ = g.AddEdge(1, 2)
_ = g.AddEdge(1, 3)
_ = g.AddEdge(3, 4)

_ = graph.DFS(g, 1, func(value int) bool {
    fmt.Println(value)
    return false
})

1 3 4 2

Find strongly connected components

g := graph.New(graph.IntHash)

// Add vertices and edges ...

scc, _ := graph.StronglyConnectedComponents(g)

fmt.Println(scc)

[[1 2 5] [3 4 8] [6 7]]

Find the shortest path

g := graph.New(graph.StringHash, graph.Weighted())

// Add vertices and weighted edges ...

path, _ := graph.ShortestPath(g, "A", "B")

fmt.Println(path)

[A C E B]

Find spanning trees

g := graph.New(graph.StringHash, graph.Weighted())

// Add vertices and edges ...

mst, _ := graph.MinimumSpanningTree(g)

Perform a topological sort

g := graph.New(graph.IntHash, graph.Directed(), graph.PreventCycles())

// Add vertices and edges ...

// For a deterministic topological ordering, use StableTopologicalSort.
order, _ := graph.TopologicalSort(g)

fmt.Println(order)

[1 2 3 4 5]

Perform a transitive reduction

g := graph.New(graph.StringHash, graph.Directed(), graph.PreventCycles())

// Add vertices and edges ...

transitiveReduction, _ := graph.TransitiveReduction(g)

Prevent the creation of cycles

g := graph.New(graph.IntHash, graph.PreventCycles())

_ = g.AddVertex(1)
_ = g.AddVertex(2)
_ = g.AddVertex(3)

_ = g.AddEdge(1, 2)
_ = g.AddEdge(1, 3)

if err := g.AddEdge(2, 3); err != nil {
    panic(err)
}

panic: an edge between 2 and 3 would introduce a cycle

Visualize a graph using Graphviz

The following example will generate a DOT description for g and write it into the given file.

g := graph.New(graph.IntHash, graph.Directed())

_ = g.AddVertex(1)
_ = g.AddVertex(2)
_ = g.AddVertex(3)

_ = g.AddEdge(1, 2)
_ = g.AddEdge(1, 3)

file, _ := os.Create("./mygraph.gv")
_ = draw.DOT(g, file)

To generate an SVG from the created file using Graphviz, use a command such as the following:

dot -Tsvg -O mygraph.gv

The DOT function also supports rendering graph attributes:

_ = draw.DOT(g, file, draw.GraphAttribute("label", "my-graph"))

Draw a graph as in this documentation

This graph has been rendered using the following program:

package main

import (
	"os"

	"github.com/dominikbraun/graph"
	"github.com/dominikbraun/graph/draw"
)

func main() {
	g := graph.New(graph.IntHash)

	_ = g.AddVertex(1, graph.VertexAttribute("colorscheme", "blues3"), graph.VertexAttribute("style", "filled"), graph.VertexAttribute("color", "2"), graph.VertexAttribute("fillcolor", "1"))
	_ = g.AddVertex(2, graph.VertexAttribute("colorscheme", "greens3"), graph.VertexAttribute("style", "filled"), graph.VertexAttribute("color", "2"), graph.VertexAttribute("fillcolor", "1"))
	_ = g.AddVertex(3, graph.VertexAttribute("colorscheme", "purples3"), graph.VertexAttribute("style", "filled"), graph.VertexAttribute("color", "2"), graph.VertexAttribute("fillcolor", "1"))
	_ = g.AddVertex(4, graph.VertexAttribute("colorscheme", "ylorbr3"), graph.VertexAttribute("style", "filled"), graph.VertexAttribute("color", "2"), graph.VertexAttribute("fillcolor", "1"))
	_ = g.AddVertex(5, graph.VertexAttribute("colorscheme", "reds3"), graph.VertexAttribute("style", "filled"), graph.VertexAttribute("color", "2"), graph.VertexAttribute("fillcolor", "1"))

	_ = g.AddEdge(1, 2)
	_ = g.AddEdge(1, 4)
	_ = g.AddEdge(2, 3)
	_ = g.AddEdge(2, 4)
	_ = g.AddEdge(2, 5)
	_ = g.AddEdge(3, 5)

	file, _ := os.Create("./simple.gv")
	_ = draw.DOT(g, file)
}

It has been rendered using the neato engine:

dot -Tsvg -Kneato -O simple.gv

The example uses the Brewer color scheme supported by Graphviz.

Storing edge attributes

Edges may have one or more attributes which can be used to store metadata. Attributes will be taken into account when visualizing a graph. For example, this edge will be rendered in red color:

_ = g.AddEdge(1, 2, graph.EdgeAttribute("color", "red"))

To get an overview of all supported attributes, take a look at the DOT documentation.

The stored attributes can be retrieved by getting the edge and accessing the Properties.Attributes field.

edge, _ := g.Edge(1, 2)
color := edge.Properties.Attributes["color"] 

Storing edge data

It is also possible to store arbitrary data inside edges, not just key-value string pairs. This data is of type any.

_  = g.AddEdge(1, 2, graph.EdgeData(myData))

The stored data can be retrieved by getting the edge and accessing the Properties.Data field.

edge, _ := g.Edge(1, 2)
myData := edge.Properties.Data 

Updating edge data

Edge properties can be updated using Graph.UpdateEdge. The following example adds a new color attribute to the edge (A,B) and sets the edge weight to 10.

_ = g.UpdateEdge("A", "B", graph.EdgeAttribute("color", "red"), graph.EdgeWeight(10))

The method signature and the accepted functional options are exactly the same as for Graph.AddEdge.

Storing vertex attributes

Vertices may have one or more attributes which can be used to store metadata. Attributes will be taken into account when visualizing a graph. For example, this vertex will be rendered in red color:

_ = g.AddVertex(1, graph.VertexAttribute("style", "filled"))

The stored data can be retrieved by getting the vertex using VertexWithProperties and accessing the Attributes field.

vertex, properties, _ := g.VertexWithProperties(1)
style := properties.Attributes["style"]

To get an overview of all supported attributes, take a look at the DOT documentation.

Store the graph in a custom storage

You can integrate any storage backend by implementing the Store interface and initializing a new graph with it:

g := graph.NewWithStore(graph.IntHash, myStore)

To implement the Store interface appropriately, take a look at the documentation. graph-sql is a ready-to-use SQL store implementation.

Documentation

The full documentation is available at pkg.go.dev.

Are you using graph? Check out the graph user survey.

Documentation

Overview

Package graph is a library for creating generic graph data structures and modifying, analyzing, and visualizing them.

Hashes

A graph consists of vertices of type T, which are identified by a hash value of type K. The hash value for a given vertex is obtained using the hashing function passed to New. A hashing function takes a T and returns a K.

For primitive types like integers, you may use a predefined hashing function such as IntHash – a function that takes an integer and uses that integer as the hash value at the same time:

g := graph.New(graph.IntHash)

For storing custom data types, you need to provide your own hashing function. This example takes a City instance and returns its name as the hash value:

cityHash := func(c City) string {
	return c.Name
}

Creating a graph using this hashing function will yield a graph of vertices of type City identified by hash values of type string.

g := graph.New(cityHash)

Operations

Adding vertices to a graph of integers is simple. graph.Graph.AddVertex takes a vertex and adds it to the graph.

g := graph.New(graph.IntHash)

_ = g.AddVertex(1)
_ = g.AddVertex(2)

Most functions accept and return only hash values instead of entire instances of the vertex type T. For example, graph.Graph.AddEdge creates an edge between two vertices and accepts the hash values of those vertices. Because this graph uses the IntHash hashing function, the vertex values and hash values are the same.

_ = g.AddEdge(1, 2)

All operations that modify the graph itself are methods of Graph. All other operations are top-level functions of by this library.

For detailed usage examples, take a look at the README.

Index

• Variables
• func Acyclic() func(*Traits)
• func AllPathsBetween[K comparable, T any](g Graph[K, T], start, end K) ([][]K, error)
• func BFS[K comparable, T any](g Graph[K, T], start K, visit func(K) bool) error
• func BFSWithDepth[K comparable, T any](g Graph[K, T], start K, visit func(K, int) bool) error
• func CreatesCycle[K comparable, T any](g Graph[K, T], source, target K) (bool, error)
• func DFS[K comparable, T any](g Graph[K, T], start K, visit func(K) bool) error
• func Directed() func(*Traits)
• func EdgeAttribute(key, value string) func(*EdgeProperties)
• func EdgeAttributes(attributes map[string]string) func(*EdgeProperties)
• func EdgeData(data any) func(*EdgeProperties)
• func EdgeWeight(weight int) func(*EdgeProperties)
• func IntHash(v int) int
• func PreventCycles() func(*Traits)
• func Rooted() func(*Traits)
• func ShortestPath[K comparable, T any](g Graph[K, T], source, target K) ([]K, error)
• func StableTopologicalSort[K comparable, T any](g Graph[K, T], less func(K, K) bool) ([]K, error)
• func StringHash(v string) string
• func StronglyConnectedComponents[K comparable, T any](g Graph[K, T]) ([][]K, error)
• func TopologicalSort[K comparable, T any](g Graph[K, T]) ([]K, error)
• func Tree() func(*Traits)
• func VertexAttribute(key, value string) func(*VertexProperties)
• func VertexAttributes(attributes map[string]string) func(*VertexProperties)
• func VertexWeight(weight int) func(*VertexProperties)
• func Weighted() func(*Traits)
• type Edge
• type EdgeProperties
• type Graph
  • func MaximumSpanningTree[K comparable, T any](g Graph[K, T]) (Graph[K, T], error)
  • func MinimumSpanningTree[K comparable, T any](g Graph[K, T]) (Graph[K, T], error)
  • func New[K comparable, T any](hash Hash[K, T], options ...func(*Traits)) Graph[K, T]
  • func NewLike[K comparable, T any](g Graph[K, T]) Graph[K, T]
  • func NewWithStore[K comparable, T any](hash Hash[K, T], store Store[K, T], options ...func(*Traits)) Graph[K, T]
  • func TransitiveReduction[K comparable, T any](g Graph[K, T]) (Graph[K, T], error)
  • func Union[K comparable, T any](g, h Graph[K, T]) (Graph[K, T], error)
• type Hash
• type Store
• type Traits
• type VertexProperties

Variables

var (
	ErrVertexNotFound      = errors.New("vertex not found")
	ErrVertexAlreadyExists = errors.New("vertex already exists")
	ErrEdgeNotFound        = errors.New("edge not found")
	ErrEdgeAlreadyExists   = errors.New("edge already exists")
	ErrEdgeCreatesCycle    = errors.New("edge would create a cycle")
	ErrVertexHasEdges      = errors.New("vertex has edges")
)

var ErrTargetNotReachable = errors.New("target vertex not reachable from source")

Functions

func Acyclic

func Acyclic() func(*Traits)

Acyclic creates an acyclic graph. Note that creating edges that form a cycle will still be possible. To prevent this explicitly, use PreventCycles.

func AllPathsBetween

func AllPathsBetween[K comparable, T any](g Graph[K, T], start, end K) ([][]K, error)

AllPathsBetween computes and returns all paths between two given vertices. A path is represented as a slice of vertex hashes. The returned slice contains these paths.

AllPathsBetween utilizes a non-recursive, stack-based implementation. It has an estimated runtime complexity of O(n^2) where n is the number of vertices.

func BFS

func BFS[K comparable, T any](g Graph[K, T], start K, visit func(K) bool) error

BFS performs a breadth-first search on the graph, starting from the given vertex. The visit function will be invoked with the hash of the vertex currently visited. If it returns false, BFS will continue traversing the graph, and if it returns true, the traversal will be stopped. In case the graph is disconnected, only the vertices joined with the starting vertex are visited.

This example prints all vertices of the graph in BFS-order:

g := graph.New(graph.IntHash)

_ = g.AddVertex(1)
_ = g.AddVertex(2)
_ = g.AddVertex(3)

_ = g.AddEdge(1, 2)
_ = g.AddEdge(2, 3)
_ = g.AddEdge(3, 1)

_ = graph.BFS(g, 1, func(value int) bool {
	fmt.Println(value)
	return false
})

Similarly, if you have a graph of City vertices and the traversal should stop at London, the visit function would look as follows:

func(c City) bool {
	return c.Name == "London"
}

BFS is non-recursive and maintains a stack instead.

func BFSWithDepth

func BFSWithDepth[K comparable, T any](g Graph[K, T], start K, visit func(K, int) bool) error

BFSWithDepth works just as BFS and performs a breadth-first search on the graph, but its visit function is passed the current depth level as a second argument. Consequently, the current depth can be used for deciding whether or not to proceed past a certain depth.

_ = graph.BFSWithDepth(g, 1, func(value int, depth int) bool {
	fmt.Println(value)
	return depth > 3
})

With the visit function from the example, the BFS traversal will stop once a depth greater than 3 is reached.

func CreatesCycle

func CreatesCycle[K comparable, T any](g Graph[K, T], source, target K) (bool, error)

CreatesCycle determines whether adding an edge between the two given vertices would introduce a cycle in the graph. CreatesCycle will not create an edge.

A potential edge would create a cycle if the target vertex is also a parent of the source vertex. In order to determine this, CreatesCycle runs a DFS.

func DFS

func DFS[K comparable, T any](g Graph[K, T], start K, visit func(K) bool) error

DFS performs a depth-first search on the graph, starting from the given vertex. The visit function will be invoked with the hash of the vertex currently visited. If it returns false, DFS will continue traversing the graph, and if it returns true, the traversal will be stopped. In case the graph is disconnected, only the vertices joined with the starting vertex are visited.

This example prints all vertices of the graph in DFS-order:

g := graph.New(graph.IntHash)

_ = g.AddVertex(1)
_ = g.AddVertex(2)
_ = g.AddVertex(3)

_ = g.AddEdge(1, 2)
_ = g.AddEdge(2, 3)
_ = g.AddEdge(3, 1)

_ = graph.DFS(g, 1, func(value int) bool {
	fmt.Println(value)
	return false
})

Similarly, if you have a graph of City vertices and the traversal should stop at London, the visit function would look as follows:

func(c City) bool {
	return c.Name == "London"
}

DFS is non-recursive and maintains a stack instead.

func Directed

func Directed() func(*Traits)

Directed creates a directed graph. This has implications on graph traversal and the order of arguments of the Edge and AddEdge functions.

func EdgeAttribute

func EdgeAttribute(key, value string) func(*EdgeProperties)

EdgeAttribute returns a function that adds the given key-value pair to the attributes of an edge. This is a functional option for the graph.Graph.Edge and graph.Graph.AddEdge methods.

func EdgeAttributes

func EdgeAttributes(attributes map[string]string) func(*EdgeProperties)

EdgeAttributes returns a function that sets the given map as the attributes of an edge. This is a functional option for the graph.Graph.AddEdge and graph.Graph.UpdateEdge methods.

func EdgeData

func EdgeData(data any) func(*EdgeProperties)

EdgeData returns a function that sets the data of an edge to the given value. This is a functional option for the graph.Graph.Edge and graph.Graph.AddEdge methods.

func EdgeWeight

func EdgeWeight(weight int) func(*EdgeProperties)

EdgeWeight returns a function that sets the weight of an edge to the given weight. This is a functional option for the graph.Graph.Edge and graph.Graph.AddEdge methods.

func IntHash

func IntHash(v int) int

IntHash is a hashing function that accepts an integer and uses that exact integer as a hash value. Using it as Hash will yield a Graph[int, int].

func PreventCycles

func PreventCycles() func(*Traits)

PreventCycles creates an acyclic graph that prevents and proactively prevents the creation of cycles. These cycle checks affect the performance and complexity of operations such as AddEdge.

func Rooted

func Rooted() func(*Traits)

Rooted creates a rooted graph. This is particularly common for building tree data structures.

func ShortestPath

func ShortestPath[K comparable, T any](g Graph[K, T], source, target K) ([]K, error)

ShortestPath computes the shortest path between a source and a target vertex under consideration of the edge weights. It returns a slice of hash values of the vertices forming that path.

The returned path includes the source and target vertices. If the target is not reachable from the source, ErrTargetNotReachable will be returned. Should there be multiple shortest paths, and arbitrary one will be returned.

ShortestPath has a time complexity of O(|V|+|E|log(|V|)).

func StableTopologicalSort

func StableTopologicalSort[K comparable, T any](g Graph[K, T], less func(K, K) bool) ([]K, error)

StableTopologicalSort does the same as TopologicalSort, but takes a function for comparing (and then ordering) two given vertices. This allows for a stable and deterministic output even for graphs with multiple topological orderings.

func StringHash

func StringHash(v string) string

StringHash is a hashing function that accepts a string and uses that exact string as a hash value. Using it as Hash will yield a Graph[string, string].

func StronglyConnectedComponents

func StronglyConnectedComponents[K comparable, T any](g Graph[K, T]) ([][]K, error)

StronglyConnectedComponents detects all strongly connected components within the graph and returns the hashes of the vertices shaping these components, so each component is represented by a []K.

StronglyConnectedComponents can only run on directed graphs.

func TopologicalSort

func TopologicalSort[K comparable, T any](g Graph[K, T]) ([]K, error)

TopologicalSort runs a topological sort on a given directed graph and returns the vertex hashes in topological order. The topological order is a non-unique order of vertices in a directed graph where an edge from vertex A to vertex B implies that vertex A appears before vertex B.

Note that TopologicalSort doesn't make any guarantees about the order. If there are multiple valid topological orderings, an arbitrary one will be returned. To make the output deterministic, use StableTopologicalSort.

TopologicalSort only works for directed acyclic graphs. This implementation works non-recursively and utilizes Kahn's algorithm.

func Tree

func Tree() func(*Traits)

Tree is an alias for Acyclic and Rooted, since most trees in Computer Science are rooted trees.

func VertexAttribute

func VertexAttribute(key, value string) func(*VertexProperties)

VertexAttribute returns a function that adds the given key-value pair to the vertex attributes. This is a functional option for the graph.Graph.Vertex and graph.Graph.AddVertex methods.

func VertexAttributes

func VertexAttributes(attributes map[string]string) func(*VertexProperties)

VertexAttributes returns a function that sets the given map as the attributes of a vertex. This is a functional option for the graph.Graph.AddVertex methods.

func VertexWeight

func VertexWeight(weight int) func(*VertexProperties)

VertexWeight returns a function that sets the weight of a vertex to the given weight. This is a functional option for the graph.Graph.Vertex and graph.Graph.AddVertex methods.

func Weighted

func Weighted() func(*Traits)

Weighted creates a weighted graph. To set weights, use the Edge and AddEdge functions.

Types

type Edge

type Edge[T any] struct {
	Source     T
	Target     T
	Properties EdgeProperties
}

Edge represents an edge that joins two vertices. Even though these edges are always referred to as source and target, whether the graph is directed or not is determined by its traits.

type EdgeProperties

type EdgeProperties struct {
	Attributes map[string]string
	Weight     int
	Data       any
}

EdgeProperties represents a set of properties that each edge possesses. They can be set when adding a new edge using the corresponding functional options:

g.AddEdge("A", "B", graph.EdgeWeight(2), graph.EdgeAttribute("color", "red"))

The example above will create an edge with a weight of 2 and an attribute "color" with value "red".

type Graph

type Graph[K comparable, T any] interface {
	// Traits returns the graph's traits. Those traits must be set when creating
	// a graph using New.
	Traits() *Traits

	// AddVertex creates a new vertex in the graph. If the vertex already exists
	// in the graph, ErrVertexAlreadyExists will be returned.
	//
	// AddVertex accepts a variety of functional options to set further edge
	// details such as the weight or an attribute:
	//
	//	_ = graph.AddVertex("A", "B", graph.VertexWeight(4), graph.VertexAttribute("label", "my-label"))
	//
	AddVertex(value T, options ...func(*VertexProperties)) error

	// AddVerticesFrom adds all vertices along with their properties from the
	// given graph to the receiving graph.
	//
	// All vertices will be added until an error occurs. If one of the vertices
	// already exists, ErrVertexAlreadyExists will be returned.
	AddVerticesFrom(g Graph[K, T]) error

	// Vertex returns the vertex with the given hash or ErrVertexNotFound if it
	// doesn't exist.
	Vertex(hash K) (T, error)

	// VertexWithProperties returns the vertex with the given hash along with
	// its properties or ErrVertexNotFound if it doesn't exist.
	VertexWithProperties(hash K) (T, VertexProperties, error)

	// RemoveVertex removes the vertex with the given hash value from the graph.
	//
	// The vertex is not allowed to have edges and thus must be disconnected.
	// Potential edges must be removed first. Otherwise, ErrVertexHasEdges will
	// be returned. If the vertex doesn't exist, ErrVertexNotFound is returned.
	RemoveVertex(hash K) error

	// AddEdge creates an edge between the source and the target vertex.
	//
	// If either vertex cannot be found, ErrVertexNotFound will be returned. If
	// the edge already exists, ErrEdgeAlreadyExists will be returned. If cycle
	// prevention has been activated using PreventCycles and if adding the edge
	// would create a cycle, ErrEdgeCreatesCycle will be returned.
	//
	// AddEdge accepts functional options to set further edge properties such as
	// the weight or an attribute:
	//
	//	_ = g.AddEdge("A", "B", graph.EdgeWeight(4), graph.EdgeAttribute("label", "my-label"))
	//
	AddEdge(sourceHash, targetHash K, options ...func(*EdgeProperties)) error

	// AddEdgesFrom adds all edges along with their properties from the given
	// graph to the receiving graph.
	//
	// All vertices that the edges are joining have to exist already. If needed,
	// these vertices can be added using AddVerticesFrom first. Depending on the
	// situation, it also might make sense to clone the entire original graph.
	AddEdgesFrom(g Graph[K, T]) error

	// Edge returns the edge joining two given vertices or ErrEdgeNotFound if
	// the edge doesn't exist. In an undirected graph, an edge with swapped
	// source and target vertices does match.
	Edge(sourceHash, targetHash K) (Edge[T], error)

	// Edges returns a slice of all edges in the graph. These edges are of type
	// Edge[K] and hence will contain the vertex hashes, not the vertex values.
	Edges() ([]Edge[K], error)

	// UpdateEdge updates the edge joining the two given vertices with the data
	// provided in the given functional options. Valid functional options are:
	// - EdgeWeight: Sets a new weight for the edge properties.
	// - EdgeAttribute: Adds a new attribute to the edge properties.
	// - EdgeAttributes: Sets a new attributes map for the edge properties.
	// - EdgeData: Sets a new Data field for the edge properties.
	//
	// UpdateEdge accepts the same functional options as AddEdge. For example,
	// setting the weight of an edge (A,B) to 10 would look as follows:
	//
	//	_ = g.UpdateEdge("A", "B", graph.EdgeWeight(10))
	//
	// Removing a particular edge attribute is not possible at the moment. A
	// workaround is to create a new map without the respective element and
	// overwrite the existing attributes using the EdgeAttributes option.
	UpdateEdge(source, target K, options ...func(properties *EdgeProperties)) error

	// RemoveEdge removes the edge between the given source and target vertices.
	// If the edge cannot be found, ErrEdgeNotFound will be returned.
	RemoveEdge(source, target K) error

	// AdjacencyMap computes an adjacency map with all vertices in the graph.
	//
	// There is an entry for each vertex. Each of those entries is another map
	// whose keys are the hash values of the adjacent vertices. The value is an
	// Edge instance that stores the source and target hash values along with
	// the edge metadata.
	//
	// For a directed graph with two edges AB and AC, AdjacencyMap would return
	// the following map:
	//
	//	map[string]map[string]Edge[string]{
	//		"A": map[string]Edge[string]{
	//			"B": {Source: "A", Target: "B"},
	//			"C": {Source: "A", Target: "C"},
	//		},
	//		"B": map[string]Edge[string]{},
	//		"C": map[string]Edge[string]{},
	//	}
	//
	// This design makes AdjacencyMap suitable for a wide variety of algorithms.
	AdjacencyMap() (map[K]map[K]Edge[K], error)

	// PredecessorMap computes a predecessor map with all vertices in the graph.
	//
	// It has the same map layout and does the same thing as AdjacencyMap, but
	// for ingoing instead of outgoing edges of each vertex.
	//
	// For a directed graph with two edges AB and AC, PredecessorMap would
	// return the following map:
	//
	//	map[string]map[string]Edge[string]{
	//		"A": map[string]Edge[string]{},
	//		"B": map[string]Edge[string]{
	//			"A": {Source: "A", Target: "B"},
	//		},
	//		"C": map[string]Edge[string]{
	//			"A": {Source: "A", Target: "C"},
	//		},
	//	}
	//
	// For an undirected graph, PredecessorMap is the same as AdjacencyMap. This
	// is because there is no distinction between "outgoing" and "ingoing" edges
	// in an undirected graph.
	PredecessorMap() (map[K]map[K]Edge[K], error)

	// Clone creates a deep copy of the graph and returns that cloned graph.
	//
	// The cloned graph will use the default in-memory store for storing the
	// vertices and edges. If you want to utilize a custom store instead, create
	// a new graph using NewWithStore and use AddVerticesFrom and AddEdgesFrom.
	Clone() (Graph[K, T], error)

	// Order returns the number of vertices in the graph.
	Order() (int, error)

	// Size returns the number of edges in the graph.
	Size() (int, error)
}

Graph represents a generic graph data structure consisting of vertices of type T identified by a hash of type K.

func MaximumSpanningTree

func MaximumSpanningTree[K comparable, T any](g Graph[K, T]) (Graph[K, T], error)

MaximumSpanningTree returns a minimum spanning tree within the given graph.

The MST contains all vertices from the given graph as well as the required edges for building the MST. The original graph remains unchanged.

func MinimumSpanningTree

func MinimumSpanningTree[K comparable, T any](g Graph[K, T]) (Graph[K, T], error)

MinimumSpanningTree returns a minimum spanning tree within the given graph.

The MST contains all vertices from the given graph as well as the required edges for building the MST. The original graph remains unchanged.

func New

func New[K comparable, T any](hash Hash[K, T], options ...func(*Traits)) Graph[K, T]

New creates a new graph with vertices of type T, identified by hash values of type K. These hash values will be obtained using the provided hash function.

The graph will use the default in-memory store for persisting vertices and edges. To use a different Store, use NewWithStore.

func NewLike

func NewLike[K comparable, T any](g Graph[K, T]) Graph[K, T]

NewLike creates a graph that is "like" the given graph: It has the same type, the same hashing function, and the same traits. The new graph is independent of the original graph and uses the default in-memory storage.

g := graph.New(graph.IntHash, graph.Directed())
h := graph.NewLike(g)

In the example above, h is a new directed graph of integers derived from g.

func NewWithStore

func NewWithStore[K comparable, T any](hash Hash[K, T], store Store[K, T], options ...func(*Traits)) Graph[K, T]

NewWithStore creates a new graph same as New but uses the provided store instead of the default memory store.

func TransitiveReduction

func TransitiveReduction[K comparable, T any](g Graph[K, T]) (Graph[K, T], error)

TransitiveReduction returns a new graph with the same vertices and the same reachability as the given graph, but with as few edges as possible. The graph must be a directed acyclic graph.

TransitiveReduction is a very expensive operation scaling with O(V(V+E)).

func Union

func Union[K comparable, T any](g, h Graph[K, T]) (Graph[K, T], error)

Union combines two given graphs into a new graph. The vertex hashes in both graphs are expected to be unique. The two input graphs will remain unchanged.

Both graphs should be either directed or undirected. All traits for the new graph will be derived from g.

type Hash

type Hash[K comparable, T any] func(T) K

Hash is a hashing function that takes a vertex of type T and returns a hash value of type K.

Every graph has a hashing function and uses that function to retrieve the hash values of its vertices. You can either use one of the predefined hashing functions or provide your own one for custom data types:

cityHash := func(c City) string {
	return c.Name
}

The cityHash function returns the city name as a hash value. The types of T and K, in this case City and string, also define the types of the graph.

type Store

type Store[K comparable, T any] interface {
	// AddVertex should add the given vertex with the given hash value and vertex properties to the
	// graph. If the vertex already exists, it is up to you whether ErrVertexAlreadyExists or no
	// error should be returned.
	AddVertex(hash K, value T, properties VertexProperties) error

	// Vertex should return the vertex and vertex properties with the given hash value. If the
	// vertex doesn't exist, ErrVertexNotFound should be returned.
	Vertex(hash K) (T, VertexProperties, error)

	// RemoveVertex should remove the vertex with the given hash value. If the vertex doesn't
	// exist, ErrVertexNotFound should be returned. If the vertex has edges to other vertices,
	// ErrVertexHasEdges should be returned.
	RemoveVertex(hash K) error

	// ListVertices should return all vertices in the graph in a slice.
	ListVertices() ([]K, error)

	// VertexCount should return the number of vertices in the graph. This should be equal to the
	// length of the slice returned by ListVertices.
	VertexCount() (int, error)

	// AddEdge should add an edge between the vertices with the given source and target hashes.
	//
	// If either vertex doesn't exit, ErrVertexNotFound should be returned for the respective
	// vertex. If the edge already exists, ErrEdgeAlreadyExists should be returned.
	AddEdge(sourceHash, targetHash K, edge Edge[K]) error

	// UpdateEdge should update the edge between the given vertices with the data of the given
	// Edge instance. If the edge doesn't exist, ErrEdgeNotFound should be returned.
	UpdateEdge(sourceHash, targetHash K, edge Edge[K]) error

	// RemoveEdge should remove the edge between the vertices with the given source and target
	// hashes.
	//
	// If either vertex doesn't exist, it is up to you whether ErrVertexNotFound or no error should
	// be returned. If the edge doesn't exist, it is up to you whether ErrEdgeNotFound or no error
	// should be returned.
	RemoveEdge(sourceHash, targetHash K) error

	// Edge should return the edge joining the vertices with the given hash values. It should
	// exclusively look for an edge between the source and the target vertex, not vice versa. The
	// graph implementation does this for undirected graphs itself.
	//
	// Note that unlike Graph.Edge, this function is supposed to return an Edge[K], i.e. an edge
	// that only contains the vertex hashes instead of the vertices themselves.
	//
	// If the edge doesn't exist, ErrEdgeNotFound should be returned.
	Edge(sourceHash, targetHash K) (Edge[K], error)

	// ListEdges should return all edges in the graph in a slice.
	ListEdges() ([]Edge[K], error)
}

Store represents a storage for vertices and edges. The graph library provides an in-memory store by default and accepts any Store implementation to work with - for example, an SQL store.

When implementing your own Store, make sure the individual methods and their behavior adhere to this documentation. Otherwise, the graphs aren't guaranteed to behave as expected.

type Traits

type Traits struct {
	IsDirected    bool
	IsAcyclic     bool
	IsWeighted    bool
	IsRooted      bool
	PreventCycles bool
}

Traits represents a set of graph traits and types, such as directedness or acyclicness. These traits can be set when creating a graph by passing the corresponding functional options, for example:

g := graph.New(graph.IntHash, graph.Directed())

This will set the IsDirected field to true.

type VertexProperties

type VertexProperties struct {
	Attributes map[string]string
	Weight     int
}

VertexProperties represents a set of properties that each vertex has. They can be set when adding a vertex using the corresponding functional options:

_ = g.AddVertex("A", "B", graph.VertexWeight(2), graph.VertexAttribute("color", "red"))

The example above will create a vertex with a weight of 2 and an attribute "color" with value "red".