# Implement custom `shrink` for non-algebraic graph data types #150

Open
opened this Issue Nov 28, 2018 · 0 comments

Projects
None yet
1 participant
Owner

### snowleopard commented Nov 28, 2018 • edited

Right now we do not provide a custom implementation of the method `shrink` in `Arbitrary` instances of non-algebraic data types, such as `AdjacencyMap`, which makes it difficult to understand test failures, e.g. see https://travis-ci.org/snowleopard/alga/jobs/460799751:

``````============ Labelled.AdjacencyMap.replaceEdge ============
Test failure:
replaceEdge e x y m                 == overlay (removeEdge x y m) (edge e x y)
*** Failed! Falsifiable (after 11 tests and 3 shrinks):
Sum {getSum = 0}
1
0
edges [(Sum {getSum = 6},-10,-10),(Sum {getSum = -5},-10,-5),(Sum {getSum = -2},-10,-2),(Sum {getSum = 2},-10,5),(Sum {getSum = 2},-10,6),(Sum {getSum = -7},-10,7),(Sum {getSum = -5},-9,-9),(Sum {getSum = 6},-9,-7),(Sum {getSum = 2},-9,-5),(Sum {getSum = 9},-9,-2),(Sum {getSum = -10},-9,1),(Sum {getSum = -5},-9,6),(Sum {getSum = -9},-3,-10),(Sum {getSum = 2},-3,-9),(Sum {getSum = -1},-3,-3),(Sum {getSum = 4},-3,3),(Sum {getSum = 2},-3,7),(Sum {getSum = 10},-3,9),(Sum {getSum = 3},0,-5),(Sum {getSum = -5},0,-3),(Sum {getSum = 2},0,2),(Sum {getSum = 10},1,-10),(Sum {getSum = -6},1,-9),(Sum {getSum = -3},1,-7),(Sum {getSum = -1},1,-5),(Sum {getSum = 9},1,-3),(Sum {getSum = -10},1,-1),(Sum {getSum = 2},1,5),(Sum {getSum = 0},1,6),(Sum {getSum = 1},1,7),(Sum {getSum = -1},1,8),(Sum {getSum = 8},1,10),(Sum {getSum = 12},5,-8),(Sum {getSum = 5},5,-7),(Sum {getSum = -1},5,-6),(Sum {getSum = -4},5,-5),(Sum {getSum = 4},5,-3),(Sum {getSum = -9},5,-2),(Sum {getSum = -1},5,-1),(Sum {getSum = 0},5,1),(Sum {getSum = 9},5,4),(Sum {getSum = -3},5,5),(Sum {getSum = -4},5,6),(Sum {getSum = 5},5,7),(Sum {getSum = 2},5,9),(Sum {getSum = 5},5,10),(Sum {getSum = 1},10,-8)]
``````

One simple custom `shrink` method would try to delete a vertex or an edge -- hopefully that would lead to much simpler counterexamples.

Here is one of the corresponding TODOs in the code (there are a few more):

Lines 112 to 114 in 9f64c82

 -- TODO: Implement a custom shrink method. instance (Arbitrary a, Ord a) => Arbitrary (AdjacencyMap a) where arbitrary = arbitraryAdjacencyMap

This is an easy task, suitable for a newcomer.