3

For the example shown below, in which I added the True and False values over the original document (so if something is wrong there, it's probably my fault), I understand there should be seven states to test (at a minimum) (because the cyclomatic complexity number is 7), but looking at the activity diagram, (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 and (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.) 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.

So, could someone please help me relate what's going, in that regard, with the graph / activity diagram and the table (9.32)?

For what it's worth, the book I'm using only has one example regarding this topic and this is it, so I can't try to see the pattern for myself by comparing different examples.

Here is the example.:

First image of the example

Second image of the example

Third image of the example

Edit: Here are the 15 paths (for what it's worth).: { {1,2,3,4,5,6,8,9,10,18}, {1,2,3,4,5,6,8,11,12,13,16,18}, {1,2,3,4,5,6,8,11,12,13,17,18}, {1,2,3,4,5,6,8,11,12,15,18}, {1,2,3,4,5,8,11,12,15,18}, {1,2,3,4,5,8,11,12,13,17,18}, {1,2,3,4,5,8,9,10,18}, {1,2,3,5,6,8,11,12,13,16,18}, {1,2,3,5,6,8,11,12,13,17,18}, {1,2,3,5,6,8,9,14,18}, {1,2,3,8,9,10,18}, {1,2,3,8,9,14,18}, {1,2,3,8,11,12,13,16,18}, {1,2,3,8,11,12,13,17,18}, {1,2,3,8,11,12,15,18} }

Using the numbering scheme I made, shown below. enter image description here

1 Answer 1

5

(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:

enter image description 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.

enter image description here

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)?

enter image description here

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=:

enter image description here

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'.

enter image description here

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)

  1. (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:

enter image description here

Which boils down to

enter image description here

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.

enter image description here

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.

enter image description here
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.

17
  • 1
    Wow! Thanks for the great answer! Just one question, though: I'm not sure if it's just because I'm tired as I write this (I'll check again whenever I'm more alert), but I'm still confused about the "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." and the diagram with the seven colours. Could you please elaborate on that? Sorry. :( I feel bad for not understanding that part because you seem to have put a lot of effort into your answer. Commented Sep 12, 2022 at 4:38
  • I do understand this ( geeksforgeeks.org/count-possible-paths-two-vertices ). Commented Sep 12, 2022 at 4:38
  • 1
    Also, lol at "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.". :P Commented Sep 12, 2022 at 4:39
  • So, it can be said that the cyclomatic complexity is exactly the number of test cases if the program is in its most succinct form, right? As for the stuff from my previous comment, I confirmed that the maximum number of paths is 15 by brute-forcing it and getting the set of paths I will add in my edit to my main question, but I still don't get the "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." part and the diagram with the seven colours. Commented Sep 13, 2022 at 8:11
  • I'll mark it as answered since you answered the important part(s), but I'd appreciate it if you could also clear up the rest (that you brought to my attention). Commented Sep 13, 2022 at 8:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.