Graph

Documentation

API Reference

Graph

Description

Typesafe directed graph definition.

Node payloads are owned by the graph. Each live node occupies one internal slot and is referred to by a stable generation/index GraphNodeId. Edges are directed and tracked incrementally in both outgoing and incoming adjacency lists of those ids.

This container is designed for analysis-style workloads such as reachability, control-flow, dependency, and graph-rewrite passes where cheap node lookup, explicit traversal, and deferred destructive mutation matter more than object-oriented node wrappers.

Like the other generic containers in this project, each Graph(T) expansion creates a distinct anonymous type. Prefer a typedef when you need to reuse the same graph type across APIs.

Fields

Name	Description
`slots`	Internal slot storage for live and reusable nodes.
`free_indices`	Reusable slot indices populated by deletion/clear.
`pending_edge_removals`	Directed edges marked for removal on next commit.
`copy_init`	Optional deep-copy callback for node payloads.
`copy_deinit`	Optional deinit callback for node payloads.
`live_count`	Number of currently live nodes.
`edge_count`	Number of directed edges currently stored.
`pending_delete_count`	Number of nodes marked for deletion but not yet committed.
`mutation_epoch`	Structural mutation counter used by traversal helpers.
`allocator`	Allocator bound to this graph. Its `alignment` field governs node payload alignment.

Usage example (from documentation)

  typedef Graph(int) IntGraph;
  IntGraph graph = GraphInit();

Usage example (Cross-references)

Usage examples (Cross-references)

In Graph.c:7:

    /// Generic directed graph implementation
    
    #include <Misra/Std/Container/Graph.h>
    #include <Misra/Std/Log.h>
    #include <Misra/Std/Memory.h>

In Graph.c:32:

    
        if ((alignment > 1) && !graph_alignment_is_pow2(alignment)) {
            LOG_FATAL("Graph allocator alignment must be 1 or a power of two");
        }
    }

In Graph.c:38:

    static void graph_validate_slot_limit(const GenericGraph *graph) {
        if (VecLen(&graph->slots) > (u64)UINT32_MAX) {
            LOG_FATAL("Graph exceeded maximum supported slot count");
        }
    }

In Graph.c:181:

                1
            )) {
            LOG_FATAL("Graph failed to record a reusable slot index");
        }
    }

In Graph.c:249:

        in_idx       = graph_find_neighbor_index(in_neighbors, from);
        if (in_idx == SIZE_MAX) {
            LOG_FATAL("Graph reverse adjacency is inconsistent during edge removal");
        }

In Graph.c:275:

            } else {
                if (!graph_remove_edge_now(graph, from, neighbor_id)) {
                    LOG_FATAL("Graph failed to remove marked outgoing edge");
                }
                removed += 1;

In Graph.c:291:

            GraphNodeId to = VecLast(neighbors);
            if (!graph_remove_edge_now(graph, from, to)) {
                LOG_FATAL("Graph failed to remove outgoing edge during node deletion");
            }
            removed += 1;

In Graph.c:308:

    
        if (!graph) {
            LOG_FATAL("Expected a valid Graph pointer");
        }

In Graph.c:312:

    
        if (!MAGIC_MATCHES(graph->__magic, GRAPH_MAGIC)) {
            LOG_FATAL("Graph is uninitialized or corrupted");
        }

In Graph.c:329:

        // dereferencing the method table.
        if (!graph->allocator) {
            LOG_FATAL("Graph allocator pointer is NULL");
        }

In Graph.c:334:

        if (!graph->allocator->allocate || !graph->allocator->resize || !graph->allocator->remap ||
            !graph->allocator->deallocate) {
            LOG_FATAL("Graph allocator is not fully configured");
        }

In Graph.c:344:

    
        if (graph->live_count > VecLen(&graph->slots)) {
            LOG_FATAL("Graph live node count exceeds slot count");
        }

In Graph.c:348:

    
        if (graph->pending_delete_count > graph->live_count) {
            LOG_FATAL("Graph pending delete count exceeds live node count");
        }

In Graph.c:352:

    
        if ((graph->live_count + VecLen(&graph->free_indices)) != VecLen(&graph->slots)) {
            LOG_FATAL("Graph slot accounting is inconsistent");
        }

In Graph.c:384:

                    target_slot = graph_require_live_slot_const(graph, neighbor_id);
                    if (!graph_neighbors_contains(&target_slot->in_neighbors, self_id)) {
                        LOG_FATAL("Graph reverse adjacency is missing predecessor entry");
                    }
                }

