The Applications include
General
How many Paths in a Flow Graph?
Structured flow graphs
Lower Path Count Arithmetic
Calculation the Probability
The Mean Processing Time of a Routine
Push/Pop, Get/Return
Limitations and Solutions
General:
The intention of the node removal algorithm is to present one very generalized concept, which is the path expression and way of achieving it
The following is the common pattern, every application follows:
Convert the program or graph into a path expression
Recognize a property of interest and originate an appropriate set of "arithmetic" rules that describes the property
For the property of interest, replace the link names by the link weights
The path expression has now been converted to and expression in some algebra, such as ordinary algebra, regular expressions, or Boolean algebra
Over the set of all paths, algebraic expression summarizes the property of interest
Simplify or evaluate the resulting "algebraic" expression to answer the question you asked
How many Paths in a Flow Graph?
A Question:
The question is not simple, Here are some ways you could ask it:
what are the maximum number of different paths possible?
What are the fewest number of paths possible?
How many different paths are really available>
What are the average number of paths?
Discovering the actual number of different paths is an intrinsically tough problem, because there could be unachievable paths resulting from correlated and dependent predicates
If both the maximum and minimum number of possible paths are known, then one will have good idea of how to complete our testing
Asking for "the average number of paths" is meaningless
Maximum Path Count Arithmetic
Label each link with a link weight that corresponds to the number of paths that link represents
Also, mark each loop with the maximum number of times that loop can be taken. If the anser is infinite, you might as well stop the analysis because it is clear that the maximum number of paths is infinite
There are three cases of interest: parallel links, serial links, and loops
This arithmetic is an ordinary algebra. The weight is the number of paths is each set
Example:
The following is a reasonably well-structured program
Each link represents a single link and accordingly is given a weight of "1" to start. Let us say the outer loop is taken exactly four times and inner loop can be taken zero or three times its path expression, with a modest work, that is:
Path expression: a(b+c)d{d(fi) * fgj(m+l)k}*e(fi)*fgh*
A: The flow graph should be interpreted by substituting the link name with the maximum of paths through that link (1) and also note the number of times for looping
B: Unite the first pair of parallel loops outside the loop and also the pair in the outer loop
C: Multiply the things and remove nodes to clear the clutter
The following is a reasonably well-structured program
>
Each link represents a single link and accordingly is given a weight of "1" to start. Let us say the outer loop is taken exactly four times and inner loop can be taken zero or three times its path expression, with a modest work, that is:
Path expression: a(b+c)d{d(fi) * fgj(m+l)k}*e(fi)*fgh*
A: The flow graph should be interpreted by substituting the link name with the maximum of paths through that link (1) and also note the number of times for looping
B: Unite the first pair of parallel loops outside the loop and also the pair in the outer loop
C: Multiply the things and remove nodes to clear the clutter
Example:
For the Inner Loop:D: Calculate the total weight of inner loop, which can execute a minimum of 0 times and maximum
of 3 times. So, the inner loop can be evaluated as follows:
13 = 10 + 11 + 12 + 13 = 1+1+1+1 =4
E: Inside the loop, multiply the link weights:
1 X 4 =4
F: By multiplying the link weights, evaluate the loop:
2 X 4 = 8
G: Simplifying the loop further results in the total maximum number of paths of paths in the flow graph:
2 X 84 X 2 = 32,768
Otherwise, you could have substituted a '1' for each link in the path expression and then simplified, as follows:
a(b+c)d{e(fi)*fg(m+l)k}e(fi)*fgh
Structured flow Graphs:
In numerous ways the structured code can be defined, which do not involve ad-hoc such as not using GOTO statement
A structured flow graph is one that can be reduced to a single link by successive application of the transformations of below image
The node-by-node reduction procedure can also be used as a test for structured code
Flow graphs that do not contain one or more of the graphs shown in the image as subgraphs, are structured
Jumping into loops
Jumping out of loops
Branching into decisions
Branching out of decisions
For structured flow graphs, a lower bound on the number of paths in a routine can be approximated
the arithmetic is as follows:
This arithmetic is an ordinary algebra. The weight is the number of paths in each set
Example:
Applying the arithmetic to the earlier example gives us the identical steps until step 3(c) as displayed below.
From step 4, it would be different from the previous example:
If the original graph is observed, it takes at least two paths to cover and that, it can be done in two paths.
If you have fewer paths in your test plan than the minimum you probably haven't covered. It's another check
Calculating the probability
Rather than the high probability paths, path selection should be biased towards the low, this elevates an interesting question:
What is the probability of being aer a certain point in a routine?
Under suitable statements the above question can be answered, primarily that all probabilities involved are independent, which is to say that all decisions are independent and uncorrelated
We use the same algorithm as before> Node-by-Node removal of uninteresting nodes
Including decisions associate with loops, probabilities can come into the act only at decisions
Annotate each outlink with a weight equal to the probability of going in that direction
Apparently , the sum of the outlink probabilities must equal '1'
For simple loop, if the loop is taken a mean of N times, the looping probability is (N/(N+1)) and the probability of not looping is 1/(N+1)
a link that is not part of a decision node has a probability of '1'
The arithmetic rules are those of ordinary arithmetic
Annotate each outlink with a weight equal to the probability of going in that direction
Apparently , the sum of the outlink probabilities must equal '1'
For simple loop, if the loop is taken a mean of N times, the looping probability is (N/(N+1)) and the probability of not looping is 1/(N+1)
a link that is not part of a decision node has a probability of '1'
The arithmetic rules are those of ordinary arithmetic
The rules are those of ordinary probability theory
If you can do something either from column A with a probability of PA or from column B with a probability PB, then the probability that you do either PA + PB
If you must do both things for series case, and as assumed their probabilities are autonomous, then the probability that you do both is the product of their probabilities
For example, a loop node has a looping probability of PL and a probability of not looping of PA, which is
clearly equal to I - PL
Following the above rule, all we have done is replace the outgoing probability with 1. so why the complicated rule?After few steps in which you have removed nodes, combined parallel terms, removed loops and the like, you might find it something like this:
Because P1+PB+PB+PC = 1, 1 PL = PA+PB+PC and PA/(1-PL) + PB/(1-PL) + PC/(1-PL) = (PA+PB+PC) / (1-PL) = 1
which is what we have assumed for any decision
In other words, division by 1-PL makes the outlink probabilities normal with the intention that their sum equals unity after the loop is removed.
Mean Procession Time of a Routine
Given the execution time of all statements or instruction for every link in a flow graph and the probability for each direction for all decision, mean processing time for the routine as a whole should have to be known
The model has two weights connected with every link: The processing time for that link (T). and the probability of that link (P)
For calculating the mean time, the arithmetic rules are:
Given the execution time of all statements or instruction for every link in a flow graph and the probability for each direction for all decision, mean processing time for the routine as a whole should have to be known
The model has two weights connected with every link: The processing time for that link (T). and the probability of that link (P)
For calculating the mean time, the arithmetic rules are:
Example:
Step 1:
Start with the original flow graph annotated with probabilities and processing time
combine the parallel links of the outer loop
The result is the mean of the processing times for the links since there are not any other links leaving the first node
At the beginning of the flow graph, combine the pair of links
Step 1:
Start with the original flow graph annotated with probabilities and processing time
combine the parallel links of the outer loop
The result is the mean of the processing times for the links since there are not any other links leaving the first node
At the beginning of the flow graph, combine the pair of links
Push/Pop, Get/Return
To answer several different questions this model can be used, that can turn up in debugging
It can also help to decide which test cases to design
The question is:
Given a pair of complementary operations such as PUSH (the statck) and POP (the stack), taking into consideration that the set of all possible paths through routine, what is the net effect of the routine?PUSH or POP? How many times? Under what conditions
Here are some other examples of complementary operations to which this model applies
GET/RETURN a resource book
OPEN/CLSOE a file
START/STOP a device or process
Limitations and Solutions
- The problem of unachievable paths, is the main limitation of this applications
- When all paths are possible, the node by node reduction procedure, and most graph theory based algorithms work well but may provide misleading results when some paths are unachievable
- The approach to handling unachievable paths (for any application) is to partition the graph into subgraphs so that all paths in each of the subgraphs are achievable
- The path may be common to several different subgraphs, so there is a chance of overlapping of subgraphs
- Each predicates truth functional value potentially splits the graph into two subgraphs
- There could be as many as 2n subgraphs, for 'n' predicates
0 comments:
Post a Comment