ZGraph

ZGraph is a high-performance, in-memory graph library with:

• Pluggable storages: adjacency list, adjacency matrix, incidence matrix.
• Compile-time graph semantics: directed / undirected, weighted / unweighted.
• Unified algorithms that operate across storages via a common trait surface.
• Portable formats:
  • .zgraph – human-readable, human-writable
  • .zgraphb – compressed, chunked binary for fast I/O / mmap
• Robust conversion strategies (duplicate, streamed, chunked, copy-on-write) to switch layouts under tight memory budgets.

ZGraphDB (paged container) builds on the same chunks and APIs; algorithms continue to live in ZGraph.

Status

• ✅ Core storages compile and pass tests on Zig 0.16.
• ✅ AdjacencyList, AdjacencyMatrix, IncidenceMatrix with CRUD + neighbor ops.
• ✅ .zgraph / .zgraphb specifications documented; parsers/writers in progress.
• 🚧 Conversion strategies module & CLI utilities.

See ZGraph.Spec.md for the canonical checklist and roadmap.

Install

zig build test
zig build run

Zig: 0.16.x

Quick start

const GS = @import("src/lib/core/graph_storage.zig").GraphStorage;
const Storage = GS(.AdjacencyList, true, true); // directed, weighted

var g = Storage.init(std.heap.page_allocator);
defer g.deinit();

try g.addEdge(0, 1, 3.5);
try g.addEdge(1, 1, 7.5);

if (g.getNeighbors(0)) |edges| {
    // ...
}

Convert storage (e.g., list → matrix) with a memory budget

const conv = @import("src/lib/conversion/strategies.zig");
var dst = try conv.convertStorage(
    std.heap.page_allocator,
    Storage,                             // source type
    .AdjacencyMatrix, true, true,        // dest type + semantics
    &g,
    .Streamed,                           // strategy
    .{ .max_bytes_in_flight = 4 * 1024 * 1024 * 1024 }, // 4 GiB
);
defer dst.deinit();

Import / Export

# text -> binary
zig build run -- convert --in graph.zgraph --out graph.zgraphb

# validate and print stats
zig build run -- stats --in graph.zgraphb

Design pillars

• Predictable performance: zero-copy views, cache-friendly CSR, zstd block compression.
• Compatibility: readers ignore unknown chunks; text & binary round-trip.
• Safety: memory ownership is explicit; threads guarded by mutexes where needed.
• Tested: unit, property, and fuzz tests; algorithm parity across storages.

Repo layout (idealized)

ZGraph/
├─ README.md
├─ ZGraph.Spec.md                  # Source of truth (feature checklist)
├─ LICENSE
├─ build.zig
├─ zig.mod
├─ docs/
│  ├─ formats/
│  │  ├─ zgraph-text-spec.md
│  │  └─ zgraphb-binary-spec.md
│  ├─ algorithms/
│  │  ├─ traversal.md
│  │  ├─ shortest_paths.md
│  │  ├─ connectivity.md
│  │  ├─ flow_cut.md
│  │  ├─ centrality.md
│  │  └─ spectral.md
│  ├─ storage_design.md
│  ├─ conversion_strategies.md
│  ├─ perf_tuning.md
│  ├─ safety_and_threading.md
│  └─ roadmap.md
├─ examples/
│  ├─ tiny/
│  │  ├─ triangle.zgraph
│  │  ├─ weighted_digraph.zgraph
│  │  └─ attributes.zgraph
│  ├─ conversions/
│  │  ├─ list_to_matrix.zig
│  │  └─ streamed_live_convert.zig
│  └─ cli/
│     ├─ import_export.zig
│     └─ metrics.zig
├─ src/
│  ├─ root.zig
│  ├─ lib/
│  │  ├─ core/
│  │  │  ├─ node.zig
│  │  │  ├─ edge.zig
│  │  │  ├─ graph_storage.zig
│  │  │  ├─ iterators.zig
│  │  │  └─ attributes.zig
│  │  ├─ data_structures/
│  │  │  ├─ adjacency_list.zig
│  │  │  ├─ adjacency_matrix.zig
│  │  │  └─ incidence_matrix.zig
│  │  ├─ formats/
│  │  │  ├─ zgraph_text.zig
│  │  │  ├─ zgraphb.zig
│  │  │  └─ chunk_provider.zig
│  │  ├─ conversion/
│  │  │  ├─ strategies.zig
│  │  │  ├─ duplicate_convert.zig
│  │  │  ├─ streamed_convert.zig
│  │  │  ├─ chunked_convert.zig
│  │  │  └─ cow_convert.zig
│  │  ├─ indices/
│  │  │  ├─ csr.zig
│  │  │  └─ degree_table.zig
│  │  ├─ algorithms/
│  │  │  ├─ traversal/
│  │  │  │  ├─ bfs.zig
│  │  │  │  └─ dfs.zig
│  │  │  ├─ shortest_paths/
│  │  │  │  ├─ dijkstra.zig
│  │  │  │  ├─ bellman_ford.zig
│  │  │  │  └─ floyd_warshall.zig
│  │  │  ├─ connectivity/
│  │  │  │  ├─ union_find.zig
│  │  │  │  └─ strongly_connected.zig
│  │  │  ├─ flow_cut/
│  │  │  │  ├─ edmonds_karp.zig
│  │  │  │  └─ dinic.zig
│  │  │  ├─ centrality/
│  │  │  │  ├─ pagerank.zig
│  │  │  │  └─ betweenness.zig
│  │  │  └─ spectral/
│  │  │     ├─ laplacian.zig
│  │  │     └─ power_iteration.zig
│  │  ├─ io/
│  │  │  ├─ file.zig
│  │  │  ├─ csv.zig
│  │  │  └─ zstd.zig
│  │  ├─ mem/
│  │  │  ├─ alloc.zig
│  │  │  └─ pool.zig
│  │  └─ util/
│  │     ├─ bitset.zig
│  │     ├─ hash.zig
│  │     └─ time.zig
│  └─ cli/
│     ├─ zgraph.zig
│     └─ subcommands/
│        ├─ convert.zig
│        ├─ validate.zig
│        ├─ build_index.zig
│        └─ stats.zig
├─ tests/
│  ├─ unit/
│  │  ├─ adjacency_list_test.zig
│  │  ├─ adjacency_matrix_test.zig
│  │  ├─ incidence_matrix_test.zig
│  │  ├─ formats_text_test.zig
│  │  ├─ formats_binary_test.zig
│  │  ├─ conversion_strategies_test.zig
│  │  └─ algorithms_smoke_test.zig
│  ├─ property/
│  │  ├─ graph_idempotence_test.zig
│  │  └─ random_graph_agreement_test.zig
│  ├─ fuzz/
│  │  └─ fuzzer.zig
│  └─ data/
│     ├─ tiny_graphs/*.zgraph
│     └─ medium_graphs/*.zgraph
├─ tools/
│  ├─ scripts/
│  │  ├─ gen_random_graph.zig
│  │  └─ bench_matrix_vs_list.zig
│  └─ perf/
│     └─ flamegraph_instructions.md
└─ benches/
   ├─ micro/
   │  ├─ csr_iter_bench.zig
   │  └─ parse_zgraph_bench.zig
   └─ macro/
      ├─ bfs_vs_dijkstra_bench.zig
      └─ convert_streamed_vs_duplicate.zig

License

MIT