¿Cuándo dos actividades son la misma?

La equivalencia no es única

Cada actividad de esta progresión existe en dos plataformas: Protobject (bloques desde el celular) y micro:bit (MakeCode). Queremos poder afirmar, con rigor, que ambas versiones son «la misma actividad». Pero al estudiar qué significa ser la misma, aparece una distinción que organiza todo este documento.

Distinguimos al menos dos dimensiones —y dejamos la puerta abierta a otras:

La equivalencia algorítmica es necesaria pero no suficiente: dos actividades pueden ser algorítmicamente idénticas y experiencialmente divergentes, o viceversa. Por eso el veredicto final no es un sí/no, sino un perfil de equivalencia. Esta guía recorre primero la dimensión algorítmica en profundidad (Parte I), luego la experiencial (Parte II), y finalmente cómo ambas se sostienen como un programa de investigación (Parte III).

Dos programas, dos plataformas, una pregunta

Imagina que tienes dos programas escritos en plataformas distintas. Por ejemplo, dos entornos de programación por bloques, hechos por empresas diferentes, con paletas de colores y vocabularios distintos. Los miras: parecen muy diferentes. Los ejecutas: hacen, más o menos, lo mismo. ¿Son el mismo programa?

Esta pregunta parece fácil, pero esconde una trampa. La respuesta correcta depende de qué entiendes por «equivalente». Y descubrir las distintas respuestas posibles — y por qué cada una es útil en contextos diferentes — es el viaje que vamos a hacer en estas páginas.

La pregunta no es académica: surge cada vez que alguien quiere comparar proyectos de estudiantes hechos en plataformas distintas, traducir entre lenguajes de programación, detectar plagio, o simplemente entender si dos colegas han resuelto un problema «de la misma manera». Es un problema fundamental de las ciencias de la computación, y todavía hoy abierto en muchos aspectos.

El árbol sintáctico, o cómo empieza la mayoría

Cuando escribimos un programa, su estructura puede representarse como un árbol sintáctico abstracto, o AST (Abstract Syntax Tree). Es la representación que usan los compiladores: la raíz es el programa entero, las ramas son las instrucciones, las hojas son los valores y operadores.

Comparar dos programas por sus AST es una idea natural. Si dos AST son iguales (o muy parecidos), los programas tienen la misma estructura sintáctica. Herramientas reales como Moss o JPlag usan exactamente este enfoque para detectar plagio en código universitario.

Pero para nuestra pregunta — ¿son el mismo algoritmo? — el AST tiene tres problemas serios.

Problema 1 · Está atado al dialecto

El AST de un programa en MakeCode tiene nodos llamados plot, acceleration, ring tone. El AST de un programa en otra plataforma puede tener nodos draw on, Inclinación, play note. Para una comparación ingenua del AST, estos son nodos completamente diferentes, aunque representen el mismo concepto subyacente.

Problema 2 · Mantiene el orden sintáctico

En el AST, «primero dibujar el punto, después producir el sonido» es estructuralmente distinto de «primero producir el sonido, después dibujar el punto», aunque las dos instrucciones sean independientes y el orden no importe para el resultado final.

Problema 3 · Mezcla forma y contenido

En el AST, acceleration / 350 y acceleration / 15 son subárboles diferentes porque las constantes son diferentes. Pero a nivel algorítmico, ambos son «transformación lineal del sensor»: la misma forma, parámetros distintos. El AST trata operadores y constantes como parte de la estructura.

Veámoslo en concreto

Los tres problemas anteriores suenan abstractos. Hagámoslos tangibles. Tomemos una sola línea equivalente de nuestros dos programas — el bloque que dibuja el punto — y dibujemos sus AST. Así de diferentes se ven:

plot_statement
├── arg_x
│   └── add
│       ├── literal: 2
│       └── round
│           └── div
│               ├── sensor_read
│               │   ├── kind: acceleration
│               │   └── axis: x
│               └── literal: 350
└── arg_y
    └── literal: 2

draw_on_statement
├── surface_ref: DibujoLED4
├── arg_x
│   └── literal: 4
├── arg_y
│   └── add
│       ├── literal: 4
│       └── round
│           └── div
│               ├── sensor_read
│               │   ├── kind: inclination
│               │   └── axis: y
│               └── literal: 15
└── colour_param
    └── color: red

Un algoritmo clásico de comparación de AST (tree edit distance, isomorfismo, hash de subárboles) ve estas seis diferencias:

1. El nodo raíz tiene nombre distinto. plot_statement ≠ draw_on_statement. Para el algoritmo son tipos sintácticos diferentes: es como comparar un IfStatement con un WhileStatement. Que conceptualmente hagan lo mismo (poner un píxel en una pantalla) es conocimiento que el algoritmo no posee.
2. Aridad distinta. A tiene 2 hijos (x, y). B tiene 4 (superficie, x, y, color). Transformar uno en el otro requiere insertar dos subárboles enteros que en A no existen.
3. El subárbol «interesante» está en posiciones distintas. En A, la expresión que depende del sensor está bajo arg_x. En B está bajo arg_y. Una comparación estructural posicional (hijo 1 con hijo 1, hijo 2 con hijo 2) los ve como muy diferentes: donde A tiene una constante, B tiene un árbol complejo, y viceversa.
4. Las hojas identificador no coinciden. acceleration ≠ inclination, x ≠ y. Incluso después de haber alineado la estructura, cada cadena de texto es distinta. Sin una tabla de equivalencia semántica externa («acceleration e inclination son ambos sensores de inclinación»), el algoritmo no puede saber que deberían mapearse.
5. Las constantes difieren. 2 vs 4, 350 vs 15. Para el AST naive son nodos literal con valores distintos: tres pares de discrepancias adicionales sobre las literales.
6. Nodos presentes solo en uno de los dos. colour_param con red y surface_ref con DibujoLED4 simplemente no existen en el AST de A. No hay con qué compararlos: son inserciones puras desde el punto de vista del algoritmo.

Sumando todo, una distancia de edición razonable entre estos dos subárboles está en el orden de 8–12 operaciones (renombrar raíz + insertar 2 subárboles + intercambiar la posición del subárbol variable + 2 renombrados de identificadores + 3 modificaciones de constantes). Sobre un AST que en total tiene unos 12–15 nodos, eso significa una similitud porcentual bajísima, en torno al 20–30 %.

Compáralo con la conclusión que vamos a alcanzar vía PDG e IR en las próximas secciones: mismo algoritmo, misma forma. El PDG verá unos 7–8 nodos prácticamente isomorfos. El AST ve dos árboles que apenas se parecen.

La representación intermedia

La Representación Intermedia (Intermediate Representation, IR) es una representación «de en medio» del programa: ya no es la sintaxis original (los bloques de colores, las palabras de la plataforma), pero todavía no es el comportamiento observable. Es un lenguaje neutro al que se traducen los programas escritos en plataformas distintas.

La idea es elegante: si traducimos ambos programas a una IR común, con vocabulario neutro, podemos compararlos sin que el «dialecto» de la plataforma nos confunda. Tanto acceleration(mg).x como Inclinación.y se traducen al mismo concepto abstracto: TiltSensorRead(axis). Tanto ring tone (Hz) como play note number se vuelven EmitPitchedSound.

El grafo de dependencias

El Program Dependence Graph (PDG) es un grafo que representa el programa mostrando quién depende de quién, ignorando el orden cuando ese orden no importa para el resultado.

Tiene dos tipos de aristas:

• Dependencias de datos: el nodo Y usa un valor producido por el nodo X — flecha de X a Y.
• Dependencias de control: el nodo Y se ejecuta solo si estamos dentro del bucle o condición X — flecha de X a Y.