In Graph.c:395:

                    source_slot = graph_require_live_slot_const(graph, predecessor_id);
                    if (!graph_neighbors_contains(&source_slot->out_neighbors, self_id)) {
                        LOG_FATAL("Graph reverse adjacency is missing outgoing edge");
                    }
                }

In Graph.c:420:

            u32 index = VecAt(&graph->free_indices, free_index_i);
            if ((u64)index >= VecLen(&graph->slots)) {
                LOG_FATAL("Graph free slot index out of bounds");
            }

In Graph.c:424:

    
            if (graph_slot_is_occupied(VecPtrAt((GraphSlots *)&graph->slots, index))) {
                LOG_FATAL("Graph free index points to an occupied slot");
            }
        }

In Graph.c:438:

    
            if (!graph_neighbors_contains(neighbors, pending->to)) {
                LOG_FATAL("Graph pending edge removal refers to a missing edge");
            }
        }

In Graph.c:443:

    
        if (graph->live_count != live_count) {
            LOG_FATAL("Graph live node count is inconsistent");
        }

In Graph.c:447:

    
        if ((graph->edge_count != out_edge_count) || (graph->edge_count != in_edge_count)) {
            LOG_FATAL("Graph edge count is inconsistent");
        }

In Graph.c:451:

    
        if (graph->pending_delete_count != marked_count) {
            LOG_FATAL("Graph pending delete count is inconsistent");
        }
        // Mark verified.

In Graph.c:939:

            if (graph_slot_is_occupied(slot) && graph_slot_is_marked(slot)) {
                if (VecLen(&slot->out_neighbors) || VecLen(&slot->in_neighbors)) {
                    LOG_FATAL("Graph marked node retained incident edges before release");
                }
                graph_release_slot(graph, slot, item_size);

In Graph.Access.c:3:

    #include <Misra/Std/Allocator/Default.h>
    #include <Misra/Std/Zstr.h>
    #include <Misra/Std/Container/Graph.h>
    #include <Misra/Std/Log.h>

In Graph.Access.c:9:

    
    static bool test_graph_access_helpers(void) {
        WriteFmt("Testing Graph access helpers\n");
    
        DefaultAllocator alloc = DefaultAllocatorInit();

In Graph.Access.c:13:

        DefaultAllocator alloc = DefaultAllocatorInit();
    
        typedef Graph(int) IntGraph;
        IntGraph graph = GraphInit(&alloc);

In Graph.Access.c:55:

        DefaultAllocator alloc = DefaultAllocatorInit();
    
        typedef Graph(Zstr) ZstrGraph;
        ZstrGraph graph = GraphInit(&alloc);

In Graph.Access.c:81:

        DefaultAllocator alloc = DefaultAllocatorInit();
    
        typedef Graph(int) IntGraph;
        IntGraph  graph_a = GraphInit(&alloc);
        IntGraph  graph_b = GraphInit(&alloc);

In Graph.Access.c:99:

        DefaultAllocator alloc = DefaultAllocatorInit();
    
        typedef Graph(int) IntGraph;
        IntGraph graph = GraphInit(&alloc);

In Graph.Access.c:118:

        DefaultAllocator alloc = DefaultAllocatorInit();
    
        typedef Graph(int) IntGraph;
        IntGraph graph = GraphInit(&alloc);

In Graph.Access.c:143:

        };
    
        WriteFmt("[INFO] Starting Graph.Access tests\n\n");
        return run_test_suite(
            tests,

In Graph.Access.c:149:

            deadend_tests,
            (int)(sizeof(deadend_tests) / sizeof(deadend_tests[0])),
            "Graph.Access"
        );
    }

In Graph.Type.c:3:

    #include <Misra/Std/Allocator/Default.h>
    #include <Misra/Std/Allocator/Heap.h>
    #include <Misra/Std/Container/Graph.h>
    #include <Misra/Std/Log.h>

