3
$\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?

$\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$ Dec 22 '20 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$
    – Mergasov
    Dec 23 '20 at 10:28
  • $\begingroup$ No, since different functions are different connected components. $\endgroup$ Dec 23 '20 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$
    – Mergasov
    Dec 23 '20 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$ Dec 23 '20 at 10:56
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

$\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$ Dec 22 '20 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$
    – tylerhx111
    Dec 22 '20 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.
    Dec 23 '20 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.
    Dec 23 '20 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$
    – tylerhx111
    Dec 23 '20 at 8:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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