dafny pre-condition failure

Question

• I'm trying to run a dafny verified version of BFS (from here)
• My input graph is perfectly fine, but for some reason it fails the pre-condition check.
• Here is the permalink
• And for self completeness here is the graph definition + validity conditions

class Graph
{
    var adjList : seq<seq<int>>;
    constructor (adjListInput : seq<seq<int>>)
    {
        adjList := adjListInput;
    }
}
function ValidGraph(G : Graph) : bool
    reads G
{
    (forall u :: 0 <= u < |G.adjList| ==> forall v   :: 0 <= v <     |G.adjList[u]| ==> 0 <= G.adjList[u][v] < |G.adjList|) &&
    (forall u :: 0 <= u < |G.adjList| ==> forall v,w :: 0 <= v < w < |G.adjList[u]| ==> G.adjList[u][v] != G.adjList[u][w])
}
method main()
{
    var G : Graph := new Graph([[1,2],[0,2],[0,1]]);
    assert (ValidGraph(G));
}

• dafny's response is Error: assertion violation

Answer 1

You just need to add ensures adjList == adjListInput to the constructor. Because Dafny treats a constructor basically just like a method, and because Dafny analyzes each method in isolation, when Dafny analyzes main, it only uses the specification of the constructor, not the body of the constructor. So the reason the assert was failing was because from the perspective of main, the constructor was setting the field adjList to an arbitrary value that did not necessarily correspond to its argument.