A graph is a model that declares nodes and edges and names Graph as its parent. node a { k = v, … } and edge a → b { … } (->; ↔/<-> both ways) carry attributes: a number, or a quoted text. The braces are optional, and a node no node line declares exists through its edges. Nodes are numbered in the order the model first names them — the order every tie is broken by. See Declaring a graph and searching it.

open Prelude.Graphs

model Roads : Graph {
  node park { x = 1, y = 1, label = "Central Park" }
  edge home → shop { length = 4, time = 7, toll = 0, road = "A1" }
  edge home → park { length = 2, time = 3 }
  edge park ↔ shop { length = 1, time = 2 }
  edge shop → office { length = 5, time = 6, toll = 2 }

  def cost(edges) ≔ time(edges) + 2 · toll(edges)
}

Attributes in formulas

A numeric attribute is a def of its own name: population(v) reads a node attribute at the nodes v marks, and time(edges) an edge attribute on the edges edges marks — 0 where a node or edge does not declare it. In a graph’s defs v stands for every node and the parameter of cost for every edge, so cost is element-wise over the whole edge matrix. A text attribute never reaches a formula; C# reads it. A node name inside a def of its graph is that node’s index. (e is Euler’s number: never a parameter name, never a node name.)

Graph gives	Default	A graph overrides by
length(uv), capacity(uv), strength(uv)	1 on every edge	declaring the edge attribute
x(v), y(v)	0	declaring the node attribute
cost(uv) — what every path algorithm minimises	length(uv)	def cost(edges) ≔ …
heuristic(v) — A*’s estimate, naming its own goal	0 (A* is Dijkstra)	def heuristic(v) ≔ distanceTo(v, office)
distanceTo(v, goal)	Euclidean over x, y	— (refused when the nodes lack them)
pathWeight	1	0 — greedy best-first
damping, iterations	0.85, 200	PageRank’s damping; power iterations

The class

C#	Answers	Case
Nodes, Index(name), Name(i), Count	the nodes	AdjacencyClassCase
Node(name)	NodeAttributes — Name, Index, one double?/string? per attribute, null where undeclared	AdjacencyClassCase
Edge(from, to), Linked(from, to)	EdgeAttributes — From, To, the attributes; ArgumentException when not an edge	AdjacencyClassCase
Attribute(name), Describe(names)	a numeric attribute as [n] or [n, n]; the named nodes’ records	AdjacencyClassCase
Adjacency, NodeTable, EdgeTable, Costs()	the matrices the defs read	AdjacencyClassCase
Dijkstra(source, by), Path(source, goal, by)	ShortestPaths; the cheapest route’s names	RouteCase, GraphSampleCase
AStar(source, goal, by)	Route — places, length, nodes closed	RouteCase.A_star_by_name_closes_four_places_where_no_estimate_closes_twelve
BellmanFord(source, by), Longest(source, by), CriticalPath(source, goal, by)	negative weights and cycles; the longest paths of a DAG	RouteCase
Bfs(source), Dfs(source), Topological()	BreadthFirst, DepthFirst, TopologicalOrder	TraversalCase
SpanningTree(by), Prim(by)	SpanningForest — links, weight	SpanningCase
MaxFlow(source, sink, by)	MaximumFlow over capacity — value, links carrying flow, source side of a minimum cut	FlowCase
Distances(by), Closeness(by), Betweenness(by), Degree(), Eigenvector(by), PageRank(by)	by name; the last two weigh strength	CentralityCase

by names a numeric edge attribute and swaps the weighting; any other name is an ArgumentException listing the valid ones. Every method taking a node also takes its index. Every def is a method too, over tensors and indices.

What each answer holds

Record	Fields
ShortestPaths	Distances (name → length, \(+\infty\) unreached), Parents (name → parent, null for the source and for anything unreached), NegativeCycle
Route	Places (source first, empty when the goal cannot be reached), Length (\(+\infty\) when there is none), Expanded (nodes closed)
BreadthFirst	Levels (hops), Parents
DepthFirst	Discovery, Finish, Parents
TopologicalOrder	Order (the nodes placed, shorter than the graph when it is not a DAG), Acyclic
SpanningForest, MaximumFlow	Links (Link(From, To, Weight)) and Weight; Value, Links, SourceSide

Longest and every centrality answer a name → number dictionary; Distances() a dictionary of dictionaries; Path and CriticalPath a list of names.

Guarantees, and what they do not cover

