Complejidad ciclomática

La complejidad ciclomática de un programa es una medida estructural (o topológica) de la complejidad de un programa de computadora . La medida fue desarrollada por Thomas J. McCabe en 1976.

Al calcular la complejidad ciclomática, se utiliza el gráfico de flujo de control del programa. Los nodos del gráfico corresponden a grupos indivisibles de comandos de programa, están conectados por aristas dirigidas si el grupo de comandos correspondiente al segundo nodo puede ejecutarse inmediatamente después del grupo de comandos del primer nodo. La complejidad ciclomática también se puede calcular para funciones , módulos , métodos o clases individuales dentro de un programa.

McCabe utilizó el cálculo de la complejidad ciclomática en las pruebas . El método que propuso fue probar cada ruta linealmente independiente a través del programa, en cuyo caso el número de pruebas necesarias es igual a la complejidad ciclomática del programa. [una]

Descripción

La complejidad ciclomática de una pieza de código de programa es el número de rutas linealmente independientes a través del código de programa . Por ejemplo, si el código fuente no contiene puntos de bifurcación o bucles, entonces la complejidad es una porque solo hay una ruta a través del código. Si el código tiene una sola declaración IFque contiene una condición simple, entonces hay dos rutas a través del código: una si la condición de la declaración IFes verdadera TRUEy otra si FALSE.

Matemáticamente, la complejidad ciclomática de un programa estructurado [2] se determina utilizando un grafo dirigido , cuyos nodos son bloques de programa conectados por aristas, si se puede transferir el control de un bloque a otro. Entonces la complejidad se define como: [3] :

METRO = mi - norte + 2 PAGS ,

dónde:

M = complejidad ciclomática, E = número de aristas en el gráfico, N = número de nodos en el gráfico, P = número de componentes de conectividad .

Otra formulación utiliza un gráfico en el que cada punto de salida está conectado a un punto de entrada. En este caso, el gráfico está fuertemente conectado y la complejidad ciclomática del programa es igual al número ciclomático de ese gráfico (también conocido como el primer número de Betti ), que se define como [3]

METRO = mi - norte + PAGS .

Esta definición se puede considerar como el cálculo del número de ciclos linealmente independientes que existen en un gráfico, es decir, aquellos ciclos que no contienen otros ciclos. Dado que cada punto de salida está conectado a un punto de entrada, hay al menos un ciclo para cada punto de salida.

Para un programa, subrutina o método simple, P es siempre 1. Sin embargo, la complejidad ciclomática puede aplicarse a varios programas o subrutinas (por ejemplo, a todos los métodos en una clase ), en cuyo caso P es igual al número de subrutinas en cuestión, ya que cada subrutina se puede representar como una parte independiente del gráfico.

Se puede demostrar que la complejidad ciclomática de cualquier programa estructurado con un solo punto de entrada y un punto de salida es equivalente al número de puntos de bifurcación (es decir, sentencias ifo bucles condicionales) contenidos en ese programa más uno. [3] [4]

La complejidad ciclomática se puede extender a un programa con múltiples puntos de salida; en este caso es [4] [5]

π - s + 2,

dónde:

π es el número de puntos de bifurcación en el programa, s es el número de puntos de salida.

Formal definición

Formalmente, la complejidad ciclomática se puede definir como el número relativo de Betti :

M:=b_{1}(G,t):=\operatorname {rango} H_{1}(G,t),

es decir, "la primera homología del grafo G con respecto a los nodos terminales t " . Esta es otra forma de decir "el número de caminos linealmente independientes a través del gráfico desde la entrada hasta la salida".

Además, la complejidad ciclomática se puede calcular en términos del número de Betti absoluto (usando homología absoluta, no relativa) uniendo todos los nodos terminales de un componente dado (lo que equivale a conectar puntos de salida con puntos de entrada), en este caso para un nuevo, extendido, gráfico $\ tilde G$

M=b_{1}({\tilde {G)))=\operatorname {rango} H_{1}({\tilde {G))).

Aplicación

Limitando la complejidad en el desarrollo

Uno de los usos originales de McCabe era limitar la complejidad de los programas durante el desarrollo. Recomienda que se exija a los programadores que calculen la complejidad de los módulos que desarrollan y que dividan los módulos en otros más pequeños siempre que la complejidad ciclomática de esos módulos exceda diez. [3] Esta práctica fue incorporada por NIST en la metodología de Pruebas Estructurales con la observación de que desde la publicación original de McCabe, la elección de 10 ha recibido un fuerte apoyo, pero en algunos casos puede ser apropiado relajar la restricción y permitir módulos hasta la complejidad. 15. En esta metodología se reconoce que a veces puede haber razones para ir más allá del límite acordado. Esto está redactado como una recomendación: "Para cada módulo, la complejidad ciclomática debe limitarse a los límites acordados o debe proporcionarse una explicación por escrito de por qué se excedió el límite".

Aplicación en pruebas de software

Otro uso de la complejidad ciclomática es determinar el número de pruebas requeridas para la cobertura completa del código .

Es útil porque la complejidad ciclomática de M tiene dos propiedades, para un módulo particular :

M es una estimación superior del número de pruebas que brindan cobertura de condiciones (puntos de ramificación);
M es una estimación más baja para el número de rutas a través del gráfico de flujo de control y, por lo tanto, el número de pruebas para completar la cobertura de la ruta.

Como parte de otras métricas

La complejidad ciclomática se utiliza como uno de los parámetros en el índice de mantenibilidad [ 6 ] .

Notas

↑ AJ Sobey. Ruta principal de prueba . Consultado el 2 de mayo de 2009. Archivado desde el original el 26 de abril de 2012. (indefinido)
↑ Aquí, el término "estructurado" significa que el programa tiene solo un punto de salida.
↑ 1 2 3 4 McCabe. Una medida de complejidad // Transacciones IEEE en ingeniería de software : diario. - 1976. - Diciembre. - P. 308-320 . Archivado desde el original el 29 de diciembre de 2009.
↑ 1 2 Belzer, Kent, Holzman y Williams. Enciclopedia de Informática y Tecnología (inglés) . - CRC Press , 1992. - P. 367-368.
↑ Harrison. Aplicación de la medida de complejidad de Mccabe a programas de salida múltiple // Software: práctica y experiencia: revista. - J Wiley & Sons, 1984. - Octubre.
↑ Linda M. Laird, M. Carol Brennan John. Medición y estimación de software: un enfoque práctico. Wiley & Sons, 2006.