NAME
    Data::Graph::Shared - Shared-memory directed weighted graph for Linux

SYNOPSIS
        use Data::Graph::Shared;

        my $g = Data::Graph::Shared->new(undef, 100, 500);  # 100 nodes, 500 edges
        my $a = $g->add_node(10);    # returns node index
        my $b = $g->add_node(20);
        my $c = $g->add_node(30);

        $g->add_edge($a, $b, 5);     # a->b weight 5
        $g->add_edge($a, $c, 3);     # a->c weight 3
        $g->add_edge($b, $c, 1);     # b->c weight 1

        my @nbrs = $g->neighbors($a);  # ([2,3], [1,5]) - [dst,weight] pairs, newest edge first
        say $g->degree($a);            # 2
        say $g->node_data($a);         # 10

        $g->remove_node($b);          # removes node and outgoing edges

DESCRIPTION
    Directed weighted graph in shared memory. Nodes allocated from a bitmap
    pool, edges stored as adjacency lists in a separate edge pool.
    Mutex-protected mutations with PID-based stale recovery.

    Note: "remove_node" removes the node and its outgoing edges only. Incoming
    edges from other nodes are NOT automatically removed (this is an O(1)
    design choice) -- their "dst" is left dangling until the slot's bit is
    reused. Use "remove_node_full" when this matters; it additionally splices
    incoming edges in O(N+E).

    Linux-only. Requires 64-bit Perl.

METHODS
  Constructors
        my $g = Data::Graph::Shared->new($path, $max_nodes, $max_edges);  # file-backed
        my $g = Data::Graph::Shared->new(undef, $max_nodes, $max_edges);  # anonymous
        my $g = Data::Graph::Shared->new_memfd($name, $max_nodes, $max_edges);
        my $g = Data::Graph::Shared->new_from_fd($fd);                    # reopen memfd
        my $ro = Data::Graph::Shared->new_readonly($path);   # frozen file, read-only

    $max_nodes is rounded up to the next even number for alignment, so
    "$g->max_nodes" may report one more than requested; $max_edges is the
    edge-slot capacity. An optional trailing octal $mode (see "SECURITY") sets
    the backing-file permissions. "new_readonly" opens a frozen file read-only
    for lock-free queries (see "FROZEN (READ-ONLY) MODE"). The descriptor you
    pass is duplicated ("F_DUPFD_CLOEXEC"), so it stays yours to close and
    closing it does not disturb the handle.

  Operations
        my $id = $g->add_node($data);            # returns node index or undef
        $g->add_edge($src, $dst);                # weight defaults to 1
        $g->add_edge($src, $dst, $weight);
        $g->remove_node($id);                    # O(1) -- outgoing edges only
        $g->remove_node_full($id);               # O(N+E) -- also splices incoming
        $g->has_node($id);
        $g->node_data($id);
        $g->set_node_data($id, $data);
        my @pairs = $g->neighbors($id);          # list of [$dst, $weight]
        $g->each_neighbor($id, sub { my ($dst, $w) = @_ });
        $g->degree($id);
        my @ids = $g->nodes;                     # all node indices
        $g->node_count;  $g->edge_count;
        $g->max_nodes;   $g->max_edges;

    An id becomes stale once its node is removed, and the two kinds of method
    treat that differently. "add_edge", "remove_node" and "remove_node_full"
    return true when they did something and false when the node is not there
    -- so an "add_edge" naming a removed node adds no edge and reports it only
    through that return value. "node_data", "set_node_data", "degree",
    "neighbors" and "each_neighbor" instead croak on an id that does not
    exist. "has_node" is the cheap way to tell beforehand.

  Lifecycle
        $g->path;              # backing file path, or undef for anon/memfd
        $g->memfd;             # memfd fd (-1 for file-backed/anon)
        $g->stats;             # diagnostic hashref
        $g->sync;              # msync mmap to backing store
        $g->unlink;            # remove backing file
        Class->unlink($path);  # class-method form

  Event Loop Integration
        my $fd = $g->eventfd;         # lazy-create eventfd, returns fd
        $g->eventfd_set($fd);         # attach an external eventfd
        my $fd = $g->fileno;          # current eventfd fd, or -1
        $g->notify;                   # write 1 to eventfd (caller signals update)
        my $n = $g->eventfd_consume;  # read+reset eventfd counter

