Complejidad ciclomática

La complejidad ciclomática es una métrica de software que se utiliza para indicar la complejidad de un programa . Es una medida cuantitativa del número de rutas linealmente independientes a través del código fuente de un programa . Fue desarrollado por Thomas J. McCabe, Sr. en 1976.

La complejidad ciclomática se calcula utilizando el gráfico de flujo de control del programa: los nodos del gráfico corresponden a grupos indivisibles de comandos de un programa, y ​​un borde dirigido conecta dos nodos si el segundo comando pudiera ejecutarse inmediatamente después del primer comando. La complejidad ciclomática también se puede aplicar a funciones , módulos , métodos o clases individuales dentro de un programa.

Una estrategia de prueba , llamada prueba de ruta base por McCabe, quien la propuso por primera vez, es probar cada ruta linealmente independiente a través del programa; en este caso, el número de casos de prueba será igual a la complejidad ciclomática del programa. ^[1]

Descripción

Definición

Un gráfico de flujo de control de un programa simple. El programa comienza a ejecutarse en el nodo rojo, luego entra en un bucle (grupo de tres nodos inmediatamente debajo del nodo rojo). Al salir del ciclo, hay una declaración condicional (grupo debajo del ciclo), y finalmente el programa sale en el nodo azul. Este gráfico tiene 9 aristas, 8 nodos y 1 componente conectado , por lo que la complejidad ciclomática del programa es 9 - 8 + 2 * 1 = 3.

La complejidad ciclomática de una sección de código fuente es el número máximo de rutas linealmente independientes dentro de ella, donde "linealmente independiente" significa que cada ruta tiene al menos un borde que no está en ninguna de las otras rutas. Por ejemplo, si el código fuente no contuviera declaraciones de flujo de control (condicionales o puntos de decisión), la complejidad sería 1, ya que solo habría una ruta única a través del código. Si el código tuviera una declaración IF de condición única, habría dos rutas a través del código: una donde la instrucción IF se evalúa como VERDADERA y otra donde se evalúa como FALSO, por lo que la complejidad sería 2. Dos IF de condición única anidadas , o un SI con dos condiciones, produciría una complejidad de 3.

Matemáticamente, la complejidad ciclomática de un programa estructurado ^[a] se define con referencia al gráfico de flujo de control del programa, un gráfico dirigido que contiene los bloques básicos del programa, con un borde entre dos bloques básicos si el control puede pasar del primero al segundo. La complejidad M se define entonces como ^[2]

M = E - N + 2 P ,

dónde

E = el número de aristas del gráfico.

N = el número de nodos del gráfico.

P = el número de componentes conectados .

La misma función que la anterior, representada mediante la formulación alternativa, donde cada punto de salida se conecta de nuevo al punto de entrada. Este gráfico tiene 10 bordes, 8 nodos y 1 componente conectado , lo que también da como resultado una complejidad ciclomática de 3 utilizando la formulación alternativa (10 - 8 + 1 = 3).

Una formulación alternativa es utilizar un gráfico en el que cada punto de salida esté conectado con el 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 su gráfico (también conocido como el primer número de Betti ), que se define como ^[2]

M = E - N + P .

Esto puede verse como un cálculo del número de ciclos linealmente independientes que existen en el gráfico, es decir, aquellos ciclos que no contienen otros ciclos dentro de sí mismos. Tenga en cuenta que debido a que cada punto de salida vuelve al punto de entrada, hay al menos uno de esos ciclos para cada punto de salida.

Para un solo programa (o subrutina o método), P siempre es igual a 1. Por lo tanto, una fórmula más simple para una sola subrutina es

M = E - N + 2. ^[3]

Sin embargo, la complejidad ciclomática puede aplicarse a varios programas o subprogramas de este tipo al mismo tiempo (por ejemplo, a todos los métodos de una clase), y en estos casos P será igual al número de programas en cuestión, ya que cada subprograma aparecerá como un subconjunto desconectado del gráfico.

McCabe demostró que la complejidad ciclomática de cualquier programa estructurado con un solo punto de entrada y un punto de salida es igual al número de puntos de decisión (es decir, declaraciones "si" o bucles condicionales) contenidos en ese programa más uno. Sin embargo, esto es cierto solo para los puntos de decisión contados en las instrucciones más bajas a nivel de máquina. ^{[4] Las} decisiones que involucran predicados compuestos como las que se encuentran en lenguajes de alto nivel como IF cond1 AND cond2 THEN ...deben contarse en términos de variables de predicado involucradas, es decir, en este ejemplo uno debe contar dos puntos de decisión, porque a nivel de máquina es equivalente a IF cond1 THEN IF cond2 THEN .... ^{[2] [5]}

