From 21a77482adf7ad702847e6d8a0975a4ecc0251be Mon Sep 17 00:00:00 2001
From: Jason Eisner <jason@cs.jhu.edu>
Date: Wed, 10 Jul 2013 04:35:01 -0400
Subject: [PATCH] simplified examples/dijkstra-backpointers.dyna, and added a
 variant

---
 debug                                |  0
 examples/dijkstra-backpointers.dyna  | 21 ++++++++++--------
 examples/dijkstra-backpointers2.dyna | 32 ++++++++++++++++++++++++++++
 3 files changed, 44 insertions(+), 9 deletions(-)
 mode change 100755 => 100644 debug
 create mode 100644 examples/dijkstra-backpointers2.dyna

diff --git a/debug b/debug
old mode 100755
new mode 100644
diff --git a/examples/dijkstra-backpointers.dyna b/examples/dijkstra-backpointers.dyna
index b550665..68f5f97 100644
--- a/examples/dijkstra-backpointers.dyna
+++ b/examples/dijkstra-backpointers.dyna
@@ -1,7 +1,16 @@
-% single source shortest path with optimal path extraction.
-path(start) min= 0                   with_key start.
+% Single source shortest path with optimal path extraction.
+
+% Cost of the optimal path from start to each node.  
+path(start) min= 0                   with_key [].
 path(B)     min= path(A) + edge(A,B) with_key A.
-goal        min= path(end)           with_key end.
+
+% The cost of the optimal path to the end node, and that path itself.
+goal        = path(end).
+optimalpath = reverse(bestpath(end)).
+
+% extract cheapest path by following backpointers from each vertex.
+bestpath(V) := [V | bestpath($key(path(V)))].
+bestpath(start) := [start].
 
 % expensive path
 edge("a","b") := 1.
@@ -16,12 +25,6 @@ edge("e","d") := 1.
 start := "a".
 end := "d".
 
-% extract cheapest path by following backpointers from each vertex.
-bestpath(start) := [start].
-bestpath(V) := U is $key(path(V)), [V | bestpath(U)] for V != start.
-
-% the optimal path is the one from the `end`.
-optimalpath = reverse(bestpath(end)).
 
 % ---------------------------------------
 % list utilities
diff --git a/examples/dijkstra-backpointers2.dyna b/examples/dijkstra-backpointers2.dyna
new file mode 100644
index 0000000..bb7948e
--- /dev/null
+++ b/examples/dijkstra-backpointers2.dyna
@@ -0,0 +1,32 @@
+% Single source shortest path with optimal path extraction.
+% This version is briefer but possibly less efficient.
+
+% Cost of the optimal path from start to each node.  
+% In each case, the associated key is a reversed version of the path itself.
+path(start) min= 0                   with_key [start].
+path(B)     min= path(A) + edge(A,B) with_key P for P is append($key(path(A)),B).
+
+% The cost of the optimal path to the end node, and that path itself.
+goal        = path(end).
+optimalpath = $key(path(end)).
+
+% expensive path
+edge("a","b") := 1.
+edge("b","c") := 1.
+edge("c","d") := 1.
+
+% cheap path
+edge("a","e") := 1.
+edge("e","d") := 1.
+
+% define begining and end.
+start := "a".
+end := "d".
+
+
+% ---------------------------------------
+% list utilities
+
+:- backchain append/2.
+append([], Y) = [Y].
+append([X|Xs], Y) = [X|append(Xs, Y)].
-- 
2.50.1