#alga

#Quick start

moon add dowdiness/alga

// Build a graph: 1 → 2 → 3 → 4
let g = @alga.AdjacencyMap::from_edges([(1, 2), (2, 3), (3, 4)])

// Traverse
let r = @alga.reachable(g, 1)         // [1, 2, 3, 4]
let order = @alga.toposort(g)         // Some([1, 2, 3, 4])
let cyclic = @alga.has_cycle(g)       // false

// Strongly connected components
let sccs = @alga.tarjan_scc(g)        // [[4], [3], [2], [1]]

// DFS with edge classification
for event in @alga.dfs_events(g) {
  match event {
    @alga.BackEdge(u, v) => println("cycle: \{u} → \{v}")
    _ => ()
  }
}

// Reverse traversal: "what can reach vertex 4?"
let ancestors = @alga.reachable(@alga.reversed(g), 4)  // [4, 3, 2, 1]

// Algebraic construction
let expr = @alga.Graph::path([1, 2, 3])
let am = expr.to_adjacency_map()

#Why algebraic graphs?

#How it works

Observation layer                      Construction layer
(DirectedGraph + Predecessors)         (GraphSym + Graph enum)

  ┌─────────────────┐                    ┌──────────────────┐
  │ DirectedGraph    │                    │ GraphSym         │
  │  iter            │                    │  empty, vertex   │
  │  successors      │                    │  overlay, connect│
  │  (+ 4 defaults)  │                    └──────┬───────────┘
  ├─────────────────┤                           │
  │ Predecessors     │                     ┌────┴────┐
  │  predecessors    │    bridge:          │  Graph   │
  └──────┬──────────┘   foldg             │  (enum)  │
         │                                 └──────────┘
   ┌─────┴─────┐   ┌────────────┐
   │AdjacencyMap│   │ DenseGraph │
   └────────────┘   └────────────┘

• AdjacencyMap — Map[Int, Array[Int]] with bidirectional storage. Handles sparse, non-contiguous vertex IDs. Supports algebraic operations. O(log V) successor lookup.
• DenseGraph — Array[Array[Int]] with bidirectional storage. Requires vertex IDs in 0..n-1. O(1) successor lookup. 8–23x faster than AdjacencyMap for traversals.

#Algorithms

#Using your own graph type

struct MyGraph { edges : Array[Array[Int]] }

impl @alga.DirectedGraph for MyGraph with iter(self) {
  (0).until(self.edges.length())
}

impl @alga.DirectedGraph for MyGraph with successors(self, v) {
  self.edges[v].iter()
}

// Now available: toposort(g), tarjan_scc(g), reachable(g, 0),
// has_cycle(g), dfs_events(g), dfs_fold(g, ...), bfs_fold(g, ...), etc.

test "MyGraph conforms" {
  let g : MyGraph = make_test_graph()
  assert_eq(@alga.check_conformance(g), [])
  // assert_eq(@alga.check_predecessors_conformance(g), [])  // if MyGraph impls Predecessors
}

#Graph construction

#Design notes

#Repository layout

src/
  traits.mbt          DirectedGraph, Predecessors traits
  adjacency_map.mbt   AdjacencyMap — sparse representation
  dense_graph.mbt     DenseGraph — dense, high-performance representation
  reversed.mbt        Reversed[G] — zero-cost reverse-direction adaptor
  graph_expr.mbt      Graph enum — algebraic expression tree + foldg
  graph_sym.mbt       GraphSym trait — algebraic construction interface
  dfs.mbt             DFS fold, DFS events (edge classification)
  bfs.mbt             BFS fold
  toposort.mbt        Topological sort, topo levels, cycle detection
  scc.mbt             Kosaraju SCC, Tarjan SCC, condensation
  degree.mbt          Indegree, outdegree
docs/
  philosophy.md       Why algebraic graphs, the axiom system, design principles
  architecture.md     Two-layer design, trait system, algorithm details
  TODO.md             Active backlog

#Further reading

• Philosophy — the algebraic graph model and why it matters
• Architecture — trait design, representations, algorithm details
• Andrey Mokhov, Algebraic Graphs with Class (Haskell Symposium, 2017)
• Haskell algebraic-graphs package

#License