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.
`alignment`	Alignment used for graph-owned node payload allocations.
`type_anchor`	Type anchor for generic node payload macros.

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/Sys.h>

In Graph.c:33:

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

In Graph.c:59:

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

In Graph.c:287:

        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:312:

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

In Graph.c:328:

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

In Graph.c:345:

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

In Graph.c:349:

    
        if (graph->__magic != MISRA_GRAPH_MAGIC) {
            LOG_FATAL("Graph is uninitialized or corrupted");
        }

In Graph.c:359:

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

In Graph.c:363:

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

In Graph.c:367:

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

In Graph.c:399:

                    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:410:

                    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:435:

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

In Graph.c:439:

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

In Graph.c:452:

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

In Graph.c:457:

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

In Graph.c:461:

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

In Graph.c:465:

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

In Graph.c:901:

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

In Graph.Foreach.c:1:

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

In Graph.Foreach.c:46:

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

In Graph.Foreach.c:131:

        WriteFmt("Testing nested foreach with external count tracking map\n");
    
        typedef Graph(int) IntGraph;
        typedef Map(GraphNodeId, u64) CountMap;

In Graph.Foreach.c:168:

        WriteFmt("Testing GraphNodeForeachPredecessor\n");
    
        typedef Graph(int) IntGraph;
        IntGraph graph = GraphInit();

In Graph.Foreach.c:201:

        WriteFmt("Testing GraphForeachNode rejects structural mutation (should abort)\n");
    
        typedef Graph(int) IntGraph;
        IntGraph graph = GraphInit();

In Graph.Foreach.c:219:

        WriteFmt("Testing GraphNodeForeachNeighbor rejects structural mutation (should abort)\n");
    
        typedef Graph(int) IntGraph;
        IntGraph graph = GraphInit();

In Graph.Foreach.c:240:

        WriteFmt("Testing GraphNodeForeachPredecessor rejects structural mutation (should abort)\n");
    
        typedef Graph(int) IntGraph;
        IntGraph graph = GraphInit();

In Graph.Foreach.c:272:

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

In Graph.Foreach.c:278:

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

In Graph.Ops.c:1:

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