La complejidad ciclomática puede extenderse a un programa con múltiples puntos de salida; en este caso es igual a

π - s + 2,

donde π es el número de puntos de decisión en el programa y s es el número de puntos de salida. ^{[5] [6]}

Explicación en términos de topología algebraica

Un subgrafo par de un gráfico (también conocido como subgrafo euleriano ) es aquel en el que cada vértice incide con un número par de aristas; tales subgrafos son uniones de ciclos y vértices aislados. A continuación, los subgráficos pares se identificarán con sus conjuntos de bordes, lo que equivale a considerar solo los subgráficos pares que contienen todos los vértices del gráfico completo.

El conjunto de todos los subgráficos pares de un gráfico se cierra bajo diferencia simétrica y, por lo tanto, puede verse como un espacio vectorial sobre GF (2) ; este espacio vectorial se llama espacio cíclico del gráfico. El número ciclomático del gráfico se define como la dimensión de este espacio. Dado que GF (2) tiene dos elementos y el espacio cíclico es necesariamente finito, el número ciclomático también es igual al logaritmo 2 del número de elementos en el espacio cíclico.

Una base para el espacio de ciclo se construye fácilmente fijando primero un bosque de expansión del gráfico y luego considerando los ciclos formados por un borde que no está en el bosque y el camino en el bosque que conecta los puntos finales de ese borde; estos ciclos constituyen una base para el espacio cíclico. Por lo tanto, el número ciclomático también es igual al número de bordes que no están en un bosque de expansión máxima de un gráfico. Dado que el número de aristas en un bosque de expansión máxima de un gráfico es igual al número de vértices menos el número de componentes, la fórmula${\displaystyle E-N+P}$anterior para el número ciclomático sigue. ^[7]

Para los más inclinados a la topología, la complejidad ciclomática se puede definir alternativamente como un número de Betti relativo , el tamaño de un grupo de homología relativa :

${\displaystyle M:=b_{1}(G,t):=\operatorname {rank} H_{1}(G,t),}$

que se lee como "el rango del primer grupo de homología del gráfico G , con respecto a los nodos terminales t ". Esta es una forma técnica de decir "el número de rutas linealmente independientes a través del diagrama de flujo desde una entrada a una salida", donde:

• "linealmente independiente" corresponde a la homología, y significa que uno no cuenta el retroceso doble;
• "caminos" corresponde a la primera homología: un camino es un objeto unidimensional;
• "relativo" significa que la ruta debe comenzar y terminar en un punto de entrada o salida.

Esto corresponde a la noción intuitiva de complejidad ciclomática y se puede calcular como se indicó anteriormente.

Alternativamente, uno puede calcular esto a través del número Betti absoluto (homología absoluta - no relativa) identificando (pegando) todos los nodos terminales en un componente dado (o de manera equivalente, dibujando caminos que conectan las salidas a la entrada), en cuyo caso (llamando el nuevo gráfico aumentado ${\displaystyle {\tilde {G}}}$, que es ^{[ aclaración necesaria ]} ), se obtiene

${\displaystyle M=b_{1}({\tilde {G}})=\operatorname {rank} H_{1}({\tilde {G}}).}$

También se puede calcular mediante homotopía . Si se considera el gráfico de flujo de control como un complejo CW unidimensional llamado${\displaystyle X}$, entonces el grupo fundamental de${\displaystyle X}$ estarán ${\displaystyle \pi _{1}(X)=\mathbb {Z} ^{n}}$. El valor de${\displaystyle n+1}$es la complejidad ciclomática. El grupo fundamental cuenta cuántos bucles hay a través del gráfico, hasta la homotopía, y por lo tanto se alinea con lo que intuitivamente esperaríamos.

Esto corresponde a la caracterización de la complejidad ciclomática como "número de bucles más número de componentes".

Aplicaciones

Limitar la complejidad durante el desarrollo