In Graph.Type.c:9:

    
    static bool test_graph_type_defaults(void) {
        WriteFmt("Testing Graph defaults\n");
    
        DefaultAllocator alloc = DefaultAllocatorInit();

In Graph.Type.c:13:

        DefaultAllocator alloc = DefaultAllocatorInit();
    
        typedef Graph(int) IntGraph;
        IntGraph graph = GraphInit(&alloc);

In Graph.Type.c:35:

    
    static bool test_graph_aligned_init_and_id_layout(void) {
        WriteFmt("Testing Graph aligned init and node id layout\n");
    
        HeapAllocator alloc = HeapAllocatorInitAligned(32);

In Graph.Type.c:39:

        HeapAllocator alloc = HeapAllocatorInitAligned(32);
    
        typedef Graph(int) IntGraph;
        IntGraph graph = GraphInit(&alloc);

In Graph.Type.c:62:

        };
    
        WriteFmt("[INFO] Starting Graph.Type tests\n\n");
        return run_test_suite(tests, (int)(sizeof(tests) / sizeof(tests[0])), NULL, 0, "Graph.Type");
    }

In Graph.Type.c:63:

    
        WriteFmt("[INFO] Starting Graph.Type tests\n\n");
        return run_test_suite(tests, (int)(sizeof(tests) / sizeof(tests[0])), NULL, 0, "Graph.Type");
    }

In Graph.Ops.c:2:

    #include <Misra/Std/Allocator/Default.h>
    #include <Misra/Std/Container/Graph.h>
    #include <Misra/Std/Log.h>

