Graphs

use graph.qweruse graph_shortest_path, graph_toposort from graph      // Quillo 0.6: only these

petgraph = "0.6"

// A delivery network and a project plan: the fastest route between depots, the order to do tasks// in, and the circular dependency that blocks it.////   quillo run graph.qwe      then open http://localhost:8080/route?from=Depot&to=Harbouruse "graph.qwer"let roads = [["Depot", "Market", 7], ["Depot", "Mill", 9], ["Depot", "Farm", 14], ["Market", "Mill", 10], ["Market", "Station", 15],             ["Mill", "Station", 11], ["Mill", "Farm", 2], ["Farm", "Harbour", 9], ["Station", "Harbour", 6], ["Island", "Lighthouse", 3]]route GET /route ? { from: str, to: str } {    let p = graph_shortest_path(roads, from, to, false)?    if p == null { reply 404 { error: `no road from ${from} to ${to}` } }    { route: join(p.path, " → "), minutes: p.distance }}route GET /islands = graph_components(roads)? | map((c) => len(c))let tasks = [["design", "build"], ["build", "test"], ["design", "docs"], ["test", "release"], ["docs", "release"], ["setup", "build"]]route GET /plan = {    order: graph_toposort(tasks)?.order,    after_build: graph_reachable(tasks, "build")?,    blocked: graph_toposort(push(tasks, ["release", "design"]))?.cycle,}

