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 graph.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 graph.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.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.AddEdge] creates an edge between two vertices and accepts the hash values of those vertices. Because this graph uses the graph.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.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 BFS[K comparable, T any](g Graph[K, T], start K, visit func(K) 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 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 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 VertexWeight(weight int) func(*VertexProperties)
- func Weighted() func(*Traits)
- type Edge
- type EdgeProperties
- type Graph
- type Hash
- type Store
- type Traits
- type VertexProperties
Constants ¶
This section is empty.
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") )
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 BFS ¶ added in v0.9.0
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 CreatesCycle ¶ added in v0.9.0
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 ¶ added in v0.9.0
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 ¶ added in v0.8.0
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.Edge] and [Graph.AddEdge] methods.
func EdgeData ¶ added in v0.16.0
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.Edge] and [Graph.AddEdge] methods.
func EdgeWeight ¶ added in v0.8.0
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.Edge] and [Graph.AddEdge] methods.
func IntHash ¶
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 ¶ added in v0.13.0
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 ¶ added in v0.9.0
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 StringHash ¶
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 ¶ added in v0.9.0
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 ¶ added in v0.10.0
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.
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 ¶ added in v0.13.0
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.Vertex] and [Graph.AddVertex] methods.
func VertexWeight ¶ added in v0.13.0
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.Vertex] and [Graph.AddVertex] methods.
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 ¶ added in v0.8.0
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 // 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) // 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 // 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) // 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. 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 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 graph.Store, use graph.NewWithStore.
func NewWithStore ¶ added in v0.16.0
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 ¶ added in v0.10.0
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)).
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 ¶ added in v0.16.0
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) // 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 // 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 ¶ added in v0.7.0
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 ¶ added in v0.13.0
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".