Una de las aplicaciones originales de McCabe fue limitar la complejidad de las rutinas durante el desarrollo del programa; recomendó que los programadores deberían contar la complejidad de los módulos que están desarrollando y dividirlos en módulos más pequeños siempre que la complejidad ciclomática del módulo excediera de 10. ^[2] Esta práctica fue adoptada por la metodología NIST Structured Testing, con una observación que desde En la publicación original de McCabe, la cifra de 10 había recibido pruebas sustanciales que lo corroboraban, pero en algunas circunstancias puede ser apropiado relajar la restricción y permitir módulos con una complejidad de hasta 15. Como la metodología reconoció que había razones ocasionales para ir más allá el límite acordado, expresó su recomendación como "Para cada módulo, limite la complejidad ciclomática al [límite acordado] o proporcione una explicación por escrito de por qué se excedió el límite". ^[8]

Medir la "estructuración" de un programa

La Sección VI del artículo de McCabe de 1976 se ocupa de determinar cómo se ven los gráficos de flujo de control (CFG) de los programas no estructurados en términos de sus subgrafos, que McCabe identifica. (Para más detalles sobre esa parte, ver el teorema del programa estructurado .) McCabe concluye esa sección proponiendo una medida numérica de cuán cerca del ideal de programación estructurada está un programa dado, es decir, su "estructuración" usando el neologismo de McCabe. McCabe calificó la medida que ideó para este propósito de complejidad esencial . ^[2]

Para calcular esta medida, el CFG original se reduce iterativamente mediante la identificación de subgrafos que tienen un punto de entrada única y un punto de salida único, que luego son reemplazados por un solo nodo. Esta reducción corresponde a lo que haría un humano si extrajera una subrutina del código más grande. (Hoy en día, tal proceso se incluiría en el término general de refactorización ). El método de reducción de McCabe se denominó más tarde condensación en algunos libros de texto, porque se lo veía como una generalización de la condensación a los componentes utilizados en la teoría de grafos . ^[9] Si un programa está estructurado, el proceso de reducción / condensación de McCabe lo reduce a un solo nodo CFG. Por el contrario, si el programa no está estructurado, el proceso iterativo identificará la parte irreducible. La medida de complejidad esencial definida por McCabe es simplemente la complejidad ciclomática de este grafo irreductible, por lo que será precisamente 1 para todos los programas estructurados, pero mayor que uno para los programas no estructurados. ^{[8] : 80}

Implicaciones para las pruebas de software

Otra aplicación de la complejidad ciclomática es determinar el número de casos de prueba que son necesarios para lograr una cobertura de prueba completa de un módulo en particular.

Es útil debido a dos propiedades de la complejidad ciclomática, M , para un módulo específico:

• M es un límite superior para el número de casos de prueba que son necesarios para lograr una cobertura completa de sucursales .
• M es un límite inferior para el número de rutas a través del gráfico de flujo de control (CFG). Suponiendo que cada caso de prueba toma un camino, el número de casos necesarios para lograr la cobertura del camino es igual al número de caminos que realmente se pueden tomar. Sin embargo, algunos caminos puede ser imposible, por lo que aunque el número de caminos a través de la CFG es claramente un límite superior en el número de casos de prueba necesarios para la cobertura de ruta, este último número (de posibles caminos) es a veces menos de M .

Los tres números anteriores pueden ser iguales: cobertura de sucursales ${\displaystyle \leq }$ complejidad ciclomática ${\displaystyle \leq }$ número de caminos.

Por ejemplo, considere un programa que consta de dos instrucciones if-then-else secuenciales.

si  ( c1 ())  f1 (); más  f2 ();si  ( c2 ())  f3 (); más  f4 ();

El gráfico de flujo de control del código fuente anterior; el círculo rojo es el punto de entrada de la función y el círculo azul es el punto de salida. La salida se ha conectado a la entrada para hacer que el gráfico esté fuertemente conectado.

En este ejemplo, dos casos de prueba son suficientes para lograr una cobertura de sucursal completa, mientras que cuatro son necesarios para una cobertura de ruta completa. La complejidad ciclomática del programa es 3 (ya que el gráfico fuertemente conectado del programa contiene 9 bordes, 7 nodos y 1 componente conectado) (9 - 7 + 1).