• A* wants a consistent estimate. The goal closes the search and a closed node is never reopened, so the route is cheapest only while \(h(u) \le C_{uv} + h(v)\) for every edge. Merely admissible is not enough here: an admissible but inconsistent estimate can answer a route that is not the cheapest. A straight line over x, y is consistent whenever no edge costs less than the line it follows — true of Roads under its cost, not under length.
• Rounding is not a difference. A length is a sum, so 0.1 + 0.2 and 0.15 + 0.15 are one length: every comparison of distances, costs and flows is tolerant at a relative \(10^{-12}\) with an absolute floor of \(10^{-12}\). Two consequences: weights below about \(10^{-12}\) are all one flat tie, and a negative cycle lighter than that is not flagged.
• A tie goes to the lowest index, everywhere — Dijkstra’s pick, Bellman–Ford’s parent, Kahn’s ready node, Kruskal’s next edge. A breadth-first parent is the lowest-indexed node of the frontier that reaches it, not the first in a FIFO queue, so Bfs parents need not match a queue-based implementation’s.
• pathTo(P, target) asks nothing. It walks whatever parent vector it is handed, so an unreachable target — parent \(-1\) — answers [target, −1, …], the target alone as if it were the source. Gate on reachability first; shortestRoute does, and answers all \(-1\).
• Eigenvector centrality answers NaN rather than a number it has not reached. Power iteration over \(W + I\) only converges when the leading eigenvalue is simple and strictly largest, which a reducible graph — a DAG, or parts that do not reach one another — need not give. The vector is answered only when a further turn moves it by less than \(10^{-9}\); otherwise every entry is NaN. Raise iterations and ask again.
• Closeness and degree follow networkx at \(n = 1\). Closeness is outward and Wasserman–Faust, \(r^2 / ((n-1)\sum d)\), and 0 whenever that sum is 0 — a node reaching none, the only node of a graph of one, or a component joined by zero-length edges alone. Degree counts out-edges other than a self-loop over \(n - 1\), and is 1 for the only node of a graph of one.
• Betweenness counts ordered pairs, unnormalised, with the endpoints excluded (\(\sum_{s \ne v}\)): halve it for an undirected graph. It wants positive weights — a zero-weight cycle would put a cycle in the shortest-path DAG.
• A graph’s own def may not take a Prelude name its inherited algorithms reach. def positions ≔ … is not a private helper: the algorithms would call it instead of Prelude’s, and the build stops with HB0001. Give it a name of its own.
• Node names are checked too. adjacency, nodeTable and edgeTable are how a graph is read; e and pi are constants a formula reads; and a node may not share its name with one of the graph’s defs (heuristic, cost, …). Each is refused by name at build time.

The algorithms, over matrices

Every algorithm is also a module-level def over a plain tensor — a node is a number — so a matrix built at run time works the same from a fn. A tie goes to the lowest index; an unreachable node is \(+\infty\) away with parent \(-1\); a route is a length-\(n\) vector, the source first, padded with \(-1\). A mask becomes a length by division, \(\operatorname{unreached}(r) = (1-r)/r\) and \(\operatorname{shut}(v) = v/(1-v)\). Each algorithm is one loop.

Family	Defs	Formulation
Views	linked, edgeLengths, unreached, shut, costsOf(W), negatedCosts, nodeSlots, nodeHot	a weight at or above \(10^{308}\) is no edge
Search	searchRun(want, C, a, H, s, goal), shortestLengths/Parents(C, s), shortestRoute(C, s, goal), guidedLength/Route/Expansions(C, s, goal, H), pathTo(P, target)	\(n\) turns; key \(a\,d + H\); the least-key reached, unclosed node closes
Bellman–Ford	bellmanLengths, bellmanParents, bellmanRoute, negativeCycle	\(n\) synchronous turns; the \(n\)-th turn’s improvement is the cycle flag
Traversal	hopLevels, hopParents, reachable, depthOrder, finishOrder, depthParents, topologicalOrder, acyclic	the DFS stack is a place vector; Kahn takes the lowest ready node
Spanning	primParents, primWeight, primEdges, kruskalEdges, kruskalWeight	Kruskal without a sort
Flow	maxFlow(K, s, sink), flowMatrix, minCut	Edmonds–Karp over a skew-symmetric flow
Centrality	allPairs, closenessCentrality, betweenness, degreeCentrality, eigenCentrality(t, W)	Manifold’s min-plus closure; Brandes by path counts over ordered pairs

PageRank is Patterns’ pagerank(t, W, d), which Graph calls.