2
\$\begingroup\$

Consider a process composed of three algorithms: makeRuns, meld and traverse (each taking the output of the previous one as input): it is interesting to test each separately. Now consider three (or more) instances (e.g. singleton, twoPairs, SimplePair): it is interesting to test the behavior of the three algorithms on each of those instances. The result can be described as an array of (say) 3*3 tests. Is the code below the correct implementation of such a test? (I find the result of the tests to be lacking in clarity.)

import unittest, doctest
import insertionRank

##############################################################################
class TestMTDRAG(unittest.TestCase):

    def test_singleton(self):
        """Basic example [1]."""
        run = makeRuns([1])
        self.assertEqual(run,[Node(1,1)])
        graph = meld(run)
        self.assertEqual(graph,Node(1,1))
        lengths=traverse(graph)
        self.assertEqual(lengths,[1,0])

    def test_TwoPairsExample(self):
        """Two messages of distinct probabilities [1,2]."""
        run = makeRuns([1,2])
        self.assertEqual(run,[Node(1,1),Node(2,1)])
        graph = meld(run)
        self.assertEqual(graph,Node(3,1,[Node(1,1),Node(2,1)]))
        lengths=traverse(graph)
        self.assertEqual(lengths,[0,2,0])

    def test_SimplePairExample(self):
        """Basic example of four equiprobable messages [1,1,1,1]."""
        run = makeRuns([1,1,1,1])
        self.assertEqual(run,[Node(1,4)])
        graph = meld(run)
        self.assertEqual(graph,
                         Node(4,1,
                              [Node(2,2,[Node(1,4),Node(1,4)]),
                               Node(2,2,[Node(1,4),Node(1,4)])
                               ]))
        lengths=traverse(graph)
        self.assertEqual(lengths,[0,0,4])
##############################################################################

class Node(object):
    """
    A node in a MTDRAG (Moffat-Turpin Directed Rooted Acyclic Graph).
    """

    def __init__(self, weight, frequency, children=[], minDepth=None, nbPathsAtMinDepth=0, nbPathsAtMinDepthPlusOne=0):
        assert frequency>0
        self.weight = weight
        self.frequency = frequency
        self.children = children
        self.minDepth= minDepth
        self.nbPathsAtMinDepth = nbPathsAtMinDepth
        self.nbPathsAtMinDepthPlusOne = nbPathsAtMinDepthPlusOne

    def computeDepths(self,depthParent=-1,nd=1,ndp1=0):
        assert self.frequency>0
        if self.minDepth==None: # Node is not yet labeled
            self.minDepth = depthParent+1
            self.nbPathsAtMinDepth = nd
            self.nbPathsAtMinDepthPlusOne = ndp1
        elif self.minDepth == depthParent: # Node labeled at same depth as parent
            self.nbPathsAtMinDepthPlusOne += nd
        else:
            assert(self.minDepth==depthParent+1) # Node labeled at depth + 1 of parent
            self.nbPathsAtMinDepth += nd
            self.nbPathsAtMinDepthPlusOne += ndp1
        if self.nbPathsAtMinDepthPlusOne > 0:
            maxDepth = depthParent+2
        else:
            maxDepth = depthParent+1
        for child in self.children:
            maxDepth = max( maxDepth,
                            child.computeDepths(depthParent+1,self.nbPathsAtMinDepth,self.nbPathsAtMinDepthPlusOne)
                            )
        return maxDepth

    def collectDepths(self,M):
        assert self.frequency>0
        if self.children == []: 
            M[self.minDepth] += self.nbPathsAtMinDepth
            M[self.minDepth+1] += self.nbPathsAtMinDepthPlusOne
        else:
            for child in self.children:
                child.collectDepths(M)

    def __eq__(self,node):
        assert self.frequency>0
        if node == None:
            return False
        assert node.frequency>0
        return self.weight==node.weight and self.frequency == node.frequency and self.children == node.children

    def __str__(self):
        assert self.frequency>0
        if self.children == None:
            return "("+str(self.weight)+", "+str(self.frequency)+")"
        else:
            return "("+str(self.weight)+", "+str(self.frequency)+", "+str(self.children)+")"

    def __repr__(self):
        assert self.frequency>0
        return self.__str__()

    def copy(self):
        assert self.frequency>0
        return Node(self.weight,self.frequency,self.children,self.minDepth,self.nbPathsAtMinDepth,self.nbPathsAtMinDepthPlusOne)

