From 78141459980d57b08a6dc045de55075a307402eb Mon Sep 17 00:00:00 2001
From: Nathaniel Wesley Filardo <nwf@cs.jhu.edu>
Date: Mon, 10 Jun 2013 01:04:57 -0400
Subject: [PATCH] Initial example of Euclidean Dijkstra example

See nwf/dyna#16; still open to improve.
---
 docs/sphinx/tutorial/dijkstra.rst | 11 +++++++++++
 examples/dijkstra-euclid.dyna     | 29 +++++++++++++++++++++++++++++
 2 files changed, 40 insertions(+)
 create mode 100644 examples/dijkstra-euclid.dyna

diff --git a/docs/sphinx/tutorial/dijkstra.rst b/docs/sphinx/tutorial/dijkstra.rst
index d3d3d5b..5eb4d74 100644
--- a/docs/sphinx/tutorial/dijkstra.rst
+++ b/docs/sphinx/tutorial/dijkstra.rst
@@ -213,6 +213,17 @@ special value :term:`null`, which is the *identity* of every aggregator and
 a *zero* of every expression.  Since we aggregate answers with ``min=``,
 :term:`null` approximates :math:`+\infty`.
 
+Deriving The Graph From Rules
+=============================
+
+There's nothing that mandates that ``edge`` weights be the base case; we
+could also derive ``edge`` facts from other facts, such as position and
+reachability.  An example is available in ``examples/dijkstra-euclid.dyna``
+(or :dynasrc:`here <examples/dijkstra-euclid.dyna>`).
+
+
+.. todo:: This section is mostly a placeholder!
+
 Endnotes
 ========
 
diff --git a/examples/dijkstra-euclid.dyna b/examples/dijkstra-euclid.dyna
new file mode 100644
index 0000000..f710513
--- /dev/null
+++ b/examples/dijkstra-euclid.dyna
@@ -0,0 +1,29 @@
+% Dijkstra's algorithm for single-source shortest path
+path(start) min= 0.0.
+path(B) min= path(A) + edge(A,B).
+goal min= path(end).
+
+% Euclidean distance on reachable pairs.
+edge(A,B) := ((AX-BX)**(2.0) + (AY-BY)**(2.0))**(0.5)
+             for pair(AX,AY) is pos(A),
+                 pair(BX,BY) is pos(B),
+                 reachable(A,B).
+
+% Assert the position of some places on the map
+pos("origin") := pair(0.0,0.0).
+pos("t1"    ) := pair(1.0,2.0).
+pos("PyTrip") := pair(3.0,4.0).
+pos("t2"    ) := pair(2.0,3.5).
+
+% separately, assert the adjacency graph
+reachable("origin","t1").
+reachable("origin","PyTrip").
+reachable("t1"    ,"PyTrip").
+reachable("PyTrip","t2").
+reachable("t1"    ,"t2").
+
+start := "origin".
+end   := "t2".
+
+% This file is mentioned in the tutorial!
+% XREF:docs/sphinx/tutorial/dijkstra.rst
-- 
2.50.1