En general, para probar completamente un módulo, se deben ejercitar todas las rutas de ejecución a través del módulo. Esto implica que un módulo con un número de complejidad alto requiere más esfuerzo de prueba que un módulo con un valor más bajo, ya que el número de complejidad más alto indica más rutas a través del código. Esto también implica que un módulo con mayor complejidad es más difícil de entender para un programador, ya que el programador debe comprender las diferentes rutas y los resultados de esas rutas.

Desafortunadamente, no siempre es práctico probar todas las rutas posibles a través de un programa. Teniendo en cuenta el ejemplo anterior, cada vez que se agrega una instrucción if-then-else adicional, el número de rutas posibles aumenta en un factor de 2. A medida que el programa crece de esta manera, alcanza rápidamente el punto en el que probar todas las rutas se convierte en poco práctico.

Una estrategia de prueba común, adoptada, por ejemplo, por la metodología de prueba estructurada del NIST, es utilizar la complejidad ciclomática de un módulo para determinar el número de pruebas de caja blanca que se requieren para obtener una cobertura suficiente del módulo. En casi todos los casos, de acuerdo con dicha metodología, un módulo debería tener al menos tantas pruebas como su complejidad ciclomática; en la mayoría de los casos, este número de pruebas es adecuado para ejercitar todos los caminos relevantes de la función. ^[8]

Como ejemplo de una función que requiere más que simplemente cobertura de rama para probar con precisión, considere nuevamente la función anterior, pero suponga que para evitar que ocurra un error, cualquier código que llame a f1 () o f3 () también debe llamar a la otra. ^[b] Suponiendo que los resultados de c1 () y c2 () son independientes, eso significa que la función presentada anteriormente contiene un error. La cobertura de sucursales nos permitiría probar el método con solo dos pruebas, y un posible conjunto de pruebas sería probar los siguientes casos:

• c1()devuelve verdadero y c2()devuelve verdadero
• c1()devuelve falso y c2()devuelve falso

Ninguno de estos casos expone el error. Sin embargo, si utilizamos la complejidad ciclomática para indicar el número de pruebas que requerimos, el número aumenta a 3. Por lo tanto, debemos probar una de las siguientes rutas:

• c1()devuelve verdadero y c2()devuelve falso
• c1()devuelve falso y c2()devuelve verdadero

Cualquiera de estas pruebas expondrá el error.

Correlación con el número de defectos

Varios estudios han investigado la correlación entre el número de complejidad ciclomática de McCabe con la frecuencia de defectos que ocurren en una función o método. ^[10] Algunos estudios ^[11] encuentran una correlación positiva entre la complejidad ciclomática y los defectos: las funciones y los métodos que tienen la mayor complejidad tienden a contener también la mayoría de los defectos. Sin embargo, la correlación entre la complejidad ciclomática y el tamaño del programa (normalmente medido en líneas de código ) se ha demostrado muchas veces. Les Hatton ha afirmado ^[12] que la complejidad tiene la misma capacidad predictiva que las líneas de código. Los estudios que controlaron el tamaño del programa (es decir, la comparación de módulos que tienen diferentes complejidades pero un tamaño similar) son generalmente menos concluyentes, y muchos no encuentran una correlación significativa, mientras que otros sí la encuentran. Algunos investigadores que han estudiado el área cuestionan la validez de los métodos utilizados por los estudios al no encontrar correlación. ^[13] Aunque esta relación probablemente sea cierta, no es fácilmente utilizable. ^[14] Dado que el tamaño del programa no es una característica controlable del software comercial, se ha cuestionado la utilidad del número de McCabes. ^[10] La esencia de esta observación es que los programas más grandes tienden a ser más complejos y a tener más defectos. No se ha demostrado que reducir la complejidad ciclomática del código reduzca el número de errores o errores en ese código. Los estándares de seguridad internacionales como ISO 26262 , sin embargo, exigen pautas de codificación que imponen una complejidad de código baja. ^[15]

Inteligencia artificial

La complejidad ciclomática también se puede utilizar para la evaluación de la complejidad semántica de los programas de inteligencia artificial. ^[dieciséis]

Topología ultramétrica

La complejidad ciclomática ha demostrado su utilidad en el análisis geográfico y paisajístico-ecológico, luego de que se demostró que se puede implementar en gráficos de distancias ultramétricas . ^[17]

Ver también