##############################################################################

def makeRuns(A):
    """Compresses a list of INTEGER weights into a list of nodes, in
    sublinear time (if all weights are not distinct). 

    """
    A.sort() # Linear if already sorted
    output = []
    position = 0
    while position < len(A):
        weight = A[position]
        frequency = insertionRank.fibonacciSearch(A[position:],weight+1)
        output.append(Node(weight,frequency))
        position += frequency
    return output


def meld(leaves):
    """Moffat and Turpin's algorithm to simulate van Leeuwen's
    algorithm on a compressed representation of a list of weights.

    """
    assert(len(leaves)>0)
    graphs = []
    source = leaves
    first = source[0]
    while first.frequency>1 or len(leaves)+len(graphs)>=2:
        if first.frequency>1:
            graphs.append(Node(first.weight*2,first.frequency//2,[first,first]))
            if first.frequency %2 == 1:
                first.frequency = 1
            else:
                source.remove(first)
        else: #first.frequency == 1 but len(leaves)+len(graphs)>=2
            source.remove(first)
            source = min(s for s in (leaves,graphs) if s)
            second = source[0]
            assert(second.frequency>0)
            if second.frequency==1:
                source.remove(second)
                graphs.append(Node(first.weight+second.weight,1,[first,second]))
            else:
                extract = second.copy()
                extract.frequency=1
                second.frequency -= 1
                graphs.append(Node(first.weight+extract.weight,1,[first,extract]))
        source = min(s for s in (leaves,graphs) if s)
        first = source[0]
    return(first)

def traverse(graph):
    """Computes an array containing the depth of the leaves of the
    graph produced by the algorithm meld(). 

    """
    if graph==None: 
        return None
    maxDepth = graph.computeDepths()
    M = [0]*(maxDepth+2)
    graph.collectDepths(M)
    return M


##############################################################################
def main():
    unittest.main()
if __name__ == '__main__':
    doctest.testmod()
    main()

##############################################################################
\$\endgroup\$
1
\$\begingroup\$

You have recognized that each of the tree functions can be tested separately. In the context of unit testing this means that each function is a "unit". Now each of your tests tests all three functions. This has drawbacks:

  • When a test fails, the name of the failing test does not tell you in which function the bug is.
  • It seems to me that you have chosen the test inputs with makeRuns in mind. If you would instead make tests separately, you have better opportunity to consider corner cases of each function.
\$\endgroup\$
  • \$\begingroup\$ The problem with dividing into 3 tests each of those above, is that a single problem with makeRuns will result into three fails. (I copied only my three first instances out of 10 or so, which aim more specifically to meld and traverse.) \$\endgroup\$ – Jeremy May 24 '13 at 9:14
  • 1
    \$\begingroup\$ @Jeremy It is normal that a single bug causes many tests to fail. \$\endgroup\$ – Janne Karila May 24 '13 at 9:21
  • 1
    \$\begingroup\$ I humbly assert that "if you would instead make tests separately..." should say "you should also make some tests separately". Meaning, of course you should test "high level" behavior, but you must test the "core" methods as Janne says. \$\endgroup\$ – radarbob May 25 '13 at 4:49
1
\$\begingroup\$

The result can be described as an array of (say) 3*3 tests. Is the code below the correct implementation of such a test? (I find the result of the tests to be lacking in clarity.)

Build data structures to generate more tests instead of writing more test code.

It strikes me that the amount of test code explodes with the need to test more involved graph complexity. Test code must be as thoughtfully architected as the target code to avoid all the bad things about poor OO design.

Looks like your tests are basically the same except for hard coded method parameters. Make the method parameters variables then you can have a single test method.

  1. Design a data object that holds the parameters for your method calls in your test. Imagine a property for each parameter for each call - including the asserts.
  2. You might want to design a data object factory such that you simply pass in Node construction arguments, probably in some kind of array arrangement.
  3. One object for each test; bundle them all in a single collection of some kind.
  4. A driver that iterates the collection and passes each data object to...
  5. A method that maps the data to the method parameter variables. Then call the test methods.

Now the test code stays small yet your tests are as variably complex as your data object collection.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.