Entendendo a complexidade ciclomática

11

Recentemente, deparei-me com a Complexidade Ciclomática e gostaria de tentar entendê-la melhor.

Quais são alguns exemplos práticos de codificação dos diferentes fatores envolvidos no cálculo da complexidade? Especificamente, para a equação da Wikipedia de M = E − N + 2P, quero entender melhor o que cada um dos seguintes termos significa:

  • E = o número de arestas do gráfico
  • N = o número de nós do gráfico
  • P = o número de componentes conectados

Suspeito que E ou N possa ser o número de pontos de decisão (se, senão se, for foreach etc.) em um bloco de código, mas não tenho muita certeza de qual é qual ou o que o outro significa. Também estou supondo que P se refira a chamadas de função e instanciações de classe, mas não há uma definição clara, dado que eu possa ver. Se alguém pudesse esclarecer um pouco mais alguns exemplos claros de código de cada um, isso ajudaria.

Como acompanhamento, a Complexidade Ciclomática se correlaciona diretamente com o número de testes de unidade necessários para 100% de cobertura do caminho ? Como exemplo, um método com uma complexidade de 4 indica que são necessários 4 testes de unidade para cobrir esse método?

Finalmente, expressões regulares afetam a complexidade ciclomática e, se sim, como?

VirtuosiMedia
fonte
Descobri que você pode obter o artigo original de McCabe na Wikipedia e o Google Livros produzirá o livro que McCabe usou em seu artigo original. Curiosamente, você descobrirá que McCabe usou o teorema original incorretamente (e também explica de maneira confusa, pois ele deve começar com um gráfico não direcionado e não há necessidade de torná-lo fortemente conectado em primeiro lugar), mas os números saem corretamente de qualquer maneira ( a fórmula correta seria M = E + 1-N + P, mas como P é sempre 1, ela se encaixa ...) Ocorre o pensamento de que o "Manuseio de exceções" moderno joga uma chave de boca nos trabalhos dessa métrica.
David Tonhofer
... e as chamadas recursivas (possivelmente passando por uma cadeia de funções). Alguém funde os gráficos de funções? Que tal operadores booleanos em curto-circuito, como "&&". Operadores protegidos como "ref? .X" que produzem nulo se ref for nulo? Bem, é apenas mais uma métrica. Mas há algum trabalho para um pequeno projeto universitário aqui.
David Tonhofer

Respostas:

8

Em relação à fórmula: nós representam estados, arestas representam alterações de estado. Em todos os programas, as instruções trazem alterações no estado do programa. Cada instrução consecutiva é representada por uma borda, e o estado do programa após (ou antes de ...) a execução da instrução é o nó.

Se você tem uma instrução de ramificação ( ifpor exemplo) - então você tem dois nós saindo, porque o estado pode mudar de duas maneiras.

Outra maneira de calcular o número de complexidade ciclomática (CCN) é calcular quantas "regiões" no gráfico de execução você possui (onde "região independente" é um círculo que não contém outros círculos). Nesse caso, o CCN será o número de regiões independentes mais 1 (que seria exatamente o mesmo número que a fórmula anterior fornece).

O CCN é usado para cobertura de ramificação ou cobertura de caminho , que é a mesma. O CCN é igual ao número de caminhos de ramificação diferentes teoricamente possíveis em um único aplicativo encadeado (que pode incluir ramificações como " if x < 2 and x > 5 then", mas que deve ser capturado por um bom compilador como um código inacessível). É necessário ter pelo menos esse número de casos de teste diferentes (pode ser mais, pois alguns casos de teste podem estar repetindo caminhos cobertos pelos anteriores, mas não menos assumindo que cada caso cobre um único caminho). Se você não pode cobrir um caminho com qualquer caso de teste possível - encontrou um código inacessível (embora precise provar para si mesmo porque é inacessível, provavelmente alguns aninhados à x < 2 and x > 5espreita em algum lugar).

