ImplicitNet
Some deterministic network and routing experiments need a graph model without allocating and storing every edge.
An experimental, allocation-free C17 library that computes mappings, dimension-based neighbors, deterministic next hops and reversible state updates directly from compact state, without materializing the graph.
Relationships without a stored edge list
ImplicitNet is an experimental C17 library for deterministic networks over power-of-two node sets. It computes mappings, dimension-based neighbors, next hops and reversible state changes from a 64-bit state without materializing graph edges.
The implementation has no heap allocation, recursion, dependencies or mutable global state. Supported size and input checks are part of the API contract.
State-derived bijection with inverse
in_map maps a valid node identifier through a state-derived coordinate permutation and XOR mask. in_unmap is its inverse for valid inputs, giving a bijection over the supported node set.
This is an address/index transform within the defined network model. The repository explicitly makes no cryptographic security claim.
in_state state;
const uint32_t n = 1024u;
if (!in_init(&state, n, UINT64_C(0x1234))) return 1;
uint32_t mapped = in_map(17u, n, state);
uint32_t original = in_unmap(mapped, n, state);Each direction is an involution
For a valid node and dimension, in_neighbor returns an implicit neighbor. Applying the same dimension again returns the original node: the relation is a fixed-point-free involution under the documented valid-input conditions. The operation needs no adjacency table.
There are log₂(N) dimensions. The API returns UINT32_MAX for invalid value-returning inputs; callers should use documented validity checks rather than treating that sentinel as a node.
Deterministic choice, not a universal optimality claim
in_next(current, target, n, state) computes a deterministic next hop from current toward target using the implicit network definition. The graph is not enumerated or retained. The project describes itself as an experimental compact primitive and does not claim that its routing is optimal for every metric, topology interpretation or workload.
uint32_t neighbor = in_neighbor(17u, 3u, n, state);
uint32_t next_hop = in_next(17u, 900u, n, state);
/* Check UINT32_MAX before using either value. */Apply and reverse the same event
in_step applies an event-derived XOR update to the 64-bit state. in_prev applies the inverse for the same event and network size. Reversal depends on supplying the same event and valid domain; it is not a general history buffer or multi-event rollback mechanism.
Cross-check mappings and routing against properties
The C invariant suite checks supported sizes, fixed and single-bit state corpora, inverse map identities, neighbor range/symmetry/distinctness, state reversibility and invalid inputs. A Python reference oracle cross-checks randomized mapping/routing behavior, including 100,000 generated vectors as recorded in RESULTS.md.
Benchmark figures are intentionally not committed because timing depends on hardware, compiler and optimization. The C test executable prints approximate CPU-time measurements after the invariant suite; those are not published comparative performance claims.
cmake -S . -B build
cmake --build build --config Release
ctest --test-dir build -C Release --output-on-failureA compact experimental network primitive
- Only power-of-two node counts from 4 through 65,536 are supported by the documented API.
- No stored graph exists; integrations must use the implicit API's node and dimension model.
- The project is experimental and asks users to validate it for their workload before production use.
- It does not claim cryptographic security or universally optimal routing.
- Reference-oracle agreement validates tested behavior, not every application interpretation or target compiler.