El PDG es perfecto para detectar la «forma» del algoritmo, ignorando reorganizaciones triviales del código. Dos programas pueden tener AST muy distintos pero PDG idénticos: tienen la misma estructura algorítmica, simplemente expresada de forma diferente en la superficie.

Mira la figura. El rectángulo punteado rojo representa el alcance de control del bucle: todo lo que está dentro se ejecuta porque estamos dentro del loop. Es la convención visual estándar para indicar que todos los nodos contenidos tienen una dependencia de control del bucle, sin tener que dibujar seis flechas rojas separadas que abarrotarían el diagrama.

Las flechas oscuras dentro del recinto representan el flujo de datos. La lectura del sensor (en ocre) se bifurca: produce un valor v que alimenta dos ramas independientes. Una rama calcula la posición c del punto, la otra el tono p del sonido. Las dos ramas no dependen una de la otra: por eso pueden ejecutarse en cualquier orden, o incluso en paralelo.

La flecha verde discontinua de clear a plot point representa una dependencia por efecto colateral: ambos nodos operan sobre el mismo recurso (la pantalla LED), y por tanto el orden importa aunque no haya una variable que viaje entre ellos. Si dibujáramos primero y limpiáramos después, perderíamos el dibujo. Esta dependencia no aparece como variable en el código fuente, pero existe en la semántica del programa, y el PDG la hace explícita.

Los números a la izquierda de cada nodo indican un orden topológico válido de ejecución. La regla es simple: números distintos = secuenciales, el mismo número = paralelizables. Así: primero clear (1), después read sensor (2), luego los dos cálculos aritméticos en paralelo (ambos con etiqueta 3), después los dos outputs en paralelo (ambos 4), finalmente delay (5). Esta numeración no añade información al grafo — es solo una de las posibles ordenaciones consistentes con las dependencias mostradas — pero ayuda a leer el diagrama como un programa concreto.

El PDG hace esta estructura — dependencias reales, paralelismo, efectos colaterales — visible inmediatamente. El AST no.

Dos programas en busca de equivalencia

Veamos dos programas reales, escritos en plataformas de bloques distintas. A la izquierda, MakeCode (la plataforma del micro:bit). A la derecha, otra plataforma de bloques en español.

A primera vista parecen diferentes: colores distintos, idiomas distintos, nombres de bloques diferentes. Pero ambos hacen algo conceptualmente similar: en un bucle infinito, leen un sensor de inclinación, dibujan un punto en una pantalla LED basado en ese sensor, producen un sonido que también depende del sensor, y esperan un poco antes de repetir.

¿Son equivalentes? Apliquemos lo que hemos aprendido.

Aplicando el método

Paso 1 · Traducción a IR común

Traducimos ambos programas a la misma IR neutra:

Loop:
  ClearDisplay(d)
  v = TiltSensorRead(horizontal)
  c = Add(2, Round(Div(v, 350)))
  PlotPoint(x=c, y=2, d)
  p = Add(v, 1000)
  EmitPitchedSound(p, tone)
  Delay(100)

Loop:
  ClearDisplay(d)
  v = TiltSensorRead(vertical)
  c = Add(4, Round(Div(v, 15)))
  PlotPoint(x=4, y=c, d, red)
  p = Add(v, 60)
  EmitPitchedSound(p, note)
  Delay(100)

Ya con esta sola transformación, las similitudes saltan a la vista. La misma secuencia de operaciones: limpiar, leer sensor, calcular posición, dibujar, calcular tono, sonar, esperar. Los operadores son los mismos. Solo cambian las constantes (porque los sensores devuelven valores en escalas distintas) y unos pocos detalles (qué eje varía, qué canal de audio).

Paso 2 · Construcción y comparación del PDG

El objetivo de este paso es producir una prueba algorítmica y reproducible de que ambos programas tienen el mismo PDG. No basta con decir «se ven iguales»: lo que necesitamos es código ejecutable, que cualquiera pueda correr, con un veredicto verificable al final.

Toda la pipeline se apoya en dos paquetes Python estándar:

• NetworkX — biblioteca para construir y analizar grafos. La usamos en su variante MultiDiGraph (grafo dirigido con posibilidad de múltiples aristas entre el mismo par de nodos), porque queremos distinguir aristas de datos y de efecto colateral incluso cuando van entre los mismos extremos.
• Graphviz (binding Python sobre el binario dot) — para renderizar grafos en SVG. Usa el algoritmo Sugiyama layered drawing de 1981: asignación de nodos a capas, minimización de cruces, asignación de coordenadas, ruteo de aristas.

Construcción del PDG canónico

Después de la normalización vía IR, los dos programas se traducen a un PDG idéntico. La función siguiente lo construye. Nota importante: no hay un PDG_A con etiquetas distintas del PDG_B. La única información que sobrevive a la normalización es el tipo de cada nodo en el lenguaje de la IR, no su nombre en la plataforma original. Por eso una sola función basta para construir ambos.

import networkx as nx

def build_canonical_pdg(name: str) -> nx.MultiDiGraph:
    """
    Build the canonical PDG of one of our example programs,
    AFTER normalization via IR. Both A and B produce this same structure.
    """
    G = nx.MultiDiGraph(name=name)

    # Nodes: (id, kind, sequence)
    G.add_node('n1', kind='ClearDisplay',     seq=1)
    G.add_node('n2', kind='TiltSensorRead',   seq=2)
    G.add_node('n3', kind='Arithmetic',       seq=3)  # → c
    G.add_node('n4', kind='Arithmetic',       seq=3)  # → p
    G.add_node('n5', kind='PlotPoint',        seq=4)
    G.add_node('n6', kind='EmitPitchedSound', seq=4)
    G.add_node('n7', kind='Delay',            seq=5)

    # Data dependencies
    G.add_edge('n2', 'n3', type='data', var='v')
    G.add_edge('n2', 'n4', type='data', var='v')
    G.add_edge('n3', 'n5', type='data', var='c')
    G.add_edge('n4', 'n6', type='data', var='p')

    # Side-effect dependency
    G.add_edge('n1', 'n5', type='side_effect', var='display')

    return G

La tabla de mapeo IR

La información específica de cada plataforma no se pierde: queda en una tabla de mapeo separada, que documenta cómo cada nodo canónico del PDG se materializa en bloques de la plataforma A y de la plataforma B. Esta tabla es la ontología sobre la que se apoya toda la equivalencia.

Las diferencias que ves entre la columna A y la columna B (350 vs 15, x vs y, Hz vs MIDI, etc.) son lo que la normalización ha decidido considerar como parámetros, no como estructura. Cambiarlas no cambia el algoritmo; solo cambia cuánto se inclina, qué eje se mueve, qué timbre suena.

Renderizado algorítmico

El diagrama del PDG no se dibuja a mano: se genera por código desde la estructura de datos NetworkX, vía Graphviz. La función render_pdg toma el grafo, aplica el estilo visual (colores por tipo de nodo, líneas discontinuas para efecto colateral, números de secuencia en las etiquetas) y delega el layout a Graphviz.

import graphviz

COLORS = {
    'background': '#FBF6EB', 'ink': '#1A1612', 'ink_soft': '#4A3F33',
    'burgundy':   '#8B2418', 'ochre': '#B8843A', 'moss': '#5A6B3B',
    'paper':      '#FBF6EB',
}
NODE_STYLES = {
    'TiltSensorRead':   {'fillcolor': COLORS['ochre'], 'fontcolor': COLORS['paper']},
    'PlotPoint':        {'fillcolor': COLORS['moss'],  'fontcolor': COLORS['paper']},
    'EmitPitchedSound': {'fillcolor': COLORS['moss'],  'fontcolor': COLORS['paper']},
}

