Involved Source Filescollection.godag.godirected.go 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.paths.gosets.gostore.gotraits.gotraversal.gotrees.goundirected.go
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".Attributesmap[string]stringDataanyWeightint
Type Parameters:
K: comparable
T: any Graph represents a generic graph data structure consisting of vertices of
type T identified by a hash of type K. 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")) 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. 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")) 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. 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. 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. 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. 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. Order returns the number of vertices in the graph. 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. RemoveEdge removes the edge between the given source and target vertices.
If the edge cannot be found, ErrEdgeNotFound will be returned. 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. Size returns the number of edges in the graph. Traits returns the graph's traits. Those traits must be set when creating
a graph using New. 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. Vertex returns the vertex with the given hash or ErrVertexNotFound if it
doesn't exist. VertexWithProperties returns the vertex with the given hash along with
its properties or ErrVertexNotFound if it doesn't exist.
func MaximumSpanningTree[K, T](g Graph[K, T]) (Graph[K, T], error)
func MinimumSpanningTree[K, T](g Graph[K, T]) (Graph[K, T], error)
func New[K, T](hash Hash[K, T], options ...func(*Traits)) Graph[K, T]
func NewLike[K, T](g Graph[K, T]) Graph[K, T]
func NewWithStore[K, T](hash Hash[K, T], store Store[K, T], options ...func(*Traits)) Graph[K, T]
func TransitiveReduction[K, T](g Graph[K, T]) (Graph[K, T], error)
func Union[K, T](g, h Graph[K, T]) (Graph[K, T], error)
func Graph[K, T].Clone() (Graph[K, T], error)
func AllPathsBetween[K, T](g Graph[K, T], start, end K) ([][]K, error)
func BFS[K, T](g Graph[K, T], start K, visit func(K) bool) error
func BFSWithDepth[K, T](g Graph[K, T], start K, visit func(K, int) bool) error
func CreatesCycle[K, T](g Graph[K, T], source, target K) (bool, error)
func DFS[K, T](g Graph[K, T], start K, visit func(K) bool) error
func MaximumSpanningTree[K, T](g Graph[K, T]) (Graph[K, T], error)
func MinimumSpanningTree[K, T](g Graph[K, T]) (Graph[K, T], error)
func NewLike[K, T](g Graph[K, T]) Graph[K, T]
func ShortestPath[K, T](g Graph[K, T], source, target K) ([]K, error)
func StableTopologicalSort[K, T](g Graph[K, T], less func(K, K) bool) ([]K, error)
func StronglyConnectedComponents[K, T](g Graph[K, T]) ([][]K, error)
func TopologicalSort[K, T](g Graph[K, T]) ([]K, error)
func TransitiveReduction[K, T](g Graph[K, T]) (Graph[K, T], error)
func Union[K, T](g, h Graph[K, T]) (Graph[K, T], error)
func Graph[K, T].AddEdgesFrom(g Graph[K, T]) error
func Graph[K, T].AddVerticesFrom(g Graph[K, T]) error
Type Parameters:
K: comparable
T: any 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.
func New[K, T](hash Hash[K, T], options ...func(*Traits)) Graph[K, T]
func NewWithStore[K, T](hash Hash[K, T], store Store[K, T], options ...func(*Traits)) Graph[K, T]
Type Parameters:
K: comparable
T: any 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. 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. 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. 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. ListEdges should return all edges in the graph in a slice. ListVertices should return all vertices in the graph in a slice. 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. 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. 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. Vertex should return the vertex and vertex properties with the given hash value. If the
vertex doesn't exist, ErrVertexNotFound should be returned. VertexCount should return the number of vertices in the graph. This should be equal to the
length of the slice returned by ListVertices.
func NewWithStore[K, T](hash Hash[K, T], store Store[K, T], options ...func(*Traits)) Graph[K, T]
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.IsAcyclicboolIsDirectedboolIsRootedboolIsWeightedboolPreventCyclesbool
func Graph.Traits() *Traits
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".Attributesmap[string]stringWeightint
func Graph.VertexWithProperties(hash K) (T, VertexProperties, error)
func Store.Vertex(hash K) (T, VertexProperties, error)
func Store.AddVertex(hash K, value T, properties VertexProperties) error
Package-Level Functions (total 31)
Acyclic creates an acyclic graph. Note that creating edges that form a cycle will still be
possible. To prevent this explicitly, use PreventCycles.
Type Parameters:
K: comparable
T: any 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.
Type Parameters:
K: comparable
T: any 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.
Type Parameters:
K: comparable
T: any 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.
Type Parameters:
K: comparable
T: any 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.
Type Parameters:
K: comparable
T: any 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.
Directed creates a directed graph. This has implications on graph traversal and the order of
arguments of the Edge and AddEdge functions.
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.
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.
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.
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.
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].
Type Parameters:
K: comparable
T: any 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.
Type Parameters:
K: comparable
T: any 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.
Type Parameters:
K: comparable
T: any 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].
Type Parameters:
K: comparable
T: any 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.
Type Parameters:
K: comparable
T: any NewWithStore creates a new graph same as [New] but uses the provided store
instead of the default memory store.
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.
Rooted creates a rooted graph. This is particularly common for building tree data structures.
Type Parameters:
K: comparable
T: any 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|)).
Type Parameters:
K: comparable
T: any 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.
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].
Type Parameters:
K: comparable
T: any 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.
Type Parameters:
K: comparable
T: any 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.
Type Parameters:
K: comparable
T: any 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)).
Tree is an alias for Acyclic and Rooted, since most trees in Computer Science are rooted trees.
Type Parameters:
K: comparable
T: any 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.
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.
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.
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.
Weighted creates a weighted graph. To set weights, use the Edge and AddEdge functions.
The pages are generated with Goldsv0.8.2. (GOOS=linux GOARCH=amd64)
Golds is a Go 101 project developed by Tapir Liu.
PR and bug reports are welcome and can be submitted to the issue list.
Please follow @zigo_101 (reachable from the left QR code) to get the latest news of Golds.