Quanto às expressões regulares - é claro que elas afetam, como qualquer outro pedaço de código. No entanto, o CCN da construção regex provavelmente é alto demais para ser coberto em um único teste de unidade, e você pode assumir que o mecanismo regex foi testado e ignorar o potencial de ramificação das expressões para suas necessidades de teste (a menos que você esteja testando seu mecanismo regex, é claro).

littleadv
fonte
2
+1: na verdade, você deve confiar que o mecanismo regex foi testado. Se você não confiar nele, obter um que você fazê- confiança.
S.Lott 27/09
"O CCN é igual ao número de caminhos de execução diferentes possíveis em um único aplicativo encadeado" Isso está errado, pois o CCN se baseia apenas na topologia do código e não no seu significado . Pode ser impossível exercitar uma boa porcentagem desses caminhos, pois exigem um estado de entrada que não pode ser definido (alguns x sendo 5 e também menores que 2, por exemplo). Francamente, acho que usar o CCN para decidir sobre os casos de teste a serem executados é perverso. CCN é um número para informar ao desenvolvedor "você pode ter ido ao mar aqui, considere refatorar". E mesmo assim, pode haver uma boa razão para alta CCN.
David Tonhofer
1
@ David adicionou uma frase para resolver isso. A CCN é uma cobertura de filial e nunca há boas razões para uma CCN alta em um nível mais baixo (geralmente sugiro reforçar por função individual).
Littleadv
A cobertura das filiais e a cobertura do caminho não são as mesmas. A cobertura das agências visa cobrir todas as agências, enquanto a cobertura do caminho visa cobrir todas as combinações de agências.
Mouviciel
13

Algumas observações sobre isso que eu ociosamente escrevo ...

Especificamente, para a equação da Wikipedia de M = E - N + 2P

Essa equação está muito errada .

Por alguma razão, McCabe realmente o usa em seu artigo original ("Uma Medida de Complexidade", IEEE Transactions on Software Engineering, Vo .. SE-2, No.4, dezembro de 1976), mas sem justificá-lo e depois de realmente citar o correto fórmula na primeira página, que é

v (G) = e - v + p

(Aqui, os elementos da fórmula foram rotulados novamente)

Especificamente, McCabe faz referência ao livro C.Berge, Graphs and Hypergraphs (abreviado abaixo para G&HG). Diretamente desse livro :

Definição (página 27 na parte inferior da G&HG):

O número ciclomático v (G) de um gráfico (não direcionado) G (que pode ter vários componentes desconectados) é definido como:

v (G) = e - v + p

onde e = número de arestas, v = número de vértices, p = número de componentes conectados

Teorema (página 29 no topo de G&HG) (não usado por McCabe):

O número ciclomático v (G) de um gráfico G é igual ao número máximo de ciclos independentes

Um ciclo é uma sequência de vértices iniciando e terminando no mesmo vértice, com cada dois vértices consecutivos na sequência adjacentes um ao outro no gráfico.

Intuitivamente, um conjunto de ciclos é independente se nenhum dos ciclos puder ser construído dos outros, sobrepondo as caminhadas.

Teorema (página 29 no meio de G&HG) (usado por McCabe):

Em um gráfico fortemente conectado G, o número ciclomático é igual ao número máximo de circuitos linearmente independentes.

Um circuito é um ciclo sem repetições de vértices e arestas permitidas.

Diz-se que um gráfico direcionado está fortemente conectado se todos os vértices puderem ser alcançados a partir de qualquer outro vértice passando pelas bordas na direção designada.

Observe que aqui passamos de gráficos não direcionados para gráficos fortemente conectados (que são direcionados ... Berge não deixa isso totalmente claro)

McCabe agora aplica o teorema acima para derivar uma maneira simples de calcular um "Número de complexidade ciclomática de McCabe" (CCN) da seguinte forma:

Dado um gráfico direcionado representando a "topologia de salto" de um procedimento (o gráfico de fluxo de instruções), com um vértice designado representando o ponto de entrada exclusivo e um vértice designado representando o ponto de saída exclusivo (o vértice do ponto de saída pode precisar ser "construído" adicionando-o no caso de retornos múltiplos), crie um gráfico fortemente conectado adicionando uma aresta direcionada do vértice do ponto de saída ao vértice do ponto de entrada, tornando assim o vértice do ponto de entrada acessível a partir de qualquer outro vértice.

McCabe agora postula (de maneira bastante confusa) que o número ciclomático do gráfico de fluxo de instruções modificado "está de acordo com nossa noção intuitiva de 'número mínimo de caminhos'" e, portanto, devemos usar esse número como medida de complexidade.

Legal, então:

O número de complexidade ciclomática do gráfico de fluxo de instruções modificado pode ser determinado contando os "menores" circuitos no gráfico não direcionado. Isso não é particularmente difícil de ser feito pelo homem ou pela máquina, mas a aplicação do teorema acima nos fornece uma maneira ainda mais fácil de determiná-lo:

v (G) = e - v + p

se alguém desconsiderar a direcionalidade das arestas.

Em todos os casos, consideramos apenas um único procedimento, portanto, há apenas um componente conectado no gráfico inteiro e, portanto:

v (G) = e - v + 1.

Caso se considere o gráfico original sem a borda "saída a entrada" adicionada , obtém-se simplesmente:

ṽ (G) = ẽ - v + 2

como ẽ = e - 1

Vamos ilustrar usando o exemplo de McCabe de seu artigo:

Exemplo de McCabe

Aqui temos:

  • e = 10
  • v = 6
  • p = 1 (um componente)
  • v (G) = 5 (estamos contando claramente 5 ciclos)

A fórmula para o número ciclomático diz:

v (G) = e - v + p

que produz 5 = 10 - 6 + 1 e, portanto, correto!

O "número de complexidade ciclomática de McCabe", conforme indicado em seu artigo, é

5 = 9 - 6 + 2 (nenhuma explicação adicional é fornecida no artigo sobre como)

que está correto (resulta em v (G)), mas pelas razões erradas, ou seja, usamos:

ṽ (G) = ẽ - v + 2

e assim ṽ (G) = v (G) ... ufa!

Mas essa medida é boa?

Em duas palavras: não muito

  • Não está totalmente claro como estabelecer o "gráfico de fluxo de instruções" de um procedimento, especialmente se o tratamento e a recursão de exceção entrarem em cena. Observe que McCabe aplicou sua idéia ao código escrito no FORTRAN 66 , uma linguagem sem recursão, sem exceções e uma estrutura de execução direta.
  • O fato de um procedimento com uma decisão e um procedimento com um loop produzir o mesmo CCN não é um bom sinal.

insira a descrição da imagem aqui

David Tonhofer
fonte
1
@JayElston Boa captura. De fato, eu faço. Fixo!
David Tonhofer
1
Big +1 para vincular ao artigo original. Muitos dos documentos escritos nessa época são bastante legíveis para qualquer programador de nível médio e devem ser lidos.
Daniel T.
1

Como acompanhamento, a Complexidade Ciclomática se correlaciona diretamente com o número de testes de unidade necessários para 100% de cobertura do caminho?

Sim basicamente. Também é uma boa idéia usar a complexidade ciclomática como um indicador de quando refatorar. Na minha experiência, a testabilidade e a reutilização aumentam muito para um CC mais baixo (embora você deva ser prático - não refatorar demais, e alguns métodos terão um CC alto devido à sua natureza - nem sempre faz sentido tentar forçá-lo mais baixo).

Finalmente, expressões regulares afetam a complexidade ciclomática e, se sim, como?

Sim, se você quiser ser exato, embora a maioria das ferramentas de análise de código não pareça levá-las em consideração dessa maneira. Expressões regulares são apenas máquinas de estado finito, então acho que o CC delas pode ser calculado a partir do gráfico FSM, mas seria um número bastante grande.

Daniel B
fonte
+1 - Acho que calcular o CC para RegExes não é uma tarefa divertida.
VirtuosiMedia