def render_pdg(G: nx.MultiDiGraph, output_path: str) -> str:
    dot = graphviz.Digraph(name=G.graph['name'])
    dot.attr(rankdir='TB', bgcolor=COLORS['background'])
    dot.attr('node', shape='box', style='rounded,filled',
             fontname='JetBrains Mono', fontsize='11', penwidth='1.5')
    dot.attr('edge', fontname='JetBrains Mono', fontsize='10',
             color=COLORS['ink_soft'], fontcolor=COLORS['burgundy'])

    with dot.subgraph(name='cluster_loop') as c:
        c.attr(label='loop', style='dashed,rounded',
               color=COLORS['burgundy'], penwidth='1.8')

        for node_id, attrs in G.nodes(data=True):
            style = NODE_STYLES.get(attrs['kind'],
                                    {'fillcolor': COLORS['paper']})
            label = f"{attrs['seq']}   {attrs['kind']}"
            c.node(node_id, label=label, **style)

        for u, v, edge_attrs in G.edges(data=True):
            if edge_attrs['type'] == 'data':
                c.edge(u, v, label=f" {edge_attrs['var']} ")
            else:  # side_effect
                c.edge(u, v, label=f" {edge_attrs['var']} ",
                       color=COLORS['moss'], style='dashed',
                       constraint='false')

    return dot.render(output_path, format='svg', cleanup=True)

Aplicación: construir y renderizar ambos PDG

Aunque por construcción producirán el mismo grafo, ejecutamos la pipeline dos veces — una por programa — y mostramos ambos resultados lado a lado. Es una verificación visual: si los diagramas A y B no son idénticos, hay un error en algún punto del pipeline (típicamente, en la tabla de mapeo IR).

if __name__ == '__main__':
    pdg_a = build_canonical_pdg('PDG_A')
    pdg_b = build_canonical_pdg('PDG_B')

    render_pdg(pdg_a, 'pdg_a_render')   # → pdg_a_render.svg
    render_pdg(pdg_b, 'pdg_b_render')   # → pdg_b_render.svg

Y estos son los dos SVG generados:

Comparación algorítmica con VF2

El test de equivalencia se reduce a una pregunta formal: ¿son los dos grafos isomorfos como grafos etiquetados? Es decir, ¿existe una biyección entre los nodos de A y los nodos de B tal que (a) cada par de nodos correspondidos tienen el mismo kind IR, y (b) las aristas se preservan junto con sus atributos?

NetworkX implementa el algoritmo VF2 (Cordella, Foggia, Sansone, Vento, 2004) precisamente para esto. Hay que pasarle dos funciones de matching que definen qué cuenta como compatibilidad entre nodos y entre aristas:

from networkx.algorithms import isomorphism

def node_match(node_a, node_b):
    """Two nodes are compatible iff they have the same IR kind."""
    return node_a['kind'] == node_b['kind']

def edge_match(edges_a, edges_b):
    """
    For MultiDiGraph, edges_a/edges_b are dicts edge_key -> attr_dict
    (multiple edges between same pair allowed). We require the
    multiset of (type, var) pairs to be equal.
    """
    sig_a = sorted((d['type'], d.get('var', '')) for d in edges_a.values())
    sig_b = sorted((d['type'], d.get('var', '')) for d in edges_b.values())
    return sig_a == sig_b

def compare_pdgs(G1, G2) -> dict:
    matcher = isomorphism.MultiDiGraphMatcher(
        G1, G2, node_match=node_match, edge_match=edge_match,
    )
    is_iso = matcher.is_isomorphic()
    report = {
        'isomorphic':   is_iso,
        'nodes_A':      G1.number_of_nodes(),
        'nodes_B':      G2.number_of_nodes(),
        'edges_A':      G1.number_of_edges(),
        'edges_B':      G2.number_of_edges(),
        'node_kinds_A': sorted({d['kind'] for _, d in G1.nodes(data=True)}),
        'node_kinds_B': sorted({d['kind'] for _, d in G2.nodes(data=True)}),
    }
    if is_iso:
        report['node_mapping'] = matcher.mapping
    return report

# Uso:
result = compare_pdgs(pdg_a, pdg_b)
for k, v in result.items():
    print(f"  {k}: {v}")

Detalles importantes de las funciones de matching:

• node_match compara solo kind. El número de secuencia (seq) es metadato visual, no parte de la estructura lógica del grafo — dos PDG con secuencias distintas pero misma topología son lógicamente iguales.
• edge_match es más sutil: como tenemos un MultiDiGraph, entre dos nodos puede haber varias aristas (por ejemplo una de datos y una de efecto colateral). NetworkX nos pasa todas las aristas entre dos nodos a la vez, y nosotros las normalizamos como multiconjuntos de pares (tipo, variable). Ordenamos para poder compararlos directamente.

Output ejecutable

Al correr el script completo (python3 pdg_compare.py) se obtiene este informe para el par A–B:

--- A vs B ---
  isomorphic: True
  graph_edit_distance: 0.0
  nodes_G1: 7
  nodes_G2: 7
  edges_G1: 5
  edges_G2: 5
  node_mapping: {'n1': 'n1', 'n2': 'n2', 'n3': 'n3', 'n4': 'n4',
                 'n5': 'n5', 'n6': 'n6', 'n7': 'n7'}

El veredicto isomorphic: True es la prueba algorítmica que buscábamos. El graph_edit_distance: 0.0 confirma la equivalencia desde otro ángulo: cero operaciones de edit separan los dos grafos. El campo node_mapping dice además cómo los nodos de A se corresponden con los de B: en este caso cada ni de A se mapea con el ni de B (la biyección identidad), lo que era esperable porque construimos ambos a partir de la misma función.

Si los dos PDG hubieran salido de programas verdaderamente distintos (mismo algoritmo, código construido por separado), el mapeo no sería la identidad sino una permutación no trivial — pero el veredicto seguiría siendo True si los algoritmos son equivalentes. Lo importante es que el algoritmo encuentra la biyección por sí solo.

Más allá del sí/no: cuando los PDG difieren un poco

Hasta aquí el caso fácil. Pero en tu corpus real, no todas las parejas de actividades serán perfectamente isomorfas. Algunas tendrán una diferencia menor — un bloque de configuración aquí, un argumento explícito allá — típicamente debida a vincoli de plataforma, no a divergencias algorítmicas. Para esos casos necesitamos:

• Un PDG fiel que muestre la diferencia tal cual es (sin esconderla bajo abstracciones de comodo);
• Una métrica continua — no binaria — que cuantifique cuán grande es la diferencia.

Imaginemos esta situación concreta, plausible en tu corpus: una actividad pide que el display de los puntos LED sea negro con puntos rojos. Sobre la plataforma A es automático — la matriz LED del micro:bit tiene LEDs rojos sobre un fondo negro por construcción del hardware, no hay decisión que tomar. Sobre la plataforma B la matriz es virtual y configurable: para obtener el mismo efecto visual, hay que añadir un bloque extra, una vez, antes del bucle, que fije el fondo a negro. El programa resultante de B produce exactamente lo mismo que el de A, pero estructuralmente tiene un bloque que el de A no tiene.

Llamemos al PDG de este programa variante PDG_C. Su construcción en código es así:

