graph

README

A 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

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)

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)

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)

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))

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
})

1 3 4 2

Find strongly connected components

g := graph.New(graph.IntHash)

// Add vertices and edges ...

scc, _ := graph.StronglyConnectedComponents(g)

fmt.Println(scc)

[[1 2 5] [3 4 8] [6 7]]

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)

[A C E B]

Perform a topological sort

g := graph.New(graph.IntHash, graph.Directed(), graph.PermitCycles())

// Add vertices and edges ...

order, _ := graph.TopologicalSort(g)

fmt.Println(order)

[1 2 3 4 5]

Perform a transitive reduction

g := graph.New(graph.StringHash, graph.Directed(), graph.PermitCycles())

// Add vertices and edges ...

_ := graph.TransitiveReduction(g)

Prevent the creation of cycles

g := graph.New(graph.IntHash, graph.PermitCycles())

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

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)

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

dot -Tsvg -O mygraph.gv

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"))

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)

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
}

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)

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())

Documentation

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

Documentation

Index

• Variables
• func Acyclic() func(*Traits)
• func BFS[K comparable, T any](g Graph[K, T], start K, visit func(K) 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 EdgeWeight(weight int) func(*EdgeProperties)
• func IntHash(v int) int
• func PermitCycles() func(*Traits)
• 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 TopologicalSort[K comparable, T any](g Graph[K, T]) ([]K, error)
• func TransitiveReduction[K comparable, T any](g Graph[K, T]) error
• func Tree() func(*Traits)
• func Weighted() func(*Traits)
• type Edge
• type EdgeProperties
• type Graph
  • func New[K comparable, T any](hash Hash[K, T], options ...func(*Traits)) Graph[K, T]
• type Hash
• type Traits

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. Note that creating edges that form a cycle will still be possible. To prevent this explicitly, use PermitCycles.

func BFS

func BFS[K comparable, T any](g Graph[K, T], start K, visit func(K) bool) error

BFS 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, 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 CreatesCycle

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

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

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

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

func IntHash(v int) int

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 PermitCycles

func PermitCycles() func(*Traits)

PermitCycles creates an acyclic graph that permits 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

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

func StringHash(v string) string

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

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.

func TopologicalSort

func TopologicalSort[K comparable, T any](g Graph[K, T]) ([]K, error)

TopologicalSort performs a topological sort on a given graph and returns the vertex hashes in topological order. A topological order is a non-unique order of the vertices in a directed graph where an edge from vertex A to vertex B implies that vertex A appears before vertex B.

TopologicalSort only works for directed acyclic graphs. The current implementation works non- recursively and uses Kahn's algorithm.

func TransitiveReduction

func TransitiveReduction[K comparable, T any](g Graph[K, T]) error

TransitiveReduction transforms the graph into its own transitive reduction. The transitive reduction of the given graph is another graph with the same vertices and the same reachability, but with as few edges as possible. This greatly reduces the complexity of the graph.

With a time complexity of O(V(V+E)), TransitiveReduction is a very costly operation.

func Tree

func Tree() func(*Traits)

Tree is an alias for Acyclic and Rooted, since most trees in Computer Science are rooted trees.

func Weighted

func Weighted() func(*Traits)

Weighted creates a weighted graph. To set weights, use the Edge and AddEdge functions.

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

type EdgeProperties struct {
	Attributes map[string]string
	Weight     int
}

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)

	// RemoveEdge removes the edge between the given source and target vertices. If the edge doesn't
	// exist, ErrEdgeNotFound will be returned.
	RemoveEdge(source, target K) 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: "C"}
	//		}
	//	}
	//
	// This design makes AdjacencyMap suitable for a wide variety of scenarios and demands.
	AdjacencyMap() (map[K]map[K]Edge[K], error)

	// PredecessorMap computes and returns a predecessors map containing all vertices in the graph.
	//
	// The map layout is the same as for Adjacencies.
	//
	// For an undirected graph, PredecessorMap is the same as AdjacencyMap. For a directed graph,
	// PredecessorMap is the complement of AdjacencyMap. This is because in a directed graph, only
	// vertices joined by an outgoing edge are considered adjacent to the current vertex, whereas
	// predecessors are the vertices joined by an ingoing edge.
	PredecessorMap() (map[K]map[K]Edge[K], error)

	// Clone creates an independent deep copy of the graph and returns that cloned graph.
	Clone() (Graph[K, T], error)

	// Order computes and returns the number of vertices in the graph.
	Order() int

	// Size computes and returns the number of edges in the graph.
	Size() int
}

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

type Traits struct {
	IsDirected   bool
	IsAcyclic    bool
	IsWeighted   bool
	IsRooted     bool
	PermitCycles 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.