7.5 Breadth-first search strategy

7.5 Breadth-first search strategy

7.5.1 Breadth-first search assumptions

The breadth-first search strategy is analogous to the breadth-first search method taught in introductory algorithm classes. The strategy assumes that the program being debugged has a single main procedure. If the problem system has multiple main procedures, because there are multiple executables in the system, wrap an outer loop around the control structure that visits each main procedure in turn. If the problem system has no main procedure, as in the case of libraries, treat the test case that is invoking the library as the main procedure.

This strategy is easier to use if you have a tool available that will generate a tree structure showing the calling hierarchy of the application. Failing that, a cross-reference listing of the application can also be useful.

7.5.2 Breadth-first control structure

The next code sample shows the control structure for the breadth-first strategy.

 Set suspect list to empty  Invoke BFS with name of top level procedure   BFS ( ancestor )      Set visited(ancestor) = true      Set queue to the empty list      Loop forever          For each descendant procedure called by ancestor              procedure              If visited(descendant) is false              Then                  Append descendant at end of queue                  Set visited(descendant) to true              End-if          End-for          If queue is empty          Then              Return          End-if          Set candidate to the first element of queue          Delete first element of queue          Test the hypothesis that the errors occurs               during the execution of the candidate          If the hypothesis is true          Then              If the candidate has no descendants                  Set the suspect list to the candidate                  Return              Else                  Prepend the candidate to the front of                     the suspect list              End-if          End-if      End-loop  End-BFS  The first element of the suspect list is the procedure      in which the defect occurs 

Debugging by Thinking. A Multidisciplinary Approach
Debugging by Thinking: A Multidisciplinary Approach (HP Technologies)
ISBN: 1555583075
EAN: 2147483647
Year: 2002
Pages: 172

Similar book on Amazon

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net