def build_pdg_with_bg_setup() -> nx.MultiDiGraph:
    """
    Variant PDG: same canonical structure as A and B, plus an extra
    SetBackground node OUTSIDE the loop, to compensate for a platform
    that doesn't have a default LED background color.
    """
    G = nx.MultiDiGraph(name='PDG_C')

    # Setup node OUTSIDE the loop
    G.add_node('n0', kind='SetBackground', seq=0, in_loop=False)

    # The rest is the canonical structure
    G.add_node('n1', kind='ClearDisplay',     seq=1, in_loop=True)
    G.add_node('n2', kind='TiltSensorRead',   seq=2, in_loop=True)
    G.add_node('n3', kind='Arithmetic',       seq=3, in_loop=True)
    G.add_node('n4', kind='Arithmetic',       seq=3, in_loop=True)
    G.add_node('n5', kind='PlotPoint',        seq=4, in_loop=True)
    G.add_node('n6', kind='EmitPitchedSound', seq=4, in_loop=True)
    G.add_node('n7', kind='Delay',            seq=5, in_loop=True)

    # Same edges as the canonical PDG
    G.add_edge('n2', 'n3', type='data', var='v')
    G.add_edge('n2', 'n4', type='data', var='v')
    G.add_edge('n3', 'n5', type='data', var='c')
    G.add_edge('n4', 'n6', type='data', var='p')
    G.add_edge('n1', 'n5', type='side_effect', var='display')

    # NEW edge: the background affects how plot point renders
    G.add_edge('n0', 'n5', type='side_effect', var='display')

    return G

La función render_pdg está escrita para mirar el atributo in_loop de cada nodo: los que tienen in_loop=False los pinta fuera del rectángulo del bucle. Las aristas pueden cruzar la frontera del cluster sin problemas. Renderizando, sale este diagrama:

La diferencia con PDG_A se ve a ojo: un nodo más, fuera del cluster del loop; una arista más, en verde discontinuo. Ahora corremos la comparación:

--- A vs C ---
  isomorphic: False
  graph_edit_distance: 2.0
  nodes_G1: 7
  nodes_G2: 8
  edges_G1: 5
  edges_G2: 6

Esta vez isomorphic: False — los grafos no son idénticos. Pero el campo importante es graph_edit_distance: 2.0. Significa: con dos operaciones de edit (añadir un nodo + añadir una arista) se transforma PDG_A en PDG_C. Es una diferencia pequeña, localizada, identificable.

Interpretación: GED es un punto de partida, no un veredicto

El GED bajo te dice que los grafos son casi iguales, pero no te dice por qué. Esa es tu tarea como analista. La regla operativa que recomiendo aplicar a tu corpus es así:

1. Calcula is_isomorphic y graph_edit_distance para cada par de actividades.
2. Si is_isomorphic es True (GED = 0): equivalencia algorítmica perfecta. Anota y pasa adelante.
3. Si GED es bajo (1–3, lo calibras tú en tu corpus): inspecciona dónde está la diferencia. Identifica los nodos/aristas añadidos o quitados. Escribe una explicación en una sola línea.
4. Si la explicación cae bajo plumbing de plataforma (como nuestro caso del fondo): clasificación equivalentes módulo plumbing.
5. Si la explicación implica una diferencia algorítmica real: clasificación variantes — y describir qué cambia.
6. Si el GED es alto y no encuentras explicación corta: clasificación diferentes, sin atajos.

Para la actividad de nuestro ejemplo, la anotación que escribiría la estudiante sería más o menos así:

Actividad N · PDG_A vs PDG_C
  is_isomorphic: False
  graph_edit_distance: 2
  Diferencia: nodo SetBackground(color=black) fuera del bucle en C,
             + arista side-effect SetBackground → PlotPoint.
  Causa: A tiene fondo negro por construcción del hardware del micro:bit;
         B necesita establecerlo explícitamente con un bloque adicional
         para conseguir el mismo efecto visual.
  Clasificación: equivalentes módulo plumbing de plataforma.

Complejidad y escalabilidad

VF2 tiene complejidad exponencial en el peor caso (lo que se espera de un problema en la clase GI: ni se sabe que esté en P ni que sea NP-completo), pero es muy rápido en la práctica cuando los grafos tienen estructura clara —como los PDG de programas reales. Para nuestros PDG de 7 nodos el cómputo es instantáneo (microsegundos). Para PDG de unos cientos de nodos (programa de algunos cientos de líneas), milisegundos. Para grafos verdaderamente grandes (decenas de miles de nodos), conviene cambiar de algoritmo:

• nauty / bliss — canonización exacta, muy eficiente para grafos con muchos automorfismos. Bindings Python disponibles (pynauty).
• Weisfeiler-Lehman graph kernels — aproximación basada en hashing iterativo, sub-cuadrática, y proporciona medidas de similitud (no solo sí/no), útiles para detectar grafos «casi» equivalentes. Implementado en grakel y pyg.
• Graph Edit Distance — la distancia exacta entre dos grafos en términos de operaciones de edición. Implementada en NetworkX como nx.graph_edit_distance. Muy útil para diferenciar «equivalentes» de «casi equivalentes con un par de operaciones distintas». Es lenta (NP-hard en general), pero hay variantes aproximadas.

Para el corpus de un curso (decenas de actividades, cada una con un PDG de unos pocos nodos), nada de esto es un problema: el cuello de botella no es el algoritmo de comparación sino la fase manual previa de transcripción de los bloques en estructura de datos.

Paso 3 · Métricas de comprensibilidad

Más allá de la estructura algorítmica, comparamos las dos versiones según métricas estándar usadas en ingeniería de software para estimar cuán comprensible es un programa.

Prácticamente superpuestos. Cualquier diferencia entre los dos programas, según estas métricas, está dentro del ruido.

El detalle del cálculo

Algunos de estos conteos esconden decisiones que merece la pena hacer explícitas. Vamos métrica por métrica.

Bloques de instrucciones · 5 y 5. Cuento los bloques imperativos: los que hacen algo, no los que producen un valor. En A: forever, clear screen, plot, ring tone, pause. En B: repeat forever, erase draw, draw on, play note number, delay. Incluyo el bloque contenedor (forever / repeat forever) como statement: es la convención estándar.

Bloques de expresiones · 6 y 6. Aquí cuento operadores, funciones y lecturas de sensor, pero no literales numéricos ni de color — es una convención común, no la única. En A: + (en plot), round, accel x (dentro del round), /, accel x (en ring tone), + (en ring tone). En B la estructura es idéntica con el sensor de inclinación. Si contáramos también los literales obtendríamos 11 y 12: la diferencia relativa sigue siendo mínima.

Tipos de bloque distintos · ~9 y ~9. Ambos programas usan 5 tipos de statement (los listados arriba) más 4 tipos de expresión (+, /, round, lectura de sensor). La tilde (~) recuerda que el conteo depende de convenciones: si incluyes red como un tipo «color_literal» o tratas el menú desplegable del eje como parte del tipo del bloque sensor, ambos números suben juntos por la misma cantidad.

Profundidad de expresión · 3 y 3. La expresión más profunda en cada programa tiene la misma forma: sensor → / → round → +. Tres operadores apilados, en ambos casos. Las expresiones del sonido (accel + 1000, incl + 60) son de profundidad 1, así que no son el máximo.

Complejidad ciclomática · 1 y 1. Mide el número de caminos linealmente independientes a través del código. Fue introducida por Thomas J. McCabe en 1976 («A Complexity Measure», IEEE Transactions on Software Engineering). Fórmula breve: 1 + número de puntos de decisión (if, switch, &&, ||, ternarios y, según algunas variantes, también bucles). Ambos programas: cero if, cero condicionales, un bucle sin condición. Con la convención «forever no cuenta como decisión» → 1. Con McCabe estricto «el bucle cuenta» → 2. La elección no cambia la conclusión: idéntica para los dos.

