Functional coverage tree

Functional coverage tree is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Functional coverage is a measure of how much a particular function of a system has been verified as correct. It is used heavily in tracking the completeness of the verification of complex System on Chip (SoC) integrated circuits, where it can also be used to track how well the functional requirements of the system have been verified.

This task uses a sub-set of the calculations sometimes used in tracking functional coverage but uses a more familiar(?) scenario.

Task Description

The head of the clean-up crews for "The Men in a very dark shade of grey when viewed at night" has been tasked with managing the cleansing of two properties after an incident involving aliens.

She arranges the task hierarchically with a manager for the crews working on each house who return with a breakdown of how they will report on progress in each house.

The overall hierarchy of (sub)tasks is as follows,

cleaning
    house1
        bedrooms
        bathrooms
            bathroom1
            bathroom2
            outside lavatory
        attic
        kitchen
        living rooms
            lounge
            dining room
            conservatory
            playroom
        basement
        garage
        garden
    house2
        upstairs
            bedrooms
                suite 1
                suite 2
                bedroom 3
                bedroom 4
            bathroom
            toilet
            attics
        groundfloor
            kitchen
            living rooms
                lounge
                dining room
                conservatory
                playroom
            wet room & toilet
            garage
            garden
            hot tub suite
        basement
            cellars
            wine cellar
            cinema

The head of cleanup knows that her managers will report fractional completion of leaf tasks (tasks with no child tasks of their own), and she knows that she will want to modify the weight of values of completion as she sees fit.

Some time into the cleaning, and some coverage reports have come in and she thinks see needs to weight the big house2 60-40 with respect to coverage from house1 She prefers a tabular view of her data where missing weights are assumed to be 1.0 and missing coverage 0.0.

NAME_HIERARCHY                  |WEIGHT  |COVERAGE  |
cleaning                        |        |          |
    house1                      |40      |          |
        bedrooms                |        |0.25      |
        bathrooms               |        |          |
            bathroom1           |        |0.5       |
            bathroom2           |        |          |
            outside_lavatory    |        |1         |
        attic                   |        |0.75      |
        kitchen                 |        |0.1       |
        living_rooms            |        |          |
            lounge              |        |          |
            dining_room         |        |          |
            conservatory        |        |          |
            playroom            |        |1         |
        basement                |        |          |
        garage                  |        |          |
        garden                  |        |0.8       |
    house2                      |60      |          |
        upstairs                |        |          |
            bedrooms            |        |          |
                suite_1         |        |          |
                suite_2         |        |          |
                bedroom_3       |        |          |
                bedroom_4       |        |          |
            bathroom            |        |          |
            toilet              |        |          |
            attics              |        |0.6       |
        groundfloor             |        |          |
            kitchen             |        |          |
            living_rooms        |        |          |
                lounge          |        |          |
                dining_room     |        |          |
                conservatory    |        |          |
                playroom        |        |          |
            wet_room_&_toilet   |        |          |
            garage              |        |          |
            garden              |        |0.9       |
            hot_tub_suite       |        |1         |
        basement                |        |          |
            cellars             |        |1         |
            wine_cellar         |        |1         |
            cinema              |        |0.75      |

Calculation

The coverage of a node in the tree is calculated as the weighted average of the coverage of its children evaluated bottom-upwards in the tree.

The task is to calculate the overall coverage of the cleaning task and display the coverage at all levels of the hierarchy on this page, in a manner that visually shows the hierarchy, weights and coverage of all nodes.

Note: to aid in getting the data into your program you might want to use an alternative, more functional description of the starting data given on the discussion page.

J

Implementation (raw data):

<lang J>raw=: 0 :0 NAME_HIERARCHY |WEIGHT |COVERAGE | cleaning | | |

   house1                      |40      |          |
       bedrooms                |        |0.25      |
       bathrooms               |        |          |
           bathroom1           |        |0.5       |
           bathroom2           |        |          |
           outside_lavatory    |        |1         |
       attic                   |        |0.75      |
       kitchen                 |        |0.1       |
       living_rooms            |        |          |
           lounge              |        |          |
           dining_room         |        |          |
           conservatory        |        |          |
           playroom            |        |1         |
       basement                |        |          |
       garage                  |        |          |
       garden                  |        |0.8       |
   house2                      |60      |          |
       upstairs                |        |          |
           bedrooms            |        |          |
               suite_1         |        |          |
               suite_2         |        |          |
               bedroom_3       |        |          |
               bedroom_4       |        |          |
           bathroom            |        |          |
           toilet              |        |          |
           attics              |        |0.6       |
       groundfloor             |        |          |
           kitchen             |        |          |
           living_rooms        |        |          |
               lounge          |        |          |
               dining_room     |        |          |
               conservatory    |        |          |
               playroom        |        |          |
           wet_room_&_toilet   |        |          |
           garage              |        |          |
           garden              |        |0.9       |
           hot_tub_suite       |        |1         |
       basement                |        |          |
           cellars             |        |1         |
           wine_cellar         |        |1         |
           cinema              |        |0.75      |

)</lang>

