1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
|
// Schorr-Waite algorithm in Chalice
// (see Test/dafny1/SchorrWaite.dfy)
// Add arbitrary number of children, not just two.
// Remove visited field for visited nodes; next node is selected non-deterministically (verification time 30s)
// Added parent pointer p (stack remains) (verification time 8s, limited functions)
class Node {
var children: seq<Node>;
var marked: bool;
ghost var path: seq<Node>;
}
class Main {
function Reachable(to: Node, p:seq<Node>, from: Node): bool
requires acc(p[*].children);
{
|p| == 0 ? to == from :
(p[0] != null && to in p[0].children && Reachable(p[0], p[1..], from))
}
method SchorrWaite(root: Node, S: seq<Node>)
requires acc(S[*].*);
requires root in S;
requires forall n in S :: n != null && (forall ch in n.children :: ch != null && ch in S);
requires forall n in S :: ! n.marked;
ensures acc(S[*].*);
// graph structure is the same
ensures forall n in S :: n.children == old(n.children);
// all nodes reachable from root are marked
ensures root.marked;
ensures forall n in S :: n.marked ==> (forall ch in n.children :: ch.marked);
// all marked nodes are reachable from root
ensures forall n in S :: n.marked ==> (forall m in n.path :: m in S) && Reachable(n, n.path, root);
{
var p:Node := null;
var t:Node := root;
t.marked := true;
var stack: seq<Node> := [];
t.path := stack;
// no termination check
var stop := false;
while(!stop)
invariant acc(S[*].*);
invariant root.marked;
invariant t in S && t.marked && t !in stack;
// stack well-formed
invariant forall i in [0..|stack|] :: forall j in [i+1..|stack|] :: stack[i] != stack[j];
invariant forall n in stack :: n in S && n.marked;
invariant forall i in [1..|stack|] :: stack[i-1] in stack[i].children;
invariant 0 < |stack| ==> p == stack[0] && t in p.children;
invariant 0 == |stack| ==> p == null;
// goal
invariant forall n in S :: n.marked && n !in stack && n != t ==>
(forall ch in n.children :: ch in S && ch.marked);
invariant forall n in S :: n.marked ==>
(forall m in n.path :: m in S) && Reachable(n, n.path, root);
// preservation
invariant forall n in S :: n.children == old(n.children);
// termination
invariant stop ==> |stack| == 0 && (forall ch in t.children :: ch.marked);
{
call n := PickUnmarked(t.children);
if (n != null) {
// push
p := t;
stack := [t] ++ stack;
n.path := [t] ++ t.path;
t := n;
t.marked := true;
assert Reachable(t.path[0], t.path[1..], root); // limited function
} else {
// pop
if (p == null) {
stop := true;
} else {
t := p;
stack := stack[1..];
p := |stack| > 0 ? stack[0] : null;
}
}
}
}
method PickUnmarked(p: seq<Node>) returns (x: Node)
requires rd(p[*].marked);
requires forall n in p :: n != null;
ensures rd(p[*].marked);
ensures x != null ==> x in p && ! x.marked;
ensures x == null ==> (forall n in p :: n.marked);
{
assume false; // magic!
}
}
|