Complejidad cognitiva · 1 y 1. Métrica propuesta por SonarSource (G. Ann Campbell, 2018) como alternativa a la ciclomática, diseñada para acercarse más a la percepción humana de «cuán difícil es de leer» un fragmento de código. Reglas: +1 por cada ruptura del flujo lineal (if, bucle, catch...), +1 adicional por cada nivel de anidamiento. Ambos programas: un bucle al nivel 0, nada anidado dentro → +1 por el bucle, 0 de penalización por anidamiento → 1.

Profundidad de anidamiento · 1 y 1. El bucle está al nivel 1, los statements directamente dentro están al nivel 2. No hay bucles dentro de bucles, ni if dentro de bucles. Anidamiento máximo de control = 1.

Cuando las métricas no bastan

Las métricas automáticas son útiles como proxies (aproximaciones) de la comprensibilidad, pero hay algo que escapa al conteo de bloques y a la complejidad ciclomática. La comprensibilidad es una propiedad cognitiva: depende de quién está leyendo, de su edad, de su experiencia previa, de su modelo mental.

Por ejemplo: las dos constantes que controlan el sonido en nuestros programas — 1000 en A (frecuencia en Hertz) y 60 en B (número MIDI) — son tratadas por todas las métricas como «constantes mágicas» equivalentes. Pero su transparencia cognitiva no es una propiedad del programa: depende de qué conoce el lector.

Un estudiante con nociones de física lee 1000 Hz y entiende inmediatamente: es una frecuencia, número más alto = sonido más agudo. Otro estudiante que ha trasteado con software musical lee 60 y entiende inmediatamente: es el Do central. Un tercero que conoce las dos convenciones ve algo aún más interesante: los dos programas codifican el sonido de forma distinta (escala lineal en Hz, logarítmica en MIDI), y este contraste puede volverse el contenido pedagógico mismo. Para un cuarto estudiante que no conoce ninguna de las dos convenciones, los dos números son códigos opacos por igual.

Cuatro estudiantes, cuatro lecturas distintas del mismo par de programas. Ninguna métrica estática puede prever esta variabilidad, porque la métrica solo mira el código — no sabe quién lo va a leer.

Para validar de verdad la equivalencia de comprensibilidad en un contexto educativo, se necesitan estudios con humanos: tareas de comprensión («¿qué hace este programa?»), de predicción («¿qué se mostrará en pantalla?»), de modificación («cámbialo para que haga X»). Son métodos lentos y caros, pero son los únicos que dan respuestas robustas.

La equivalencia depende del objetivo

Y ahora la pregunta más interesante. Nuestros dos programas son algorítmicamente equivalentes, las métricas dicen que son comprensiblemente equivalentes. ¿Hemos terminado?

No. Falta un detalle. El programa A produce sonido en Hertz (escala lineal en frecuencia). El programa B produce sonido como número MIDI (escala logarítmica, donde cada unidad es un semitono). Si haces variar el sensor de la misma manera, los dos sonidos resultantes son perceptivamente muy distintos: uno es un glissando continuo tipo theremin, el otro es una escala musical con saltos discretos.

¿Son equivalentes los dos programas? Depende:

• Si el objetivo es «entender que inclinar el dispositivo controla un sonido y un movimiento»: sí, equivalentes. Ambos consiguen ese aprendizaje.
• Si el objetivo es «entender la diferencia entre representación lineal y logarítmica del sonido»: no equivalentes. Al contrario, su contraste se vuelve el contenido pedagógico mismo.

En semántica formal de los lenguajes de programación esto se llama equivalencia observacional relativa a una especificación: defines qué quieres observar, y la equivalencia se sigue de eso. Cambiar la especificación cambia el veredicto, sin que el código cambie en absoluto.

Esto significa que ninguna herramienta automática puede dar una respuesta universal a la pregunta «¿son equivalentes estos dos programas?». La respuesta requiere un input adicional: ¿qué te importa observar? Sin ese input, la pregunta está mal formulada. Es una idea sutil pero potente, que tiene implicaciones muy concretas en software educativo, detección de plagio, traducción entre lenguajes y verificación formal de programas.

Aplicar este método a tu corpus de 17 actividades

Hasta aquí hemos descrito el método en abstracto y aplicado a un caso de dos programas pequeños. El paso siguiente es tuyo: aplicarlo a las 17 actividades reales de tu corpus, sabiendo que (a) solo tienes la imagen de los bloques, no el código exportado, y (b) las dos plataformas usan vocabularios distintos. Estas son las decisiones prácticas que tendrás que tomar, en el orden en que las encontrarás.

1. Define un protocolo de transcripción antes de empezar. Cuando solo tienes la imagen de los bloques, lo primero que debes decidir es qué cuenta como nodo del PDG y qué es decoración visual. Por ejemplo: ¿los literales numéricos son nodos separados o atributos del nodo padre? ¿Los colores de los bloques se transcriben o se ignoran? ¿Los menús desplegables (asociados a un bloque sensor) se ven como parte del tipo del bloque o como un argumento? Escribe un protocolo de transcripción de una página y aplícalo de manera idéntica a las 17 actividades. Sin protocolo previo, terminarás racionalizando decisiones a posteriori para que «cuadre», y el resultado no será reproducible. Documenta también los casos ambiguos antes de resolverlos: serán útiles cuando defiendas el método.
2. Construye la ontología antes de comparar nada. Lista todos los tipos de bloque que aparecen en las dos plataformas a lo largo de las 17 actividades. Para cada par equivalente entre plataformas (acceleration.x ↔ y in Inclinación, ring tone ↔ play note, etc.), escribe el nombre canónico que vas a usar. Esta tabla de mapeo es tu ontología, y será el artefacto más reutilizable de tu trabajo. ¿Qué granularidad eliges? TiltSensorRead puede ser suficiente, o quizá necesites distinguir AccelerometerRead de InclinometerRead; la respuesta depende de lo que las actividades pretenden enseñar. Decide a priori y deja constancia escrita de por qué.
3. Aplica el código del Paso 2 actividad por actividad. Para cada actividad, construye su build_canonical_pdg manualmente a partir de la transcripción y la ontología, exactamente como en el ejemplo. Esta fase es la más lenta del trabajo — calcula entre 15 y 30 minutos por actividad si la transcripción está limpia. Renderiza cada PDG con la función render_pdg y guarda el SVG con un nombre sistemático (pdg_actividad_03_A.svg, etc.). Al final tendrás 34 archivos (17 actividades × 2 plataformas) que puedes revisar de un vistazo antes de cualquier análisis automático.
4. Detecta «casi equivalencias» con graph edit distance, no solo con isomorfismo. El isomorfismo VF2 te da una respuesta binaria: sí o no. Pero entre las 17 actividades, algunas serán equivalentes y otras casi-equivalentes (un operador distinto, una constante extra, un bloque de configuración que existe en una plataforma y no en la otra). Aplica también networkx.graph_edit_distance(G1, G2) y define un umbral: distancia 0 → equivalentes, 1–3 → variantes menores que merecen una nota a pie de página (típicamente plumbing de plataforma), > 3 → variación algorítmica real. Decide el umbral antes de mirar los resultados, para no racionalizar a posteriori. Mira el ejemplo PDG_C en el Paso 2 como plantilla: aprende a leer un GED bajo, identificar la causa, escribir la anotación de una línea, y clasificar. Y recuerda la nota crítica: cuando un GED salga distinto de cero, primero intenta minimizarlo usando representaciones alternativas honestas; solo el residuo después de la minimización es la diferencia algorítmica real.
5. Valida con una persona externa una muestra. Elige 3 o 4 actividades de las 17 y pídele a otra persona (un compañero, no a tu director) que las transcriba siguiendo tu protocolo y construya el PDG. Compara con tus transcripciones. Si divergen sistemáticamente en algún tipo de bloque o en alguna decisión, tu protocolo tiene un agujero ahí y conviene refinarlo antes de fiarte del resto. Esta validación cruzada vale para una sola tabla de tu informe, pero protege todo el trabajo.
6. Documenta el pipeline para que otra estudiante pueda reproducirlo. Tu informe final debería contener: el protocolo de transcripción, la ontología (tabla de mapeo), el código (con dependencias y versiones), los umbrales elegidos con justificación, y una bitácora corta de las decisiones tomadas durante el análisis. La prueba ácida de la reproducibilidad: si dentro de seis meses, con todos los archivos en la mano, no puedes rehacer el análisis tú misma sin acordarte de detalles, nadie más podrá. Y si en algún momento un revisor te pregunta «¿por qué decidiste que X mapea a Y?», la respuesta debe estar escrita, no en tu cabeza.

