This lecture segment details the foundational principles of Basic Path Testing, a structural testing technique aimed at executing every independent logical path within a program at least once. The process begins with drawing a flow graph of the code, followed by calculating the Cyclomatic Complexity ($V(G)$). $V(G)$ serves as a quantitative measure of logical complexity and provides an upper bound on the number of paths required for testing. The presenter explains the graphical notation for sequential, conditional, and iterative statements, along with rules for simplifying the flow graph by merging sequential nodes. Finally, the segment defines what constitutes a "basic set" of linearly independent paths, emphasizing that this set is not unique and should focus on logically complicated or critical components of the software to ensure comprehensive statement coverage.
Basic Path Testing: Flow Graphs and Cyclomatic Complexity
0:00 Basic Path Testing Goal: The objective is to execute all independent paths within a program at least once. This requires deriving the Cyclomatic Complexity ($V(G)$) to define a basic set of independent execution paths.
0:19 Four Steps of Basic Path Testing:
Draw a flow graph from the code.
Determine the Cyclomatic Complexity ($V(G)$).
Determine a set of linearly independent paths based on $V(G)$.
Prepare test cases to execute these independent paths.
0:30 Flow Graph Notation: Standard drawings are used to represent sequential execution, conditional statements (if/else), case/switch blocks, and loops (do-while/do-until).
2:29 Flow Graph Simplification: Sequential statements that are always executed together should be combined into a single node. Rules for merging include starting with a simple node (one outgoing arrow) and stopping when a predicate node or a shared node is reached.
5:16 Mapping Table Requirement: After simplification, a mapping table must be maintained to link the simplified nodes back to the original statement numbers.
5:57 Cyclomatic Complexity ($V(G)$): This is a quantitative measure of a source code's logical complexity. Crucially, it provides an upper bound on the number of paths that must be tested.
6:40 Calculating $V(G)$ (Method 1: Regions): $V(G)$ equals the number of enclosed regions in the flow graph, plus the outside (background) region.
7:44 Calculating $V(G)$ (Method 2: Edges and Nodes): $V(G) = E - N + 2$ (where E = edges, N = nodes).
8:17 Calculating $V(G)$ (Method 3: Predicate Nodes): $V(G) = P + 1$ (where P = predicate nodes, which have more than one outgoing branch).
9:15 Defining an Independent Path: An independent path must traverse at least one edge in the flow graph that has not been traversed by previous paths.
10:07 Basic Set Properties (Key Takeaway): A basic set of paths is not unique and is guaranteed to execute every statement at least once. The number of paths in the basic set may be less than the Cyclomatic Complexity.
14:35 Testing Non-Independent Paths: It is valuable to include paths that test edge cases (e.g., exiting an empty loop immediately, like path 1-14 in the example), even if they are not technically linearly independent of the basic set.
16:47 Application Focus: Basic path testing should only be applied to critical components that are logically complicated (contain many conditional statements and loops), as drawing flow graphs for simple sequential procedures is time-consuming and unnecessary. Basic path testing does not test all possible path combinations, only the basic set of independent paths.