4
$\begingroup$

Cyclomatic Complexity is defined with reference to the control flow graph of the program through this formula (borrowed from Wikipedia):

M = E − N + 2P,
where
E = the number of edges of the graph.
N = the number of nodes of the graph.
P = the number of connected components.

I can't understand the last. What is "the number of connected components" in this context? Wikipedia itself uses the notion of (connected) components in relation to undirected graphs only.

There is also the concept of strongly connected component: a directed graph is said to be strongly connected if every vertex is reachable from every other vertex. So one can guess that the number of connected components is the number of strongly connected components of the control flow graph. Is it right? If not, can someone provide samples of control flow graphs with differerent numbers of connected components?

Improve this question
$\endgroup$
6
  • $\begingroup$ From context, it seems that they are counting the connected components of the undirected graph underlying the control flow graph (obtained by forgetting the orientation of the edges). $\endgroup$
    – Yuval Filmus
    Commented Dec 22, 2020 at 15:32
  • $\begingroup$ @YuvalFilmus If so, this number is always 1, considering this undirected graph has any two vertices are connected to each other by paths, isn't? $\endgroup$
    – Ilya Loskutov
    Commented Dec 23, 2020 at 10:28
  • $\begingroup$ No, since different functions are different connected components. $\endgroup$
    – Yuval Filmus
    Commented Dec 23, 2020 at 10:29
  • $\begingroup$ @YuvalFilmus do you mean this metric can be measured for more than 1 control flow graphs (i.e. unconnected graphs)? What's the rationale for it? If you imply subfunctions calls, it seems graphs of the subfunctions should still be considered as connected subgraphs of the initial one. $\endgroup$
    – Ilya Loskutov
    Commented Dec 23, 2020 at 10:53
  • $\begingroup$ Quoting from Wikipedia: For a single program (or subroutine or method), P is always equal to 1 ... Cyclomatic complexity may, however, be applied to several such programs or subprograms at the same time (e.g., to all of the methods in a class), and in these cases P will be equal to the number of programs in question, as each subprogram will appear as a disconnected subset of the graph. $\endgroup$
    – Yuval Filmus
    Commented Dec 23, 2020 at 10:56

1 Answer 1

Reset to default
0
$\begingroup$

When they say connected component, they mean a weakly connected component. Take a look at the third formula they provide in the Wiki.

For a single program (or subroutine or method), P is always equal to 1. So a simpler formula for a single subroutine is M = E − N + 2.

This implies that for $P > 1$ is used for multiple programs. In other words, it is used for programs with multiple start points with distinct end points.

So for the first formula, it takes in consideration of multiple programs, subroutines, or methods that are completely disconnected from each other (i.e. they do not call upon or interfere with each other) in a single program control graph.

The following is an example where the first formula would be applied. Here $M = 9 - 8 + 2*2 = 5$.

many_programs

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ This doesn't seem right to me. The digraph you've drawn has 6 strong components: in addition to the component 1, we have 5 other strong components, each consisting of a single vertex. So if this digraph only has one "connected component", as the article says, then "connected component" can't mean "strong component". $\endgroup$
    – Gregory J. Puleo
    Commented Dec 22, 2020 at 21:58
  • $\begingroup$ We do not consider single vertices as "connected component". A connected component is defined to be a path between each pair of vertices u and v. The definition of a path requires a distinct sequence of vertices. Thus you cannot have a path from u to u (i.e. a path starting and finishing at the same vertex). $\endgroup$
    – tylerh111
    Commented Dec 22, 2020 at 22:47
  • $\begingroup$ By standard terminology, there are definitely 6 strongly connected components (not 4, not 1). The graph is weakly connected. There seems to be some gap where you write "Thus, this graph only contains 1 connected component"; I don't understand how that follows. This answer is not clear on what "connected components" means for cyclomatic complexity - does it mean strongly connected components, or something else? If it means something else, it might be useful to describe what you assert it does mean and provide some references to support that statement. $\endgroup$
    – D.W. ♦
    Commented Dec 23, 2020 at 6:34
  • $\begingroup$ I see you linked to a Geeksforgeeks article on the definitions of strongly, unilaterally, weakly connected. The definition of weakly connected there is not a correct statement of the standard definition. I've never heard of "unilaterally connected". In my experience Geeksforgeeks is not a reliable resource. It is a collection of articles from random people; some of those articles are good ones; others are poor and contain major errors. $\endgroup$
    – D.W. ♦
    Commented Dec 23, 2020 at 6:36
  • $\begingroup$ After rereading the wiki article and parts of the original paper, I changed my answer in favor of weakly connected components. As far as the discussion on single vertices as strongly connected components, I was only considering non-trivial connected components. I should have specified that in my original answer and comment (even though it is wrong). $\endgroup$
    – tylerh111
    Commented Dec 23, 2020 at 8:39

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.