Las decisiones difíciles que vas a encontrar

Algunos casos previsibles que probablemente te tocará resolver, listos para anotarlos en tu bitácora:

• Bloques sin contrapartida en la otra plataforma. Si en MakeCode hay un bloque que en la plataforma española no existe (o viceversa), tu ontología deberá decidir si lo abstraes a un concepto que sí tenga ambos lados, o lo dejas como nodo «exclusivo» que rompe la equivalencia.
• Diferencias de granularidad. Una plataforma puede ofrecer un bloque compuesto («mostrar emoción contenta») que en la otra requiere tres bloques separados. Ambos producen el mismo efecto, pero el PDG nativo tiene topologías distintas. Decisión: ¿des-componer el bloque compuesto en la ontología, o aceptar la diferencia?
• Efectos colaterales no documentados. Como vimos con clear → plot, no todos los efectos colaterales son visibles en el código fuente. Tendrás que conocer la semántica de cada plataforma para añadir las aristas correctas. Si no la conoces, los PDG saldrán incompletos y la comparación dará falsos positivos.
• Bucles con condiciones. Nuestros ejemplos usan forever, sin condición. Si alguna actividad usa un while o repeat N veces, el PDG ganará nodos y aristas de control. Tu ontología debe prever esto.

Conceptos para profundizar (si el tiempo lo permite)

• Graph edit distance aproximada — nx.optimize_graph_edit_distance en NetworkX da resultados utilizables en tiempo razonable para grafos de hasta unas decenas de nodos.
• Weisfeiler-Lehman (biblioteca grakel) si quieres una medida de similitud continua, no solo isomorfismo binario.
• Semantic clone detection (Type-4) — la literatura sobre detectar fragmentos de código que «hacen lo mismo» aunque parezcan distintos. Reutilizable para argumentar el contexto teórico de tu método.
• Program sketches (Armando Solar-Lezama) — «mismo esqueleto, constantes distintas» formalizado, útil para justificar por qué tu umbral de graph edit distance separa «equivalentes» de «casi-equivalentes».

El script en su totalidad

Lo que sigue es el contenido íntegro del script pdg_compare.py referenciado a lo largo del informe. Es ejecutable tal cual: copiándolo en un archivo de Python con las dependencias instaladas (networkx, graphviz) y el binario dot disponible en el sistema, reproduce los tres SVG (PDG_A, PDG_B, PDG_C), los dos informes de comparación (A vs B y A vs C) y, por lo tanto, todos los resultados algorítmicos discutidos en el Paso 2.

El script está organizado en cuatro secciones:

• Construcción — build_canonical_pdg (el PDG común a A y B después de la normalización IR) y build_pdg_with_bg_setup (la variante PDG_C con un nodo de setup fuera del bucle).
• Renderizado — render_pdg, paleta de colores, estilos por tipo de nodo. Gestiona nodos dentro y fuera del cluster del bucle vía el atributo in_loop.
• Comparación — node_match, dos versiones de edge_match (una para MultiDiGraphMatcher, otra para graph_edit_distance) y la función envoltorio compare_pdgs.
• Main — el punto de entrada que construye los tres PDG, los renderiza y los compara dos a dos.

Te animo a leerlo, modificarlo, y reutilizarlo para tu corpus. Es la parte más reusable de este informe: las funciones de construcción, renderizado y comparación se pueden invocar 17 veces para tus 17 actividades sin modificarlas.

"""
PDG construction, visualization and comparison.

Pipeline:
  1. Define PDG canonical (the structure shared by A and B after IR normalization)
  2. Define PDG_C: a variant with an extra SetBackground node outside the loop,
     used to demonstrate near-equivalent (non-isomorphic) cases.
  3. Render each via Graphviz (output: SVG files)
  4. Compare via:
       a. VF2 isomorphism (binary: yes / no)
       b. Graph Edit Distance (continuous: number of edit operations)

Required packages:
  pip install networkx graphviz
  (and the `graphviz` system binary, used as a backend)
"""

import networkx as nx
from networkx.algorithms import isomorphism
import graphviz
from collections import defaultdict


# ---------- 1. PDG construction ----------

def build_canonical_pdg(name: str) -> nx.MultiDiGraph:
    """
    Canonical PDG of programs A and B AFTER normalization via IR.
    They produce the same structure, so a single function suffices.

    Node attrs:
      - kind:    the IR-level operation (used by node_match)
      - seq:     topological sequence number (visual only)
      - in_loop: True (all canonical nodes are inside the loop body)

    Edge attrs:
      - type: 'data' or 'side_effect'
      - var:  variable / resource name on the edge
    """
    G = nx.MultiDiGraph(name=name)

    G.add_node('n1', kind='ClearDisplay',     seq=1, in_loop=True)
    G.add_node('n2', kind='TiltSensorRead',   seq=2, in_loop=True)
    G.add_node('n3', kind='Arithmetic',       seq=3, in_loop=True)
    G.add_node('n4', kind='Arithmetic',       seq=3, in_loop=True)
    G.add_node('n5', kind='PlotPoint',        seq=4, in_loop=True)
    G.add_node('n6', kind='EmitPitchedSound', seq=4, in_loop=True)
    G.add_node('n7', kind='Delay',            seq=5, in_loop=True)

    G.add_edge('n2', 'n3', type='data', var='v')
    G.add_edge('n2', 'n4', type='data', var='v')
    G.add_edge('n3', 'n5', type='data', var='c')
    G.add_edge('n4', 'n6', type='data', var='p')

    G.add_edge('n1', 'n5', type='side_effect', var='display')

    return G