//! Graphs given as a list of edges: shortest paths with distances, build or task order (topological sort) with cycles named, groups of connected things, and everything reachable from a node. For routes, dependencies, org charts and social links.//! version: 1.0.0//!//! [dependencies]//! petgraph = "0.6"use petgraph::graph::{DiGraph, NodeIndex};use petgraph::visit::{Bfs, EdgeRef};use serde_json::{json, Value};use std::collections::{BTreeSet, HashMap};const MAX_EDGES: usize = 500_000;struct G {    g: DiGraph<String, f64>,    at: HashMap<String, NodeIndex>,}fn label(v: &Value) -> Result<String, String> {    match v {        Value::String(s) => Ok(s.clone()),        Value::Number(n) => Ok(n.to_string()),        other => Err(format!("a node is a name or a number, not {}", other)),    }}/// Edges as `["a", "b"]`, `["a", "b", 4.5]` or `{ from, to, weight }` (weight 1 when left out); undirected graphs get each edge both ways.fn build(edges: &[Value], directed: bool) -> Result<G, String> {    if edges.len() > MAX_EDGES {        return Err("at most 500,000 edges".into());    }    let mut g = G { g: DiGraph::new(), at: HashMap::new() };    let mut node = |g: &mut G, n: String| *g.at.entry(n.clone()).or_insert_with(|| g.g.add_node(n));    for e in edges {        let (a, b, w) = match e {            Value::Array(x) if x.len() == 2 || x.len() == 3 => (label(&x[0])?, label(&x[1])?, x.get(2).and_then(Value::as_f64).unwrap_or(1.0)),            Value::Object(_) => (label(&e["from"])?, label(&e["to"])?, e.get("weight").and_then(Value::as_f64).unwrap_or(1.0)),            Value::String(s) => {                // A lone name is a node with no edges.                node(&mut g, s.clone());                continue;            }            other => return Err(format!("an edge is [from, to], [from, to, weight] or {{ from, to, weight }}, not {}", other)),        };        if !w.is_finite() {            return Err("a weight is a finite number".into());        }        let (ia, ib) = (node(&mut g, a), node(&mut g, b));        g.g.add_edge(ia, ib, w);        if !directed {            g.g.add_edge(ib, ia, w);        }    }    Ok(g)}/// The cheapest path from `from` to `to`, adding up the weights (none may be negative): `{ path: [nodes], distance, steps }`, or null when `to` cannot be reached./// `directed` false lets every edge be walked both ways (roads); true only from → to (one-way streets, dependencies).pub fn graph_shortest_path(edges: Vec<serde_json::Value>, from: serde_json::Value, to: serde_json::Value, directed: bool) -> Result<Value, String> {    let g = build(&edges, directed)?;    if g.g.edge_weights().any(|w| *w < 0.0) {        return Err("shortest paths need weights of 0 or more".into());    }    let (Some(&s), Some(&t)) = (g.at.get(&label(&from)?), g.at.get(&label(&to)?)) else { return Ok(Value::Null) };    Ok(match petgraph::algo::astar(&g.g, s, |n| n == t, |e| *e.weight(), |_| 0.0) {        Some((cost, path)) => json!({ "path": path.iter().map(|i| g.g[*i].clone()).collect::<Vec<_>>(), "distance": cost, "steps": path.len().saturating_sub(1) }),        None => Value::Null,    })}/// An order in which every edge's `from` comes before its `to`: tasks after what they depend on, migrations, build steps. Ties keep the order nodes first appear./// Gives `{ order, cycle }`: when there is a cycle there is no order (`order` null) and `cycle` lists the nodes caught in one.pub fn graph_toposort(edges: Vec<serde_json::Value>) -> Result<Value, String> {    let g = build(&edges, true)?;    // Kahn's algorithm, taking ready nodes in the order they first appeared.    let n = g.g.node_count();    let mut indeg = vec![0usize; n];    for e in g.g.edge_references() {        indeg[e.target().index()] += 1;    }    let mut ready: BTreeSet<usize> = (0..n).filter(|i| indeg[*i] == 0).collect();    let mut order = Vec::new();    while let Some(&i) = ready.iter().next() {        ready.remove(&i);        order.push(g.g[NodeIndex::new(i)].clone());        for e in g.g.edges(NodeIndex::new(i)) {            let t = e.target().index();            indeg[t] -= 1;            if indeg[t] == 0 {                ready.insert(t);            }        }    }    if order.len() == n {        return Ok(json!({ "order": order, "cycle": null }));    }    let cycle = cycles(&g).into_iter().next().unwrap_or_default();    Ok(json!({ "order": null, "cycle": cycle }))}fn cycles(g: &G) -> Vec<Vec<String>> {    let mut out: Vec<Vec<String>> = petgraph::algo::tarjan_scc(&g.g)        .into_iter()        .filter(|c| c.len() > 1 || g.g.contains_edge(c[0], c[0]))        .map(|c| {            let mut c: Vec<NodeIndex> = c;            c.sort();            c.into_iter().map(|i| g.g[i].clone()).collect()        })        .collect();    out.sort();    out}/// The groups of nodes caught in cycles (each group: nodes that can all reach each other), for finding circular dependencies; `[]` when there are none.pub fn graph_cycles(edges: Vec<serde_json::Value>) -> Result<Vec<Vec<String>>, String> {    Ok(cycles(&build(&edges, true)?))}/// The connected groups, edges taken both ways: friend circles, islands of a network, duplicate clusters. Largest first, each in the order its nodes first appear.pub fn graph_components(edges: Vec<serde_json::Value>) -> Result<Vec<Vec<String>>, String> {    let g = build(&edges, false)?;    let mut seen = vec![false; g.g.node_count()];    let mut out = Vec::new();    for start in g.g.node_indices() {        if seen[start.index()] {            continue;        }        let mut part = Vec::new();        let mut bfs = Bfs::new(&g.g, start);        while let Some(n) = bfs.next(&g.g) {            if !seen[n.index()] {                seen[n.index()] = true;                part.push(n);            }        }        part.sort();        out.push(part.into_iter().map(|i| g.g[i].clone()).collect::<Vec<_>>());    }    out.sort_by(|a, b| b.len().cmp(&a.len()));    Ok(out)}/// Every node reachable from `from` by following edges forward (`from` left out), nearest first: what depends on a package, who reports to a manager.pub fn graph_reachable(edges: Vec<serde_json::Value>, from: serde_json::Value) -> Result<Vec<String>, String> {    let g = build(&edges, true)?;    let Some(&s) = g.at.get(&label(&from)?) else { return Ok(vec![]) };    let mut bfs = Bfs::new(&g.g, s);    let mut out = Vec::new();    while let Some(n) = bfs.next(&g.g) {        if n != s {            out.push(g.g[n].clone());        }    }    Ok(out)}