In Graph.Ops.c:8:

    
    static bool test_graph_node_visit_scratch_state(void) {
        WriteFmt("Testing Graph node scratch visit state\n");
    
        DefaultAllocator alloc = DefaultAllocatorInit();

In Graph.Ops.c:12:

        DefaultAllocator alloc = DefaultAllocatorInit();
    
        typedef Graph(int) IntGraph;
        IntGraph graph = GraphInit(&alloc);

In Graph.Ops.c:38:

        DefaultAllocator alloc = DefaultAllocatorInit();
    
        typedef Graph(int) IntGraph;
        IntGraph graph = GraphInit(&alloc);

In Graph.Ops.c:81:

    
    static bool test_graph_query_and_unmark_node_deletion(void) {
        WriteFmt("Testing Graph node mark query and unmark\n");
    
        DefaultAllocator alloc = DefaultAllocatorInit();

In Graph.Ops.c:85:

        DefaultAllocator alloc = DefaultAllocatorInit();
    
        typedef Graph(int) IntGraph;
        IntGraph graph = GraphInit(&alloc);

In Graph.Ops.c:112:

        DefaultAllocator alloc = DefaultAllocatorInit();
    
        typedef Graph(int) IntGraph;
        IntGraph graph = GraphInit(&alloc);

In Graph.Ops.c:157:

    
    static bool test_graph_query_and_unmark_edge_removal(void) {
        WriteFmt("Testing Graph edge mark query and unmark\n");
    
        DefaultAllocator alloc = DefaultAllocatorInit();

In Graph.Ops.c:161:

        DefaultAllocator alloc = DefaultAllocatorInit();
    
        typedef Graph(int) IntGraph;
        IntGraph graph = GraphInit(&alloc);

In Graph.Ops.c:190:

        DefaultAllocator alloc = DefaultAllocatorInit();
    
        typedef Graph(int) IntGraph;
        IntGraph graph = GraphInit(&alloc);

In Graph.Ops.c:224:

        DefaultAllocator alloc = DefaultAllocatorInit();
    
        typedef Graph(int) IntGraph;
        IntGraph graph = GraphInit(&alloc);

In Graph.Ops.c:250:

        DefaultAllocator alloc = DefaultAllocatorInit();
    
        typedef Graph(int) IntGraph;
        IntGraph graph = GraphInit(&alloc);

In Graph.Ops.c:286:

        DefaultAllocator alloc = DefaultAllocatorInit();
    
        typedef Graph(int) IntGraph;
        IntGraph graph = GraphInit(&alloc);

In Graph.Ops.c:321:

        DefaultAllocator alloc = DefaultAllocatorInit();
    
        typedef Graph(int) IntGraph;
        IntGraph graph = GraphInit(&alloc);

In Graph.Ops.c:352:

        };
    
        WriteFmt("[INFO] Starting Graph.Ops tests\n\n");
        return run_test_suite(
            tests,

In Graph.Ops.c:358:

            deadend_tests,
            (int)(sizeof(deadend_tests) / sizeof(deadend_tests[0])),
            "Graph.Ops"
        );
    }

In Graph.Init.c:4:

    #include <Misra/Std/Zstr.h>
    #include <Misra/Std/Allocator/Heap.h>
    #include <Misra/Std/Container/Graph.h>
    #include <Misra/Std/Container/Str.h>
    #include <Misra/Std/Log.h>

In Graph.Init.c:15:

        DefaultAllocator alloc = DefaultAllocatorInit();
    
        typedef Graph(int) IntGraph;
        IntGraph graph = GraphInit(&alloc);

In Graph.Init.c:74:

    
    static bool test_graph_node_deep_copy(void) {
        WriteFmt("Testing Graph node deep-copy\n");
    
        DefaultAllocator alloc = DefaultAllocatorInit();

In Graph.Init.c:78:

        DefaultAllocator alloc = DefaultAllocatorInit();
    
        typedef Graph(Str) StrGraph;
        StrGraph    graph = GraphInitWithDeepCopy(str_init_copy, str_deinit, &alloc);
        Str         name  = StrInitFromZstr("alpha", &alloc);

In Graph.Init.c:99:

    
    static bool test_graph_node_owned_str_rvalue(void) {
        WriteFmt("Testing Graph node owned Str r-value insertion\n");
    
        DefaultAllocator alloc = DefaultAllocatorInit();

In Graph.Init.c:103:

        DefaultAllocator alloc = DefaultAllocatorInit();
    
        typedef Graph(Str) StrGraph;
        StrGraph    graph = GraphInitWithDeepCopy(NULL, str_deinit, &alloc);
        GraphNodeId node_id;

In Graph.Init.c:122:

    
    static bool test_graph_init_optional_allocator(void) {
        WriteFmt("Testing Graph init optional allocator\n");
    
        typedef Graph(Str) StrGraph;

In Graph.Init.c:124:

        WriteFmt("Testing Graph init optional allocator\n");
    
        typedef Graph(Str) StrGraph;
    
        // intentional bypass: no public setter on `Allocator` for effort /

In Graph.Init.c:192:

        };
    
        WriteFmt("[INFO] Starting Graph.Init tests\n\n");
        return run_test_suite(tests, (int)(sizeof(tests) / sizeof(tests[0])), NULL, 0, "Graph.Init");
    }

In Graph.Init.c:193:

    
        WriteFmt("[INFO] Starting Graph.Init tests\n\n");
        return run_test_suite(tests, (int)(sizeof(tests) / sizeof(tests[0])), NULL, 0, "Graph.Init");
    }

In Graph.Insert.c:2:

    #include <Misra/Std/Allocator/Default.h>
    #include <Misra/Std/Container/Graph.h>
    #include <Misra/Std/Log.h>

In Graph.Insert.c:12:

        DefaultAllocator alloc = DefaultAllocatorInit();
    
        typedef Graph(int) IntGraph;
        IntGraph graph  = GraphInit(&alloc);
        int      owned  = 42;

In Graph.Insert.c:35:

        DefaultAllocator alloc = DefaultAllocatorInit();
    
        typedef Graph(int) IntGraph;
        IntGraph graph = GraphInit(&alloc);

In Graph.Insert.c:61:

    
    static bool test_graph_self_loop_and_predecessor_order(void) {
        WriteFmt("Testing Graph self-loop handling and predecessor order\n");
    
        DefaultAllocator alloc = DefaultAllocatorInit();

In Graph.Insert.c:65:

        DefaultAllocator alloc = DefaultAllocatorInit();
    
        typedef Graph(int) IntGraph;
        IntGraph graph = GraphInit(&alloc);

In Graph.Insert.c:96:

        };
    
        WriteFmt("[INFO] Starting Graph.Insert tests\n\n");
        return run_test_suite(tests, (int)(sizeof(tests) / sizeof(tests[0])), NULL, 0, "Graph.Insert");
    }