def build_pdg_with_bg_setup() -> nx.MultiDiGraph:
    """
    Variant PDG ('PDG_C'): same canonical structure plus an extra
    SetBackground node OUTSIDE the loop. Used to demonstrate the
    case 'near-equivalent because of platform plumbing'.

    Imagine: on platform A the LED matrix has a black background by
    hardware. On platform B the matrix can be configured; to match A's
    look the student must explicitly add a 'set background black' block
    once, before the loop. The behaviour is identical, but the program
    has one extra block.
    """
    G = nx.MultiDiGraph(name='PDG_C')

    # Setup node OUTSIDE the loop
    G.add_node('n0', kind='SetBackground', seq=0, in_loop=False)

    # The rest is the canonical structure
    G.add_node('n1', kind='ClearDisplay',     seq=1, in_loop=True)
    G.add_node('n2', kind='TiltSensorRead',   seq=2, in_loop=True)
    G.add_node('n3', kind='Arithmetic',       seq=3, in_loop=True)
    G.add_node('n4', kind='Arithmetic',       seq=3, in_loop=True)
    G.add_node('n5', kind='PlotPoint',        seq=4, in_loop=True)
    G.add_node('n6', kind='EmitPitchedSound', seq=4, in_loop=True)
    G.add_node('n7', kind='Delay',            seq=5, in_loop=True)

    G.add_edge('n2', 'n3', type='data', var='v')
    G.add_edge('n2', 'n4', type='data', var='v')
    G.add_edge('n3', 'n5', type='data', var='c')
    G.add_edge('n4', 'n6', type='data', var='p')

    G.add_edge('n1', 'n5', type='side_effect', var='display')

    # NEW edge: background affects how plot point renders
    G.add_edge('n0', 'n5', type='side_effect', var='display')

    return G


# ---------- 2. Rendering ----------

COLORS = {
    'background': '#FBF6EB', 'ink': '#1A1612', 'ink_soft': '#4A3F33',
    'burgundy':   '#8B2418', 'ochre': '#B8843A', 'moss': '#5A6B3B',
    'paper':      '#FBF6EB',
}
NODE_STYLES = {
    'TiltSensorRead':   {'fillcolor': COLORS['ochre'], 'fontcolor': COLORS['paper']},
    'PlotPoint':        {'fillcolor': COLORS['moss'],  'fontcolor': COLORS['paper']},
    'EmitPitchedSound': {'fillcolor': COLORS['moss'],  'fontcolor': COLORS['paper']},
}
DEFAULT_NODE_STYLE = {'fillcolor': COLORS['paper'], 'fontcolor': COLORS['ink']}


def render_pdg(G: nx.MultiDiGraph, output_path: str) -> str:
    """Render a PDG to SVG, putting in_loop=False nodes outside the cluster."""
    dot = graphviz.Digraph(name=G.graph['name'])
    dot.attr(rankdir='TB', bgcolor=COLORS['background'],
             pad='0.3', nodesep='0.45', ranksep='0.55')
    dot.attr('node', shape='box', style='rounded,filled',
             fontname='JetBrains Mono', fontsize='11',
             color=COLORS['ink'], penwidth='1.5', margin='0.16,0.09')
    dot.attr('edge', fontname='JetBrains Mono', fontsize='10',
             color=COLORS['ink_soft'], penwidth='1.3',
             fontcolor=COLORS['burgundy'])

    # Nodes outside the loop (e.g. setup nodes)
    out_loop = [(n, a) for n, a in G.nodes(data=True) if not a.get('in_loop', True)]
    for node_id, attrs in out_loop:
        style = NODE_STYLES.get(attrs['kind'], DEFAULT_NODE_STYLE)
        label = f"{attrs['seq']}   {attrs['kind']}"
        dot.node(node_id, label=label, **style)

    # Loop cluster
    in_loop = [(n, a) for n, a in G.nodes(data=True) if a.get('in_loop', True)]
    with dot.subgraph(name='cluster_loop') as c:
        c.attr(
            label='<<b>loop</b><br/><font color="#8B2418" point-size="9">alcance de control</font>>',
            labeljust='l', labelloc='t',
            fontname='JetBrains Mono', fontsize='11',
            style='dashed,rounded', color=COLORS['burgundy'],
            penwidth='1.8', bgcolor=COLORS['paper'], margin='18'
        )
        for node_id, attrs in in_loop:
            style = NODE_STYLES.get(attrs['kind'], DEFAULT_NODE_STYLE)
            label = f"{attrs['seq']}   {attrs['kind']}"
            c.node(node_id, label=label, **style)

        # Same-rank grouping inside the loop
        by_seq = defaultdict(list)
        for n, a in in_loop:
            by_seq[a['seq']].append(n)
        for seq, nodes_at_seq in by_seq.items():
            if len(nodes_at_seq) > 1:
                with c.subgraph() as s:
                    s.attr(rank='same')
                    for n in nodes_at_seq:
                        s.node(n)

    # Edges (top level: edges can cross cluster boundaries)
    for u, v, edge_attrs in G.edges(data=True):
        if edge_attrs['type'] == 'data':
            dot.edge(u, v, label=f" {edge_attrs['var']} ",
                     color=COLORS['ink_soft'])
        elif edge_attrs['type'] == 'side_effect':
            dot.edge(u, v, label=f" {edge_attrs['var']} ",
                     color=COLORS['moss'], fontcolor=COLORS['moss'],
                     style='dashed', constraint='false')

    # Layout hint: keep Delay (or whatever is last) at the bottom
    max_seq = max(a['seq'] for _, a in G.nodes(data=True))
    last_nodes = [n for n, a in G.nodes(data=True) if a['seq'] == max_seq]
    penultimate = [n for n, a in G.nodes(data=True) if a['seq'] == max_seq - 1]
    for u in penultimate:
        for v in last_nodes:
            if u != v:
                dot.edge(u, v, style='invis')

    return dot.render(output_path, format='svg', cleanup=True)


# ---------- 3. Comparison ----------

def node_match(node_a, node_b):
    """Two nodes are compatible iff they have the same IR kind."""
    return node_a['kind'] == node_b['kind']


def _edge_signature(attrs):
    """Canonical signature of a single edge's attributes."""
    return (attrs['type'], attrs.get('var', ''))


def edge_match_multi(edges_a, edges_b):
    """
    For MultiDiGraphMatcher.is_isomorphic:
    edges_a / edges_b are dicts edge_key -> attr_dict
    (because there can be multiple edges between the same pair).
    """
    sig_a = sorted(_edge_signature(d) for d in edges_a.values())
    sig_b = sorted(_edge_signature(d) for d in edges_b.values())
    return sig_a == sig_b


def edge_match_single(attrs_a, attrs_b):
    """
    For nx.graph_edit_distance:
    attrs_a / attrs_b are single edge attribute dicts (one edge each).
    """
    return _edge_signature(attrs_a) == _edge_signature(attrs_b)


def compare_pdgs(G1: nx.MultiDiGraph, G2: nx.MultiDiGraph) -> dict:
    """Compare two PDGs and return a report dict."""
    # VF2 isomorphism (binary)
    matcher = isomorphism.MultiDiGraphMatcher(
        G1, G2, node_match=node_match, edge_match=edge_match_multi,
    )
    is_iso = matcher.is_isomorphic()

    # Graph Edit Distance (continuous, exact for small graphs)
    ged = nx.graph_edit_distance(
        G1, G2,
        node_match=node_match,
        edge_match=edge_match_single,
        timeout=10  # seconds, safety net for larger graphs
    )

    report = {
        'isomorphic':  is_iso,
        'graph_edit_distance': ged,
        'nodes_G1': G1.number_of_nodes(),
        'nodes_G2': G2.number_of_nodes(),
        'edges_G1': G1.number_of_edges(),
        'edges_G2': G2.number_of_edges(),
    }
    if is_iso:
        report['node_mapping'] = matcher.mapping
    return report


# ---------- Main ----------