• Complejidad de programación
• Trampa de la complejidad
• Programa de computadora
• Programación de computadoras
• Flujo de control
• Camino de decisión a decisión
• Predicados de diseño
• Complejidad esencial (medida numérica de "estructuración")
• Medidas de complejidad de Halstead
• Ingeniería de software
• Pruebas de software
• Análisis de programa estático
• Mantenibilidad

Notas

1. Aquí "estructurado" significa en particular "con una única salida ( declaración de retorno ) por función".
2. Este es un tipo de condición bastante común; considere la posibilidad de que f1 asigne algún recurso que libere f3.

Referencias

1. AJ Sobey. "Prueba de ruta de base" .
2. McCabe (diciembre de 1976). "Una medida de complejidad" . Transacciones IEEE sobre ingeniería de software (4): 308–320. doi : 10.1109 / tse.1976.233837 .
3. Philip A. Laplante (25 de abril de 2007). Lo que todo ingeniero debe saber sobre la ingeniería de software . Prensa CRC. pag. 176. ISBN 978-1-4200-0674-2.
4. Fricker, Sébastien (abril de 2018). "¿Qué es exactamente la complejidad ciclomática?" . froglogic GmbH . Consultado el 27 de octubre de 2018 . Para calcular una representación gráfica de código, simplemente podemos desensamblar su código ensamblador y crear un gráfico siguiendo las reglas: ...
5. Belzer, Kent, Holzman y Williams (1992). Enciclopedia de Ciencias y Tecnología de la Computación . Prensa CRC. págs. 367–368.
6. Harrison (octubre de 1984). "Aplicando la medida de complejidad de Mccabe a programas de salida múltiple". Software: práctica y experiencia . 14 (10): 1004–1007. doi : 10.1002 / spe.4380141009 .
7. Diestel, Reinhard (2000). Teoría de grafos . Textos de posgrado en matemáticas 173 (2 ed.). Nueva York: Springer. ISBN 978-0-387-98976-1.
8. Arthur H. Watson; Thomas J. McCabe (1996). "Pruebas estructuradas: una metodología de prueba utilizando la métrica de complejidad ciclomática" (PDF) . Publicación especial NIST 500-235.
9. Paul C. Jorgensen (2002). Pruebas de software: el enfoque de un artesano, segunda edición (2ª ed.). Prensa CRC. págs. 150-153. ISBN 978-0-8493-0809-3.
10. Norman E Fenton; Martin Neil (1999). "Una crítica de los modelos de predicción de defectos de software" (PDF) . Transacciones IEEE sobre ingeniería de software . 25 (3): 675–689. CiteSeerX  10.1.1.548.2998 . doi : 10.1109 / 32.815326 .
11. Schroeder, Mark (1999). "Una guía práctica de métricas orientadas a objetos". Profesional de TI . 1 (6): 30–36. doi : 10.1109 / 6294.806902 . S2CID  14945518 .
12. Les Hatton (2008). "El papel del empirismo en la mejora de la fiabilidad del software del futuro" . versión 1.1.
13. Kan (2003). Métricas y Modelos en Ingeniería de Calidad de Software . Addison-Wesley. págs. 316–317. ISBN 978-0-201-72915-3.
14. GS Cherf (1992). "Una investigación de las características de mantenimiento y soporte del software comercial". Revista de Calidad del Software . 1 (3): 147-158. doi : 10.1007 / bf01720922 . ISSN  1573-1367 .
15. ISO 26262-3: 2011 (en) Vehículos de carretera. Seguridad funcional. Parte 3: Fase conceptual . Organización Internacional de Normalización.
16. Papadimitriou, Fivos (2012). "Inteligencia artificial en la modelización de la complejidad de las transformaciones del paisaje mediterráneo". Informática y electrónica en agricultura . 81 : 87–96. doi : 10.1016 / j.compag.2011.11.009 .
17. Papadimitriou, Fivos (2013). "Modelización matemática del uso del suelo y la complejidad del paisaje con topología ultramétrica". Revista de ciencia del uso de la tierra . 8 (2): 234-254. doi : 10.1080 / 1747423X.2011.637136 .

enlaces externos

• Generación de métricas de complejidad ciclomática con Polyspace
• El papel del empirismo en la mejora de la fiabilidad del software futuro
• Un pequeño analizador de código fuente C / C ++ que utiliza la métrica de complejidad ciclométrica (solo Windows, sin código fuente)
• La complejidad ciclomática de McCabe y por qué no la usamos