Describe what the code seems to be doing Draw the reduced CFG (DD-path graph) -
ID: 3680959 • Letter: D
Question
Describe what the code seems to be doing
Draw the reduced CFG (DD-path graph) - use the line numbers provided
Determine the Cyclomatic complexity
Develop the basis paths using the Cyclomatic complexity. Use all True paths as the initial basis path to make it easier to grade.
Develop the test cases using required input values to achieve boundary value coverage. Use a test case table to develop the test case number, inputs, expected outputs.
Determine the code coverage achieved (decision, statement, condition, etc.)
Do the test cases and outputs refute or support the code functional description?
Use basis path testing to test the following code.
Use the variable y as your return value in your test cases. Use the following template for the test case table. Assume x ranges from -4 to 10 inclusive with significance of 0.1.
Additional test instructions:
Add the number of tests required by an ECP/BV approach in addition to what basis path testing would require. For these test cases list "-" as the basis path tested.
Test non-uniform results with 1 additional testpoints for a linear function and 2 for squared function. For these test cases list "-" as the basis path tested.
1 public double calcY (double x) {
2 double y=0;
3 if (x<-0.0)
4 y=x+8;
5 else
6 if (x<4.0)
7 y=-x*x+2*x+8;
8 else
9 if (x<6.0)
10 y=4*x-16;
11 else
12 if (x<8.0)
13 y=-4.0*x+32;
14 else
15 y=0.0;
16 return y;
17 }
It has the following graph
Explanation / Answer
Answer:
DD-path - A decision-to-decision path (DD-Path) is a path chain in a program graph such that
1. Initial and terminal nodes are distinct
2. Every interior node has indeg =1 and outdeg = 1
- >The initial node is 2-connected to every other node in the path
- > No instances of 1- or 3-connected nodes occur
Connectedness 1
There are 4-types of connectedness
Two nodes J and K in a directed graph are
-> 0-connected iff no path exists between them
-> 1-connected iff a semi-path but no path exists between them
Connectedness 2
Two nodes J and K in a directed graph are
-> 2-connected iff a path exists between between them
-> 3-connected iff a path goes from J to K , and a path goes from K to n1
DD-Path – formal definition
A decision-to-decision path (DD-Path) is a chain in a program graph such that:
Case 1: consists of a single node with indeg=0
Case 2: consists of a single node with outdeg=0
Case 3: consists of a single node with indeg 2 or outdeg 2
Case 4: consists of a single node with indeg =1, and outdeg = 1
Case 5: it is a maximal chain of length 1
DD-Paths are also known as segments
DD-Path Graph – informal definition
DD-Path graph is a directed graph, in which
Nodes are DD-Paths of its program graph
Edges represent control flow between successor DD-Paths.
Also known as Control Flow Graph
Control flow graphs definition – 1
Depict which program segments may be followed by others
A segment is a node in the CFG
A conditional transfer of control is a branch represented by an edge
An entry node (no inbound edges) represents the entry point to a method
An exit node (no outbound edges) represents an exit point of a method
Control flow graphs definition – 2
An entry-exit path is a path from the entry node to the exit node
Path expressions represent paths as sequences of nodes
Loops are represented as segments within parentheses followed by an asterisk
There are 22 different entry-exit path expressions in displayLastMsg
Cyclomatic complexity
Cyclomatic complexity is a software metric (measurement), used to indicate the complexity of a program. It is a quantitative measure of the number of linearly independent paths through a program's source code. It was developed by Thomas J. McCabe, Sr. in 1976.
Cyclomatic complexity is computed using the control flow graph of the program: the nodes of the graph correspond to indivisible groups of commands of a program, and adirected edge connects two nodes if the second command might be executed immediately after the first command. Cyclomatic complexity may also be applied to individualfunctions, modules, methods or classes within a program.
One testing strategy, called basis path testing by McCabe who first proposed it, is to test each linearly independent path through the program; in this case, the number of test cases will equal the cyclomatic complexity of the program.
The cyclomatic number for a graph is given by
CN(G) = e – v + 2*c
e number of edges
v number of vertices
c number of connected regions
For strongly connected graphs, need to add edges from every sink to every source
For properly structured programs there is only one component with one entry and one exit. There is no edge from exit to entry.
Definition 1: CN(G) = e – v + 2
Only 1 component, not strongly connected
Definition 2: CN(G) = p + 1
p is the number of predicate nodes with out degree = 2
Definition 3: CN(G) = r + 1
r is the number of enclosed regions
Test Cases
Statement Coverage
Segment Coverage
Branch Coverage
Multiple-Condition Coverage
Statement Coverage
Achieved when all statements in a method have been executed at least once
A test case that will follow the path expression below will achieve statement coverage in our example
A B C (D E F)* D G H (I J K)* I L
One test case is enough to achieve statement coverage!
Segment coverage
Achieved when all segments have been executed at least once
Segment coverage counts segments rather than statements
May produce drastically different numbers
Assume two segments P and Q
P has one statement, Q has nine
Exercising only one of the segments will give either 10% or 90% statement coverage
Segment coverage will be 50% in both cases
Branch coverage
Achieved when every edge from a node is executed at least once
At least one true and one false evaluation for each predicate
How many test cases are required?
Can be achieved with D+1 paths in a control flow graph with D 2-way branching nodes and no loops
Even less if there are loops
Multiple condition coverage
All true-false combinations of simple conditions in compound predicates are considered at least once
Guarantees statement, branch and predicate coverage
Does not guarantee path coverage
A truth table may be necessary
Can have infeasible paths due to dependencies and redundant predicates
Not necessarily achievable
lazy evaluation – true-true and true-false are impossible
mutually exclusive conditions – false-false branch is impossible