if __name__ == '__main__':
    # Build both canonical PDGs (identical by construction)
    pdg_a = build_canonical_pdg('PDG_A')
    pdg_b = build_canonical_pdg('PDG_B')
    pdg_c = build_pdg_with_bg_setup()  # variant with bg setup

    # Render each one
    for G, path in [(pdg_a, '/home/claude/output/pdg_a_render'),
                    (pdg_b, '/home/claude/output/pdg_b_render'),
                    (pdg_c, '/home/claude/output/pdg_c_render')]:
        out = render_pdg(G, path)
        print(f"Rendered: {out}")

    # Compare A vs B (expected: isomorphic, GED=0)
    print("\n--- A vs B ---")
    result_ab = compare_pdgs(pdg_a, pdg_b)
    for k, v in result_ab.items():
        print(f"  {k}: {v}")

    # Compare A vs C (expected: not isomorphic, small GED)
    print("\n--- A vs C ---")
    result_ac = compare_pdgs(pdg_a, pdg_c)
    for k, v in result_ac.items():
        print(f"  {k}: {v}")

# Dependencias del sistema
$ sudo apt install graphviz       # o brew install graphviz en macOS

# Dependencias Python
$ pip install networkx graphviz

# Ejecución
$ python3 pdg_compare.py

Equivalencia experiencial entre dos plataformas tangibles

Contribuciones principales

• Una rúbrica de cinco dimensiones para evaluar la equivalencia experiencial entre plataformas tangibles comparables.
• Un protocolo de panel experto (selección, calibración, agregación de juicios) replicable en otros corpus.
• El concepto operativo de perfil de equivalencia bidimensional: equivalencia como par (algorítmica, experiencial), no como veredicto único.
• Un argumento sustantivo sobre por qué el hardware materializa decisiones pedagógicas implícitas, y por qué transferir currículos entre plataformas tangibles requiere atender ambas capas.

Venues posibles

Estos venues tienen una sensibilidad explícita para el tangible learning y la embodied interaction. La comunidad TEI en particular acepta naturalmente trabajos que problematizan la materialidad del aprendizaje —el ángulo central de este abstract.

Cómo los dos trabajos se sostienen mutuamente

Los dos trabajos forman una secuencia natural y no son un único trabajo dividido en dos —cada uno aborda una pregunta diferente, con métodos, comunidades de revisión y artefactos de validación distintos.

El primero asienta el suelo

El primer trabajo resuelve un problema metodológico bien delimitado: la equivalencia estructural entre programas a bloques en plataformas heterogéneas. Su contribución técnica es clara —el método humano-IA basado en ontología de mapeo + PDG + VF2 + GED, con una pipeline ejecutable reproducible. Su valor está en ser generalizable: cualquier comparación de programas educativos entre plataformas distintas puede usar el método, independientemente de qué sean materialmente las plataformas. Tangibles, virtuales, mixtas: el método responde a la pregunta estructural en todos los casos.

El segundo expone una limitación intencional del primero

Por construcción, el primer trabajo no dice nada sobre la dimensión experiencial. No es un descuido: es una limitación honesta del enfoque. Cuando se comparan dos plataformas con modalidades sensoriales idénticas —ambas tangibles, ambas con sensores integrados y displays físicos—, la pregunta «¿las experiencias son equivalentes?» se vuelve investigable empíricamente, porque existe un terreno común de comparación: los mismos gestos, el mismo tipo de retroalimentación, la misma categoría de objeto manipulado. Lo que cambia entre las dos plataformas son los detalles —sensibilidad, ergonomía, materialidad, estética— y justamente esos detalles pueden hacer una diferencia pedagógica importante.

La conexión narrativa

El primer abstract captura rigurosamente una dimensión de la equivalencia (la algorítmica). El segundo muestra que cuando las plataformas son conmensurables en términos materiales —ambas físicas, ambas con la misma categoría de affordances corporales—, la dimensión experiencial se vuelve medible con la misma seriedad metodológica que la primera. La pregunta «¿dos plataformas tangibles ofrecen la misma experiencia de aprendizaje?» no es una pregunta retórica: tiene respuesta posible, y este segundo trabajo propone un instrumento para responderla.

Juntos, los dos trabajos componen el argumento de que diseñar currículos transferibles entre dispositivos tangibles requiere un perfil de equivalencia bidimensional, no un veredicto único. Esta línea argumentativa es lo que justifica que sean dos trabajos separados, y no uno solo dividido artificialmente.

Una nota epistemológica importante

El marco del segundo abstract evita explícitamente pronunciarse sobre la equivalencia entre modalidades sensoriales distintas (tangible vs virtual, pantalla vs objeto físico). Existen trabajos en la literatura que intentan medir esta equivalencia trans-modal, pero el riesgo metodológico es alto: se termina midiendo el grado de sustituibilidad entre modalidades, que es una pregunta diferente —y probablemente mucho más difícil— que medir la equivalencia interna a una misma modalidad.

Concentrándose en tangible vs tangible, el segundo trabajo obtiene una pregunta bien planteada con un protocolo de evaluación factible. Evita el escollo de la conmensurabilidad trans-modal: ambas plataformas comparadas comparten ya la categoría de «artefacto físico con sensores y displays manipulable manualmente», y por tanto las cinco dimensiones de la rúbrica (gestualidad, retorno sensorial, ergonomía, materialidad, estética) son aplicables a ambas con el mismo sentido. Esta delimitación cuidadosa es parte de la contribución metodológica —y un punto explícito de discusión en la sección de limitaciones del manuscrito.

Una nota táctica sobre la publicación

Si la publicación del primer abstract precede temporalmente a la del segundo (recomendado), el segundo trabajo puede citar al primero como building block explícito en su sección de método. Esto refuerza la coherencia del programa de investigación y deja una huella clara de progresión —útil para una tesis donde los dos capítulos centrales son precisamente estos.

La situación inversa —publicar el segundo antes que el primero— es viable pero menos económica: el segundo trabajo tendría que recapitular el método algorítmico en su sección de métodos, lo cual aumenta la extensión del manuscrito y reduce el espacio disponible para la contribución original (la capa experiencial). La secuencia natural es: primero el método, después la extensión.

Lo que ambos trabajos comparten

El método central —ontología + PDG + VF2 + GED— es el núcleo técnico compartido. El primer trabajo lo presenta como contribución principal y lo valida con panel experto. El segundo trabajo lo asume como dado (citando al primero) y construye encima una rúbrica de evaluación experiencial.

Visto en conjunto, el programa de investigación responde a una pregunta más amplia que ningún trabajo individual puede atacar por sí solo: ¿qué significa, en términos operativos, decir que dos actividades educativas implementadas en plataformas distintas son equivalentes? La respuesta no es un veredicto único, es un perfil —y este programa propone tanto el método para construir el perfil como la rúbrica para interpretarlo.

Lo que este programa aporta

De la dimensión algorítmica (Parte I)

• Un protocolo reproducible de transcripción y normalización vía IR canónica de programas a bloques heterogéneos (Protobject ↔ micro:bit).
• Una pipeline ejecutable (NetworkX + Graphviz) que aplica isomorfismo VF2 y Graph Edit Distance para producir un perfil de equivalencia algorítmica entre pares de actividades.
• Un esquema de colaboración humano–IA: la ontología de mapeo se construye una vez (humano + LLM) y se reutiliza a lo largo de un curso entero.
• Una discusión sobre los límites de la equivalencia puramente estructural —que abre la dimensión experiencial.

De la dimensión experiencial (Parte II)

• Una rúbrica de cinco dimensiones (gestualidad, retorno sensorial, ergonomía, materialidad, estética) para plataformas tangibles comparables.
• El concepto operativo de perfil de equivalencia bidimensional: la equivalencia como par (algorítmica, experiencial), no como veredicto único.
• Un argumento sustantivo: el hardware materializa decisiones pedagógicas, y transferir currículos entre dispositivos tangibles exige atender ambas capas.

← volver al inicio del sitio  ·  ver la pipeline en acción →