CONCURRENCY AND CRASH SAFETY
    The graph lives entirely in a shared memory mapping, so multiple processes
    that attach the same backing file (or inherit the same anonymous/memfd
    mapping) operate on one shared structure. All mutating operations are
    serialized by a single process-shared exclusive mutex stored in the
    mapping header; it is implemented directly on a Linux futex, so it works
    across unrelated processes without any pthread setup.

    The mutex records the PID of its current owner. If a process dies while
    holding the lock, a waiter that times out detects the dead (or zombie)
    owner via "kill(pid, 0)" plus a /proc liveness check, reclaims the lock,
    and proceeds. This keeps a crash from wedging the whole graph, but it
    cannot undo a mutation that was only half-applied at the moment of death,
    so a peer crashing mid-write may leave the structure in an inconsistent
    state.

    Any process you grant write access to the mapping is trusted not to
    corrupt it. This is Linux-only (it relies on futex and /proc).

    An interrupted create is recovered too. A creator killed after the backing
    file is sized but before its header is committed leaves a full-size,
    all-zero file. "new" re-initializes such a file automatically, but only
    when it is exactly the size the requested geometry needs, is owned by your
    effective uid, and is still entirely zero -- a file holding data is never
    re-initialized. If the creator got as far as writing part of the header,
    the file cannot be told apart from a corrupt one and "new" croaks with
    "incomplete graph file left by an interrupted create; remove it and
    retry". A file left behind by an interrupted create never held data, so
    removing it is safe -- but a file whose header was corrupted after the
    fact reaches the same croak, so confirm it is an abandoned create before
    deleting anything you care about.

BENCHMARKS
    Single-process (10K ops, x86_64 Linux, Perl 5.40):

        add_node            3.9M/s
        add_edge (random)   2.3M/s
        has_node           13.3M/s
        node_data           5.5M/s
        neighbors           2.6M/s
        degree              5.6M/s

STATS
    stats() returns: "node_count", "edge_count", "max_nodes", "max_edges",
    "ops", "mmap_size", "frozen", "readonly".

FROZEN (READ-ONLY) MODE
    A file-backed graph can be frozen and then shipped to other machines,
    where consumers open it read-only and query it with no locking at all.

        # producer: build, freeze, ship the file
        my $g = Data::Graph::Shared->new("/tmp/graph.shm", 100, 500);
        my $a = $g->add_node(1);
        my $b = $g->add_node(2);
        $g->add_edge($a, $b, 5);
        $g->freeze;                  # seal: now immutable, and $g itself is read-only
        # ... copy /tmp/graph.shm to another host ...

        # consumer (any process, same architecture): read-only, lock-free
        my $ro = Data::Graph::Shared->new_readonly("/tmp/graph.shm");
        $ro->neighbors($a);

    "freeze" takes the mutex, marks the graph permanently immutable (there is
    no unfreeze -- rebuild the file to change it), and flushes the seal to
    disk. A frozen graph rejects every mutator ("add_node", "add_edge",
    "remove_node", "remove_node_full", "set_node_data") with a croak, and a
    read-write reopen ("new($path, ...)" or "new_from_fd") of a sealed file is
    refused -- so a shipped artifact can never be silently mutated out from
    under its readers.

    new_readonly($path) maps the file "O_RDONLY" / "PROT_READ" and requires it
    to be frozen (it croaks on a file that was never "freeze"d). Because a
    sealed graph's nodes and edges are immutable, "has_node", "node_data",
    "neighbors", "degree", "nodes", "each_neighbor", "node_count",
    "edge_count" and "stats" read them directly, taking no lock -- the mapping
    is never written, so a read-only view works from a read-only file
    descriptor or a read-only filesystem, and any number of processes can
    share one "PROT_READ" mapping. "frozen" and "readonly" report the two
    states.

    Portability. The on-disk format is native binary (native-endian 64-bit
    words), so a frozen file may be copied only between machines of the same
    architecture; a corrupt or foreign-endian file is rejected at open (the
    magic check fails). Copy the file to each consumer -- do not share one
    file over a network filesystem: the mutex is a Linux futex (process-local
    to one kernel), and the "no live writer" contract assumes a static copy.
    Linux-only; 64-bit Perl.

SECURITY
    Backing files are created with mode 0600 (owner-only) by default, so only
    the creating user can open and attach them. To share a backing file across
    users, pass an explicit octal file mode such as 0660 as the last argument
    to "new"; the mode is applied when the file is created, and when a file
    left behind by an interrupted create is re-initialized (see "CONCURRENCY
    AND CRASH SAFETY"); a file already in use keeps its own permissions. The
    file is opened with "O_NOFOLLOW", so a symlink planted at the path is
    refused, and created with "O_EXCL"; the on-disk header is validated when
    the file is attached. Any process you grant write access to a shared
    mapping is trusted not to corrupt its contents while other processes are
    using it.

SEE ALSO
    Data::Heap::Shared - priority queue (for Dijkstra, Prim, etc.)

    Data::Pool::Shared - fixed-size object pool

    Data::HashMap::Shared - concurrent hash table

    Data::Buffer::Shared - typed shared array

    Data::Queue::Shared - FIFO queue

    Data::Stack::Shared - LIFO stack

    Data::Deque::Shared - double-ended queue

    Data::Log::Shared - append-only log

    Data::Sync::Shared - synchronization primitives

    Data::PubSub::Shared - publish-subscribe ring

    Data::ReqRep::Shared - request-reply

    Data::BitSet::Shared - shared bitset (lock-free per-bit ops)

    Data::RingBuffer::Shared - fixed-size overwriting ring buffer

AUTHOR
    vividsnow

LICENSE
    This is free software; you can redistribute it and/or modify it under the
    same terms as Perl itself.