Functional coverage tree
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.
Python
<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 |