Implementation (unpacking raw data):

<lang J>labels=: {.<;._2;._2 raw 'hier wspec cspec'=:|:}.<;._2;._2 raw level=: (%+./) (0 i.~' '&=)"1 hier weight=: (+ 0=]) ,".wspec coverage=: ,".cspec

level=: (%+./) (0 i.~' '&=)"1 hier weight=: (+ 0=]) ,".wspec coverage=: ,".cspec</lang>

Implementation (translation of leaf coverage to functional coverage):

<lang J>unrooted=: ([:;@(({.@[,(+}.)~)&.> [: +/\1,_1}.#@>) <@(_1,$:@}.);.1)^:(1<#) parent=: unrooted level distinguish=: (1 + #) #. (1 + #) | i.~@:{~ ,. ] zone=: distinguish parent parent_cover=: (] (1}.~.parent)}~ 1}.(zone +//. *) % zone +//. [)^:_</lang>

unrooted translates indentation information to a parent tree structure. However, the limitations of recursion require we distinguish the parent node from its children, so we use _1 to denote the parent node of the recursive intermediate result unrooted trees.

To combine results, we want a key which distinguishes all children at the same level with the same parent. So that's what zone is.

Thus, parent_cover propagates coverage to parent nodes based on the weighted average of coverage at the children.

Task example (format and show result):

<lang J> 1 1 }._1 }.":labels,each ":each hier;(,.weight);,.weight parent_cover coverage NAME_HIERARCHY │WEIGHT │COVERAGE │ cleaning │ 1 │0.409167 │

   house1                      │40      │ 0.33125  │
       bedrooms                │ 1      │    0.25  │
       bathrooms               │ 1      │     0.5  │
           bathroom1           │ 1      │     0.5  │
           bathroom2           │ 1      │       0  │
           outside_lavatory    │ 1      │       1  │
       attic                   │ 1      │    0.75  │
       kitchen                 │ 1      │     0.1  │
       living_rooms            │ 1      │    0.25  │
           lounge              │ 1      │       0  │
           dining_room         │ 1      │       0  │
           conservatory        │ 1      │       0  │
           playroom            │ 1      │       1  │
       basement                │ 1      │       0  │
       garage                  │ 1      │       0  │
       garden                  │ 1      │     0.8  │
   house2                      │60      │0.461111  │
       upstairs                │ 1      │    0.15  │
           bedrooms            │ 1      │       0  │
               suite_1         │ 1      │       0  │
               suite_2         │ 1      │       0  │
               bedroom_3       │ 1      │       0  │
               bedroom_4       │ 1      │       0  │
           bathroom            │ 1      │       0  │
           toilet              │ 1      │       0  │
           attics              │ 1      │     0.6  │
       groundfloor             │ 1      │0.316667  │
           kitchen             │ 1      │       0  │
           living_rooms        │ 1      │       0  │
               lounge          │ 1      │       0  │
               dining_room     │ 1      │       0  │
               conservatory    │ 1      │       0  │
               playroom        │ 1      │       0  │
           wet_room_&_toilet   │ 1      │       0  │
           garage              │ 1      │       0  │
           garden              │ 1      │     0.9  │
           hot_tub_suite       │ 1      │       1  │
       basement                │ 1      │0.916667  │
           cellars             │ 1      │       1  │
           wine_cellar         │ 1      │       1  │
           cinema              │ 1      │    0.75  │</lang>

Python

Python: Using lists and tuples

It's actually some of the raw code used when researching this task.

<lang python>from itertools import zip_longest

fc2 = \ cleaning,,

   house1,40,
       bedrooms,,.25
       bathrooms,,
           bathroom1,,.5
           bathroom2,,
           outside_lavatory,,1
       attic,,.75
       kitchen,,.1
       living_rooms,,
           lounge,,
           dining_room,,
           conservatory,,
           playroom,,1
       basement,,
       garage,,
       garden,,.8
   house2,60,
       upstairs,,
           bedrooms,,
               suite_1,,
               suite_2,,
               bedroom_3,,
               bedroom_4,,
           bathroom,,
           toilet,,
           attics,,.6
       groundfloor,,
           kitchen,,
           living_rooms,,
               lounge,,
               dining_room,,
               conservatory,,
               playroom,,
           wet_room_&_toilet,,
           garage,,
           garden,,.9
           hot_tub_suite,,1
       basement,,
           cellars,,1
           wine_cellar,,1
           cinema,,.75

NAME, WT, COV = 0, 1, 2

def right_type(txt):

   try:
       return float(txt)
   except ValueError:
       return txt

def commas_to_list(the_list, lines, start_indent=0):

   
   Output format is a nest of lists and tuples
   lists are for coverage leaves without children items in the list are name, weight, coverage
   tuples are 2-tuples for nodes with children. The first element is a list representing the
   name, weight, coverage of the node (some to be calculated); the second element is a list of
   child elements which may be 2-tuples or lists as above.
   
   the_list is modified in-place
   lines must be a generator of successive lines of input like fc2
   
   for n, line in lines:
       indent = 0
       while line.startswith(' ' * (4 * indent)):
           indent += 1
       indent -= 1
       fields = [right_type(f) for f in line.strip().split(',')]
       if indent == start_indent:
           the_list.append(fields)
       elif indent > start_indent:
           lst = [fields]
           sub = commas_to_list(lst, lines, indent)
           the_list[-1] = (the_list[-1], lst)
           if sub not in (None, []) :
               the_list.append(sub)
       else:
           return fields if fields else None
   return None

def pptreefields(lst, indent=0, widths=['%-32s', '%-8g', '%-10g']):

   
   Pretty prints the format described from function commas_to_list as a table with 
   names in the first column suitably indented and all columns having a fixed 
   minimum column width.
   
   lhs = ' ' * (4 * indent)
   for item in lst:
       if type(item) != tuple:
           name, *rest = item
           print(widths[0] % (lhs + name), end='|')
           for width, item in zip_longest(widths[1:len(rest)], rest, fillvalue=widths[-1]):
               if type(item) == str:
                   width = width[:-1] + 's'
               print(width % item, end='|')
           print()
       else:
           item, children = item
           name, *rest = item
           print(widths[0] % (lhs + name), end='|')
           for width, item in zip_longest(widths[1:len(rest)], rest, fillvalue=widths[-1]):
               if type(item) == str:
                   width = width[:-1] + 's'
               print(width % item, end='|')
           print()
           pptreefields(children, indent+1)

def default_field(node_list):

   node_list[WT] = node_list[WT] if node_list[WT] else 1.0
   node_list[COV] = node_list[COV] if node_list[COV] else 0.0

def depth_first(tree, visitor=default_field):

   for item in tree:
       if type(item) == tuple:
           item, children = item
           depth_first(children, visitor)
       visitor(item)
           

def covercalc(tree):

   
   Depth first weighted average of coverage
   
   sum_covwt, sum_wt = 0, 0
   for item in tree:
       if type(item) == tuple:
           item, children = item
           item[COV] = covercalc(children)
       sum_wt  += item[WT]
       sum_covwt += item[COV] * item[WT]
   cov = sum_covwt / sum_wt
   return cov

if __name__ == '__main__':

   lstc = []
   commas_to_list(lstc, ((n, ln) for n, ln in enumerate(fc2.split('\n'))))
   #pp(lstc, width=1, indent=4, compact=1)
   
   #print('\n\nEXPANDED DEFAULTS\n')
   depth_first(lstc)
   #pptreefields(['NAME_HIERARCHY WEIGHT COVERAGE'.split()] + lstc)
   
   print('\n\nTOP COVERAGE = %f\n' % covercalc(lstc))
   depth_first(lstc)
   pptreefields(['NAME_HIERARCHY WEIGHT COVERAGE'.split()] + lstc)</lang>

Output:

TOP COVERAGE = 0.409167

NAME_HIERARCHY                  |WEIGHT  |COVERAGE  |
cleaning                        |1       |0.409167  |
    house1                      |40      |0.33125   |
        bedrooms                |1       |0.25      |
        bathrooms               |1       |0.5       |
            bathroom1           |1       |0.5       |
            bathroom2           |1       |0         |
            outside_lavatory    |1       |1         |
        attic                   |1       |0.75      |
        kitchen                 |1       |0.1       |
        living_rooms            |1       |0.25      |
            lounge              |1       |0         |
            dining_room         |1       |0         |
            conservatory        |1       |0         |
            playroom            |1       |1         |
        basement                |1       |0         |
        garage                  |1       |0         |
        garden                  |1       |0.8       |
    house2                      |60      |0.461111  |
        upstairs                |1       |0.15      |
            bedrooms            |1       |0         |
                suite_1         |1       |0         |
                suite_2         |1       |0         |
                bedroom_3       |1       |0         |
                bedroom_4       |1       |0         |
            bathroom            |1       |0         |
            toilet              |1       |0         |
            attics              |1       |0.6       |
        groundfloor             |1       |0.316667  |
            kitchen             |1       |0         |
            living_rooms        |1       |0         |
                lounge          |1       |0         |
                dining_room     |1       |0         |
                conservatory    |1       |0         |
                playroom        |1       |0         |
            wet_room_&_toilet   |1       |0         |
            garage              |1       |0         |
            garden              |1       |0.9       |
            hot_tub_suite       |1       |1         |
        basement                |1       |0.916667  |
            cellars             |1       |1         |
            wine_cellar         |1       |1         |
            cinema              |1       |0.75      |

Python: Class based

A cleaner implementation that uses the class static variable path2node as in the previous example so you don't have to traverse the tree to work out the position to add new nodes. This relies on parent nodes appearing before their children which is the case in the order of the add_node calls.

<lang python># -*- coding: utf-8 -*-

SPACES = 4 class Node:

   path2node = {}
   
   def add_node(self, pathname, wt, cov):
       path2node = self.path2node
       path, name = pathname.strip().rsplit('/', 1)
       node = Node(name, wt, cov)
       path2node[pathname] = node
       path2node[path].child.append(node) # Link the tree

   def __init__(self, name="", wt=1, cov=0.0, child=None):
       if child is None:
           child = []
       self.name, self.wt, self.cov, self.child = name, wt, cov, child
       if name == "": 
           # designate the top of the tree
           self.path2node[name] = self
   
   
   def __repr__(self, indent=0):
       name, wt, cov, child = self.name, self.wt, self.cov, self.child
       lhs = ' ' * (SPACES * indent) + "Node(%r," % name
       txt = '%-40s wt=%g, cov=%g, child=[' % (lhs, wt, cov)
       if not child:
           txt += (']),\n')
       else:
           txt += ('\n')
           for c in child:
               txt += c.__repr__(indent + 1)
           txt += (' ' * (SPACES * indent) + "]),\n")
       return txt

   def covercalc(self):
       
       Depth first weighted average of coverage
       
       name, wt, cov, child = self.name, self.wt, self.cov, self.child
       if not child:
           return cov
       sum_covwt, sum_wt = 0, 0
       for node in child:
           ncov = node.covercalc()
           nwt = node.wt
           sum_wt += nwt
           sum_covwt += ncov * nwt
       cov = sum_covwt / sum_wt
       self.cov = cov
       return cov

if __name__ == '__main__':

   top = Node()    # Add placeholder for top of tree
   add_node = top.add_node
   
   add_node('/cleaning', 1, 0)
   add_node('/cleaning/house1', 40, 0)
   add_node('/cleaning/house1/bedrooms', 1, 0.25)
   add_node('/cleaning/house1/bathrooms', 1, 0)
   add_node('/cleaning/house1/bathrooms/bathroom1', 1, 0.5)
   add_node('/cleaning/house1/bathrooms/bathroom2', 1, 0)
   add_node('/cleaning/house1/bathrooms/outside_lavatory', 1, 1)
   add_node('/cleaning/house1/attic', 1, 0.75)
   add_node('/cleaning/house1/kitchen', 1, 0.1)
   add_node('/cleaning/house1/living_rooms', 1, 0)
   add_node('/cleaning/house1/living_rooms/lounge', 1, 0)
   add_node('/cleaning/house1/living_rooms/dining_room', 1, 0)
   add_node('/cleaning/house1/living_rooms/conservatory', 1, 0)
   add_node('/cleaning/house1/living_rooms/playroom', 1, 1)
   add_node('/cleaning/house1/basement', 1, 0)
   add_node('/cleaning/house1/garage', 1, 0)
   add_node('/cleaning/house1/garden', 1, 0.8)
   add_node('/cleaning/house2', 60, 0)
   add_node('/cleaning/house2/upstairs', 1, 0)
   add_node('/cleaning/house2/upstairs/bedrooms', 1, 0)
   add_node('/cleaning/house2/upstairs/bedrooms/suite_1', 1, 0)
   add_node('/cleaning/house2/upstairs/bedrooms/suite_2', 1, 0)
   add_node('/cleaning/house2/upstairs/bedrooms/bedroom_3', 1, 0)
   add_node('/cleaning/house2/upstairs/bedrooms/bedroom_4', 1, 0)
   add_node('/cleaning/house2/upstairs/bathroom', 1, 0)
   add_node('/cleaning/house2/upstairs/toilet', 1, 0)
   add_node('/cleaning/house2/upstairs/attics', 1, 0.6)
   add_node('/cleaning/house2/groundfloor', 1, 0)
   add_node('/cleaning/house2/groundfloor/kitchen', 1, 0)
   add_node('/cleaning/house2/groundfloor/living_rooms', 1, 0)
   add_node('/cleaning/house2/groundfloor/living_rooms/lounge', 1, 0)
   add_node('/cleaning/house2/groundfloor/living_rooms/dining_room', 1, 0)
   add_node('/cleaning/house2/groundfloor/living_rooms/conservatory', 1, 0)
   add_node('/cleaning/house2/groundfloor/living_rooms/playroom', 1, 0)
   add_node('/cleaning/house2/groundfloor/wet_room_&_toilet', 1, 0)
   add_node('/cleaning/house2/groundfloor/garage', 1, 0)
   add_node('/cleaning/house2/groundfloor/garden', 1, 0.9)
   add_node('/cleaning/house2/groundfloor/hot_tub_suite', 1, 1)
   add_node('/cleaning/house2/basement', 1, 0)
   add_node('/cleaning/house2/basement/cellars', 1, 1)
   add_node('/cleaning/house2/basement/wine_cellar', 1, 1)
   add_node('/cleaning/house2/basement/cinema', 1, 0.75)

   top = top.child[0]  # Remove artificial top
   print('\n\nTOP COVERAGE = %g\n' % top.covercalc())
   print(top)</lang>

Output:

TOP COVERAGE = 0.409167

Node('cleaning',                         wt=1, cov=0.409167, child=[
    Node('house1',                       wt=40, cov=0.33125, child=[
        Node('bedrooms',                 wt=1, cov=0.25, child=[]),
        Node('bathrooms',                wt=1, cov=0.5, child=[
            Node('bathroom1',            wt=1, cov=0.5, child=[]),
            Node('bathroom2',            wt=1, cov=0, child=[]),
            Node('outside_lavatory',     wt=1, cov=1, child=[]),
        ]),
        Node('attic',                    wt=1, cov=0.75, child=[]),
        Node('kitchen',                  wt=1, cov=0.1, child=[]),
        Node('living_rooms',             wt=1, cov=0.25, child=[
            Node('lounge',               wt=1, cov=0, child=[]),
            Node('dining_room',          wt=1, cov=0, child=[]),
            Node('conservatory',         wt=1, cov=0, child=[]),
            Node('playroom',             wt=1, cov=1, child=[]),
        ]),
        Node('basement',                 wt=1, cov=0, child=[]),
        Node('garage',                   wt=1, cov=0, child=[]),
        Node('garden',                   wt=1, cov=0.8, child=[]),
    ]),
    Node('house2',                       wt=60, cov=0.461111, child=[
        Node('upstairs',                 wt=1, cov=0.15, child=[
            Node('bedrooms',             wt=1, cov=0, child=[
                Node('suite_1',          wt=1, cov=0, child=[]),
                Node('suite_2',          wt=1, cov=0, child=[]),
                Node('bedroom_3',        wt=1, cov=0, child=[]),
                Node('bedroom_4',        wt=1, cov=0, child=[]),
            ]),
            Node('bathroom',             wt=1, cov=0, child=[]),
            Node('toilet',               wt=1, cov=0, child=[]),
            Node('attics',               wt=1, cov=0.6, child=[]),
        ]),
        Node('groundfloor',              wt=1, cov=0.316667, child=[
            Node('kitchen',              wt=1, cov=0, child=[]),
            Node('living_rooms',         wt=1, cov=0, child=[
                Node('lounge',           wt=1, cov=0, child=[]),
                Node('dining_room',      wt=1, cov=0, child=[]),
                Node('conservatory',     wt=1, cov=0, child=[]),
                Node('playroom',         wt=1, cov=0, child=[]),
            ]),
            Node('wet_room_&_toilet',    wt=1, cov=0, child=[]),
            Node('garage',               wt=1, cov=0, child=[]),
            Node('garden',               wt=1, cov=0.9, child=[]),
            Node('hot_tub_suite',        wt=1, cov=1, child=[]),
        ]),
        Node('basement',                 wt=1, cov=0.916667, child=[
            Node('cellars',              wt=1, cov=1, child=[]),
            Node('wine_cellar',          wt=1, cov=1, child=[]),
            Node('cinema',               wt=1, cov=0.75, child=[]),
        ]),
    ]),
]),