Complexidade ciclomática

Origem: Wikipédia, a enciclopédia livre.

Complexidade ciclomática (ou complexidade condicional) é uma métrica de software usada para indicar a complexidade de um programa de computador. Desenvolvida por Thomas J. McCabe em 1976, ela mede a quantidade de caminhos de execução independentes a partir de um código fonte.

Essa complexidade é computada através do grafo de fluxo de controle do programa: os nós do grafo correspondem a grupos indivisíveis de comandos, e uma aresta direcionada conecta dois nós se o segundo comando pode ser executado imediatamente após o primeiro.

A complexidade ciclomática também pode ser aplicada a funções, módulos, métodos ou classes individuais de um programa.

Uma estratégia de teste de software formulada por McCabe é testar cada caminho independente de um programa, de forma que a quantidade de casos de teste será a complexidade ciclomática do programa.¹

Índice

  [esconder] 

·        1 Descrição

·        2 Referências

·        3 Ver também

·        4 Leitura adicional

Descrição[editar | editar código-fonte]

Grafo de fluxo de controle de um programa simples. O programa começa executando no nó vermelho, entra numa estrutura de repetição. Ao sair do dela, entra numa estrutura de seleção e então termina no nó azul. Para esse grafo, E = 9, N = 8 e P = 1, resultando numa complexidade ciclomática de 3. M=9-8+2*1 E=9 setas N=8 nós

A complexidade ciclomática de uma seção do código fonte é a quantidade de caminhos independentes pelo código. Por exemplo, se o código fonte não contém estruturas de controle senão sequenciais a complexidade é 1, já que há somente um caminho válido através do código. Se o código possui somente uma estrutura de seleção contendo somente uma condição, então há dois caminhos possíveis, aquele quando a condição é avaliada em verdadeiro, e aquele quando a condição é avaliada em falso.

Matematicamente, a complexidade ciclomática de um programa estruturado é definida com referência ao grafo direcionado que contém os blocos básicos do programa, com uma aresta entre dois blocos se o controle pode passar do primeiro para o segundo imediatamente, sem blocos intermediários. A complexidade então é definida como:²

Em que:

·       – complexidade ciclomática

·       – quantidade de setas

·       – quantidade de nós

·       – quantidade de componentes conectados

Mesma função que a acima, mostrada como um grafo de fluxo de controle fortemente conectado, para o cálculo pelo método alternativo. Para esse grafo, E = 10, N = 8 e P = 1, então a complexidade ciclomática se mantém em 3.

Uma formulação alternativa é usar um grafo em que o ponto de saída é conectado ao ponto de entrada. Nesse caso, o grafo é dito fortemente conectado, e a complexidade ciclomática do programa é equivalente ao número ciclomático do grafo, definido como:²

Isso pode ser visto como o cálculo da quantidade de ciclos independentes que existem no grafo, isto é, os ciclos que não contém outros ciclos embarcados. Notar que, tendo em vista que o ponto de saída é conectado ao ponto de entrada, há pelo menos um ciclo para cada ponto de saída.

Para um programa único, ou subrotina ou método, P é sempre igual a 1. Entretanto, a complexidade ciclomática pode ser aplicada a diversos programas ou subprogramas simultaneamente, de forma que P será a quantidade de programas em questão. Pode-se demonstrar que a complexidade ciclomática de qualquer programa estruturado com somente um ponto de entrada e um ponto de saída é igual a quantidade de pontos de decisão – como condicionais de estruturas de seleção ou uma iteração dos laços das estruturas de repetição – mais um.^2 3

A complexidade ciclomática também pode ser estendida para programas com múltiplas saídas, definida como:^3 4

Em que:

·         – quantidade de pontos de decisão do programa

·         – quantidade de pontos de saída

Referências

1.      Ir para cima↑ A J Sojev. Basis Path Testing.

2.      ↑ ^{Ir para:a b c} McCabe. (Dezembro 1976). "A Complexity Measure". IEEE Transactions on Software Engineering: 308–320.

3.      ↑ ^{Ir para:a b} Belzer, Kent, Holzman and Williams. Encyclopedia of Computer Science and Technology. [S.l.]: CRC Press, 1992. 367–368 p.

4.      Ir para cima↑ Harrison. (Outubro de 1984). "Applying Mccabe's complexity measure to multiple-exit programs". Software: Practice and Experience. J Wiley & Sons.

Ver também[editar | editar código-fonte]

·        Complexidade

·        Programa de computador

·        Estrutura de controle

·        Qualidade de software

Leitura adicional[editar | editar código-fonte]

·        Thomas J. McCabe (Dezembro de 1976). A Complexity Measure (em inglês) IEEE Transactions on Software Engineering Vol. 2, Nº 4, p. 308 IEEE.