Understand

Declaring a graph and searching it

A graph is a model. Write its nodes and edges with what you know about them, inherit every algorithm, and call them by name.

1. Declare the graph

open Prelude.Graphs

model Roads : Graph {
  node home   { x = 0, y = 0, population = 1200, label = "Home" }
  node park   { x = 1, y = 1, label = "Central Park" }
  node shop   { x = 2, y = 0, label = "Market" }
  node office { x = 6, y = 0 }

  edge home → shop   { length = 4, time = 7, toll = 0, capacity = 30, road = "A1" }
  edge home → park   { length = 2, time = 3, capacity = 10 }
  edge park ↔ shop   { length = 1, time = 2, capacity = 10 }
  edge shop → office { length = 5, time = 6, toll = 2, capacity = 20 }
}

→ (or ->) is one direction, ↔ (or <->) both. An attribute is a number or a quoted text; the braces are optional. The nodes are numbered in the order the model first names them: home 0, park 1, shop 2, office 3.

2. Say what a path costs, and how far a place looks

  def cost(edges)  ≔ time(edges) + 2 · toll(edges)
  def heuristic(v) ≔ distanceTo(v, office)

time(edges) is the time of every edge at once, 0 where an edge does not say; cost is what every path algorithm minimises (without it, length, and without that, 1 per edge). distanceTo(v, office) is the straight line from every place to the office, over the node attributes x and y. Write edges, not e: e is Euler’s number.

3. Call it from C#

var g = new Roads();
g.Path("home", "office");                // home, park, shop, office — cost 15
g.Path("home", "office", by: "length");  // the same route, length 8
g.Path("home", "office", by: "toll");    // home, shop, office
g.Node("park").Label;                    // "Central Park"
g.Edge("home", "shop").Road;             // "A1"
g.MaxFlow("home", "office").Value;       // 20 — the office road is full
g.Attribute("population");               // [1200, 0, 0, 0]

Every answer here is asserted by GraphSampleCase. Numbers in a record are double?: g.Edge("home", "shop").Toll is 0, g.Edge("home", "park").Toll is null. Each method also takes node indices: g.Path(0, 3).

An attribute an edge does not declare is two different answers: 0 in a formula, null in C#. by: names a numeric edge attribute — by: "label" is an ArgumentException listing the ones that are numbers.

4. A* and its estimate

The heuristic names its goal. On the Sample’s twelve-place Town, the straight line closes 4 places where the same roads without a map close 12, for the same route of 8 (GraphSampleCase.A_straight_line_estimate_reaches_the_tower_closing_four_places_of_twelve). A* is guaranteed cheapest only while no edge costs less than its straight line under the weighting searched — true of Roads under its cost, not under length. Strictly, the estimate must be consistent (\(h(u) \le C_{uv} + h(v)\)), not merely admissible: the goal closes the search and a closed node is never reopened. def pathWeight ≔ 0 makes the same search greedy best-first.

5. Pick an algorithm

Question	Method
cheapest distances and routes	Dijkstra, Path
cheapest route with an estimate	AStar
negative weights, negative cycles	BellmanFord
fewest hops; the order a search meets places	Bfs, Dfs
an order for tasks; when each can start	Topological, Longest, CriticalPath
the cheapest network joining everything	SpanningTree, Prim
how much gets through, and what limits it	MaxFlow
who matters	Closeness, Betweenness, Degree, Eigenvector, PageRank

6. What the answers promise

Every tie goes to the lowest node index, so an answer is a function of the graph alone — but that also means a breadth-first parent is the lowest-indexed node of the frontier reaching it, not the first in a FIFO queue. Distances are sums, so every comparison tolerates rounding at a relative \(10^{-12}\): weights below that are one flat tie, and a negative cycle lighter than that is not flagged. Eigenvector answers NaN rather than a number power iteration has not settled on (raise iterations). Betweenness counts ordered pairs, unnormalised, endpoints excluded — halve it for an undirected graph. Closeness and Degree answer what networkx answers, including at \(n = 1\). The full list is in the Graphs reference.

Two names to keep clear of: a graph’s own def may not take a Prelude name its inherited algorithms reach (positions, say — the build stops with HB0001), and a node may not be called adjacency, nodeTable, edgeTable, e, pi, or the same as one of the graph’s defs.

The build says what is wrong in the graph’s own words: edges without : Graph, an attribute that is a number on one node and text on another, a formula reading a text attribute, a cost reading an attribute no edge has, distanceTo without x and y.