Comprender la complejidad ciclomática

11

Recientemente me he encontrado con la Complejidad Ciclomática y me gustaría tratar de entenderla mejor.

¿Cuáles son algunos ejemplos prácticos de codificación de los diferentes factores que intervienen en el cálculo de la complejidad? Específicamente, para la ecuación de Wikipedia M = E − N + 2P, quiero comprender mejor lo que significa cada uno de los siguientes términos:

  • E = el número de bordes de la gráfica
  • N = el número de nodos del gráfico
  • P = el número de componentes conectados

Sospecho que E o N pueden ser el número de puntos de decisión (si, de lo contrario, si, para foreach, etc.) en un bloque de código, pero no estoy muy seguro de cuál es cuál o qué significa el otro. También supongo que P se refiere a llamadas a funciones e instancias de clase, pero no hay una definición clara dado que puedo ver. Si alguien pudiera arrojar un poco más de luz con algunos ejemplos de código claro de cada uno, sería útil.

Como seguimiento, ¿la Complejidad Ciclomática se correlaciona directamente con la cantidad de pruebas unitarias necesarias para una cobertura de ruta del 100% ? Como ejemplo, ¿un método con una complejidad de 4 indica que se necesitan 4 pruebas unitarias para cubrir ese método?

Finalmente, ¿las expresiones regulares afectan la Complejidad Ciclomática, y si es así, cómo?

VirtuosiMedia
fuente
Descubrí que puedes obtener el artículo original de McCabe de Wikipedia y Google Books producirá el libro que McCabe usó para su artículo original. Curiosamente, encontrará que McCabe usó el teorema original de manera incorrecta (y también explica de manera confusa, ya que debe comenzar con un gráfico no dirigido y no es necesario que esté fuertemente conectado en primer lugar), pero los números salen correctamente de todos modos ( la fórmula correcta sería M = E + 1-N + P, pero como P es siempre 1, se ajusta ...) Se piensa que el "manejo de excepciones" moderno arroja una llave en los trabajos de esa métrica.
David Tonhofer
... y qué pasa con las llamadas recursivas (posiblemente pasando por una cadena de funciones). ¿Se fusionan los gráficos de funciones? ¿Qué hay de los operadores booleanos de cortocircuito como "&&". Operadores guardados como "ref? .X" que dan un valor nulo si ref es nulo? Oh bueno, es solo otra métrica. Pero hay algo de trabajo para un pequeño proyecto universitario aquí.
David Tonhofer

Respuestas:

8

En cuanto a la fórmula: los nodos representan estados, los bordes representan cambios de estado. En cada programa, las declaraciones traen cambios en el estado del programa. Cada declaración consecutiva está representada por un borde, y el estado del programa después (o antes ...) de la ejecución de la declaración es el nodo.

Si tiene una declaración de ramificación ( ifpor ejemplo), entonces tiene dos nodos que salen, porque el estado puede cambiar de dos maneras.

Otra forma de calcular el Número de Complejidad Ciclomática (CCN) es calcular cuántas "regiones" en el gráfico de ejecución tiene (donde "región independiente" es un círculo que no contiene otros círculos). En este caso, el CCN será el número de regiones independientes más 1 (que sería exactamente el mismo número que le da la fórmula anterior).

El CCN se utiliza para la cobertura de ramificación , o cobertura de ruta , que es lo mismo. El CCN es igual al número de diferentes rutas de ramificación teóricamente posibles en una sola aplicación de subprocesos (que puede incluir ramas como " if x < 2 and x > 5 then", pero que un buen compilador debe detectar como un código inalcanzable). Debe tener al menos ese número de casos de prueba diferentes (puede ser más, ya que algunos casos de prueba pueden estar repitiendo rutas cubiertas por otras anteriores, pero no menos asumiendo que cada caso cubre una sola ruta). Si no puede cubrir una ruta con algún posible caso de prueba, encontró un código inalcanzable (aunque necesitará probarse a sí mismo por qué es inalcanzable, probablemente algunos anidados al x < 2 and x > 5acecho en alguna parte).

