Documentation ¶
Index ¶
- Variables
- func Acyclic() func(*Traits)
- func BFS[K comparable, T any](g Graph[K, T], start K, visit func(T) 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(T) bool) error
- func Directed() func(*Traits)
- func EdgeAttribute(key, value string) func(*EdgeProperties)
- func EdgeWeight(weight int) func(*EdgeProperties)
- func IntHash(v int) int
- 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 Tree() func(*Traits)
- func Weighted() func(*Traits)
- type Edge
- type EdgeProperties
- type Graph
- type Hash
- type Traits
Constants ¶
This section is empty.
Variables ¶
var ErrEdgeNotFound = errors.New("edge not found")
ErrEdgeNotFound will be returned when a desired edge cannot be found.
Functions ¶
func Acyclic ¶
func Acyclic() func(*Traits)
Acyclic creates an acyclic graph, which won't allow adding directed edges resulting in a cycle.
func BFS ¶ added in v0.9.0
func BFS[K comparable, T any](g Graph[K, T], start K, visit func(T) bool) error
BFS performs a Breadth-First Search on the graph, starting from the given vertex. The visit function will be invoked for each visited vertex. If it returns false, BFS will continue traversing the path, and if it returns true, the traversal will be stopped. In case the graph is disconnected, only the vertices joined with the starting vertex will be traversed.
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 an edge between the given source and target vertices would introduce a cycle. It won't create that edge in any case.
A potential edge would create a cycle if the target vertex is also a parent of the source vertex. Given a graph A-B-C-D, adding an edge DA would introduce a cycle:
A - | | B | | | C | | | D -
CreatesCycle backtracks the ingoing edges of D, resulting in a reverse walk C-B-A.
func DFS ¶ added in v0.9.0
func DFS[K comparable, T any](g Graph[K, T], start K, visit func(T) bool) error
DFS performs a depth-first search on the graph, starting from the given vertex. The visit function will be invoked for each visited vertex. If it returns false, DFS will continue traversing the path, and if it returns true, the traversal will be stopped. In case the graph is disconnected, only the vertices joined with the starting vertex will be traversed.
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 Edge and 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 Edge and 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 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 using the edge weights and returns the hash values of the vertices forming that path. This search runs in O(|V|+|E|log(|V|)) time.
The returned path includes the source and target vertices. If the target cannot be reached from the source vertex, ShortestPath returns an error. If there are multiple shortest paths, an arbitrary one will be returned.
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 given graph and returns the hashes of the vertices shaping these components, so each component is a []K.
The current implementation uses Tarjan's algorithm and runs recursively.
Types ¶
type Edge ¶
type Edge[T any] struct { Source T Target T Properties EdgeProperties }
Edge represents a graph edge with a source and target vertex as well as a weight, which has the same value for all edges in an unweighted graph. Even though the vertices are 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 functional options provided by this library:
g.Edge("A", "B", graph.EdgeWeight(2), graph.EdgeAttribute("color", "red"))
The example above will create an edge with weight 2 and a "color" attribute 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, which won't be connected to another vertex yet. // // Whether AddVertex is idempotent depends on the underlying vertex store implementation. By // default, when using the in-memory store, an existing vertex will be overwritten, whereas // other stores might return an error. AddVertex(value T) error // Vertex returns the vertex with the given hash or an error if the vertex doesn't exist. Vertex(hash K) (T, error) // AddEdge creates an edge between the source and the target vertex. If the Directed option has // been called on the graph, this is a directed edge. Returns an error if either vertex doesn't // exist or the edge already exists. // // AddEdge accepts a variety of functional options to set further edge details such as the // weight or an attribute: // // _ = graph.Edge("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 an error 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) // AdjacencyMap computes and returns an adjacency map containing all vertices in the graph. // // There is an entry for each vertex, and 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 (these are the same as the map keys) as well as edge metadata. // // For a graph with edges AB and AC, the adjacency map would look as follows: // // map[string]map[string]Edge[string]{ // "A": map[string]Edge[string]{ // "B": {Source: "A", Target: "B"} // "C": {Source: "A", Target: "B"} // } // } // // This design makes AdjacencyMap suitable for a wide variety of scenarios and demands. AdjacencyMap() (map[K]map[K]Edge[K], error) // Predecessors determines and returns the predecessors of the vertex with the given hash. // // In a directed graph, these are the directed predecessors with an outgoing edge to the given // edge whereas in an undirected graph, all adjacent vertices are considered as predecessors. // // Consequently, Predecessors returns a subset of AdjacencyMap for the given vertex. Predecessors(vertex K) (map[K]Edge[K], error) }
Graph represents a generic graph data structure consisting of vertices and edges. Its vertices are of type T, and each vertex is 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 (see Hash).
For primitive vertex values, you may use the predefined hashing functions. As an example, this graph stores integer vertices:
g := graph.New(graph.IntHash) g.AddVertex(1) g.AddVertex(2) g.AddVertex(3)
The provided IntHash hashing function takes an integer and uses it as a hash value at the same time. In a more complex scenario with custom objects, you should define your own function:
type City struct { Name string } cityHash := func(c City) string { return c.Name } g := graph.New(cityHash) g.AddVertex(london)
This graph will store vertices of type City, identified by hashes of type string. Both type parameters can be inferred from the hashing function.
All traits of the graph can be set using the predefined functional options. They can be combined arbitrarily. This example creates a directed acyclic graph:
g := graph.New(graph.IntHash, graph.Directed(), graph.Acyclic())
Which Graph implementation will be returned depends on these traits.
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, if you want to store a custom data type, provide your own function:
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 T and K of the graph.
type Traits ¶ added in v0.7.0
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.