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
}