En cuanto a las expresiones regulares, por supuesto, afectan, como cualquier otra pieza de código. Sin embargo, el CCN de la construcción regex es probablemente demasiado alto para cubrirlo en una sola prueba de unidad, y puede suponer que el motor regex ha sido probado e ignorar el potencial de ramificación de las expresiones para sus necesidades de prueba (a menos que esté probando su motor regex, por supuesto).

littleadv
fuente
2
+1: En realidad, debes confiar en que el motor regex ha sido probado. Si usted no confía en él, conseguir uno que lo hace la confianza.
S.Lott
"El CCN es igual al número de rutas de ejecución diferentes posibles en una sola aplicación de subprocesos" Esto está mal ya que el CCN se basa solo en la topología del código y no en su significado . Un buen porcentaje de estas rutas puede ser imposible de ejercer ya que exigen un estado de entrada que no se puede establecer (algunas x son 5 y también menos de 2, por ejemplo). Francamente, creo que usar el CCN para decidir sobre casos de prueba para ejecutar es perverso. CCN es un número para decirle al desarrollador "es posible que haya exagerado aquí, por favor considere refactorizar". E incluso entonces, puede haber una buena razón para un alto CCN.
David Tonhofer
1
@David agregó una oración para abordar eso. CCN es una cobertura de sucursal y nunca hay buenas razones para un CCN alto en un nivel inferior (generalmente sugiero que se haga cumplir por función individual).
littleadv
La cobertura de sucursal y la cobertura de ruta no son lo mismo. La cobertura de sucursal tiene como objetivo cubrir todas las ramas, mientras que la cobertura de ruta apunta a cubrir todas las combinaciones de sucursales.
Mouviciel
13

Algunas observaciones sobre esto que escribo ociosamente ...

Específicamente, para la ecuación de Wikipedia de M = E - N + 2P

Esa ecuación está muy mal .

Por alguna razón, McCabe de hecho lo usa en su artículo original ("A Complexity Measure", IEEE Transactions on Software Engineering, Vo .. SE-2, No.4, diciembre de 1976), pero sin justificarlo y después de realmente citar lo correcto. fórmula en la primera página, que es

v (G) = e - v + p

(Aquí, los elementos de la fórmula se han vuelto a etiquetar)

Específicamente, McCabe hace referencia al libro C.Berge, Graphs and Hypergraphs (abreviado a continuación a G&HG). Directamente de ese libro :

Definición (página 27 al final de G&HG):

El número ciclomático v (G) de un gráfico G (no dirigido) (que puede tener varios componentes desconectados) se define como:

v (G) = e - v + p

donde e = número de aristas, v = número de vértices, p = número de componentes conectados

Teorema (página 29 arriba de G&HG) (no utilizado por McCabe):

El número ciclomático v (G) de un gráfico G es igual al número máximo de ciclos independientes

Un ciclo es una secuencia de vértices que comienza y termina en el mismo vértice, con cada uno de los dos vértices consecutivos en la secuencia adyacente entre sí en el gráfico.

Intuitivamente, un conjunto de ciclos es independiente si ninguno de los ciclos se puede construir a partir de los demás superponiendo las caminatas.

Teorema (página 29 en el centro de G&HG) (según lo utilizado por McCabe):

En un gráfico G fuertemente conectado, el número ciclomático es igual al número máximo de circuitos linealmente independientes.

Un circuito es un ciclo sin repeticiones de vértices y aristas permitidas.

Se dice que un gráfico dirigido está fuertemente conectado si cada vértice es accesible desde cualquier otro vértice al pasar a través de los bordes en la dirección designada.

Tenga en cuenta que aquí pasamos de gráficos no dirigidos a gráficos fuertemente conectados (que están dirigidos ... Berge no deja esto completamente claro)

McCabe ahora aplica el teorema anterior para derivar una manera simple de calcular un "Número de Complejidad Ciclomática McCabe" (CCN) de esta manera:

