lib.bend source

lib.bend on the hub · documented module

# Graph — foundational simple directed graph for Bend.# Consumer import entry (publish via seal.bend). Depends only on Base.## Nodes are U32 values. Edges are unique ordered pairs. add_edge adds both# endpoints if needed; nodes preserve insertion order and neighbors preserve edge order.import Basetype Edge is Data:  E{from: U32, to: U32}type Graph is Data:  G{nodes: List<&2, U32>, edges: List<&2, Edge>}def Graph.empty() -> Graph:  G{Nil{}, Nil{}}def Graph.add_node.go(ns: List<&2, U32>, es: List<&2, Edge>, x: U32, present: Bool) -> Graph:  match present:    case True{}:      G{ns, es}    case False{}:      G{List.append(&2, U32, ns, x <> Nil{}), es}def Graph.add_node(g: Graph, +x: U32) -> Graph:  match g:    case G{+ns, es}:      Graph.add_node.go(ns, es, x, List.contains(~U32, ~U32.is_eq, ns, x))def Graph.edge_eq(from: U32, to: U32, e: Edge) -> Bool:  match e:    case E{u, v}:      Bool.and(U32.is_eq(from, u), U32.is_eq(to, v))def Graph.has_edge.go(+from: U32, +to: U32, es: List<&2, Edge>) -> Bool:  match es:    case Nil{}:      False{}    case h <> t:      Bool.or(Graph.edge_eq(from, to, h), Graph.has_edge.go(from, to, t))def Graph.has_edge(g: Graph, from: U32, to: U32) -> Bool:  match g:    case G{ns, es}:      Graph.has_edge.go(from, to, es)def Graph.add_edge.go(ns: List<&2, U32>, es: List<&2, Edge>, from: U32, to: U32, present: Bool) -> Graph:  match present:    case True{}:      G{ns, es}    case False{}:      G{ns, List.append(&2, Edge, es, E{from, to} <> Nil{})}def Graph.add_edge.if(g: Graph, +from: U32, +to: U32) -> Graph:  match g:    case G{+ns, +es}:      Graph.add_edge.go(ns, es, from, to, Graph.has_edge(G{ns, es}, from, to))def Graph.add_edge(g: Graph, +from: U32, +to: U32) -> Graph:  Graph.add_edge.if(Graph.add_node(Graph.add_node(g, from), to), from, to)def Graph.neighbors.go(+from: U32, es: List<&2, Edge>) -> List<&2, U32>:  match es:    case Nil{}:      Nil{}    case h <> +t:      match h:        case E{u, v}:          Bool.pick(List<&2, U32>, U32.is_eq(from, u),            v <> Graph.neighbors.go(from, t),            Graph.neighbors.go(from, t))def Graph.neighbors(g: Graph, from: U32) -> List<&2, U32>:  match g:    case G{ns, es}:      Graph.neighbors.go(from, es)def Graph.nodes(g: Graph) -> List<&2, U32>:  match g:    case G{ns, es}:      nsdef Graph.edge_count(g: Graph) -> Nat:  match g:    case G{ns, es}:      List.length(&2, Edge, es)