En este cuarto artículo, vamos a tratar un poco de complejidad ciclomática. A pesar del nombre extravagante, la complejidad ciclomática (también conocida como complejidad condicional) es una simple métrica para determinar, como su nombre lo sugiere, la complejidad de un programa estructurado (cíclico).
Complejidad Ciclomática
Este indicador fue desarrollado en 1976 por Thomas J. McCabe y refleja directamente el número de caminos independientes que un programa puede tomar durante su ejecución. Cualquier desarrollador que haya probado código en su vida, sabe que la cantidad de pruebas necesarias para ejercitar un determinado lugar del código es directamente proporcional a su árbol de decisiones. En otras palabras, cunatos más caminos el código puede tomar (ya sea por medio de condiciones o bucles), mayor es la cantidad de pruebas necesarias. Y como veremos más adelante, no hay realmente una relación directa entre la complejidad ciclomática y la cobertura de un código.
Cálculo de la complejidad ciclomática
Antes de mostrar exactamente la forma en que el cálculo se puede hacer, vamos a observar algunas cosas en relación con cualquier programa. Di que está desarrollando un programa para dar el máximo común divisor entre dos números. Una fórmula simple es el algoritmo de Euclides, que puede describirse como sigue:
Dados dos números naturales a y b, compruebe si b es igual a cero. Si es así, a es el mayor divisor común entre los mismos, de lo contrario, repetir el proceso usando b y el resto de la división de a por b.
Este algoritmo puede ser expresado por el siguiente programa en Ruby (note que no es Ruby idiomático):
require "test/unit"
def euclid(m, n)
if n > m
r = m
m = n
n = r
end
r = m % n
while r != 0
m = n
n = r
r = m % n
end
n
end
class EuclidTest < Test::Unit::TestCase
SETS = [[5, 10, 5], [2, 6, 2], [11, 7, 1],
[80, 64, 16], [2, 2, 2]]
def test_euclid
SETS.each do |set|
assert_equal set[2], euclid(set[0], set[1])
end
end
end
Si el programa de arriba se ejecuta, correrá el caso de prueba justo debajo de la función que verificará si la misma es correcta. Usted puede agregar un mayor número de casos al conjunto SETS, si lo desea.
La función de Euclides se pueden describir por un simple grafo que conecta los caminos entre las diversas declaraciones que contiene. Este grafo se muestra a continuación:
Sobre la base de este grafo, podemos definir la complejidad ciclomática de un programa de la siguiente manera:
CC = A - N + 2C
En esta fórmula:
- CC es la complejidad ciclomática
- A es el número de aristas del grafo
- N es el número de nodos en el grafo
- C es el número de componentes conectados
Debido a que esta es una función simple con un solo punto de entrada y salida, el número de componentes es 1 y la fórmula puede reducirse a:
CC = A - N + 2
Si la función posee múltiples puntos de salida, entonces, la complejidad ciclomática sería definida como:
CC = A - N + C + R
En esta fórmula, R es el número de declaraciones de salida (en Ruby, el número de returns).
Volviendo al grafo que se muestra en la figura, vemos que tiene 11 nodos y 12 aristas, que nos da una complejidad ciclomática de 12-11 + 2, es decir, 3. Otra forma muy sencilla para descubrir la complejidad ciclomática es contar el número de loops cerrados en el grafo (que son formados por condicionales y loops) y añadir el número de puntos de salida. En el grafo anterior, tenemos 2 bucles cerrados (los if y while) y un punto de salida, resultando el mismo valor 3 para la complejidad de la función.
Una cosa interesante es que la complejidad sigue siendo la misma cuando la sintaxis de un lenguaje se pone en cuestión sin cambiar la semántica del programa. Tomemos, por ejemplo, la versión idiomática del algoritmo en Ruby:
def euclid(m, n)
m, n = n, m if n > m
m, n = n, m % n while m % n != 0
n
end
El grafo generado en este caso es:
Note que, aunque el número de nodos y aristas ha cambiado, la relación entre ellos no ha cambiado y la complejidad sigue siendo las misma.
Pruebas
En general, el valor de complejidad ciclomática establece un límite superior en la cantidad de pruebas necesarias para cubrir todos los caminos decisorios del código en cuestión. Este es un límite superior, ya que no todos los caminos son necesariamente realizables.
De eso se infiere que cuanto menor es la complejidad, menor es la cantidad de pruebas necesarias para el método en cuestión. Este hecho conduce a otra curiosidad: romper un método en vrios reduce la complejidad de los métodos, pero aumenta la complejidad general del código y, de forma general, mantiene la comprobabilidad del programa completo en el mismo nivel.
Referencias
Obviamente, dado que la complejo es un valor específico, es posible establecer una referencia. Basado en el trabajo de McCabe, los valores de referencia son los siguientes:
- 1-10, métodos sencillos, sin mucho riesgo
- 11-20, métodos medianamente complejos, con riesgo moderado
- 21-50, métodos complejos, con alto riesgo
- 51 o más, métodos inestables, de altísimo riesgo
Conclusión
Se trata de una breve introducción al tema a fin de allanar el camino para posteriores artículos mostrando herramientas de apoyo al cálculo y el seguimiento de la complejidad ciclomática. Como de costumbre, sugerencias y correcciones son bienvenidas.