DEV Community

Cover image for graph: A library for creating generic graph data structures and modifying, analyzing, and visualizing them.
DB
DB

Posted on

graph: A library for creating generic graph data structures and modifying, analyzing, and visualizing them.

#showdev #go #algorithms #computerscience

graph is a Go library for creating generic graph data structures and modifying, analyzing, and visualizing them.

Features

  • Generic vertices of any type, such as int or City.
  • 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.
  • 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 graph is in version 0, the public API shouldn't be considered stable.

Getting started 

go get github.com/dominikbraun/graph
Enter fullscreen mode Exit fullscreen mode

Quick examples

Create a graph of integers 

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)
Enter fullscreen mode Exit fullscreen mode

Create a directed acyclic graph of integers 

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)
Enter fullscreen mode Exit fullscreen mode

Create a graph of a custom type

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)
Enter fullscreen mode Exit fullscreen mode

Create a weighted graph 

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))
Enter fullscreen mode Exit fullscreen mode

Perform a Depth-First Search

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 })
Enter fullscreen mode Exit fullscreen mode 
1 3 4 2
Enter fullscreen mode Exit fullscreen mode

Find strongly connected components 

g := graph.New(graph.IntHash) // Add vertices and edges ... scc, _ := graph.StronglyConnectedComponents(g) fmt.Println(scc)
Enter fullscreen mode Exit fullscreen mode 
[[1 2 5] [3 4 8] [6 7]]
Enter fullscreen mode Exit fullscreen mode

Find the shortest path 

g := graph.New(graph.StringHash, graph.Weighted()) // Add vertices and weighted edges ... path, _ := graph.ShortestPath(g, "A", "B") fmt.Println(path)
Enter fullscreen mode Exit fullscreen mode 
[A C E B]
Enter fullscreen mode Exit fullscreen mode

Perform a topological sort 

g := graph.New(graph.IntHash, graph.Directed(), graph.Acyclic()) // Add vertices and weighted edges ... order, _ := graph.TopologicalSort(g) fmt.Println(order)
Enter fullscreen mode Exit fullscreen mode 
[1 2 3 4 5]
Enter fullscreen mode Exit fullscreen mode

Cycle checks for acyclic graphs 

g := graph.New(graph.IntHash, graph.Acyclic()) 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) }
Enter fullscreen mode Exit fullscreen mode 
panic: an edge between 2 and 3 would introduce a cycle
Enter fullscreen mode Exit fullscreen mode

Visualize a graph using Graphviz

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)
Enter fullscreen mode Exit fullscreen mode

To generate an SVG from the created file using Graphviz, use a command such as the following:

dot -Tsvg -O mygraph.gv
Enter fullscreen mode Exit fullscreen mode

Setting edge attributes

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"))
Enter fullscreen mode Exit fullscreen mode

To get an overview of all supported attributes, take a look at the
DOT documentation.

Concepts

Hashes

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.

Primitive types

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)
Enter fullscreen mode Exit fullscreen mode

This also means that only one vertex with a value like 5 can exist in the graph if
graph.IntHash used.

Custom types

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 }
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

Traits

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())
Enter fullscreen mode Exit fullscreen mode

Documentation

The full documentation is available at pkg.go.dev.

Check out graph on GitHub: dominikbraun/graph

Top comments (0)