In Graph.Ops.c:7:

    
    static bool test_graph_node_visit_scratch_state(void) {
        WriteFmt("Testing Graph node scratch visit state\n");
    
        typedef Graph(int) IntGraph;

In Graph.Ops.c:9:

        WriteFmt("Testing Graph node scratch visit state\n");
    
        typedef Graph(int) IntGraph;
        IntGraph graph = GraphInit();

In Graph.Ops.c:32:

        WriteFmt("Testing GraphMarkNodeForDeletion and GraphCommitChanges\n");
    
        typedef Graph(int) IntGraph;
        IntGraph graph = GraphInit();

In Graph.Ops.c:74:

    
    static bool test_graph_query_and_unmark_node_deletion(void) {
        WriteFmt("Testing Graph node mark query and unmark\n");
    
        typedef Graph(int) IntGraph;

In Graph.Ops.c:76:

        WriteFmt("Testing Graph node mark query and unmark\n");
    
        typedef Graph(int) IntGraph;
        IntGraph graph = GraphInit();

In Graph.Ops.c:100:

        WriteFmt("Testing GraphMarkEdgeForRemoval and deferred edge commit\n");
    
        typedef Graph(int) IntGraph;
        IntGraph graph = GraphInit();

In Graph.Ops.c:144:

    
    static bool test_graph_query_and_unmark_edge_removal(void) {
        WriteFmt("Testing Graph edge mark query and unmark\n");
    
        typedef Graph(int) IntGraph;

In Graph.Ops.c:146:

        WriteFmt("Testing Graph edge mark query and unmark\n");
    
        typedef Graph(int) IntGraph;
        IntGraph graph = GraphInit();

In Graph.Ops.c:172:

        WriteFmt("Testing partial unmark of multiple pending edge removals\n");
    
        typedef Graph(int) IntGraph;
        IntGraph graph = GraphInit();

In Graph.Ops.c:203:

        WriteFmt("Testing deferred removal of self-loop edge\n");
    
        typedef Graph(int) IntGraph;
        IntGraph graph = GraphInit();

In Graph.Ops.c:226:

        WriteFmt("Testing overlap between pending edge removal and node deletion\n");
    
        typedef Graph(int) IntGraph;
        IntGraph graph = GraphInit();

In Graph.Ops.c:259:

        WriteFmt("Testing external slot-indexed state across delete and reuse\n");
    
        typedef Graph(int) IntGraph;
        IntGraph graph = GraphInit();

In Graph.Ops.c:291:

        WriteFmt("Testing stale GraphNode handle after commit (should abort)\n");
    
        typedef Graph(int) IntGraph;
        IntGraph graph = GraphInit();

In Graph.Ops.c:321:

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

In Graph.Ops.c:327:

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

In Graph.Init.c:1:

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

In Graph.Init.c:10:

        WriteFmt("Testing GraphReserve and GraphClear\n");
    
        typedef Graph(int) IntGraph;
        IntGraph graph = GraphInit();

In Graph.Init.c:62:

    
    static bool test_graph_node_deep_copy(void) {
        WriteFmt("Testing Graph node deep-copy\n");
    
        typedef Graph(Str) StrGraph;

In Graph.Init.c:64:

        WriteFmt("Testing Graph node deep-copy\n");
    
        typedef Graph(Str) StrGraph;
        StrGraph   graph = GraphInitWithDeepCopy(StrInitCopy, StrDeinit);
        Str        name  = StrInitFromZstr("alpha");

In Graph.Init.c:89:

        };
    
        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:90:

    
        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.Type.c:1:

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

In Graph.Type.c:7:

    
    static bool test_graph_type_defaults(void) {
        WriteFmt("Testing Graph defaults\n");
    
        typedef Graph(int) IntGraph;

In Graph.Type.c:9:

        WriteFmt("Testing Graph defaults\n");
    
        typedef Graph(int) IntGraph;
        IntGraph graph = GraphInit();

In Graph.Type.c:25:

    
    static bool test_graph_aligned_init_and_id_layout(void) {
        WriteFmt("Testing Graph aligned init and node id layout\n");
    
        typedef Graph(int) IntGraph;

In Graph.Type.c:27:

        WriteFmt("Testing Graph aligned init and node id layout\n");
    
        typedef Graph(int) IntGraph;
        IntGraph graph = GraphInitAligned(32);

In Graph.Type.c:48:

        };
    
        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:49:

    
        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.Access.c:1:

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

In Graph.Access.c:7:

    
    static bool test_graph_access_helpers(void) {
        WriteFmt("Testing Graph access helpers\n");
    
        typedef Graph(int) IntGraph;

In Graph.Access.c:9:

        WriteFmt("Testing Graph access helpers\n");
    
        typedef Graph(int) IntGraph;
        IntGraph graph = GraphInit();

In Graph.Access.c:48:

        WriteFmt("Testing GraphHasEdge\n");
    
        typedef Graph(const char *) ZstrGraph;
        ZstrGraph graph = GraphInit();

In Graph.Access.c:71:

        WriteFmt("Testing GraphNodeData rejects foreign graph node handles (should abort)\n");
    
        typedef Graph(int) IntGraph;
        IntGraph graph_a = GraphInit();
        IntGraph graph_b = GraphInit();

In Graph.Access.c:86:

        WriteFmt("Testing GraphPredecessorAt out-of-bounds access (should abort)\n");
    
        typedef Graph(int) IntGraph;
        IntGraph graph = GraphInit();

In Graph.Access.c:102:

        WriteFmt("Testing GraphNeighborAt out-of-bounds access (should abort)\n");
    
        typedef Graph(int) IntGraph;
        IntGraph graph = GraphInit();

In Graph.Access.c:126:

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

In Graph.Access.c:132:

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

In Graph.Insert.c:1:

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

In Graph.Insert.c:9:

        WriteFmt("Testing GraphAddNode semantics\n");
    
        typedef Graph(int) IntGraph;
        IntGraph graph  = GraphInit();
        int      owned  = 42;

In Graph.Insert.c:29:

        WriteFmt("Testing GraphAddEdge deduplication\n");
    
        typedef Graph(int) IntGraph;
        IntGraph graph = GraphInit();

In Graph.Insert.c:54:

    
    static bool test_graph_self_loop_and_predecessor_order(void) {
        WriteFmt("Testing Graph self-loop handling and predecessor order\n");
    
        typedef Graph(int) IntGraph;

In Graph.Insert.c:56:

        WriteFmt("Testing Graph self-loop handling and predecessor order\n");
    
        typedef Graph(int) IntGraph;
        IntGraph graph = GraphInit();

In Graph.Insert.c:86:

        };
    
        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:87:

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

In Container.h:18:

    #include <Misra/Std/Container/Str.h>
    #include <Misra/Std/Container/Vec.h>
    #include <Misra/Std/Container/Graph.h>
    #include <Misra/Std/Container/List.h>
    #include <Misra/Std/Container/Map.h>

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 April 28, 2026

FloatToStr GraphAddEdge