Dado un gráfico dirigido que representa la "topología de salto" de un procedimiento (el gráfico de flujo de instrucciones), con un vértice designado que representa el punto de entrada único y un vértice designado que representa el punto de salida único (el vértice del punto de salida debe ser "construido" agregándolo en caso de retornos múltiples), cree un gráfico fuertemente conectado agregando un borde dirigido desde el vértice del punto de salida al vértice del punto de entrada, haciendo que el vértice del punto de entrada sea accesible desde cualquier otro vértice.

McCabe ahora postula (de manera bastante confusa, podría decir) que el número ciclomático del diagrama de flujo de instrucciones modificado "se ajusta a nuestra noción intuitiva de 'número mínimo de caminos'", por lo que usaremos ese número como medida de complejidad.

Genial, entonces:

El número de complejidad ciclomática del gráfico de flujo de instrucciones modificado se puede determinar contando los circuitos "más pequeños" en el gráfico no dirigido. Esto no es particularmente difícil de hacer por el hombre o la máquina, pero la aplicación del teorema anterior nos da una forma aún más fácil de determinarlo:

v (G) = e - v + p

si se ignora la direccionalidad de los bordes.

En todos los casos, solo consideramos un procedimiento único, por lo que solo hay un componente conectado en todo el gráfico, y así:

v (G) = e - v + 1.

En caso de que se considere el gráfico original sin el borde agregado de "salida a entrada" , se obtiene simplemente:

ṽ (G) = ẽ - v + 2

como ẽ = e - 1

Vamos a ilustrar usando el ejemplo de McCabe de su artículo:

El ejemplo de McCabe

Aquí tenemos:

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

La fórmula para el número ciclomático dice:

v (G) = e - v + p

que produce 5 = 10 - 6 + 1 y ¡correcto!

El "número de complejidad ciclomática de McCabe" tal como figura en su artículo es

5 = 9 - 6 + 2 (no se dan más explicaciones en el documento sobre cómo)

que resulta ser correcto (produce v (G)) pero por razones equivocadas, es decir, usamos:

ṽ (G) = ẽ - v + 2

y así ṽ (G) = v (G) ... ¡uf!

¿Pero esta medida es buena?

En dos palabras: no muy

  • No está del todo claro cómo establecer el "gráfico de flujo de instrucciones" de un procedimiento, especialmente si el manejo de excepciones y la recursividad entran en escena. Tenga en cuenta que McCabe aplicó su idea al código escrito en FORTRAN 66 , un lenguaje sin recursión, sin excepciones y una estructura de ejecución sencilla.
  • El hecho de que un procedimiento con una decisión y un procedimiento con un ciclo produzca el mismo CCN no es una buena señal.

ingrese la descripción de la imagen aquí

David Tonhofer
fuente
1
@JayElston Buena captura. De hecho, lo hago. ¡Fijo!
David Tonhofer
1
Gran +1 para vincular al documento original. Muchos de los documentos escritos en ese momento son bastante legibles para cualquier programador de nivel medio y deben leerse.
Daniel T.
1

Como seguimiento, ¿la Complejidad Ciclomática se correlaciona directamente con la cantidad de pruebas unitarias necesarias para una cobertura de ruta del 100%?

Si, básicamente. También es una buena idea utilizar la complejidad ciclomática como indicador de cuándo refactorizar. En mi experiencia, la capacidad de prueba y la reutilización aumentan en gran medida para un CC más bajo (aunque debería ser práctico, no refactorice demasiado, y algunos métodos tendrán un CC alto debido a su naturaleza), no siempre tiene sentido intentar forzarlo inferior).

Finalmente, ¿las expresiones regulares afectan la Complejidad Ciclomática, y si es así, cómo?

Sí, si quieres ser exacto, aunque la mayoría de las herramientas de análisis de código no parecen tenerlas en cuenta de esa manera. Las expresiones regulares son solo máquinas de estados finitos, así que supongo que su CC podría calcularse a partir del gráfico FSM, pero sería un número bastante grande.

Daniel B
fuente
+1 - Supongo que calcular el CC para RegExes no es una tarea divertida.
VirtuosiMedia