🥮 mooncakes.io

    moongraph

    Graphs and graph algorithms for MoonBit: four storage types that share one interface, and the algorithm families that run on all of them.

    graph
    graphs
    digraph
    multigraph
    graph-theory
    graph-algorithms
    network-analysis
    adjacency-list
    adjacency-matrix
    csr
    shortest-path
    dijkstra
    bellman-ford
    floyd-warshall
    a-star
    bfs
    dfs
    topological-sort
    spanning-tree
    minimum-spanning-tree
    max-flow
    min-cut
    matching
    assignment
    centrality
    pagerank
    betweenness
    community-detection
    louvain
    leiden
    modularity
    clique
    graph-coloring
    isomorphism
    connected-components
    gale-ryser
    graphical
    digraphical
    degree-sequence
    erdos-gallai
    graphml
    dot
    gml
    pajek
    dimacs
    edge-list
    moonbit
    Download zip
    Version
    0.1.1
    License
    Apache-2.0
    Repository
    Last updated
    9 hours ago
    Downloads
    13

    #moongraph

    Graphs and graph algorithms for MoonBit: four storage types behind one interface, and twenty-three packages of algorithms that run on all of them.

    let g : @moongraph.Graph[String, Double] = @moongraph.Graph::new(directed=false)
    let a = g.add_node("a")
    let b = g.add_node("b")
    let c = g.add_node("c")
    g.add_edge(a, b, 1.0) |> ignore
    g.add_edge(b, c, 2.0) |> ignore
    g.add_edge(a, c, 5.0) |> ignore
    let w = g.weights(fn(cost) { cost })
    let paths = @path.dijkstra(g, a, weight=w)
    assert_eq(paths.path_to(c), Some([a, b, c]))
    assert_eq(paths.distance[c], Some(3.0))

    #A graph is numbers

    A graph is a set of numbered nodes and a set of numbered edges, each carrying a payload of its own. The numbers are dense and start at zero, so an algorithm can index an array by node instead of hashing it. Everything else — names, records, keys of any kind — goes in the payload, or through Keyed, which holds the translation and hands the numbers to the algorithms.

    TypeShapeParallel edgesNumbers after a deletionUse it when
    Graph[N, E]Adjacency listYesRenumberedThe default: build it, change it, run algorithms on it
    StableGraph[N, E]Adjacency list with holesYesKeptYou hold node numbers across deletions
    Csr[N, E]Compressed adjacency, both directionsYes—Read-only, built once, walked many times
    Matrix[E]V x V cellsNoRenumberedDense graphs and the passes that look at every pair

    All four implement the same trait, so an algorithm is written once and takes any of them — or a graph type of your own:

    pub(open) trait Topology {
      node_count(Self) -> Int
      edge_count(Self) -> Int
      directed(Self) -> Bool
      neighbors(Self, Int) -> ArrayView[Int]   // one entry per edge
      incident(Self, Int) -> ArrayView[Int]    // the edge numbers, in the same order
      endpoints(Self, Int) -> (Int, Int)
    }

    pub(open) trait Inbound {
      in_neighbors(Self, Int) -> ArrayView[Int]
      in_incident(Self, Int) -> ArrayView[Int]
    }

    neighbors and incident are parallel views, so a walk that only needs nodes allocates nothing and a walk that needs weights reads both without a lookup. Inbound is the extra ability a handful of algorithms need — the ones that walk edges backwards, like strong components or the second half of a bidirectional search.

    #Weights are a function

    An edge payload can be anything, so a weight is a function from edge number to cost rather than a field the library reserves. Graph::weights turns a function over payloads into one over numbers. An algorithm that is given no weight treats every edge as costing one.

    let by_cost = @path.dijkstra(g, a, weight=w)   // the payload is the cost
    let by_hop = @path.dijkstra(g, a)              // every edge costs one
    assert_eq(by_cost.distance[c], Some(3.0))
    assert_eq(by_hop.distance[c], Some(1.0))

    Results are arrays indexed by node number, so no lookup can fail: distance holds Double?, and None means the node was not reached — not infinity, not a large number, so a forgotten case is a type error rather than a poisoned sum.

    #Refusals carry the reason

    A graph-level mistake is a value, not an abort. A negative weight reaching Dijkstra, a cycle reaching a topological order, a graph that is not the shape the function needs: each comes back as Refused, naming the node, the edge, or a witness cycle.

    let r : @moongraph.Graph[Unit, Double] = @moongraph.Graph::new()
    r.add_node(()) |> ignore
    r.add_node(()) |> ignore
    r.add_edge(0, 1, -1.0) |> ignore
    let outcome = try {
      let _ = @path.dijkstra(r, 0, weight=r.weights(fn(cost) { cost }))
      "answered"
    } catch {
      @moongraph.Refused::NegativeWeight(edge~) => "edge " + edge.to_string() + " is negative"
      _ => "answered"
    }
    assert_eq(outcome, "edge 0 is negative")

    #Walks that answer one item at a time

    The enumerations — every simple cycle, every topological order, every spanning tree, every least cut, every simple route, every depth-first event — hand back one item per call and hold their place in between. A caller that wants the first ten pays for ten, which is the only way to use a count that grows factorially.

    for cycle in @cycle.simple_cycles(g).take(10) {
      inspect(cycle)
    }

    Iter is the only shape these come in, so collect() is the way to ask for the whole list when the graph is small enough for that to be the point.

    #Packages

    The root package holds the types, the two traits and the records results take. Every algorithm lives in the package for its family, so a program that imports one pays for one.

    PackageWhat it answers
    moongraphGraph, StableGraph, Csr, Matrix, Keyed, the traits, the result records
    moongraph/traversebreadth-first and depth-first walks, their trees, layers and events
    moongraph/pathDijkstra, Bellman-Ford, Johnson, Floyd-Warshall, A*, k shortest, widest, simple routes, contraction hierarchies
    moongraph/gridboard pathfinding: breadth first, Dijkstra, A*, jump-point search, any-angle Theta*, and D* Lite for a board that changes
    moongraph/componentcomponents, strong components in topological order, condensation, biconnected pieces, bridges, cuts
    moongraph/dsuthe disjoint-set forest: union, find, and the pieces a graph falls into
    moongraph/sattwo-variable clauses, and the assignment when one exists
    moongraph/dagtopological orders, generations, closures, longest path, dominance
    moongraph/cyclecycles and cycle bases, girth, Euler walks, the postman's route
    moongraph/treespanning trees, branchings, Steiner tree, centres, Prüfer codes, common ancestors
    moongraph/flowmaximum flow, minimum cut, cost flow, connectivity, disjoint routes
    moongraph/matchingmatchings, assignments, covers, the blossom walk
    moongraph/colorgreedy and saturation colourings, edge colouring, chromatic number
    moongraph/cliquemaximal cliques, independent sets, chordality
    moongraph/centralitydegree, closeness, betweenness, eigenvector, PageRank, hubs and authorities
    moongraph/communityLouvain, Leiden, label propagation, edge-betweenness splitting
    moongraph/metricdensity, distance, clustering, similarity, assortativity, accessibility
    moongraph/structwhat kind of graph this is — tree, bipartite, planar, regular — and the cores and trusses that say how tightly it is knit
    moongraph/isoisomorphism, and the mapping when there is one
    moongraph/opunions, products, complements, subgraphs, line graphs, contraction, and the algebraic operators: nmap, emap, gmap, remove_vertex, remove_edge, connect, closure
    moongraph/approxtours, covers, dominating sets, spanners, treewidth bounds
    moongraph/genthe named graphs, and the random families worth having by seed
    moongraph/ioedge lists, adjacency lists, GML, graph6, sparse6, Pajek
    moongraph/io/graphmlGraphML, on top of an XML parser

    #A degree sequence is a graph

    Some questions are about the counts alone, not the graph you drew. is_graphical says whether a list of degrees can be the degrees of a simple graph; is_digraphical says whether a list of in/out-degree pairs can be the degrees of a directed graph; is_multigraphical relaxes both to allow repeated edges. The directed case runs the Gale-Ryser criterion: a pair is digraphical exactly when some 0-1 matrix has the out-degrees as its row sums and the in-degrees as its column sums.

    assert_eq(@struct.is_digraphical([(0, 1), (0, 1)]), false)
    assert_eq(@struct.is_digraphical([(1, 1), (1, 1), (1, 1)]), true)
    assert_eq(@struct.gale_ryser([3, 0], [3, 0]), false)

    gale_ryser is the criterion itself, over two non-increasing sequences, so a caller that has its own row and column sums can reach it without wrapping them in pairs.

    #Reading and writing

    Six text formats in io, and GraphML in io/graphml so the XML dependency stays behind one package. Every reader refuses a broken document with the byte offset, the line and the column.

    let text = @io.edge_list(g)
    let back = @io.parse_edges(text)   // Graph[Unit, Double]; the third column is the weight
    assert_eq(back.node_count(), 3)
    assert_eq(back.edge_count(), 3)

    FormatWritesReadsNotes
    Edge listyesyestwo or three columns, # for comments
    Adjacency listyesyesone line per node
    GMLyesyesnested key value lists
    graph6yesyesone bit per possible edge
    sparse6yesyesonly the edges that are there, with a repeat flag
    Pajekyesyescounts nodes from one
    GraphMLyesyesnode labels and edge weights as data

    #Installing

    moon add moonbitstack/moongraph

    All four backends — wasm, wasm-gc, js and native — with no native code of its own, so nothing about the library is platform-specific.

    #Licence

    Apache-2.0.

    Inbound

    source
    pub(open) trait Inbound {
      fn in_neighbors(Self, Int) -> ArrayView[Int]
      fn in_incident(Self, Int) -> ArrayView[Int]
    }

    A graph that can also walk its edges backwards.

    Graph, StableGraph and Csr keep both directions, so starting such a walk costs O(1) and allocates nothing. An implementation that keeps only the forward direction can still satisfy the trait by building the list on demand, at O(d) per call.

    Topology

    source
    pub(open) trait Topology {
      fn node_count(Self) -> Int
      fn edge_count(Self) -> Int
      fn directed(Self) -> Bool
      fn neighbors(Self, Int) -> ArrayView[Int]
      fn incident(Self, Int) -> ArrayView[Int]
      fn endpoints(Self, Int) -> (Int, Int)
    }

    What every algorithm needs from a graph.

    neighbors and incident are parallel: position i of each describes one edge leaving node, so a walk that only wants nodes allocates nothing and a walk that wants weights reads both. In an undirected graph an edge appears at both of its endpoints, and a self-loop appears once.

    A third party's storage joins the family by implementing this trait: no algorithm in this library names a concrete graph type.

    Refused

    source
    pub(all) suberror Refused {
      NegativeWeight(edge~ : Int)
      Cycle(nodes~ : Array[Int])
      Disconnected(from~ : Int, to~ : Int)
      NoSolution
      NotA(kind~ : String, what~ : String)
      OutOfRange(node~ : Int)
      Malformed(at~ : Int, line~ : Int, column~ : Int, got~ : String, want~ : String)
    } derive(Eq, 
    Debug    )

    Why a graph was refused.

    Every function that can reject its input raises this and names the node or edge it objected to, so a caller can point at its own input instead of printing a message. A graph-level mistake is a value here, never a process abort: the numbers came from the caller, and the caller can handle them.

    test {
      let refused = @moongraph.Refused::Cycle(nodes=[0, 1, 0])
      let line = match refused {
        Cycle(nodes~) => "a cycle through " + nodes.length().to_string() + " nodes"
        _ => "something else"
      }
      assert_eq(line, "a cycle through 3 nodes")
    }

    Refused::at_offset

    source
    fn Refused::at_offset(text : StringView, at : Int, got : String, want : String) -> Refused

    The refusal for a byte offset, with the line and column computed from the text it points into. Parsers report positions in all three units because a caller may be reading a file (line and column) or a byte stream (offset).

    Refused::equal

    source
    fn Refused::equal(Refused, Refused) -> Bool

    Refused::not_equal

    source
    fn Refused::not_equal(x : Refused, y : Refused) -> Bool

    Refused::to_repr

    source

    AllPairs

    source
    pub(all) struct AllPairs {
      distance : Array[Array[Double?]]
      next : Array[Array[Int?]]
    }

    The result of an all-pairs search: a matrix of costs and a matrix of successors.

    next[from][to] is the node after from on a cheapest route, which is what keeps path reconstruction to one lookup per step. Everything is indexed by node number.

    AllPairs::path

    source
    fn AllPairs::path(self : AllPairs, from : Int, to : Int) -> Array[Int]?

    The cheapest route from from to to, both included, or None when there is none.

    AllPairs::reached

    source
    fn AllPairs::reached(self : AllPairs, from : Int, to : Int) -> Bool

    Whether to is reachable from from.

    Cliques

    source
    pub(all) struct Cliques {
      members : Array[Array[Int]]
    }

    A set of cliques.

    Coloring

    source
    pub(all) struct Coloring {
      color : Array[Int]
      count : Int
    }

    A colouring: a colour per node and how many colours were used.

    Components

    source
    pub(all) struct Components {
      label : Array[Int]
      count : Int
    }

    A labelling of nodes by component.

    Condensation

    source
    pub(all) struct Condensation {
      graph : Graph[Int, Unit]
      of_node : Array[Int]
      members : Array[Array[Int]]
    }

    The condensation of a directed graph: one node per strong component.

    Cover

    source
    pub(all) struct Cover {
      edges : Array[Int]
    }

    An edge cover: the edges that touch every node.

    Csr

    source
    pub struct Csr[N, E] {
      directed : Bool
      n : Int
      node_payload : Array[N]
      edge_payload : Array[E]
      froms : Array[Int]
      tos : Array[Int]
      f_off : Array[Int]
      f_nbr : Array[Int]
      f_eid : Array[Int]
      r_off : Array[Int]
      r_nbr : Array[Int]
      r_eid : Array[Int]
      scratch : Array[Int]
    }

    A read-only snapshot of a graph in compressed adjacency form: one flat array of neighbours per direction, with an offset per node.

    Building costs one pass and one sort; every later neighbors call is a slice of the flat array, which is what makes this the type to hand to an algorithm that walks the same graph a million times. An undirected edge sits in both directions, and each node's slice is sorted by target and then by edge number, so two walks over the same edges visit them in the same order.

    Edge numbers are the snapshot's own, dense from 0 and in the order the source graph reported them.

    test {
      let g : @moongraph.Graph[Unit, Int32] = @moongraph.Graph::from_edges(
        [(0, 1), (1, 2)],
        node=(),
        edge=0,
        directed=false,
      )
      let csr = @moongraph.Csr::from(g)
      assert_eq(csr.node_count(), 3)
      assert_eq(csr.neighbors(1), [0, 2][:])
      assert_eq(csr.in_neighbors(2), [1][:])
    }
    impl Inbound for Csr[N, E]
    impl Topology for Csr[N, E]

    Csr::directed

    source
    fn[N, E] Csr::directed(self : Csr[N, E]) -> Bool

    Csr::edge_count

    source
    fn[N, E] Csr::edge_count(self : Csr[N, E]) -> Int

    Csr::edge_data

    source
    fn[N, E] Csr::edge_data(self : Csr[N, E], edge : Int) -> E

    The payload of an edge.

    Csr::endpoints

    source
    fn[N, E] Csr::endpoints(self : Csr[N, E], edge : Int) -> (Int, Int)

    Csr::from

    source
    fn[N, E] Csr::from(graph : Graph[N, E]) -> Csr[N, E]

    Builds the snapshot from a Graph.

    Csr::from_stable

    source
    fn[N, E] Csr::from_stable(graph : StableGraph[N, E]) -> Csr[N, E]

    Builds the snapshot from a StableGraph. Vacant numbers stay vacant: the snapshot keeps the same node numbering, which is the point of the stable form.

    Csr::in_incident

    source
    fn[N, E] Csr::in_incident(self : Csr[N, E], node : Int) -> ArrayView[Int]

    Csr::in_neighbors

    source
    fn[N, E] Csr::in_neighbors(self : Csr[N, E], node : Int) -> ArrayView[Int]

    Csr::incident

    source
    fn[N, E] Csr::incident(self : Csr[N, E], node : Int) -> ArrayView[Int]

    Csr::neighbors

    source
    fn[N, E] Csr::neighbors(self : Csr[N, E], node : Int) -> ArrayView[Int]

    Csr::node_count

    source
    fn[N, E] Csr::node_count(self : Csr[N, E]) -> Int

    Csr::node_data

    source
    fn[N, E] Csr::node_data(self : Csr[N, E], node : Int) -> N

    The payload of a node.

    Csr::to_graph

    source
    fn[N, E] Csr::to_graph(self : Csr[N, E]) -> Graph[N, E]

    Back to a mutable graph carrying the same payloads and the same numbering.

    Csr::weights

    source
    fn[N, E] Csr::weights(self : Csr[N, E], of : (E) -> Double) -> ((Int) -> Double)

    A weight function over edge numbers, derived from one over payloads.

    Cut

    source
    pub(all) struct Cut {
      value : Double
      source_side : Array[Bool]
    }

    A cut: the value it separates, and which side each node falls on.

    Flow

    source
    pub(all) struct Flow {
      value : Double
      flow : Array[Double]
    }

    A feasible flow: its value and the flow on every edge.

    Graph

    source
    pub struct Graph[N, E] {
      directed : Bool
      nodes : Array[N]
      payload : Array[E]
      froms : Array[Int]
      tos : Array[Int]
      alive : Array[Bool]
      live : Int
      out_nbrs : Array[Array[Int]]
      out_eids : Array[Array[Int]]
      in_nbrs : Array[Array[Int]]
      in_eids : Array[Array[Int]]
      empty : Array[Int]
    }

    An adjacency-list graph: directed or undirected, parallel edges allowed, one payload per node and one per edge.

    Node numbers are dense and run from 0. Adding a node or an edge never changes an existing number; remove_node renumbers every node above the hole, which is why StableGraph exists for callers that hold numbers across deletions. Edge numbers are never reused, so an edge number stays valid until that edge is removed.

    test {
      let g : @moongraph.Graph[String, Double] = @moongraph.Graph::new()
      let a = g.add_node("a")
      let b = g.add_node("b")
      g.add_edge(a, b, 2.5) |> ignore
      assert_eq(g.node_count(), 2)
      assert_eq(g.neighbors(a), [b][:])
      assert_eq(g.edge_data(g.find_edge(a, b).unwrap()), 2.5)
    }
    impl Inbound for Graph[N, E]
    impl Topology for Graph[N, E]

    Graph::add_edge

    source
    fn[N, E] Graph::add_edge(self : Graph[N, E], from : Int, to : Int, data : E) -> Int

    Adds an edge from from to to carrying data, and returns its number. In an undirected graph the edge is reported from both endpoints.

    A negative endpoint is clamped to 0 and one beyond the last node is refused by not creating an edge, because the signature has no error to raise; check the endpoints first when the numbers come from outside.

    Graph::add_node

    source
    fn[N, E] Graph::add_node(self : Graph[N, E], data : N) -> Int

    Adds a node and returns its number.

    Graph::clear

    source
    fn[N, E] Graph::clear(self : Graph[N, E]) -> Unit

    Removes every node and every edge.

    Graph::clear_edges

    source
    fn[N, E] Graph::clear_edges(self : Graph[N, E]) -> Unit

    Removes every edge, keeping the nodes.

    Graph::contains_edge

    source
    fn[N, E] Graph::contains_edge(self : Graph[N, E], edge : Int) -> Bool

    Whether the edge exists and has not been removed.

    Graph::contains_node

    source
    fn[N, E] Graph::contains_node(self : Graph[N, E], node : Int) -> Bool

    Whether a node number is inside the graph.

    Graph::copy

    source
    fn[N, E] Graph::copy(self : Graph[N, E]) -> Graph[N, E]

    An independent copy. Payloads are shared, because they are values the caller owns; the structure is not.

    Graph::directed

    source
    fn[N, E] Graph::directed(self : Graph[N, E]) -> Bool

    Graph::edge_count

    source
    fn[N, E] Graph::edge_count(self : Graph[N, E]) -> Int

    Graph::edge_data

    source
    fn[N, E] Graph::edge_data(self : Graph[N, E], edge : Int) -> E

    The payload of an edge.

    Graph::edges

    source
    fn[N, E] Graph::edges(self : Graph[N, E]) -> Iter[Int]

    Every live edge number, ascending.

    Graph::endpoints

    source
    fn[N, E] Graph::endpoints(self : Graph[N, E], edge : Int) -> (Int, Int)

    Graph::find_edge

    source
    fn[N, E] Graph::find_edge(self : Graph[N, E], from : Int, to : Int) -> Int?

    The lowest-numbered edge from from to to, or None when there is none. In an undirected graph either direction counts.

    Graph::find_edges

    source
    fn[N, E] Graph::find_edges(self : Graph[N, E], from : Int, to : Int) -> Array[Int]

    Every edge between the pair, in number order.

    Graph::from_edges

    source
    fn[N, E] Graph::from_edges(edges : Array[(Int, Int)], node~ : N, edge~ : E, directed? : Bool) -> Graph[N, E]

    A graph built from (from, to) pairs, every node carrying node and every edge edge. Nodes are created up to the highest number in the list.

    Graph::in_incident

    source
    fn[N, E] Graph::in_incident(self : Graph[N, E], node : Int) -> ArrayView[Int]

    Graph::in_neighbors

    source
    fn[N, E] Graph::in_neighbors(self : Graph[N, E], node : Int) -> ArrayView[Int]

    Graph::incident

    source
    fn[N, E] Graph::incident(self : Graph[N, E], node : Int) -> ArrayView[Int]

    Graph::neighbors

    source
    fn[N, E] Graph::neighbors(self : Graph[N, E], node : Int) -> ArrayView[Int]

    Graph::new

    source
    fn[N, E] Graph::new(directed? : Bool) -> Graph[N, E]

    An empty graph. directed decides how every later edge is read; it cannot be changed afterwards, because the adjacency is stored that way.

    Graph::node_count

    source
    fn[N, E] Graph::node_count(self : Graph[N, E]) -> Int

    Graph::node_data

    source
    fn[N, E] Graph::node_data(self : Graph[N, E], node : Int) -> N

    The payload of a node. Reading a number outside the graph aborts, which is the only place in this package that does: a payload has no neutral value to give.

    Graph::nodes

    source
    fn[N, E] Graph::nodes(self : Graph[N, E]) -> Iter[Int]

    Every node number, ascending.

    Graph::relabel

    source
    fn[N, E] Graph::relabel(self : Graph[N, E], labels : Array[Int]) -> Graph[N, E] raise Refused

    The same graph with its nodes numbered differently. labels[old] is the number the node takes in the answer, and it has to be a permutation of 0..n — a one-to-one map onto the same range, which is what keeps the result dense and keeps every node's number meaningful without a translation table at the call site.

    Payloads travel with their nodes and edges, and edges are reissued in their original order. To drop nodes instead of renumbering them, use subgraph; to renumber a StableGraph without losing its vacant slots, do not — that is the one thing the stable storage exists to prevent.

    test {
      let g : @moongraph.Graph[Int32, Unit] = @moongraph.Graph::from_edges(
        [(0, 1)],
        node=0,
        edge=(),
        directed=false,
      )
      g.set_node_data(0, 7)
      let flipped = g.relabel([1, 0])
      assert_eq(flipped.node_data(1), 7)
      assert_eq(flipped.endpoints(0), (1, 0))
    }

    Graph::remove_edge

    source
    fn[N, E] Graph::remove_edge(self : Graph[N, E], edge : Int) -> Unit

    Removes an edge. Its number stays vacant, and the numbers of the other edges do not change. A number outside the graph, or one already removed, is ignored.

    Graph::remove_node

    source
    fn[N, E] Graph::remove_node(self : Graph[N, E], node : Int) -> Unit

    Removes a node and every edge on it, and renumbers the nodes after it down by one so the numbering stays dense. A number outside the graph is ignored.

    This is the one operation that invalidates node numbers; use StableGraph if that matters.

    Graph::set_edge_data

    source
    fn[N, E] Graph::set_edge_data(self : Graph[N, E], edge : Int, data : E) -> Unit

    Replaces an edge's payload.

    Graph::set_node_data

    source
    fn[N, E] Graph::set_node_data(self : Graph[N, E], node : Int, data : N) -> Unit

    Replaces a node's payload.

    Graph::to_directed

    source
    fn[N, E] Graph::to_directed(self : Graph[N, E]) -> Graph[N, E]

    The same graph, made directed: every undirected edge becomes two arcs that point at each other, and a self-loop stays one arc because it already points both ways.

    Node numbers are kept, so an answer indexed by node still names the same node. Edge numbers are reissued in pairs — the k-th undirected edge becomes arcs 2k and 2k+1, the second pointing back — so the pair is one addition apart. A directed graph is copied as it stands.

    test {
      let g : @moongraph.Graph[Unit, Unit] = @moongraph.Graph::from_edges(
        [(0, 1), (1, 2)],
        node=(),
        edge=(),
        directed=false,
      )
      let d = g.to_directed()
      assert_eq(d.directed(), true)
      assert_eq(d.edge_count(), 4)
      assert_eq(d.endpoints(2), (1, 2))
      assert_eq(d.endpoints(3), (2, 1))
    }

    Graph::to_undirected

    source
    fn[N, E] Graph::to_undirected(self : Graph[N, E]) -> Graph[N, E]

    The same graph, made undirected: two arcs that point at each other become one edge, and an arc with no partner becomes one edge.

    When both directions are present, the edge keeps the payload of the lowest-numbered arc that joins the pair, so the answer does not depend on which direction was added first and two runs over the same graph agree. Node numbers are kept. An undirected graph is copied as it stands.

    Graph::weights

    source
    fn[N, E] Graph::weights(self : Graph[N, E], of : (E) -> Double) -> ((Int) -> Double)

    A weight function over edge numbers, derived from one over payloads. Pass the result as the weight argument of an algorithm.

    Graph::with_capacity

    source
    fn[N, E] Graph::with_capacity(nodes? : Int, edges? : Int, directed? : Bool) -> Graph[N, E]

    An empty graph with room for the given counts, so that a build loop does not reallocate. The counts are hints; exceeding them is not an error.

    Keyed

    source
    pub struct Keyed[K, N, E] {
      graph : Graph[N, E]
      index : Map[K, Int]
      back : Array[K?]
    }

    A graph addressed by keys instead of numbers: keys go in, keys come out, and the numbers stay inside.

    The algorithms take dense node numbers because that is what makes them fast; a caller whose data is keyed by names should not have to translate in both directions around every call. The wrapper holds the translation and hands the inner Graph to anything that needs it.

    test {
      let g : @moongraph.Graph[Unit, Double] = @moongraph.Graph::new()
      let k = @moongraph.Keyed::new(graph=g)
      let a = k.add_node("a", ())
      let b = k.add_node("b", ())
      k.add_edge("a", "b", 1.0) |> ignore
      assert_eq(k.node("b"), Some(b))
      assert_eq(k.key(a), Some("a"))
      assert_eq(k.graph().edge_count(), 1)
    }

    Keyed::add_edge

    source
    fn[K : Hash + Eq, N, E] Keyed::add_edge(self : Keyed[K, N, E], from : K, to : K, data : E) -> Int raise Refused

    Adds an edge between two keys and returns its number. Either key missing is refused, because an edge to a node that is not there has no number to use.

    Keyed::add_node

    source
    fn[K : Hash + Eq, N, E] Keyed::add_node(self : Keyed[K, N, E], key : K, data : N) -> Int raise Refused

    Adds a node under a key and returns its number. A key that is already present is refused rather than silently overwriting the node.

    Keyed::graph

    source
    fn[K, N, E] Keyed::graph(self : Keyed[K, N, E]) -> Graph[N, E]

    The wrapped graph, for an algorithm that works in numbers.

    Keyed::key

    source
    fn[K, N, E] Keyed::key(self : Keyed[K, N, E], node : Int) -> K?

    The key behind a number.

    Keyed::new

    source
    fn[K : Hash + Eq, N, E] Keyed::new(graph~ : Graph[N, E]) -> Keyed[K, N, E]

    Wraps a graph. The wrapper takes ownership of the numbering from here on: add nodes and edges through it so the two views cannot drift.

    Keyed::node

    source
    fn[K : Hash + Eq, N, E] Keyed::node(self : Keyed[K, N, E], key : K) -> Int?

    The number behind a key.

    Keyed::path

    source
    fn[K : Hash + Eq, N, E] Keyed::path(self : Keyed[K, N, E], paths : Paths, key : K) -> Array[K]?

    The route to a key, as keys. None when the node was not reached.

    Keyed::scores

    source
    fn[K : Hash + Eq, N, E] Keyed::scores(self : Keyed[K, N, E], scores : Scores) -> Map[K, Double]

    A score per key, for a caller that thinks in keys.

    Mapping

    source
    pub(all) struct Mapping {
      to : Array[Int]
    }

    A node-to-node map between two graphs.

    Matching

    source
    pub(all) struct Matching {
      pairs : Array[(Int, Int)]
      weight : Double
    }

    A matching: pairs of nodes and the weight those pairs add up to.

    Matrix

    source
    pub struct Matrix[E] {
      n : Int
      cells : Array[E?]
      live : Int
      nbr_scratch : Array[Int]
      inc_scratch : Array[Int]
      in_nbr_scratch : Array[Int]
      in_inc_scratch : Array[Int]
      empty : Array[Int]
    }

    A dense V by V grid of cells, one edge payload per cell.

    A cell holds at most one edge, so this type cannot represent parallel edges; its edge numbers are the cell index from * V + to. That identity is what makes it the right store for the passes that consult every pair: all-pairs weights, transitive closure, a capacity grid read from a table.

    A matrix is directed. Each cell is an edge from its row to its column; write both cells to model an undirected edge.

    test {
      let m : @moongraph.Matrix[Double] = @moongraph.Matrix::new(3)
      m.set(0, 2, 1.5)
      assert_eq(m.get(0, 2), Some(1.5))
      assert_eq(m.get(2, 0), None)
      assert_eq(m.edge_count(), 1)
      assert_eq(m.neighbors(0), [2][:])
    }
    impl Inbound for Matrix[E]
    impl Topology for Matrix[E]

    Matrix::directed

    source
    fn[E] Matrix::directed(_self : Matrix[E]) -> Bool

    Matrix::edge_count

    source
    fn[E] Matrix::edge_count(self : Matrix[E]) -> Int

    Matrix::edges

    source
    fn[E] Matrix::edges(self : Matrix[E]) -> Array[(Int, Int)]

    Every edge of the matrix, as (from, to) pairs in cell order.

    Matrix::endpoints

    source
    fn[E] Matrix::endpoints(self : Matrix[E], edge : Int) -> (Int, Int)

    Matrix::get

    source
    fn[E] Matrix::get(self : Matrix[E], from : Int, to : Int) -> E?

    The payload of a cell, or None when it is empty or the coordinates are outside the matrix.

    Matrix::in_incident

    source
    fn[E] Matrix::in_incident(self : Matrix[E], node : Int) -> ArrayView[Int]

    Matrix::in_neighbors

    source
    fn[E] Matrix::in_neighbors(self : Matrix[E], node : Int) -> ArrayView[Int]

    Matrix::incident

    source
    fn[E] Matrix::incident(self : Matrix[E], node : Int) -> ArrayView[Int]

    Matrix::neighbors

    source
    fn[E] Matrix::neighbors(self : Matrix[E], node : Int) -> ArrayView[Int]

    Matrix::new

    source
    fn[E] Matrix::new(nodes : Int) -> Matrix[E]

    A matrix of nodes rows and columns with every cell empty.

    Matrix::node_count

    source
    fn[E] Matrix::node_count(self : Matrix[E]) -> Int

    Matrix::remove

    source
    fn[E] Matrix::remove(self : Matrix[E], from : Int, to : Int) -> Unit

    Empties a cell.

    Matrix::set

    source
    fn[E] Matrix::set(self : Matrix[E], from : Int, to : Int, data : E) -> Unit

    Writes a cell, adding an edge when it was empty and replacing the payload when it was not.

    Partition

    source
    pub(all) struct Partition {
      label : Array[Int]
      count : Int
    }

    A partition of the nodes into groups.

    Paths

    source
    pub(all) struct Paths {
      distance : Array[Double?]
      previous : Array[Int?]
    }

    The result of a single-source search: one distance and one predecessor per node.

    Both arrays are indexed by node number, so no lookup happens and no entry can be missing. None in distance means the node cannot be reached from the sources — not infinity, not a large number — so a caller that forgets to handle it gets a type error rather than a poisoned sum.

    Paths::path_to

    source
    fn Paths::path_to(self : Paths, node : Int) -> Array[Int]?

    The node numbers from a source to node, source first, or None when the node was not reached.

    Paths::reached

    source
    fn Paths::reached(self : Paths, node : Int) -> Bool

    Whether the node was reached at all.

    Scores

    source
    pub(all) struct Scores {
      score : Array[Double]
    }

    A score per node.

    Spanning

    source
    pub(all) struct Spanning {
      edges : Array[Int]
      weight : Double
    }

    A spanning tree: its edges and its weight.

    StableGraph

    source
    pub struct StableGraph[N, E] {
      directed : Bool
      nodes : Array[N]
      node_alive : Array[Bool]
      vacant : Int
      payload : Array[E]
      froms : Array[Int]
      tos : Array[Int]
      alive : Array[Bool]
      live : Int
      out_nbrs : Array[Array[Int]]
      out_eids : Array[Array[Int]]
      in_nbrs : Array[Array[Int]]
      in_eids : Array[Array[Int]]
      empty : Array[Int]
    }

    An adjacency-list graph whose node numbers never change: removing a node leaves its number vacant and occupied numbers stay where they were.

    Use it when you hold node numbers across deletions — an index, a map from something else to a node, a list built in an earlier pass. Graph is cheaper when you do not, because it has no vacancy check on the way to the neighbours.

    test {
      let g : @moongraph.StableGraph[String, Unit] = @moongraph.StableGraph::new()
      for name in ["a", "b", "c"] {
        g.add_node(name) |> ignore
      }
      g.remove_node(1)
      assert_eq(g.node_count(), 2)
      assert_eq(g.is_vacant(1), true)
      assert_eq(g.highest_node(), Some(2))
    }
    impl Inbound for StableGraph[N, E]
    impl Topology for StableGraph[N, E]

    StableGraph::add_edge

    source
    fn[N, E] StableGraph::add_edge(self : StableGraph[N, E], from : Int, to : Int, data : E) -> Int

    Adds an edge from from to to carrying data, and returns its number.

    StableGraph::add_node

    source
    fn[N, E] StableGraph::add_node(self : StableGraph[N, E], data : N) -> Int

    Adds a node in the lowest vacant number, or at the end when none is vacant, and returns that number.

    StableGraph::contains_edge

    source
    fn[N, E] StableGraph::contains_edge(self : StableGraph[N, E], edge : Int) -> Bool

    Whether the edge exists and has not been removed.

    StableGraph::contains_node

    source
    fn[N, E] StableGraph::contains_node(self : StableGraph[N, E], node : Int) -> Bool

    Whether a node number is inside the graph and occupied.

    StableGraph::copy

    source
    fn[N, E] StableGraph::copy(self : StableGraph[N, E]) -> StableGraph[N, E]

    An independent copy.

    StableGraph::directed

    source
    fn[N, E] StableGraph::directed(self : StableGraph[N, E]) -> Bool

    StableGraph::edge_count

    source
    fn[N, E] StableGraph::edge_count(self : StableGraph[N, E]) -> Int

    StableGraph::edge_data

    source
    fn[N, E] StableGraph::edge_data(self : StableGraph[N, E], edge : Int) -> E

    The payload of an edge.

    StableGraph::edges

    source
    fn[N, E] StableGraph::edges(self : StableGraph[N, E]) -> Iter[Int]

    Every live edge number, ascending.

    StableGraph::endpoints

    source
    fn[N, E] StableGraph::endpoints(self : StableGraph[N, E], edge : Int) -> (Int, Int)

    StableGraph::find_edge

    source
    fn[N, E] StableGraph::find_edge(self : StableGraph[N, E], from : Int, to : Int) -> Int?

    The lowest-numbered edge from from to to.

    StableGraph::find_edges

    source
    fn[N, E] StableGraph::find_edges(self : StableGraph[N, E], from : Int, to : Int) -> Array[Int]

    Every edge between the pair, in number order.

    StableGraph::from_edges

    source
    fn[N, E] StableGraph::from_edges(edges : Array[(Int, Int)], node~ : N, edge~ : E, directed? : Bool) -> StableGraph[N, E]

    A graph built from (from, to) pairs, every node carrying node and every edge edge.

    StableGraph::highest_node

    source
    fn[N, E] StableGraph::highest_node(self : StableGraph[N, E]) -> Int?

    The largest occupied node number, or None for a graph with no nodes.

    StableGraph::in_incident

    source
    fn[N, E] StableGraph::in_incident(self : StableGraph[N, E], node : Int) -> ArrayView[Int]

    StableGraph::in_neighbors

    source
    fn[N, E] StableGraph::in_neighbors(self : StableGraph[N, E], node : Int) -> ArrayView[Int]

    StableGraph::incident

    source
    fn[N, E] StableGraph::incident(self : StableGraph[N, E], node : Int) -> ArrayView[Int]

    StableGraph::is_vacant

    source
    fn[N, E] StableGraph::is_vacant(self : StableGraph[N, E], node : Int) -> Bool

    Whether a node number is inside the graph and vacant.

    StableGraph::neighbors

    source
    fn[N, E] StableGraph::neighbors(self : StableGraph[N, E], node : Int) -> ArrayView[Int]

    StableGraph::new

    source
    fn[N, E] StableGraph::new(directed? : Bool) -> StableGraph[N, E]

    An empty graph.

    StableGraph::node_count

    source
    fn[N, E] StableGraph::node_count(self : StableGraph[N, E]) -> Int

    StableGraph::node_data

    source
    fn[N, E] StableGraph::node_data(self : StableGraph[N, E], node : Int) -> N

    The payload of an occupied node.

    StableGraph::nodes

    source
    fn[N, E] StableGraph::nodes(self : StableGraph[N, E]) -> Iter[Int]

    Every occupied node number, ascending.

    StableGraph::remove_edge

    source
    fn[N, E] StableGraph::remove_edge(self : StableGraph[N, E], edge : Int) -> Unit

    Removes an edge, leaving its number vacant.

    StableGraph::remove_node

    source
    fn[N, E] StableGraph::remove_node(self : StableGraph[N, E], node : Int) -> Unit

    Removes a node and every edge on it, leaving its number vacant.

    StableGraph::set_edge_data

    source
    fn[N, E] StableGraph::set_edge_data(self : StableGraph[N, E], edge : Int, data : E) -> Unit

    Replaces an edge's payload.

    StableGraph::set_node_data

    source
    fn[N, E] StableGraph::set_node_data(self : StableGraph[N, E], node : Int, data : N) -> Unit

    Replaces a node's payload.

    StableGraph::slot_count

    source
    fn[N, E] StableGraph::slot_count(self : StableGraph[N, E]) -> Int

    How many numbers exist, vacant ones included: one more than the largest number ever handed out.

    StableGraph::slot_data

    source
    fn[N, E] StableGraph::slot_data(self : StableGraph[N, E], slot : Int) -> N

    The payload in a slot, vacant or not. A vacant slot keeps the payload it had when it was removed, which is what lets a snapshot copy the array whole.

    StableGraph::to_directed

    source
    fn[N, E] StableGraph::to_directed(self : StableGraph[N, E]) -> StableGraph[N, E]

    The same graph, made directed, with its slot numbers kept — vacant slots stay vacant, so a node number means the same thing in both graphs. This is the conversion a StableGraph exists for: with Graph a copy is already exact, but here keeping the numbering is the whole point.

    StableGraph::to_undirected

    source
    fn[N, E] StableGraph::to_undirected(self : StableGraph[N, E]) -> StableGraph[N, E]

    The same graph, made undirected, with its slot numbers kept. Reciprocal arcs become one edge carrying the payload of the lowest-numbered arc, as in Graph::to_undirected.

    StableGraph::vacant_count

    source
    fn[N, E] StableGraph::vacant_count(self : StableGraph[N, E]) -> Int

    How many numbers are vacant.

    StableGraph::weights

    source
    fn[N, E] StableGraph::weights(self : StableGraph[N, E], of : (E) -> Double) -> ((Int) -> Double)

    A weight function over edge numbers, derived from one over payloads.

    Source Files

    Powered by MoonBit

    Site sourceReport issueModulesSkillsCLIBuild queueStatistics

    © 2026 mooncakes.io