You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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
conststd=@import("std");
constgraph=@import("graph");
pubfnmain() void {
// Create a directed graph type for strings.constGraph=graph.DirectedGraph([]constu8, std.hash_map.StringContext);
// Initialize using some allocatorvarg=Graph.init(std.debug.global_allocator);
deferg.deinit();
// Add some verticestryg.add("A");
tryg.add("B");
tryg.add("C");
// Add some edges with weights. For unweighted edges just make all// weights the same value.tryg.addEdge("A", "B", 5);
tryg.addEdge("A", "C", 2);
tryg.addEdge("B", "C", 2);
tryg.addEdge("C", "B", 3);
// We can detect cyclesif (g.cycles()) |cycles| {
defercycles.deinit();
std.log.info("there are {d} cycles", .{cycles.count()});
return;
}
// We can do a depth-first search through iteration.vardfsIter=tryg.dfsIterator("B");
while (dfsIter.next()) |id| {
std.log.info("{}", .{g.lookup(id).?});
}
dfsIter.deinit();
// We can easily reverse the graph if we want.constreversed=g.reverse();
// ... and more
}