(i) how is one supposed to know that (a>=0)&&(a<=100)&&(b>=0)&&(b<=100)&&(c>=0)&&(c<=100) should lead to three different test cases
You're not. That doesn’t lead to three different test cases.
(ii) why doesn't the activity diagram have seven paths to follow from the starting node to the ending node? (It seems to me to have five paths.)
It has five outcomes. Not the same thing. Some paths fold into each other. You can see that here:
The two tests (the diamonds on left) are encoding their results in validInput as either -1, 0, or 1 which simply needlessly leads to two more tests (the diamonds on the right). This creates more paths than outcomes. Seemingly for no other reason than to make analyzing the cyclomatic complexity non-trivial.
You can actually map directly from path to path. No options here. It's just hacking the cycle count.
To elaborate, if I try to split the aforementioned large Boolean expression into three or six separate expressions (one expression per variable or expression per inequality) (in an attempt to get the number of paths and test case scenarios to match the cyclomatic complexity number), it seems to me that the cyclomatic complexity number would change.
That poorly expressed Boolean nightmare isn't even at fault here. It's just a large distraction. Let me express it in a more human friendly way:
if (0 <= a && a <= 100)
&& (0 <= b && b <= 100)
&& (0 <= c && c <= 100)
There, same logic, but any math student who remembers inequality ranges expressed as
0 ≤ x ≤ 100
will appreciate this. Yoda= be damned.
Now that we can read the code let me explain how I know this is just a distraction. It only contributes one diamond to the flow chart and the expected CMC is 7 which matches the flow chart as is. That tells me they are not using the Myers' Interval= extension to cyclomatic complexity which would break out each Boolean sub expression as a separate decision. But we aren't doing that and so we treat the whole compound Boolean expression as one. Yes this is a mess.
Anyway, now that the Boolean nightmare isn't eating up the braincells let's focus on why we even need validInput. Oh I see. We care about a == 0. Duh. Now that I can see, that's an easy fix.
if (a == 0) {
cout<<"Not quadratic";
return;
}
Sorry but I refuse to use Ratliffs indentation style because it's icky. K&R for life.
Put that before the nightmare and it's over and done with. If you're picky you can even shave that now unneeded = off of 0 <= a.
But since this is a lesson in cyclometric complexity we're not supposed to change the poorly written code. Just analyze it like the brain dead static analysis tools management keeps buying whenever we leave them alone with a sales rep for too long. Hopefully this helps you see why you can have more paths than outcomes. It's because sometimes coders are silly.
So, could someone please help me relate what's going, in that regard, with the graph / activity diagram and the table (9.32)?
Sure, you have some goofball that has asserted that paths are independent when they aren't. At least not with this limited set of input.
Lets grab a simpler example from wikipedia=:
I've numbered the nodes so we can talk about them. Let's say you've arrived at 4. You want to go to 6. As the locals say, "You can't get there from here". Why? Because the input that let you get to 4 wont let you get to 6. The software just doesn't want you to touch 4 and 6 on the same run. Why doesn't static analysis of cyclomatic complexity tell us that? Because it can't. It assumes paths are independent as it blindly counts complexity. It has no idea that some paths aren't independent. If you read that Wikipedia page you know M is supposed to be 3 here. But that doesn't mean the input will let you take every combination of paths if the programmer doesn't want you to.
I draw your attention to the testing section of that Wikipedia page
Implications for software testing
Another application of cyclomatic complexity is in determining the number of test cases that are necessary to achieve thorough test coverage of a particular module.
It is useful because of two properties of the cyclomatic complexity, M, for a specific module:
- M is an upper bound for the number of test cases that are necessary to achieve a complete branch coverage.
- M is a lower bound for the number of paths through the control-flow graph (CFG). Assuming each test case takes one path, the number of cases needed to achieve path coverage is equal to the number of paths that can actually be taken. But some paths may be impossible, so although the number of paths through the CFG is clearly an upper bound on the number of test cases needed for path coverage, this latter number (of possible paths) is sometimes less than M.
All three of the above numbers may be equal: branch coverage ≤ cyclomatic complexity ≤ number of paths.
So in your example the test case upper bound is 7 but with the program limiting you your inputs can only get you to 5.
If we assume independence (it's not) then the path count is: 3 * 2 * 1 + 3 * 1 * 3 = 15 paths. That is, 3 lead to 2 that lead to 1. 3 lead to 1 that leads to 3. 15 is more than 7. That's ok because remember, 7 is the lower bound for our paths. Not necessarily the number of paths.
So in this case 7 is not our number of paths (15), nor is it our branch coverage (5). It's just our cyclomatic complexity.
Maybe this will help you see why. I've taken the liberty of redrawing the flow diagram so the lines for range error don't cross pointlessly (I really think they're just trying to make this harder than it needs to be). And I've added colors so you can see the 'cycles'.
Notice we have 7 colors. But 2 of them are fairly useless.
Now that's a good introduction to code coverage but I'm not gonna ignore that there are a lot of missing tests here. I don't trust that Boolean nightmare. So I also wanna see boundary tests= at -1, 0, 100, & 101 for a, b, and c.
I'm still confused about the "3 * 2 * 1 + 3 * 1 * 3 = 15 paths. -
Alfred Kaminski
Alright I'm just going to admit, some of what I've said here is unsupported. I can't find proof that the 15 combinations path count that I came up with is what that Wikipedia article meant when it talked about path count. The point was you can't just count paths and get the cyclomatic complexity. A point that would be easier to make if I could find what kind of path counting they mean. I've looked and if they say I missed it. I don't think it's depth or breadth so I just guessed they meant the combinations you get if they're independent paths. But for all I know they mean count all the edges (I count 13 in this flow diagram). If someone knows please lay some clue on me.
I did look at the OPs edit and it seems they followed my meaning correctly even if I can't prove this path counting method of mine wasn't just me being silly.
the diagram with the seven colours. Could you please elaborate on that? - Alfred Kaminski
Again, it seems I can't support my claims. I've done about 20 different image searches and I'm coming up empty. Fine, let me explain the colors.
Ever heard of a Visual Proof?= Back when I was studying Cyclomatic Complexity I was into them. Also into Negative Space= around the same time. With those in my head I noticed that all they were doing was counting the holes, sorry, cycles in the graph. Load that into a paint program and you can fill each loop with a different color to count them. It's like counting the holes in a fishing net or a spider web rather than counting the knots or lines. It's just a nice visual way of seeing the Cyclomatic Complexity in a flow chart without doing math.
Of course you get a problem when you cross lines without nodes. You get holes that don't count. Which is why I moved the range error. Just as well. I hate tangled flowcharts.
Anyway, it seems no one teaches it this way since my searches came up empty. But back in the day when I asked about this in class every one saw it, even the teacher. And I ended up remembering it as what they were really asking us to count and forgot this wasn't even in the lesson plan. Funny how the mind plays tricks.
It seems to work but I can't prove it. So call it the candied_orange Cyclomatic Complexity conjecture. Which is: just count the holes.
My research did dig up something that makes why this works a little clearer. Even when you ignore the math formulas. It's the definition of Cyclomatic from wikionary.
cyclomatic
English
Pronunciation
IPA(key): /ˌsaɪkləˈmætɪk/
Adjective
cyclomatic (not comparable)
- (graph theory) Used to describe the number of edges that must be removed from a graph to ensure that no graph cycle remains; equal to the number of edges, minus the number of nodes plus one.
cyclomatic - wiktionary.org
That's what they're really counting. So long as my conjecture holds up it's counting the same thing. Here's how it works. Take all the arrow heads off the flow chart so it's just edges and nodes. Now you're free to run in circles round the loops. Take away edges until you can't do that any more. Count the edges you took away. That's your Cyclomatic Complexity.
I'm saying (so long as your edges never cross each other) the easy way to count that is to just count the holes. Each one has the edge you were going to take away anyway. The colors were just supposed to help you see that. Sorry they didn't work.
What I forget is that many people who teach this just throw the formula at you and tell you about how this is a measure of software complexity. Yeah fine but that's just fuzzy marketing hoopla. This is based on a simple idea from graph theory. Just because it has fancy names we shouldn't accept that it's that hard to understand. There is a simple idea hiding under all that noise.
Let remove the computer science noise and show what this looks like to a graph theory math nerd:
Which boils down to
Re: the Gray color. Yes I know it's weird to think of the paper as a hole. Just draw an edge from the exit (7) to the start (0) if it makes you feel better.
Which I guess you have to do to get to 7 cycles under the definition. "In this case [...] the cyclomatic complexity of the program is equal to the cyclomatic number of its graph"= Without that it's actually 6 that need to be removed (lets arbitrarily choose the edges around brown, green, and blue). With them gone there are no more cycles.
Note how you can't add an edge to this without creating a cycle. Not without also adding another node anyway. That's why M=E-N+2P works.
There, a nice simple acyclic= graph. Getting to this is what all the fuss was about. Some people really don't like cycles in their graphs. So they taught us how to count them and feel bad about them.
I wonder if this is why most coders don't make flow charts anymore.