In Graph.Insert.c:97:

    
        WriteFmt("[INFO] Starting Graph.Insert tests\n\n");
        return run_test_suite(tests, (int)(sizeof(tests) / sizeof(tests[0])), NULL, 0, "Graph.Insert");
    }

In Graph.Foreach.c:3:

    #include <Misra/Std/Allocator/Default.h>
    #include <Misra/Std/Zstr.h>
    #include <Misra/Std/Container/Graph.h>
    #include <Misra/Std/Container/Map.h>
    #include <Misra/Std/Container/Str.h>

In Graph.Foreach.c:29:

    }
    
    typedef Graph(Str) CityGraph;
    typedef Map(Str, GraphNodeId) CityIndex;

In Graph.Foreach.c:135:

        DefaultAllocator alloc = DefaultAllocatorInit();
    
        typedef Graph(int) IntGraph;
        typedef Map(GraphNodeId, u64) CountMap;

In Graph.Foreach.c:175:

        DefaultAllocator alloc = DefaultAllocatorInit();
    
        typedef Graph(int) IntGraph;
        IntGraph graph = GraphInit(&alloc);

In Graph.Foreach.c:211:

        DefaultAllocator alloc = DefaultAllocatorInit();
    
        typedef Graph(int) IntGraph;
        IntGraph graph = GraphInit(&alloc);

In Graph.Foreach.c:232:

        DefaultAllocator alloc = DefaultAllocatorInit();
    
        typedef Graph(int) IntGraph;
        IntGraph graph = GraphInit(&alloc);

In Graph.Foreach.c:256:

        DefaultAllocator alloc = DefaultAllocatorInit();
    
        typedef Graph(int) IntGraph;
        IntGraph graph = GraphInit(&alloc);

In Graph.Foreach.c:289:

        };
    
        WriteFmt("[INFO] Starting Graph.Foreach tests\n\n");
        return run_test_suite(
            tests,

In Graph.Foreach.c:295:

            deadend_tests,
            (int)(sizeof(deadend_tests) / sizeof(deadend_tests[0])),
            "Graph.Foreach"
        );
    }

In Container.h:28:

    #endif
    #if FEATURE_GRAPH
    #    include <Misra/Std/Container/Graph.h>
    #endif
    #if FEATURE_INT

In Graph.h:11:

    
    // clang-format off
    #include "Graph/Type.h"
    #include "Graph/Init.h"
    #include "Graph/Insert.h"

In Graph.h:12:

    // clang-format off
    #include "Graph/Type.h"
    #include "Graph/Init.h"
    #include "Graph/Insert.h"
    #include "Graph/Access.h"

In Graph.h:13:

    #include "Graph/Type.h"
    #include "Graph/Init.h"
    #include "Graph/Insert.h"
    #include "Graph/Access.h"
    #include "Graph/Foreach.h"

In Graph.h:14:

    #include "Graph/Init.h"
    #include "Graph/Insert.h"
    #include "Graph/Access.h"
    #include "Graph/Foreach.h"
    #include "Graph/Ops.h"

In Graph.h:15:

    #include "Graph/Insert.h"
    #include "Graph/Access.h"
    #include "Graph/Foreach.h"
    #include "Graph/Ops.h"
    #include "Graph/Memory.h"

In Graph.h:16:

    #include "Graph/Access.h"
    #include "Graph/Foreach.h"
    #include "Graph/Ops.h"
    #include "Graph/Memory.h"
    #include "Graph/Private.h"

In Graph.h:17:

    #include "Graph/Foreach.h"
    #include "Graph/Ops.h"
    #include "Graph/Memory.h"
    #include "Graph/Private.h"
    // clang-format on

In Graph.h:18:

    #include "Graph/Ops.h"
    #include "Graph/Memory.h"
    #include "Graph/Private.h"
    // clang-format on

Last updated on June 10, 2026

GenericGraphSlot GraphAddEdge