A library for creating generic graph data structures and modifying, analyzing, and visualizing them.
- Generic vertices of any type, such as
intorCity. - 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.
- Extensive tests with ~90% coverage, and zero dependencies.
Status: Because
graphis in version 0, the public API shouldn't be considered stable.
This README may contain unreleased changes. Check out the latest documentation.
go get github.com/dominikbraun/graph
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)
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)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)
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))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
g := graph.New(graph.IntHash)
// Add vertices and edges ...
scc, _ := graph.StronglyConnectedComponents(g)
fmt.Println(scc)[[1 2 5] [3 4 8] [6 7]]
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]
g := graph.New(graph.IntHash, graph.Directed(), graph.PreventCycles())
// Add vertices and edges ...
order, _ := graph.TopologicalSort(g)
fmt.Println(order)[1 2 3 4 5]
g := graph.New(graph.StringHash, graph.Directed(), graph.PreventCycles())
// Add vertices and edges ...
_ := graph.TransitiveReduction(g)
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
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
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.
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"), graph.VertexAttribute("fillcolor", "red"))To get an overview of all supported attributes, take a look at the DOT documentation.
A graph consists of nodes (or vertices) of type T, which are identified by a hash value of type
K. The hash value is obtained using the hashing function passed to graph.New.
For primitive types such as string or int, you may use a predefined hashing function such as
graph.IntHash – a function that takes an integer and uses it as a hash value at the same time:
g := graph.New(graph.IntHash)This also means that only one vertex with a value like
5can exist in the graph ifgraph.IntHashused.
For storing custom data types, you need to provide your own hashing function. This example function
takes a City and returns the city name as an unique hash value:
cityHash := func(c City) string {
return c.Name
}Creating a graph using this hashing function will yield a graph with vertices of type City
identified by hash values of type string.
g := graph.New(cityHash)The behavior of a graph, for example when adding or retrieving edges, depends on its traits. You can set the graph's traits using the functional options provided by this library:
g := graph.New(graph.IntHash, graph.Directed(), graph.Weighted())The full documentation is available at pkg.go.dev.