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
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") 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 ¶ added in v0.23.0
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 ¶ 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 BFSWithDepth ¶ added in v0.21.0
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 ¶ 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.Graph.Edge and graph.Graph.AddEdge methods.
func EdgeAttributes ¶ added in v0.20.0
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 ¶ 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.Graph.Edge and graph.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.Graph.Edge and graph.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 StableTopologicalSort ¶ added in v0.22.0
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 ¶
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.
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 ¶ 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.Graph.Vertex and graph.Graph.AddVertex methods.
func VertexAttributes ¶ added in v0.22.0
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 ¶ 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.Graph.Vertex and graph.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 // 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 ¶ added in v0.19.0
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 ¶ added in v0.19.0
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 ¶ added in v0.20.0
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 ¶ 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)).
func Union ¶ added in v0.18.0
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 ¶ 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) // 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 ¶ 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".