Thoughts on component testing

If software testing, we can compare the entire system to a jigsaw puzzle, with each component being a piece. To verify that a piece has the proper shape, we can do one of (at least) three things:

a) check whether it fits in its place,
b) check whether it fits with the pieces around it,
or c) compare it to another piece we already know has the required shape.

Approach a) is exactly standard unit testing - we simulate the proper environment for the piece, using fakes and control flow, and check whether it performs as expected. The challenge is simulating the correct "hole" for the component to fill - it's an exercise in negative space.

Option b) is integration testing. Theoretically speaking, much of it is not mandatory - as long as we've performed the proper unit tests, combinations of components should work as expected, like parts of a mathematical formula; when the number of components involved in a process grows beyond the trivial, we factor it out into separate master components and unit test those at a higher level of abstraction - which however introduces more opportunity for design flaws and excessive architecture.

More importantly, we are imperfect and so are our tests. We are not always capable of creating a perfect representation of the expected environment for our tested components - which, unlike jigsaw puzzle holes is implicit and multi-dimensional. Even well-tested components can be assumed to have undetected rough edges, and as the separate pieces integrate into the larger whole, their entropy multiplies and we risk ending up with an unpredictable system.

In the end, many integration tests serve as sanity checks to make up for deficiencies in our unit-testing code base, as well as to avoid unnecessary design layers.

Option c) would be testing by example, perhaps the topic of a future meditation. Stay tuned...

You know you're a software geek if you...

... need more non-letter characters on your keyboard.
... check your commit log to remind yourself how you spent your Sunday.
... understand what "It's all about the Pentiums" is about.
... know more programming languages than names of sports.
... find yourself jotting down programs on the subway.
... think everyone should be using hexadecimal.
... wish you had some free time so you could read more technical manuals.
... frequently use words like 'paradigm', 'implementation', 'iteration', 'overflow' and 'module'.
... think rainbow tables are SCARY.
... spend a large portion of your day optimizing the rest.
... when you hear "freedom from state", you think "Haskell"
... often repair things by rebuilding them from scratch.
... spend in a text editor or terminal the time other people spend watching TV.
... consider recursion a simple and elegant method for solving problems :-)

The Floyd-Warshall Algorithm

The classic Floyd-Warshall algorithm solves the "All-pairs shortest-path" problem on a weighted graph, namely, efficiently finding the length of the shortest route between every pair of vertices. It rests on the observation that if we denote the shortest path between A and B with {A,B}, then for every intermediate vertex K in {A,B}, {A,B}<={A,K}+{K,B}. A trivial recursive implementation follows:

floyd_warshall

    for each unordered pair (A,B)
        seen = [] // empty set
        min_paths[A,B] = fw_step(A,B)
        
fw_step A, B, seen

    if min_paths[A,B] exists
        return min_paths[A,B]
        
    min_path = |A,B| // direct distance between nodes
                     // may be infinity
                     
    seen[A,B] += 1 // dictionary keyed by unordered pair
    
    for each vertex K where seen[A,K] <= 1
                      and   seen[B,K] <= 1
        min_path = min(min_path, 
                       fw_step(A,K,seen) + fw_step(K,B,seen))
    
    return min_path

This is very inefficient. However, if we use an enumeration of all paths between A and B, based on the set of possible intermediate points [[], [0], [0,1], [0,1,2], ...], we can use that to remold the algorithm into an efficient dynamic programming solution:

    for K in [1; vertices] // for every vertex K find the shortest path {K,A,B}
    for A in [0; vertices) // that uses only [0..K-1] as intermediate nodes
    for B in [0; vertices)
        min_path[K, A, B] = min(min_path[K-1,A,B], 
                                min_path[K-1,A,K-1] + min_path[K-1,K-1,B])
                                
    // minimal paths for every A,B are in min_path[vertices, A, B]

A simple and neat O(n^3) solution to a daunting problem! Note that because we are checking the distance between nodes so often, the algorithm is vastly more efficient when using adjacency matrices rather than adjacency lists or edge lists for our graphs. Also, since in every iteration we're only using the previous enumeration level, min_path need only be of size 2*vertices^2:

    for K in [1; vertices]
    for A in [0; vertices)
    for B in [0; vertices)
        min_path[K%2, A, B] = min(min_path[(K-1)%2,A,B], 
                                  min_path[(K-1)%2,A,K-1] + min_path[(K-1)%2,K-1,B])
    
    // minimal paths for every A,B are in min_path[vertices%2, A, B]

Of course, this is overkill if you're only interested in the distance between two particular points - in that case, just use Dijkstra's algorithm, or some less general approach based on the specifics of your problem.

An important thing to note is that since the algorithm prefers shorter paths, it immediately ignores paths with cycles and repetitions (at least in the absence of negative edges); thus, it is not immediately adaptable to finding the longest paths by replacing min() with max(). It is possible to modify it for that purpose, however that requires looking out for malformed paths.