zig-graph

A Zig library for directed graph data structures and associated algorithms. This library can be used for acyclic and cyclic graphs and unweighted and weighted edges. This library requires Zig 0.9+.

Warning: This is literally the first piece of Zig code I've ever written in my life. I'm using this project as a way to learn how to do things in Zig, what is idiomatic, what isn't, etc. Feedback is very welcome on how I can improve and I expect to alter the library a bit as I do so. There is also a lot of room for improvement in performance by various measures.

Features

• Directed edges
• Cycle detection
• Strongly connected components
• Cheap edge reversal
• Depth-first traversal

TODO

• Vertex iterator
• Edge iterator
• Dijkstra for single-source shortest path w/ edge-weighting
• Kahn for topological sorting
• Shortest path given a topological sort
• String marshaling for easier debugging
• "Unmanaged" graph so allocator can be sent to each op

Example

const std = @import("std");
const graph = @import("graph");

pub fn main() void {
	// Create a directed graph type for strings.
	const Graph = graph.DirectedGraph([]const u8, std.hash_map.StringContext);

	// Initialize using some allocator
	var g = Graph.init(std.debug.global_allocator);
	defer g.deinit();

	// Add some vertices
	try g.add("A");
	try g.add("B");
	try g.add("C");

	// Add some edges with weights. For unweighted edges just make all
	// weights the same value.
	try g.addEdge("A", "B", 5);
	try g.addEdge("A", "C", 2);
	try g.addEdge("B", "C", 2);
	try g.addEdge("C", "B", 3);

	// We can detect cycles
	if (g.cycles()) |cycles| {
		defer cycles.deinit();
		std.log.info("there are {d} cycles", .{cycles.count()});
		return;
	}

	// We can do a depth-first search through iteration.
	var dfsIter = try g.dfsIterator("B");
	while (dfsIter.next()) |id| {
		std.log.info("{}", .{g.lookup(id).?});
	}
	dfsIter.deinit();

	// We can easily reverse the graph if we want.
	const reversed = g.reverse();

	// ... and more
}