Ejemplos donde sólo el uso de "mcr" no es correcto

En el tema anterior explicamos que con el algoritmo de McKay en aquellos grafos donde la primera hoja es la canónica ("f*") y las siguientes son todas iguales ("="), podábamos con automorfismos usando el campo "mcr" (MCR: minimum cell representative, representante mínimo de celda). Sin embargo cuando eso no sucede hay que usar otra técnica. Como ejemplo vemos el grafo de la Figura, un Steiner Triple System (STS-13) con 26 nodos, que puede importar en la aplicación con el JSON del archivo graph-sts-13.txt

Obtenemos el árbol de particiones con getPartitionTree() que ahora aplica otra técnica distinta con "fixMcr" que reconstruye el "mcr" como explicaremos en el siguiente apartado:

Time: 10 ms

Obtener árbol particiones (McKay): {
"useRefine":true,"orderRefine":"neighbors-desc-lengths-desc","targetCell":"max-length-first","typeCanon":"edges","useMcr":true,"useMcrPlus":false,"useMcrBreak":false,"typeIndicator":"none",
"timeTotal":10,"timeIni":1,"timeRef":6,
"iter":75,"refine":29,"indexTree":28,
"leaves":25,
"prunningMcr":43,"prunningMcrBreak":0,
"prunningIndicators":0,"prunningIndicators2":0,
"firstCanonicalPartition":[[0],[1],[18],[2],[11],[4],[17],[5],[6],[3],[15],[20],[13],[7],[16],[25],[21],[14],[22],[19],[12],[8],[24],[9],[10],[23]],
"firstCanon":false,
"canonicalPartition":[[0],[5],[25],[13],[20],[16],[3],[1],[2],[4],[15],[7],[17],[6],[18],[11],[19],[8],[9],[10],[22],[21],[14],[12],[23],[24]],
"firstCanonicalLabel":[[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[0,9],[0,10],[0,11],[0,12],[0,13],[0,14],[0,15],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7],[1,8],[1,9],[1,16],[1,17],[1,18],[1,19],[1,20],[1,21],[2,4],[2,6],[2,8],[2,9],[2,12],[2,13],[2,15],[2,18],[2,19],[2,20],[2,22],[2,23],[2,24],[3,5],[3,7],[3,8],[3,9],[3,10],[3,12],[3,14],[3,17],[3,19],[3,20],[3,22],[3,23],[3,25],[4,6],[4,8],[4,9],[4,10],[4,11],[4,14],[4,16],[4,17],[4,21],[4,22],[4,23],[4,24],[5,6],[5,7],[5,9],[5,11],[5,13],[5,15],[5,17],[5,20],[5,21],[5,22],[5,24],[5,25],[6,10],[6,11],[6,14],[6,15],[6,18],[6,19],[6,20],[6,21],[6,22],[6,25],[7,9],[7,11],[7,12],[7,14],[7,15],[7,16],[7,18],[7,19],[7,21],[7,23],[7,24],[8,12],[8,13],[8,14],[8,15],[8,16],[8,17],[8,20],[8,21],[8,23],[8,25],[9,10],[9,13],[9,16],[9,18],[9,22],[9,23],[9,24],[9,25],[10,11],[10,12],[10,13],[10,14],[10,16],[10,17],[10,18],[10,19],[10,22],[10,25],[11,13],[11,14],[11,15],[11,16],[11,17],[11,19],[11,20],[11,23],[11,24],[12,13],[12,14],[12,15],[12,17],[12,18],[12,19],[12,21],[12,22],[12,24],[13,15],[13,16],[13,17],[13,18],[13,20],[13,24],[13,25],[14,18],[14,20],[14,21],[14,23],[14,24],[14,25],[15,16],[15,19],[15,21],[15,22],[15,23],[15,25],[16,17],[16,18],[16,19],[16,21],[16,23],[16,25],[17,19],[17,20],[17,21],[17,22],[17,24],[18,19],[18,20],[18,21],[18,24],[18,25],[19,20],[19,22],[19,23],[20,23],[20,24],[20,25],[21,22],[21,24],[21,25],[22,23],[22,24],[22,25],[23,24],[23,25]],
"canonicalLabel":[[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[0,9],[0,10],[0,11],[0,12],[0,13],[0,14],[0,15],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7],[1,8],[1,9],[1,16],[1,17],[1,18],[1,19],[1,20],[1,21],[2,3],[2,4],[2,9],[2,11],[2,12],[2,13],[2,14],[2,16],[2,17],[2,18],[2,21],[2,24],[2,25],[3,5],[3,8],[3,10],[3,11],[3,13],[3,14],[3,16],[3,17],[3,19],[3,20],[3,22],[3,25],[4,5],[4,9],[4,10],[4,11],[4,12],[4,15],[4,16],[4,18],[4,19],[4,21],[4,22],[4,23],[5,8],[5,10],[5,12],[5,13],[5,15],[5,17],[5,18],[5,19],[5,20],[5,23],[5,24],[6,7],[6,8],[6,9],[6,10],[6,11],[6,14],[6,15],[6,18],[6,19],[6,20],[6,21],[6,24],[6,25],[7,8],[7,9],[7,12],[7,13],[7,14],[7,15],[7,16],[7,17],[7,20],[7,21],[7,22],[7,23],[8,9],[8,10],[8,13],[8,16],[8,18],[8,22],[8,23],[8,24],[8,25],[9,11],[9,12],[9,17],[9,19],[9,22],[9,23],[9,24],[9,25],[10,11],[10,12],[10,15],[10,16],[10,20],[10,21],[10,22],[10,24],[10,25],[11,13],[11,14],[11,19],[11,20],[11,21],[11,22],[11,23],[11,24],[12,14],[12,15],[12,16],[12,17],[12,20],[12,23],[12,24],[12,25],[13,14],[13,15],[13,17],[13,18],[13,21],[13,22],[13,23],[13,24],[14,15],[14,16],[14,18],[14,19],[14,20],[14,23],[14,25],[15,17],[15,18],[15,19],[15,21],[15,22],[15,25],[16,18],[16,20],[16,21],[16,22],[16,23],[16,25],[17,19],[17,20],[17,21],[17,22],[17,24],[17,25],[18,19],[18,21],[18,23],[18,24],[18,25],[19,20],[19,22],[19,23],[19,25],[20,21],[20,23],[20,24],[21,22],[21,24],[22,23],[22,25],[23,24],[24,25]],
"canonicalIndicator":null,
"nodes":
[[[-1,[],[],"PA","R4","PA","R5","PA","R6","PA","R7","PA","R8","PA","R9","PA","R10","PA","R11","PA","R12","PA","R13","PA","R14","PA","R15","PA","R16","PA","R17","PA","R18","PA","R19","PA","R20","PA","R21","PA","R22","PA","R23","PA","R24","PA","R25","PA"]],
[[0,[0],[],"PA","PA","PA","PA","PA","PA","PA","PA","PA"],[0,[1],[],"R2","R3","PA","PA","PA","PA","PA","PA","PA","PA","PA","PA","PA"],[0,[3],[],"R1","R2","R4","R5","R7","R9","R10","R11","R15","R18","R21","R22","R23","R24"]],
[[0,[0,1],[],"f"],[0,[0,2],[],">"],[0,[0,3],[],">"],[0,[0,4],[],"<"],[0,[0,5],[],">*"],[0,[0,6],[],"=(1 25 16)(2 18 20)(3 7 15)(4 13 11)(5 6 17)(9 12 19)(10 14 24)(21 23 22)"],[1,[1,0],[],"<"],[1,[1,2],[],"<"],[1,[1,3],[],"=(0 1 2)(3 4 5)(7 8 9)(11 12 13)(14 16 18)(15 17 19)(20 22 24)(21 23 25)"],[1,[1,6],[],"=(0 1 21 25 18 22 23 24 10 16 2 14 20)(3 8 9 13 12 15 4 11 5 6 19 7 17)"],[2,[3,0],[],"<"],[2,[3,1],[],"<"],[2,[3,2],[],"<"],[2,[3,4],[],"<"],[2,[3,5],[],"<"],[2,[3,7],[],"<"],[2,[3,9],[],"<"],[2,[3,10],[],"<"],[2,[3,11],[],"<"],[2,[3,15],[],"<"],[2,[3,18],[],"<"],[2,[3,21],[],"<"],[2,[3,22],[],"<"],[2,[3,23],[],"<"],[2,[3,24],[],"<"]]],
"nodeBest":[2,4],
"mcr":[0,3],
"fixMcr":
[[[0,8],[0,1,2,3,4,5,8,9,10,21]],
[[6,10],[0,3,6,7,10,11,14,15,20,21]],
[[],[0,3]]],
"lastEqual":false,"rebuiltMcr":38,"nonRebuiltMcr":24,
"tree":[{"index":0,"value":"(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25)","parent":-1},
{"index":1,"value":"(0)(1 2 3 4 5 6 7 11 13 15 16 17 18 20 25)(8 9 10 12 14 19 21 22 23 24)","parent":[{"index":0,"value":"０"}]},
{"index":2,"value":"(0)(1)(18)(2)(11)(4)(17)(5)(6)(3)(15)(20)(13)(7)(16)(25)(21)(14)(22)(19)(12)(8)(24)(9)(10)(23)","parent":[{"index":1,"value":"１"}]},
{"index":3,"value":"(0)(2)(13)(1)(16)(3)(15)(4)(6)(5)(25)(18)(20)(17)(11)(7)(19)(24)(12)(9)(14)(23)(8)(22)(10)(21)","parent":[{"index":1,"value":"２"}]},
{"index":4,"value":"(0)(3)(18)(15)(7)(11)(5)(4)(2)(1)(6)(17)(13)(20)(16)(25)(10)(21)(22)(24)(23)(9)(19)(12)(14)(8)","parent":[{"index":1,"value":"３"}]},
{"index":5,"value":"(0)(4)(20)(1)(25)(3)(7)(2)(17)(5)(13)(6)(11)(16)(18)(15)(8)(24)(10)(14)(12)(23)(19)(21)(9)(22)","parent":[{"index":1,"value":"４"}]},
{"index":6,"value":"(0)(5)(25)(13)(20)(16)(3)(1)(2)(4)(15)(7)(17)(6)(18)(11)(19)(8)(9)(10)(22)(21)(14)(12)(23)(24)","parent":[{"index":1,"value":"５"}]},
{"index":7,"value":"(0)(6)(16)(11)(2)(1)(7)(25)(18)(13)(3)(15)(5)(17)(20)(4)(9)(8)(12)(14)(21)(23)(24)(19)(22)(10)","parent":[{"index":1,"value":"６"}]},
{"index":8,"value":"(1)(0 2 3 4 5 6 8 11 12 14 17 18 19 21 22)(7 9 10 13 15 16 20 23 24 25)","parent":[{"index":0,"value":"１"}]},
{"index":9,"value":"(1)(0)(11)(2)(18)(4)(17)(5)(6)(3)(21)(14)(22)(19)(12)(8)(15)(20)(13)(7)(16)(25)(9)(24)(10)(23)","parent":[{"index":8,"value":"０"}]},
{"index":10,"value":"(1)(2)(14)(0)(12)(5)(19)(3)(6)(4)(17)(22)(11)(8)(18)(21)(23)(16)(24)(15)(13)(9)(20)(7)(10)(25)","parent":[{"index":8,"value":"２"}]},
{"index":11,"value":"(1)(3)(21)(11)(22)(18)(4)(2)(0)(5)(17)(8)(19)(6)(14)(12)(15)(9)(7)(10)(24)(23)(16)(13)(25)(20)","parent":[{"index":8,"value":"３"}]},
{"index":12,"value":"(1)(6)(18)(12)(0)(2)(8)(21)(14)(11)(4)(17)(3)(19)(22)(5)(7)(9)(13)(16)(23)(25)(20)(15)(24)(10)","parent":[{"index":8,"value":"６"}]},
{"index":13,"value":"(3)(0 1 2 4 5 7 9 10 11 15 18 21 22 23 24)(6 8 12 13 14 16 17 19 20 25)","parent":[{"index":0,"value":"３"}]},
{"index":14,"value":"(3)(0)(15)(7)(18)(11)(5)(4)(2)(1)(21)(10)(22)(24)(23)(9)(13)(6)(17)(20)(25)(16)(12)(19)(14)(8)","parent":[{"index":13,"value":"０"}]},
{"index":15,"value":"(3)(1)(21)(18)(11)(22)(4)(2)(0)(5)(7)(10)(9)(15)(23)(24)(6)(19)(8)(17)(12)(14)(13)(16)(20)(25)","parent":[{"index":13,"value":"１"}]},
{"index":16,"value":"(3)(2)(23)(0)(24)(5)(15)(1)(9)(4)(7)(22)(10)(18)(11)(21)(12)(6)(13)(14)(16)(19)(25)(17)(8)(20)","parent":[{"index":13,"value":"２"}]},
{"index":17,"value":"(3)(4)(23)(10)(7)(1)(24)(5)(0)(2)(9)(18)(15)(22)(21)(11)(14)(25)(12)(8)(17)(20)(6)(16)(13)(19)","parent":[{"index":13,"value":"４"}]},
{"index":18,"value":"(3)(5)(10)(21)(9)(22)(0)(4)(2)(1)(11)(23)(18)(7)(15)(24)(20)(8)(19)(16)(25)(13)(6)(14)(12)(17)","parent":[{"index":13,"value":"５"}]},
{"index":19,"value":"(3)(7)(0)(10)(4)(18)(21)(15)(23)(22)(5)(24)(1)(11)(9)(2)(20)(13)(12)(25)(14)(6)(8)(16)(17)(19)","parent":[{"index":13,"value":"７"}]},
{"index":20,"value":"(3)(9)(2)(21)(5)(18)(23)(11)(10)(24)(15)(22)(4)(1)(0)(7)(25)(16)(19)(6)(12)(20)(13)(14)(8)(17)","parent":[{"index":13,"value":"９"}]},
{"index":21,"value":"(3)(10)(4)(5)(22)(7)(11)(9)(24)(18)(0)(21)(1)(23)(2)(15)(8)(13)(12)(20)(16)(14)(19)(17)(25)(6)","parent":[{"index":13,"value":"１０"}]},
{"index":22,"value":"(3)(11)(21)(0)(15)(1)(10)(9)(24)(18)(7)(2)(22)(5)(4)(23)(20)(6)(17)(14)(16)(8)(13)(25)(19)(12)","parent":[{"index":13,"value":"１１"}]},
{"index":23,"value":"(3)(15)(24)(0)(11)(22)(2)(7)(21)(23)(4)(1)(9)(18)(10)(5)(16)(14)(17)(13)(19)(20)(8)(25)(6)(12)","parent":[{"index":13,"value":"１５"}]},
{"index":24,"value":"(3)(18)(0)(22)(7)(1)(9)(24)(10)(11)(5)(21)(15)(4)(2)(23)(13)(17)(6)(12)(19)(25)(8)(14)(20)(16)","parent":[{"index":13,"value":"１８"}]},
{"index":25,"value":"(3)(21)(9)(11)(1)(5)(7)(15)(23)(22)(10)(0)(18)(2)(24)(4)(6)(8)(19)(20)(14)(25)(17)(12)(16)(13)","parent":[{"index":13,"value":"２１"}]},
{"index":26,"value":"(3)(22)(10)(1)(5)(18)(15)(23)(21)(7)(11)(0)(4)(9)(24)(2)(8)(12)(13)(19)(17)(16)(6)(25)(20)(14)","parent":[{"index":13,"value":"２２"}]},
{"index":27,"value":"(3)(23)(24)(21)(2)(7)(9)(22)(4)(15)(11)(18)(0)(1)(5)(10)(17)(8)(6)(16)(25)(12)(14)(19)(13)(20)","parent":[{"index":13,"value":"２３"}]},
{"index":28,"value":"(3)(24)(2)(10)(23)(11)(4)(18)(15)(9)(5)(1)(21)(22)(7)(0)(19)(13)(8)(25)(14)(17)(16)(12)(6)(20)","parent":[{"index":13,"value":"２４"}]}],
"automorphisms":
[[[0],[1,25,16],[2,18,20],[3,7,15],[4,13,11],[5,6,17],[8],[9,12,19],[10,14,24],[21,23,22]],
[[0,1,2],[3,4,5],[6],[7,8,9],[10],[11,12,13],[14,16,18],[15,17,19],[20,22,24],[21,23,25]],
[[0,1,21,25,18,22,23,24,10,16,2,14,20],[3,8,9,13,12,15,4,11,5,6,19,7,17]]],
"automorphismsPlus":0}

A continuación vemos el árbol de particiones prescindiendo de los valores de los nodos pues son particiones demasiado grandes para presentar el árbol visualmente, aunque se incluyen los valores de las aristas que son los vértices que se fijan en cada nodo.

Extraemos el nivel de hojas del campo "nodes", donde observamos que la primera hoja canónica "f*" se le quitó el "*" y se encontró 3 siguientes mayores, pero al final quedó como mayor la tercera que marcamos con ">*". Las siguientes "=" lo son ahora en relación con está última ">*" y no con las anteriores, como sucedía con los ejemplos de apartados en el tema anterior. Observe que no encontró ninguna otra mayor.

[[0,[0,1],[],"f"],
[0,[0,2],[],">"],
[0,[0,3],[],">"],
[0,[0,4],[],"<"],
[0,[0,5],[],">*"],
[0,[0,6],[],"=(1 25 16)(2 18 20)(3 7 15)(4 13 11)(5 6 17)(9 12 19)(10 14 24)(21 23 22)"],
[1,[1,0],[],"<"],
[1,[1,2],[],"<"],
[1,[1,3],[],"=(0 1 2)(3 4 5)(7 8 9)(11 12 13)(14 16 18)(15 17 19)(20 22 24)(21 23 25)"],
[1,[1,6],[],"=(0 1 21 25 18 22 23 24 10 16 2 14 20)(3 8 9 13 12 15 4 11 5 6 19 7 17)"],
[2,[3,0],[],"<"],
[2,[3,1],[],"<"],
[2,[3,2],[],"<"],
[2,[3,4],[],"<"],
[2,[3,5],[],"<"],
[2,[3,7],[],"<"],
[2,[3,9],[],"<"],
[2,[3,10],[],"<"],
[2,[3,11],[],"<"],
[2,[3,15],[],"<"],
[2,[3,18],[],"<"],
[2,[3,21],[],"<"],
[2,[3,22],[],"<"],
[2,[3,23],[],"<"],
[2,[3,24],[],"<"]]]

Haciendo un test de isormorfismos iterando por todas las permutaciones en orden que pueda verificar en un máximo de tiempo de 60 segundos, vemos que pudo verificar satisfactoriamente 11638 permutaciones, todas ellas isomórficas:

Time: 61511 ms

Test isomorfismos (McKay): {"useRefine":true,"orderRefine":"neighbors-desc-lengths-desc","typeCanon":"edges","targetCell":"max-length-first","useMcr":true,"useMcrPlus":false,"useMcrBreak":false,"typeIndicator":"none",
"isomorphic":11638,"nonIsomorphic":0,
"firstTime":23,"minTime":2,"averageTime":5,"maxTime":23,
"iter1":75,"iter2":75,
"indexTree1":28,"indexTree2":26,
"minIndexTree":16,"maxIndexTree":84,
"refine1":29,"refine2":27,
"numAut1":3,"numAut2":2,"numAutPlus1":0,"numAutPlus2":0,
"prunningMcr1":43,"prunningMcr2":45,"prunningMcrBreak1":0,"prunningMcrBreak2":0,
"prunningIndicators1":0,"prunningIndicators2":0,
"prunningIndicators1b":0,"prunningIndicators2b":0,
"canonical":[[0,1],[0,2],[0,3], ...],
"warnings":["The graph has more than 9 nodes and only the first 9!=362880 permutations will be tested or less if the maximum time of 60 seconds is exceeded"]}

Si en el algoritmo getPartitionTree() usamos sólo "mcr" prescindiendo de la nueva técnica "fixMcr" y hacemos un test isomorfismos, vemos que iteró por las primeras 1170 permutaciones y en la 1171 encontró la primera no isomórfica, finalizando el test pues marcamos que finalice cuando esto suceda:

Time: 4913 ms

Test isomorfismos (McKay): {"useRefine":true,"orderRefine":"neighbors-desc-lengths-desc","typeCanon":"edges","targetCell":"max-length-first","useMcr":true,"useMcrPlus":false,"useMcrBreak":false,"typeIndicator":"none",
"isomorphic":1170,"nonIsomorphic":1,
"firstTime":6,"minTime":1,"averageTime":4,"maxTime":8,
"iter1":107,"iter2":91,
"indexTree1":21,"indexTree2":20,
"minIndexTree":12,"maxIndexTree":52,
"refine1":22,"refine2":21,
"numAut1":2,"numAut2":3,"numAutPlus1":0,"numAutPlus2":0,
"prunningMcr1":80,"prunningMcr2":66,"prunningMcrBreak1":0,"prunningMcrBreak2":0,
"prunningIndicators1":0,"prunningIndicators2":0,
"prunningIndicators1b":0,"prunningIndicators2b":0,
"canonical":[[0,1],[0,2],[0,3], ..., [4,9], [4,10], ...],
"warnings":["The graph has more than 9 nodes and only the first 9!=362880 permutations will be tested or less if the maximum time of 60 seconds is exceeded"],
"noCanonical":[[0,1],[0,2],[0,3], ..., [4,9], [4,11], ...]

Si dejamos que siga para completar todos los tests posibles en 60 segundos obtenemos "isomorphic":15273, "nonIsomorphic":1017 encontrando 15273 isomórficos y 1017 no isomórficos, lo que indica que el algoritmo es incorrecto pues todas las permutaciones de un grafo han de ser obligatoriamente isomórficas.

Así que cuando encontramos una nueva hoja distinta de "=" entonces no podemos usar sólo el campo "mcr" y habremos de usar el campo "fixMCr".

Antes de exponer esta técnica con más detalle, veamos lo que dice el documento de referencia [D1] que es el documento original del algoritmo de McKay, en su página 60 y primer párrafo de la 61 expone como podar con automorfismos cuando tenemos la primera partición canónica (que marcamos con "f*") y todas las demás son iguales "=", es decir, no se encuentran hojas que no sean reconocidas como equivalentes a esa primera. Usa el concepto de órbitas, pero creo que en el fondo es lo mismo que vimos para los ejemplos del tema anterior, donde la primera hoja "f*" era la canónica y todas las demás iguales "=". El resto de la página 61 se transcribe a continuación (donde cambiamos la letra griega "nu" ν por "nu" μ pues también usaremos la letra "uve" v que puede confundirse visualmente con la "nu" griega).

La técnica descrita a menudo nos permite retroceder hasta un ancestro μ de ς tras generar un único nodo terminal de un subárbol con raíz en un sucesor de μ. Desafortunadamente, esto no siempre es posible, por ejemplo, cuando un nuevo nodo terminal no se reconoce como equivalente a uno anterior. Para utilizar nuestros automorfismos en estos casos, hemos ideado el siguiente esquema.

En primer lugar, mantenemos un almacén Ψ que contiene (fix(γ), mcr(γ)) para cada automorfismo explícito γ descubierto hasta el momento (o un subconjunto de ellos). Luego, a cada nodo no terminal μ ∈ T(G, π) le asociamos un conjunto W(μ) ⊂ V. La primera vez que lo encontramos (si la hay) en la búsqueda de T(G, π), W(μ) se establece igual a la primera celda no trivial más pequeña de π_m, donde μ = [π₁, ..., π_m]. La siguiente vez que lo encontramos (si la hay), redefinimos W(μ):= W(μ) ∩ mcr(γ₁) ∩ ... ∩ mcr(γ_r), donde γ₁, ..., γ_r son los automorfismos explícitos encontrados previamente que fijan μ. A partir de entonces, podemos ignorar los subárboles T(G, π, μ(v)) para los cuales v ∉ W(μ).

Las razones para aplazar la modificación de W(μ) hasta el segundo encuentro con μ son: (1) que el subárbol enraizado en el sucesor más antiguo de μ debe examinarse de todos modos (ya que el elemento más pequeño de W(μ) antes de la modificación permanece en W(μ) después de la modificación) y (2) que a menudo no hay un segundo encuentro con μ (podemos encontrar un automorfismo que nos permita regresar a un ancestro de μ). El siguiente lema muestra que podemos determinar si γ fija μ observando fix(γ).

Sea μ = [π₁, ..., π_m] ∈ T(G, π) derivado de G, π y v₁, ..., v_m-1. Entonces γ fija μ si y solo si {v₁, ..., v_m-1} ⊆ fix(γ).

Identifiquemos las variables utilizadas:

• μ es un nodo del árbol.
• ς es la primera partición canónica que siempre se encuentra y que marcamos con "f*".
• γ es un automorfismo.
• π es una partición.
• T(G, π) es el árbol de particiones del grafo G que se inicia con la partición π.
• V es el conjunto de vértices del grafo.
• W(μ) es la celda objetivo del nodo μ.
• v es un vértice del grafo.
• T(G, π, μ(v)) es el subárbol que se inicia fijando el vértice v en el nodo μ.
• μ = [π₁, ..., π_m] significa que un nodo μ se forma con los vértices fijados anteriormente v₁, ..., v_m-1 y que tras fijar el vértice v_m da lugar a la sucesión de particiones π₁, ..., π_m.

Vea la importancia de la frase cuando un nuevo nodo terminal no se reconoce como equivalente a uno anterior que es lo que sucede cuando encontramos una hoja que no es igual "=" que la canónica anterior.

Lo que nosotros guardamos en el campo "mcr" son las intersecciones de los MCR mcr(γ₁) ∩ ... ∩ mcr(γ_r), de tal forma que cuando vayamos a fijar un vértice de la celda objetivo W(μ) hemos de observar que está en "mcr". Y esto es lo mismo que hacer W(μ):= W(μ) ∩ mcr(γ₁) ∩ ... ∩ mcr(γ_r) y fijar el vértice del W(μ) resultante.

El segundo párrafo del documento viene a decir que el primer vértice de la celda objetivo siempre se fija. Y es a partir de los siguientes cuando se filtran sólo si están en "mcr".

Pero lo más importante es observar que para obtener el "mcr" en este caso sólo usaremos los automorfismos γ que fijan el nodo μ, definiendo en el último párrafo que ello sucede si la secuencia de vértices fijados previamente en el nodo μ es v₁, ..., v_m-1 entonces estos vértices también deben ser fijados por γ, lo cual sucede si todos esos vértices están en el conjunto de celdas unitarias del automorfismo γ.

Para entender esto vemos como quedaron los campos "mcr" y "fixMcr" al final del algoritmo, tal como podemos observar en el árbol de particiones más arriba, donde se observa como se reconstruye el MCR en 38 ocasiones ("rebuiltMcr":38) y en 24 ("nonRebuiltMcr":24) se usa directamente el MCR previo resconstruido. Vemos como se forma "fixMcr" con el primer automorfismo encontrado:

"mcr":[0,3],
"fixMcr":
[[[0,8],[0,1,2,3,4,5,8,9,10,21]],
[[6,10],[0,3,6,7,10,11,14,15,20,21]],
[[],[0,3]]],
"lastEqual":false,
"rebuiltMcr":38,
"nonRebuiltMcr":24,

El primer campo "fixMcr" es [[0,8],[0,1,2,3,4,5,8,9,10,21]] donde [0,8] son los vértices fijados por el primer autormorfismo encontrado y [0,1,2,3,4,5,8,9,10,21] es el MCR (minimum cell representative) de ese automorfismo:

Primer automorfismo
(0)(1 25 16)(2 18 20)(3 7 15)(4 13 11)(5 6 17)(8)(9 12 19)(10 14 24)(21 23 22)

"fixMcr" = [[0,8],[0,1,2,3,4,5,8,9,10,21]]

Replicamos el campo "nodes" de las hojas terminales a partir de encontrar la hoja canónica ">*":

Terminal nodes                       "fixMcr"
---------------------------------------------------------------------------
...
[0,[0,5],[],">*"],
[0,[0,6],[],"="],                    [[0,8],[0,1,2,3,4,5,8,9,10,21]]
[1,[1,0],[],"<"],
[1,[1,2],[],"<"],
[1,[1,3],[],"="],                    [[6,10],[0,3,6,7,10,11,14,15,20,21]]
[1,[1,6],[],"="],                    [[],[0,3]]
[2,[3,0],[],"<"],
...
[2,[3,24],[],"<"]]

Recordemos la estructura de un nodo que ya hemos explicado, como el primero de los anteriores [0,[0,5],[],">*"], un Array donde tenemos en la primera posición el índice "0" del nodo padre en el nivel inmediatamente superior, el camino de vértices fijados por ese nodo en [0,5], un subarray vacío [] que se usa con poda con indicadores que veremos en temas posteriores y, finalmente, un marcado informativo como ">*" cuando se activa el trazado.

Vemos que luego encuentra una "=" con ese primer automorfismo, con lo que al volver al nodo raíz fijará el siguiente vértice 1 pues está en el MCR de "fixMcr" pues al pasar por un "=" sólo mira el mcr. Pero tras finalizar en la siguiente hoja en el camino fijado [1,0] encuentra un "<", con lo que para fijar el camino [1,2] debe considerar que 2 esté en [0,8] para aplicar el MCR del "fixMcr" anterior, que al no estar entonces no se poda esa rama. Continua con [1,3] y encuentra otro automorfismo con fix=[6,10] y luego otro con fix=[]. En este caso cuando el "fix" es vacío el MCR se aplica a todos los nodos que encuentre, pero como interseccionando los tres existentes es [0,3] igual que el último, entonces solo se fijará el vértice 3 (pues el 0 ya fue fijado previo), podándose el resto de ramas con vértice 2 y de 4 en adelante. Así el árbol finaliza explorando las ramas que se inician desde el vértice 3 e ignora el resto.

No sé si quedó bien explicado, pero en un siguiente apartado reconstruyendo MCR con "fixMcr" veremos otros ejemplos de grafos con menos nodos y quizás más ilustrativos.

En la Figura vemos otro grafo donde hay que aplicar "fixMcr". Se trata de HAD-20, Hadamard de 80 vértices y 840 aristas que puede importar en la aplicación usando el JSON del archivo graph-had-20.txt

Realizando tests con permutaciones en orden, al menos las 142 primeras permutaciones que pudo hacer en 60 segundos resultaron isomórficas:

Time: 61177 ms

Test isomorfismos (McKay): {"useRefine":true,"orderRefine":"neighbors-desc-lengths-desc","typeCanon":"edges","targetCell":"max-length-first","useMcr":true,"useMcrPlus":false,"useMcrBreak":true,"typeIndicator":"none",
"isomorphic":142,"nonIsomorphic":0,
"firstTime":442,"minTime":71,"averageTime":426,"maxTime":1087,
"iter1":1081,"iter2":2696,
"indexTree1":823,"indexTree2":2043,
"minIndexTree":140,"maxIndexTree":2078,
"refine1":824,"refine2":2044,
"numAut1":11,"numAut2":41,"numAutPlus1":0,"numAutPlus2":0,
"prunningMcr1":75,"prunningMcr2":211,"prunningMcrBreak1":21,"prunningMcrBreak2":33,
"prunningIndicators1":0,"prunningIndicators2":0,
"prunningIndicators1b":0,"prunningIndicators2b":0,
"canonical":[[0,59],[0,60],[0,61],[0,62],[0,63],[0,64],[0,65],[0,66],[0,67],[0,68],[0,69],[0,70],[0,71],[0,72],[0,73],[0,74],[0,75],[0,76],[0,77],[0,78],[0,79],[1,38],[1,39],[1,40],[1,41],[1,42],[1,43],[1,44],[1,45],[1,46],[1,47],[1,48],[1,59],[1,60],[1,61],[1,62],[1,63],[1,64],[1,65],[1,66],[1,67],[1,68],[2,37],[2,39],[2,40],[2,41],[2,42],[2,43],[2,49],[2,50],[2,51],[2,52],[2,53],[2,59],[2,60],[2,61],[2,62],[2,63],[2,69],[2,70],[2,71],[2,72],[2,73],[3,26],[3,39],[3,40],[3,44],[3,45],[3,48],[3,49],[3,50],[3,51],[3,54],[3,55],[3,59],[3,60],[3,63],[3,67],[3,68],[3,69],[3,70],[3,74],[3,75],[3,78],[4,24],[4,39],[4,41],[4,44],[4,47],[4,48],[4,49],[4,51],[4,52],[4,56],[4,57],[4,61],[4,62],[4,63],[4,65],[4,68],[4,70],[4,71],[4,74],[4,76],[4,78],[5,23],[5,40],[5,42],[5,46],[5,47],[5,48],[5,50],[5,51],[5,52],[5,54],[5,57],[5,60],[5,61],[5,63],[5,66],[5,68],[5,71],[5,72],[5,75],[5,77],[5,78],[6,25],[6,41],[6,42],[6,45],[6,46],[6,48],[6,49],[6,50],[6,52],[6,55],[6,56],[6,59],[6,62],[6,63],[6,64],[6,68],[6,69],[6,72],[6,76],[6,77],[6,78],[7,20],[7,40],[7,41],[7,45],[7,46],[7,48],[7,49],[7,51],[7,53],[7,57],[7,58],[7,60],[7,61],[7,62],[7,65],[7,67],[7,69],[7,72],[7,74],[7,77],[7,78],[8,19],[8,39],[8,42],[8,44],[8,46],[8,48],[8,51],[8,52],[8,53],[8,55],[8,58],[8,59],[8,60],[8,62],[8,65],[8,66],[8,69],[8,71],[8,75],[8,76],[8,78],[9,22],[9,41],[9,42],[9,44],[9,47],[9,48],[9,49],[9,50],[9,53],[9,54],[9,58],[9,59],[9,60],[9,61],[9,64],[9,67],[9,70],[9,71],[9,76],[9,77],[9,78],[10,21],[10,39],[10,40],[10,45],[10,47],[10,48],[10,50],[10,52],[10,53],[10,56],[10,58],[10,59],[10,61],[10,62],[10,64],[10,66],[10,70],[10,72],[10,74],[10,75],[10,78],[11,28],[11,39],[11,42],[11,45],[11,46],[11,47],[11,49],[11,51],[11,53],[11,54],[11,56],[11,59],[11,61],[11,63],[11,65],[11,67],[11,72],[11,73],[11,75],[11,76],[11,78],[12,27],[12,39],[12,41],[12,44],[12,45],[12,46],[12,50],[12,52],[12,53],[12,54],[12,57],[12,60],[12,61],[12,63],[12,64],[12,66],[12,69],[12,73],[12,74],[12,76],[12,78],[13,29],[13,40],[13,41],[13,44],[13,46],[13,47],[13,50],[13,51],[13,53],[13,55],[13,56],[13,59],[13,62],[13,63],[13,66],[13,67],[13,71],[13,73],[13,74],[13,77],[13,78],[14,30],[14,40],[14,42],[14,44],[14,45],[14,47],[14,49],[14,52],[14,53],[14,55],[14,57],[14,60],[14,62],[14,63],[14,64],[14,65],[14,70],[14,73],[14,75],[14,77],[14,78],[15,34],[15,42],[15,43],[15,44],[15,45],[15,48],[15,50],[15,51],[15,53],[15,56],[15,57],[15,61],[15,62],[15,63],[15,66],[15,67],[15,69],[15,70],[15,75],[15,76],[15,77],[16,33],[16,41],[16,43],[16,45],[16,47],[16,48],[16,51],[16,52],[16,53],[16,54],[16,55],[16,59],[16,60],[16,63],[16,65],[16,66],[16,70],[16,72],[16,74],[16,76],[16,77],[17,32],[17,40],[17,43],[17,44],[17,46],[17,48],[17,49],[17,52],[17,53],[17,54],[17,56],[17,59],[17,61],[17,63],[17,64],[17,65],[17,69],[17,71],[17,74],[17,75],[17,77],[18,31],[18,39],[18,43],[18,46],[18,47],[18,48],[18,49],[18,50],[18,53],[18,55],[18,57],[18,60],[18,62],[18,63],[18,64],[18,67],[18,71],[18,72],[18,74],[18,75],[18,76],[19,40],[19,41],[19,43],[19,45],[19,47],[19,49],[19,50],[19,54],[19,56],[19,57],[19,61],[19,63],[19,64],[19,67],[19,68],[19,70],[19,72],[19,73],[19,74],[19,77],[20,39],[20,42],[20,43],[20,44],[20,47],[20,50],[20,52],[20,54],[20,55],[20,56],[20,59],[20,63],[20,64],[20,66],[20,68],[20,70],[20,71],[20,73],[20,75],[20,76],[21,41],[21,42],[21,43],[21,44],[21,46],[21,49],[21,51],[21,54],[21,55],[21,57],[21,60],[21,63],[21,65],[21,67],[21,68],[21,69],[21,71],[21,73],[21,76],[21,77],[22,39],[22,40],[22,43],[22,45],[22,46],[22,51],[22,52],[22,55],[22,56],[22,57],[22,62],[22,63],[22,65],[22,66],[22,68],[22,69],[22,72],[22,73],[22,74],[22,75],[23,39],[23,41],[23,43],[23,44],[23,45],[23,49],[23,53],[23,55],[23,56],[23,58],[23,59],[23,62],[23,64],[23,65],[23,67],[23,69],[23,70],[23,73],[23,74],[23,76],[24,40],[24,42],[24,43],[24,45],[24,46],[24,50],[24,53],[24,54],[24,55],[24,58],[24,59],[24,60],[24,64],[24,66],[24,67],[24,69],[24,72],[24,73],[24,75],[24,77],[25,39],[25,40],[25,43],[25,44],[25,47],[25,51],[25,53],[25,54],[25,57],[25,58],[25,60],[25,61],[25,65],[25,66],[25,67],[25,70],[25,71],[25,73],[25,74],[25,75],[26,41],[26,42],[26,43],[26,46],[26,47],[26,52],[26,53],[26,56],[26,57],[26,58],[26,61],[26,62],[26,64],[26,65],[26,66],[26,71],[26,72],[26,73],[26,76],[26,77],[27,40],[27,42],[27,43],[27,47],[27,48],[27,49],[27,51],[27,55],[27,56],[27,58],[27,59],[27,62],[27,65],[27,67],[27,68],[27,70],[27,71],[27,72],[27,75],[27,77],[28,40],[28,41],[28,43],[28,44],[28,48],[28,50],[28,52],[28,55],[28,57],[28,58],[28,60],[28,62],[28,64],[28,66],[28,68],[28,69],[28,70],[28,71],[28,74],[28,77],[29,39],[29,42],[29,43],[29,45],[29,48],[29,49],[29,52],[29,54],[29,57],[29,58],[29,60],[29,61],[29,64],[29,65],[29,68],[29,69],[29,70],[29,72],[29,75],[29,76],[30,39],[30,41],[30,43],[30,46],[30,48],[30,50],[30,51],[30,54],[30,56],[30,58],[30,59],[30,61],[30,66],[30,67],[30,68],[30,69],[30,71],[30,72],[30,74],[30,76],[31,40],[31,41],[31,42],[31,44],[31,45],[31,51],[31,52],[31,54],[31,56],[31,58],[31,59],[31,61],[31,65],[31,66],[31,68],[31,69],[31,70],[31,73],[31,77],[31,78],[32,39],[32,41],[32,42],[32,45],[32,47],[32,50],[32,51],[32,55],[32,57],[32,58],[32,60],[32,62],[32,66],[32,67],[32,68],[32,70],[32,72],[32,73],[32,76],[32,78],[33,39],[33,40],[33,42],[33,44],[33,46],[33,49],[33,50],[33,56],[33,57],[33,58],[33,61],[33,62],[33,64],[33,67],[33,68],[33,69],[33,71],[33,73],[33,75],[33,78],[34,39],[34,40],[34,41],[34,46],[34,47],[34,49],[34,52],[34,54],[34,55],[34,58],[34,59],[34,60],[34,64],[34,65],[34,68],[34,71],[34,72],[34,73],[34,74],[34,78],[35,36],[35,43],[35,44],[35,45],[35,46],[35,47],[35,49],[35,50],[35,51],[35,52],[35,58],[35,59],[35,60],[35,61],[35,62],[35,68],[35,73],[35,74],[35,75],[35,76],[35,77],[36,39],[36,40],[36,41],[36,42],[36,48],[36,53],[36,54],[36,55],[36,56],[36,57],[36,63],[36,64],[36,65],[36,66],[36,67],[36,69],[36,70],[36,71],[36,72],[36,78],[37,44],[37,45],[37,46],[37,47],[37,48],[37,54],[37,55],[37,56],[37,57],[37,58],[37,64],[37,65],[37,66],[37,67],[37,68],[37,74],[37,75],[37,76],[37,77],[37,78],[38,49],[38,50],[38,51],[38,52],[38,53],[38,54],[38,55],[38,56],[38,57],[38,58],[38,69],[38,70],[38,71],[38,72],[38,73],[38,74],[38,75],[38,76],[38,77],[38,78],[39,77],[39,79],[40,76],[40,79],[41,75],[41,79],[42,74],[42,79],[43,78],[43,79],[44,72],[44,79],[45,71],[45,79],[46,70],[46,79],[47,69],[47,79],[48,73],[48,79],[49,66],[49,79],[50,65],[50,79],[51,64],[51,79],[52,67],[52,79],[53,68],[53,79],[54,62],[54,79],[55,61],[55,79],[56,60],[56,79],[57,59],[57,79],[58,63],[58,79]],
"warnings":["The graph has more than 9 nodes and only the first 9!=362880 permutations will be tested or less if the maximum time of 60 seconds is exceeded"]}

En estos casos es preferible usar tests aleatorios, pues pudiera ser que al tomar permutaciones en orden, las primeras resulten isomórficas. Con 100 test aleatorios o todos los que pueda ejecutar en 60 segundos, vemos que completó todos los 65 tests que pudo realizar resultando isomórficos:

Time: 60327 ms

Test isomorfismos (McKay): {"useRefine":true,"orderRefine":"neighbors-desc-lengths-desc","typeCanon":"edges","targetCell":"max-length-first","useMcr":true,"useMcrPlus":false,"useMcrBreak":true,"typeIndicator":"none",
"isomorphic":65,"nonIsomorphic":0,
"firstTime":607,"minTime":341,"averageTime":913,"maxTime":2176,
"iter1":1081,"iter2":3522,
"indexTree1":823,"indexTree2":2822,
"minIndexTree":402,"maxIndexTree":2987,
"refine1":824,"refine2":2823,
"numAut1":11,"numAut2":33,"numAutPlus1":0,"numAutPlus2":0,
"prunningMcr1":75,"prunningMcr2":102,"prunningMcrBreak1":21,"prunningMcrBreak2":31,
"prunningIndicators1":0,"prunningIndicators2":0,

El árbol generado tiene 823 nodos de los cuales hay 641 hojas, encontrando el cánonico ">*" en las primeras hojas y el resto son algunas iguales y la mayor parte menores, con lo que se reconstruye el MCR en 663 ocasiones y no se reconstruye en 36.

[[0,[0,2,4,6],[],"f"],
[0,[0,2,4,17],[],"<"],
...
[2,[0,2,6,20],[],">*"],
[2,[0,2,6,22],[],"<"],
...
[4,[0,2,8,10],[],"="],
[4,[0,2,8,13],[],"<"],
...
[9,[0,2,18,36],[],"="],
[10,[0,3,4,12],[],"<"],
...
[14,[0,4,2,14],[],"="],
[15,[0,4,3,8],[],"<"],
...

Si prescindimos de "fixMcr" y solo usamos "mcr", ejecutando 100 tests aleatorios, vemos que 84 resultan isomórficos y 16 no isomórficos, algo que nos confirma que no podemos prescindir de la técnica "fixMcr":

Time: 14377 ms

Test isomorfismos (McKay): {"useRefine":true,"orderRefine":"neighbors-desc-lengths-desc","typeCanon":"edges","targetCell":"max-length-first","useMcr":true,"useMcrPlus":false,"useMcrBreak":true,"typeIndicator":"none",
"isomorphic":84,"nonIsomorphic":16,
"firstTime":106,"minTime":42,"averageTime":140,"maxTime":311,
"iter1":374,"iter2":314,
"indexTree1":154,"indexTree2":132,
"minIndexTree":52,"maxIndexTree":405,
"refine1":155,"refine2":133,
"numAut1":3,"numAut2":2,"numAutPlus1":0,"numAutPlus2":0,
"prunningMcr1":142,"prunningMcr2":117,"prunningMcrBreak1":69,"prunningMcrBreak2":58,
"prunningIndicators1":0,"prunningIndicators2":0,
"prunningIndicators1b":0,"prunningIndicators2b":0,

Reconstruyendo MCR con "fixMcr"

Vamos a intentar explicar la técnica "fixMcr" usando un grafo con menos nodos. Como decíamos, si llegamos a alguna hoja que no sea "=" al volver de esa hoja reconstruirá el MCR usando "fixMcr" y el primer subarray del nodo [indexParent, [], []]. Para observarlo veamos el grafo de ejemplo de la Figura que puede verse en el documento de referencia [D3] y que puede importar en la aplicación con este JSON en el archivo graph-sample-4b.txt

En la traza siguiente vemos "rebuiltMcr": 1, "nonRebuiltMcr": 5 con lo que tuvo que reconstruir el MCR en un caso.

Time: 1 ms

Obtener árbol particiones (McKay): {
"useRefine":true,"orderRefine":"neighbors-desc-lengths-desc","targetCell":"max-length-first","typeCanon":"edges","useMcr":true,"useMcrPlus":false,"useMcrBreak":false,"typeIndicator":"none",
"timeTotal":1,"timeIni":0,"timeRef":1,
"iter":14,"refine":9,"indexTree":8,
"leaves":7,
"prunningMcr":4,"prunningMcrBreak":0,
"prunningIndicators":0,"prunningIndicators2":0,
"firstCanonicalPartition":[[0],[7],[3],[6],[2],[9],[5],[1],[8],[4]],
"firstCanon":false,
"canonicalPartition":[[1],[5],[6],[7],[4],[9],[8],[3],[2],[0]],
"firstCanonicalLabel":[[0,7],[0,8],[0,9],[1,6],[1,8],[1,9],[2,4],[2,7],[2,8],[3,5],[3,6],[3,9],[4,5],[4,7],[5,6]],
"canonicalLabel":[[0,7],[0,8],[0,9],[1,2],[1,3],[1,5],[2,4],[2,5],[3,4],[3,6],[4,9],[5,8],[6,7],[6,9],[7,8]],
"canonicalIndicator":null,
"nodes":
[[[-1,[],[],"R5","PA","PA","PA","PA"]],
[[0,[0],[],"f"],[0,[1],[],">*"],[0,[2],[]],[0,[3],[],"=(0 8)(1 3)(4 7)(5 6)"],[0,[4],[],"<"],[0,[5],[],"=(0 7)(1 5)(2 9)(3 6)(4 8)"]],
[[2,[2,5],[],"<"],[2,[2,6],[],"<"]]],
"nodeBest":[1,1],
"mcr":[0,1,2,4],
"fixMcr":
[[[2,9],[0,1,2,4,5,9]],
[[],[0,1,2,3,4]]],
"lastEqual":true,"rebuiltMcr":1,"nonRebuiltMcr":5,
"tree":[{"index":0,"value":"(0 1 2 3 4 5 6 7 8 9)","parent":-1},
{"index":1,"value":"(0)(7)(3)(6)(2)(9)(5)(1)(8)(4)","parent":[{"index":0,"value":"０"}]},
{"index":2,"value":"(1)(5)(6)(7)(4)(9)(8)(3)(2)(0)","parent":[{"index":0,"value":"１"}]},
{"index":3,"value":"(2)(5 6)(0 8)(4 7)(1 3)(9)","parent":[{"index":0,"value":"２"}]},
{"index":4,"value":"(2)(5)(6)(0)(8)(7)(4)(3)(1)(9)","parent":[{"index":3,"value":"５"}]},
{"index":5,"value":"(2)(6)(5)(8)(0)(4)(7)(1)(3)(9)","parent":[{"index":3,"value":"６"}]},
{"index":6,"value":"(3)(6)(5)(4)(7)(9)(0)(1)(2)(8)","parent":[{"index":0,"value":"３"}]},
{"index":7,"value":"(4)(8)(5)(1)(9)(2)(3)(6)(7)(0)","parent":[{"index":0,"value":"４"}]},
{"index":8,"value":"(5)(1)(3)(0)(8)(2)(4)(6)(9)(7)","parent":[{"index":0,"value":"５"}]}],
"automorphisms":
[[[0,8],[1,3],[2],[4,7],[5,6],[9]],
[[0,7],[1,5],[2,9],[3,6],[4,8]]],
"automorphismsPlus":0}

El árbol obtenido en la Figura es similar al de documento de referencia, donde expone sólo las 3 primeras ramas que dan lugar a las 4 primeras hojas.

El test de isomorfimos verifica que al menos las 9! = 362880 primeras permutaciones del grafo son isomórficas, pues el grafo tiene 10 nodos y se limita a un máximo de 9! permutaciones.

Time: 51529 ms

Test isomorfismos (McKay): {"useRefine":true,"orderRefine":"neighbors-desc-lengths-desc","typeCanon":"edges","targetCell":"max-length-first","useMcr":true,"useMcrPlus":false,"useMcrBreak":false,"typeIndicator":"none",
"isomorphic":362880,"nonIsomorphic":0,
"firstTime":0,"minTime":0,"averageTime":0,"maxTime":1,
"iter1":14,"iter2":14,
"indexTree1":8,"indexTree2":7,
"minIndexTree":6,"maxIndexTree":10,
"refine1":9,"refine2":8,
"numAut1":2,"numAut2":2,"numAutPlus1":0,"numAutPlus2":0,
"prunningMcr1":4,"prunningMcr2":5,"prunningMcrBreak1":0,"prunningMcrBreak2":0,
"prunningIndicators1":0,"prunningIndicators2":0,
"prunningIndicators1b":0,"prunningIndicators2b":0,
"canonical":[[0,7],[0,8],[0,9],[1,2],[1,3],[1,5],[2,4],[2,5],[3,4],[3,6],[4,9],[5,8],[6,7],[6,9],[7,8]],
"warnings":["The graph has more than 9 nodes and only the first 9!=362880 permutations will be tested or less if the maximum time of 60 seconds is exceeded"]}

Si ejecutamos todos los tests aleatorios posibles que pueda realizar en 60 segundos, vemos a continuación que pudo verificar 60000 permutaciones resultando todas isomórficas. Este número 60000 tests surge de una estimación que el algoritmo testIsomorphisms() realiza con la primera ejecución del árbol de particiones, observando en "firstTime":1 que le ocupó 1 ms, con lo que dividiendo 60 segundos entre 1 test cada milisegundo resulta que estima que podrá ejecutar 60000 tests en 60 segundos. Pero de hecho los ejecuta en menos tiempo 16556 ms, puesto que muchos tests ocupan menos de 1 ms. Vea que el tiempo promedio "averageTime":0, entendiendo 0 como algo mayor que 0 pero menor que 1 ms, pues JavaScript no registra períodos de tiempo inferiores a 1 ms.

Time: 16556 ms

Test isomorfismos (McKay): {"useRefine":true,"orderRefine":"neighbors-desc-lengths-desc","typeCanon":"edges","targetCell":"max-length-first","useMcr":true,"useMcrPlus":false,"useMcrBreak":false,"typeIndicator":"none",
"isomorphic":60000,"nonIsomorphic":0,
"firstTime":1,"minTime":0,"averageTime":0,"maxTime":6,
"iter1":14,"iter2":14,
"indexTree1":8,"indexTree2":8,
"minIndexTree":6,"maxIndexTree":13,
"refine1":9,"refine2":9,
"numAut1":2,"numAut2":2,"numAutPlus1":0,"numAutPlus2":0,
"prunningMcr1":4,"prunningMcr2":4,"prunningMcrBreak1":0,"prunningMcrBreak2":0,
"prunningIndicators1":0,"prunningIndicators2":0,
"prunningIndicators1b":0,"prunningIndicators2b":0,
"canonical":[[0,7],[0,8],[0,9],[1,2],[1,3],[1,5],[2,4],[2,5],[3,4],[3,6],[4,9],[5,8],[6,7],[6,9],[7,8]]}

A continuación mostramos el árbol de particiones que se almacena en el campo "nodes", incluyendo las particiones:

Nivel  Nodos                                       Particiones
---------------------------------------------------------------------------------
0      [-1,[],[],"R5","PA","PA","PA","PA"]         (0 1 2 3 4 5 6 7 8 9)
1          [[0,[0],[],"f"]                         (0)(7)(3)(6)(2)(9)(5)(1)(8)(4)
1          [0,[1],[],">*"]                         (1)(5)(6)(7)(4)(9)(8)(3)(2)(0)
1          [0,[2],[]]                              (2)(5 6)(0 8)(4 7)(1 3)(9)
2              [2,[2,5],[],"<"]                    (2)(5)(6)(0)(8)(7)(4)(3)(1)(9)
2              [2,[2,6],[],"<"]                    (2)(6)(5)(8)(0)(4)(7)(1)(3)(9)
1          [0,[3],[],"=(0 8)(1 3)(4 7)(5 6)"]      (3)(6)(5)(4)(7)(9)(0)(1)(2)(8)
1          [0,[4],[],"<"]                          (4)(8)(5)(1)(9)(2)(3)(6)(7)(0)
1          [0,[5],[],"=(0 7)(1 5)(2 9)(3 6)(4 8)"] (5)(1)(3)(0)(8)(2)(4)(6)(9)(7)

"mcr":[0,1,2,4],
"fixMcr":
[[[2,9],[0,1,2,4,5,9]],
[[],[0,1,2,3,4]]],
"lastEqual":true,
"rebuiltMcr":1,
"nonRebuiltMcr":5,

Empezamos con la partición (0 1 2 3 4 5 6 7 8 9) fijando el primer vértice 0 de donde resulta la primera partición canónica (0)(7)(3)(6)(2)(9)(5)(1)(8)(4) que se marca con "f*". Recordemos que siempre se fija el primer vértice de cada celda objetivo. Inicialmente "mcr" es nulo, lo que nos permite fijar el segundo vértice 1.

Al fijar ese vértice 1 obtenemos la segunda hoja (1)(5)(6)(7)(4)(9)(8)(3)(2)(0) cuyo etiquetado canónico resulta mayor, con lo que marcamos esta con ">*" y le quitamos el "*" a la primera quedando como "f". Aun "mcr" es nulo pues necesitamos una segunda hoja que resulte "=" para obtener el autormorfismo y de ahí obtener "mcr".

Al fijar el siguiente vértice 2 se producen dos hojas que resultan menores "<". Al fijar el vértice 3 encontramos la primera igual "=" que la canónica, que era la segunda hoja, momento en el que descubre el automorfismo (0 8)(1 3)(2)(4 7)(5 6)(9), de donde resulta "mcr"=[0,1,2,4,5,9], que son los primeros vértices de cada celda incluyendo las unitarias que se suelen omitir pero están implícitas, lo que nos permitiría en principio podar los vértices 6, 7 y 8 del nodo raíz que faltan por fijar. Sin embargo al fijar el vértice 4, que vemos que está en "mcr", encuentra una hoja menor "<" con lo que habremos de reconstruir el mcr.

Cuando encontramos el primer automorfismo (0 8)(1 3)(2)(4 7)(5 6)(9) guardamos también "fixMcr" = [[[2,9],[0,1,2,4,5,9]]], donde el primer subarray [2, 9] son las celdas unitarias de ese automorfismo, vértices que fijan el automorfismo. El segundo subarray es el MCR del automorfismo. Entonces tras encontrar la hoja que fijaba el vértice 4 con la marca "<" pasamos a fijar el resto de vértices 5, 6, 7, 8 y 9. El nodo raíz es [-1,[],[]] donde el primer subarray es la lista de vértices que resultan fijados para ese nodo, ninguno por ser el primero. Así {} ⊂ {2, 9} es verdadero pues el conjunto vacío está contenido en cualquier otro conjunto, con lo que el mcr [0,1,2,4,5,9] de "fixMcr" pasa a ser el "mcr" y fijará ese vértice 5, que al final encuentra la hoja (5)(1)(3)(0)(8)(2)(4)(6)(9)(7) resultando "=" al compararla con la canónica (la segunda hoja) y encontrando el nuevo automorfismo (0 7)(1 5)(2 9)(3 6)(4 8), lo que genera en "fixMr" la nueva entrada [[],[0,1,2,3,4]], donde el primer subarray fix = [] que fija el automorfismo es vacío pues no hay ninguna celda unitaria en el autormorfismo. Con esto resulta que para el nodo raíz al verificar {} ⊂ {} resulta verdadero con lo que tenemos este esquema de reconstrucción del MCR al intentar fijar el resto de los vértices 6, 7, 8 y 9:

                                       Path        Path
"fixMcr"                MCR            root        automorphism      Se incluye
---------------------------------------------------------------------------------
[[2,9],[0,1,2,4,5,9]]   {0,1,2,4,5,9}   {}    ⊂   {2, 9}  = true    {0,1,2,4,5,9}
[[],[0,1,2,3,4]]        {0,1,2,3,4}     {}    ⊂   {}      = true    {0,1,2,3,4}

mcr = {0,1,2,4,5,9} ⋂ {0,1,2,3,4} = {0,1,2,4}

Se observa que 6, 7, 8 y 9 no están en el MCR reconstruido [0,1,2,4] así que resultan ramas podadas.

En la traza del nodo raíz vemos [[[-1,[],[],"R5","PA","PA","PA","PA"]], donde se observan las anotaciones "R5" que significa que se reconstruyó el MCR tras fijar el vértice 5. Y luego cuatro "PA" que son las podas con automorfismos de los vértices 6, 7, 8 y 9.

A continuación vemos el resultado en Wolfram Cloud:

g = AdjacencyGraph[{{0,1,0,0,1,0,0,0,1,0},{1,0,1,1,0,0,0,0,0,0},{0,1,0,1,0,0,0,0,0,1},{0,1,1,0,0,0,0,0,1,0},{1,0,0,0,0,0,1,1,0,0},{0,0,0,0,0,0,1,1,0,1},{0,0,0,0,1,1,0,0,0,1},
{0,0,0,0,1,1,0,0,1,0},{1,0,0,1,0,0,0,1,0,0},{0,0,1,0,0,1,1,0,0,0}}, ImageSize -> 275, VertexSize -> {"Scaled", 0.11}, VertexLabels -> {1 -> Placed[0,Center], 2 -> Placed[1,Center], 
3 -> Placed[2,Center], 4 -> Placed[3,Center], 5 -> Placed[4,Center], 6 -> Placed[5,Center], 7 -> Placed[6,Center], 8 -> Placed[7,Center], 9 -> Placed[8,Center], 10 -> Placed[9,Center]}, 
VertexLabelStyle -> Directive[Black,17.5], EdgeLabelStyle -> Directive[Black,17.5,Bold], VertexStyle -> White, EdgeStyle -> {{Black,Thickness[0.005]}}];
h = CanonicalGraph[g,Method->"Nauty"]
Normal[AdjacencyMatrix[h]]
EdgeList[h]
GraphAutomorphismGroup[g]
GroupElements[%]

PermutationGroup[{
Cycles[{{1,5},{2,7},{3,10},{4,6},{8,9}}],
Cycles[{{1,8},{2,6},{3,10},{4,7},{5,9}}]}]

"automorphisms":
[[[0,8],[1,3],[2],[4,7],[5,6],[9]],
[[0,7],[1,5],[2,9],[3,6],[4,8]]]

Vemos que no se obtiene el mismo conjunto generador de automorfismos, pues sólo coincide los dos segundos, pero si coinciden el grupo de automorfismos del grafo que se obtiene con GroupElements[%] en Wolfram y con refinamiento y sin podas en nuestra aplicación, teniendo en cuenta que nosotros omitimos la identidad y que los índices se inician en 0.

GroupElements[%] in Wolfram                 "automorphisms" with only refinement
----------------------------------------------------------------------------------
{Cycles[{}],
Cycles[{{1,5},{2,7},{3,10},{4,6},{8,9}}],   [[0,4],[1,6],[2,9],[3,5],[7,8]]
Cycles[{{1,8},{2,6},{3,10},{4,7},{5,9}}],   [[0,7],[1,5],[2,9],[3,6],[4,8]]
Cycles[{{1,9},{2,4},{5,8},{6,7}}]}          [[[0,8],[1,3],[2],[4,7],[5,6],[9]]

En la Figura vemos otro grafo en el que tendremos que reconstruir el MCR, ejemplo del documento de referencia [D8] que puede importar en la aplicación con el JSON del archivo graph-sample-7.tx.

Se observa en la traza siguiente la anotación "rebuiltMcr": 7, "nonRebuiltMcr": 15 donde tuvo que reconstruir el MCR en 7 ocasiones.

Time: 1 ms

Obtener árbol particiones (McKay): {
"useRefine":true,"orderRefine":"neighbors-asc","targetCell":"first","typeCanon":"edges","useMcr":true,"useMcrPlus":false,"useMcrBreak":false,"typeIndicator":"none",
"timeTotal":1,"timeIni":1,"timeRef":0,
"iter":49,"refine":13,"indexTree":18,
"leaves":6,
"prunningMcr":18,"prunningMcrBreak":0,
"prunningIndicators":0,"prunningIndicators2":0,
"firstCanonicalPartition":[[0],[3],[6],[4],[5],[1],[2]],
"firstCanon":false,
"canonicalPartition":[[3],[0],[1],[2],[6],[4],[5]],
"firstCanonicalLabel":[[0,5],[0,6],[1,3],[1,4],[2,3],[2,4],[5,6]],
"canonicalLabel":[[0,5],[0,6],[1,2],[1,3],[2,3],[4,5],[4,6]],
"canonicalIndicator":null,
"nodes":
[[[-1,[],[],"PA","R4","PA","R5","PA","R6","PA"]],
[[0,[0],[],"PA","PA"],[0,[1],[],"PA","PA","PA"],[0,[3],[],"R1","PA","R2","PA"]],
[[0,[0,3],[]],[0,[0,4],[],"PA"],[1,[1,3],[],"PA"],[2,[3,0],[],"R2","PA"]],
[[0,[0,3,4],[]],[0,[0,3,5],[],"PA"],[1,[0,4,3],[],"PA"],[2,[1,3,4],[],"PA"],[3,[3,0,1],[],"R5","PA"]],
[[0,[0,3,4,1],[],"f"],[0,[0,3,4,2],[],"=(1 2)"],[1,[0,3,5,1],[],"=(4 5)"],[2,[0,4,3,1],[],"=(3 4)(5 6)"],[3,[1,3,4,0],[],"=(0 1)"],[4,[3,0,1,4],[],">*"]]],
"nodeBest":[4,5],
"mcr":[0,3],
"fixMcr":
[[[0,3,4,5,6],[0,1,3,4,5,6]],
[[0,1,2,3,6],[0,1,2,3,4,6]],
[[0,1,2],[0,1,2,3,5]],
[[2,3,4,5,6],[0,2,3,4,5,6]]],
"lastEqual":false,"rebuiltMcr":7,"nonRebuiltMcr":15,
"tree":[{"index":0,"value":"(0 1 2 3 4 5 6)","parent":-1},
{"index":1,"value":"(0)(3 4 5 6)(1 2)","parent":[{"index":0,"value":"０"}]},
{"index":2,"value":"(0)(3)(6)(4 5)(1 2)","parent":[{"index":1,"value":"３"}]},
{"index":3,"value":"(0)(3)(6)(4)(5)(1 2)","parent":[{"index":2,"value":"４"}]},
{"index":4,"value":"(0)(3)(6)(4)(5)(1)(2)","parent":[{"index":3,"value":"１"}]},
{"index":5,"value":"(0)(3)(6)(4)(5)(2)(1)","parent":[{"index":3,"value":"２"}]},
{"index":6,"value":"(0)(3)(6)(5)(4)(1 2)","parent":[{"index":2,"value":"５"}]},
{"index":7,"value":"(0)(3)(6)(5)(4)(1)(2)","parent":[{"index":6,"value":"１"}]},
{"index":8,"value":"(0)(4)(5)(3 6)(1 2)","parent":[{"index":1,"value":"４"}]},
{"index":9,"value":"(0)(4)(5)(3)(6)(1 2)","parent":[{"index":8,"value":"３"}]},
{"index":10,"value":"(0)(4)(5)(3)(6)(1)(2)","parent":[{"index":9,"value":"１"}]},
{"index":11,"value":"(1)(3 4 5 6)(0 2)","parent":[{"index":0,"value":"１"}]},
{"index":12,"value":"(1)(3)(6)(4 5)(0 2)","parent":[{"index":11,"value":"３"}]},
{"index":13,"value":"(1)(3)(6)(4)(5)(0 2)","parent":[{"index":12,"value":"４"}]},
{"index":14,"value":"(1)(3)(6)(4)(5)(0)(2)","parent":[{"index":13,"value":"０"}]},
{"index":15,"value":"(3)(0 1 2)(6)(4 5)","parent":[{"index":0,"value":"３"}]},
{"index":16,"value":"(3)(0)(1 2)(6)(4 5)","parent":[{"index":15,"value":"０"}]},
{"index":17,"value":"(3)(0)(1)(2)(6)(4 5)","parent":[{"index":16,"value":"１"}]},
{"index":18,"value":"(3)(0)(1)(2)(6)(4)(5)","parent":[{"index":17,"value":"４"}]}],
"automorphisms":
[[[0],[1,2],[3],[4],[5],[6]],
[[0],[1],[2],[3],[4,5],[6]],
[[0],[1],[2],[3,4],[5,6]],
[[0,1],[2],[3],[4],[5],[6]]],
"automorphismsPlus":0}

Este es el árbol de particiones, con las mismas ramas que la del documento de referencia:

Con todas las 7! = 5040 permutaciones del grafo inicial vemos que resultan isomorficas.

Time: 672 ms

Test isomorfismos (McKay): {"useRefine":true,"orderRefine":"neighbors-asc","typeCanon":"edges","targetCell":"first","useMcr":true,"useMcrPlus":false,"useMcrBreak":false,"typeIndicator":"none",
"isomorphic":5040,"nonIsomorphic":0,
"firstTime":1,"minTime":0,"averageTime":0,"maxTime":1,
"iter1":49,"iter2":49,
"indexTree1":18,"indexTree2":18,
"minIndexTree":18,"maxIndexTree":30,
"refine1":13,"refine2":13,
"numAut1":4,"numAut2":4,"numAutPlus1":0,"numAutPlus2":0,
"prunningMcr1":18,"prunningMcr2":18,"prunningMcrBreak1":0,"prunningMcrBreak2":0,
"prunningIndicators1":0,"prunningIndicators2":0,
"prunningIndicators1b":0,"prunningIndicators2b":0,
"canonical":[[0,5],[0,6],[1,2],[1,3],[2,3],[4,5],[4,6]]}

[[0,[0,3,4,1],[],"f"],
[0,[0,3,4,2],[],"=(1 2)"],
[1,[0,3,5,1],[],"=(4 5)"],
[2,[0,4,3,1],[],"=(3 4)(5 6)"],
[3,[1,3,4,0],[],"=(0 1)"],
[4,[3,0,1,4],[],">*"]]]

Observando las 6 hojas del campo "nodes" vemos que la hoja de la última rama que empieza fijando el 3 es la que resulta mayor. Y que de la partición raíz (0 1 2 3 4 5 6) se podan las ramas con vértices 2, 4, 5 y 6.

"nodeBest":[4,5],
"mcr":[0,3],
"fixMcr":
[[[0,3,4,5,6],[0,1,3,4,5,6]],
[[0,1,2,3,6],[0,1,2,3,4,6]],
[[0,1,2],[0,1,2,3,5]],
[[2,3,4,5,6],[0,2,3,4,5,6]]],

También observamos que los MCR de los tres primeros "fixMcr" seguidos se interseccionan para producir "mcr":[0,1,3], con lo que no incluye 2 en el nodo raíz con lo que se poda esa rama. Y después se intersecciona con el cuarto MCR de "fixMcr" que produce "mcr":[0,3] que no contiene 4, 5 y 6 podándose esas ramas también.

A continuación vemos el resultado en Wolfram Cloud:

g = AdjacencyGraph[{{0,1,1,0,0,0,0},{1,0,1,0,0,0,0},{1,1,0,0,0,0,0},{0,0,0,0,1,1,0},{0,0,0,1,0,0,1},{0,0,0,1,0,0,1},{0,0,0,0,1,1,0}}, ImageSize -> 138, 
VertexSize -> {"Scaled", 0.23}, VertexLabels -> {1 -> Placed[0,Center], 2 -> Placed[1,Center], 3 -> Placed[2,Center], 4 -> Placed[3,Center], 5 -> Placed[4,Center], 
6 -> Placed[5,Center], 7 -> Placed[6,Center]}, VertexLabelStyle -> Directive[Black,17.5], EdgeLabelStyle -> Directive[Black,17.5,Bold], VertexStyle -> White, 
EdgeStyle -> {{Black,Thickness[0.005]}}];
h = CanonicalGraph[g,Method->"Nauty"]
Normal[AdjacencyMatrix[h]]
EdgeList[h]
GraphAutomorphismGroup[g]
GroupElements[%]

PermutationGroup[{
Cycles[{{2,3}}],
Cycles[{{5,6}}],
Cycles[{{4,5},{6,7}}],
Cycles[{{1,2}}]}]

"automorphisms":
[[[0],[1,2],[3],[4],[5],[6]],
[[0],[1],[2],[3],[4,5],[6]],
[[0],[1],[2],[3,4],[5,6]],
[[0,1],[2],[3],[4],[5],[6]]]

En este caso se obtiene el mismo conjunto generador de automorfismos.

En la Figura vemos un grafo del documento de referencia [D9] que puede importar en la aplicación con el JSON del archivo graph-sample-8.txt

Como vemos en la traza siguiente, se reconstruye el MCR en 5 ocasiones.

Time: 1 ms

Obtener árbol particiones (McKay): {
"useRefine":true,"orderRefine":"neighbors-asc","targetCell":"last","typeCanon":"edges","useMcr":true,"useMcrPlus":false,"useMcrBreak":true,"typeIndicator":"none",
"timeTotal":1,"timeIni":0,"timeRef":1,
"iter":39,"refine":17,"indexTree":17,
"leaves":7,
"prunningMcr":11,"prunningMcrBreak":2,
"prunningIndicators":0,"prunningIndicators2":0,
"firstCanonicalPartition":[[0],[5],[6],[2],[4],[7],[1],[3]],
"firstCanon":false,
"canonicalPartition":[[1],[5],[6],[7],[3],[0],[2],[4]],
"firstCanonicalLabel":[[0,5],[0,6],[0,7],[1,2],[1,4],[1,5],[2,3],[2,5],[3,6],[3,7],[4,6],[4,7]],
"canonicalLabel":[[0,5],[0,6],[0,7],[1,2],[1,3],[1,7],[2,3],[2,6],[3,5],[4,5],[4,6],[4,7]],
"canonicalIndicator":null,
"nodes":
[[[-1,[],[],"PA","PA","R6","PA","PA1"]],
[[0,[0],[]],[0,[1],[],"R2","PA"],[0,[3],[],"PA","PA1"],[0,[5],[],"R7","PA"]],
[[0,[0,1],[]],[0,[0,3],[],"PA"],[1,[1,0],[],"R4","PA"],[1,[1,2],[],"PA"],[2,[3,0],[],"PA"],[3,[5,6],[],"R3","PA"]],
[[0,[0,1,2],[],"f"],[0,[0,1,4],[],"=(2 4)(5 6)"],[1,[0,3,2],[],"=(1 3)"],[2,[1,0,2],[],">*"],[3,[1,2,0],[],"=(0 2)(6 7)"],[4,[3,0,2],[],"=(1 3)"],[5,[5,6,1],[],"<"]]],
"nodeBest":[3,3],
"mcr":[0,1,5],
"fixMcr":
[[[0,1,3,7],[0,1,2,3,5,7]],
[[0,2,4,5,6,7],[0,1,2,4,5,6,7]],
[[1,3,4,5],[0,1,3,4,5,6]],
[[0,2,4,5,6,7],[0,1,2,4,5,6,7]]],
"lastEqual":false,"rebuiltMcr":5,"nonRebuiltMcr":11,
"tree":[{"index":0,"value":"(0 1 2 3 4 5 6 7)","parent":-1},
{"index":1,"value":"(0)(5 6)(2 4)(7)(1 3)","parent":[{"index":0,"value":"０"}]},
{"index":2,"value":"(0)(5 6)(2 4)(7)(1)(3)","parent":[{"index":1,"value":"１"}]},
{"index":3,"value":"(0)(5)(6)(2)(4)(7)(1)(3)","parent":[{"index":2,"value":"２"}]},
{"index":4,"value":"(0)(6)(5)(4)(2)(7)(1)(3)","parent":[{"index":2,"value":"４"}]},
{"index":5,"value":"(0)(5 6)(2 4)(7)(3)(1)","parent":[{"index":1,"value":"３"}]},
{"index":6,"value":"(0)(5)(6)(2)(4)(7)(3)(1)","parent":[{"index":5,"value":"２"}]},
{"index":7,"value":"(1)(5 6 7)(3)(0 2 4)","parent":[{"index":0,"value":"１"}]},
{"index":8,"value":"(1)(5 6)(7)(3)(0)(2 4)","parent":[{"index":7,"value":"０"}]},
{"index":9,"value":"(1)(5)(6)(7)(3)(0)(2)(4)","parent":[{"index":8,"value":"２"}]},
{"index":10,"value":"(1)(5 7)(6)(3)(2)(0 4)","parent":[{"index":7,"value":"２"}]},
{"index":11,"value":"(1)(5)(7)(6)(3)(2)(0)(4)","parent":[{"index":10,"value":"０"}]},
{"index":12,"value":"(3)(5 6 7)(1)(0 2 4)","parent":[{"index":0,"value":"３"}]},
{"index":13,"value":"(3)(5 6)(7)(1)(0)(2 4)","parent":[{"index":12,"value":"０"}]},
{"index":14,"value":"(3)(5)(6)(7)(1)(0)(2)(4)","parent":[{"index":13,"value":"２"}]},
{"index":15,"value":"(5)(0 2)(1 3)(4)(6 7)","parent":[{"index":0,"value":"５"}]},
{"index":16,"value":"(5)(0)(2)(1 3)(4)(6)(7)","parent":[{"index":15,"value":"６"}]},
{"index":17,"value":"(5)(0)(2)(1)(3)(4)(6)(7)","parent":[{"index":16,"value":"１"}]}],
"automorphisms":
[[[0],[1],[2,4],[3],[5,6],[7]],
[[0],[1,3],[2],[4],[5],[6],[7]],
[[0,2],[1],[3],[4],[5],[6,7]],
[[0],[1,3],[2],[4],[5],[6],[7]]],
"automorphismsPlus":0}

El test de isomorfismos completa todas los 8! = 40320 permutaciones del grafo resultando isomórficas.

Time: 6126 ms

Test isomorfismos (McKay): {"useRefine":true,"orderRefine":"neighbors-asc","typeCanon":"edges","targetCell":"last","useMcr":true,"useMcrPlus":false,"useMcrBreak":true,"typeIndicator":"none",
"isomorphic":40320,"nonIsomorphic":0,
"firstTime":1,"minTime":0,"averageTime":0,"maxTime":6,
"iter1":39,"iter2":41,
"indexTree1":17,"indexTree2":19,
"minIndexTree":14,"maxIndexTree":23,
"refine1":17,"refine2":18,
"numAut1":4,"numAut2":3,"numAutPlus1":0,"numAutPlus2":0,
"prunningMcr1":11,"prunningMcr2":10,"prunningMcrBreak1":2,"prunningMcrBreak2":2,
"prunningIndicators1":0,"prunningIndicators2":0,
"prunningIndicators1b":0,"prunningIndicators2b":0,
"canonical":[[0,5],[0,6],[0,7],[1,2],[1,3],[1,7],[2,3],[2,6],[3,5],[4,5],[4,6],[4,7]]}

El árbol de particiones tiene un nodo más que el del documento de referencia, pues nosotros fijamos en el nodo raíz los vértices 0, 1, 3, 5 y en ese documento se fijan 0, 1, 2, 5 siendo la rama que fija el 2 con dos nodos en el documento y nuestra rama que fija el 3 tiene tres nodos. Esto es por la forma en que se ordenan las particiones, pero al final ambos algoritmos determinan que la misma hoja canónica es la cuarta, encontrando los mismos automorfismos, aunque no en el mismo orden.

[[0,[0,1,2],[],"f"],
[0,[0,1,4],[],"=(2 4)(5 6)"],
[1,[0,3,2],[],"=(1 3)"],
[2,[1,0,2],[],">*"],
[3,[1,2,0],[],"=(0 2)(6 7)"],
[4,[3,0,2],[],"=(1 3)"],
[5,[5,6,1],[],"<"]]],

Vemos que la mejor hoja es la cuarta y que la peor es la última, lo que coincide con el documento de referencia. Encuentra los mismos automorfismos aunque en distinto orden. Observe que el automorfismo (1 3) se encuentra al comparar la tercera hoja con la primera que en ese momento era la canónica "f*". Y luego vuelve a encontrar el mismo (1 3) en la sexta hoja al compararla con la nueva canónica ">*" en la cuarta hoja.

"mcr":[0,1,5],
"fixMcr":
[[[0,1,3,7],[0,1,2,3,5,7]],
[[0,2,4,5,6,7],[0,1,2,4,5,6,7]],
[[1,3,4,5],[0,1,3,4,5,6]],
[[0,2,4,5,6,7],[0,1,2,4,5,6,7]]],
"lastEqual":false,
"rebuiltMcr":5,
"nonRebuiltMcr":11,

En el nodo raíz se podan las ramas que fijan los vértices 2, 4, 6 y 7. Observe que se reconstruye el MCR en 5 ocasiones, que son las que marcamos con "R" seguido del vértice que se está considerando fijar en ese momento, como vemos a continuación con el campo "nodes" de los nodos que no son terminales y puestos en posición de árbol vertical, donde también poda la última rama inferior derecha que intenta fijar el vértice 3 de la celda (1 3).

[[[-1,[],[],"PA","PA","R6","PA","PA1"]],
    [[0,[0],[]],
        [[0,[0,1],[]],
        [0,[0,3],[],"PA"],
    [0,[1],[],"R2","PA"],
        [1,[1,0],[],"R4","PA"],
        [1,[1,2],[],"PA"],
    [0,[3],[],"PA","PA1"],
        [2,[3,0],[],"PA"],
    [0,[5],[],"R7","PA"]],
        [3,[5,6],[],"R3","PA"]]

A continuación vemos el resultado en Wolfram Cloud:

g = AdjacencyGraph[{{0,1,0,1,0,0,0,1},{1,0,1,0,1,0,0,0},{0,1,0,1,0,0,1,0},{1,0,1,0,1,0,0,0},{0,1,0,1,0,1,0,0},{0,0,0,0,1,0,1,1},{0,0,1,0,0,1,0,1},{1,0,0,0,0,1,1,0}}, 
ImageSize -> 263, VertexSize -> {"Scaled", 0.12}, VertexLabels -> {1 -> Placed[0,Center], 2 -> Placed[1,Center], 3 -> Placed[2,Center], 4 -> Placed[3,Center], 5 -> Placed[4,Center], 
6 -> Placed[5,Center], 7 -> Placed[6,Center], 8 -> Placed[7,Center]}, VertexLabelStyle -> Directive[Black,17.5], EdgeLabelStyle -> Directive[Black,17.5,Bold], VertexStyle -> White, 
EdgeStyle -> {{Black,Thickness[0.005]}}];
h = CanonicalGraph[g,Method->"Nauty"]
Normal[AdjacencyMatrix[h]]
EdgeList[h]
GraphAutomorphismGroup[g]
GroupElements[%]

El conjunto generador de nuestra aplicación devuelve uno más que Wolfram, que viene a ser el último que es una repetición del segundo:

"automorphisms"                     PermutationGroup[g]
--------------------------------------------------------------
[[[0],[1],[2,4],[3],[5,6],[7]],     Cycles[{{3,5},{6,7}}]
[[0],[1,3],[2],[4],[5],[6],[7]],    Cycles[{{2,4}}]
[[0,2],[1],[3],[4],[5],[6,7]],      Cycles[{{1,3},{7,8}}]}]
[[0],[1,3],[2],[4],[5],[6],[7]]]

Con solo refinamiento obtenemos los mismos automorfismos, aunque en nuestra aplicación se repiten los 3 finales con los 3 primeros:

"automorphisms"                        GroupElements[%]
-----------------------------------------------------------------
                                       Cycles[{}]
[[[0],[1,3],[2],[4],[5],[6],[7]],      Cycles[{{2,4}}]
[[0],[1],[2,4],[3],[5,6],[7]],         Cycles[{{3,5},{6,7}}]
[[0],[1,3],[2,4],[5,6],[7]],           Cycles[{{2,4},{3,5},{6,7}}]
[[0,2],[1],[3],[4],[5],[6,7]],         Cycles[{{1,3},{7,8}}]
[[0,4,2],[1],[3],[5,6,7]],             Cycles[{{1,5,3},{6,7,8}}]
[[0,2,4],[1],[3],[5,7,6]],             Cycles[{{1,3,5},{6,8,7}}]
[[0,4],[1],[2],[3],[5,7],[6]],         Cycles[{{1,5},{6,8}}]
[[0,2],[1,3],[4],[5],[6,7]],           Cycles[{{1,3},{2,4},{7,8}}]
[[0,4,2],[1,3],[5,6,7]],               Cycles[{{1,5,3},{2,4},{6,7,8}}]
[[0,2,4],[1,3],[5,7,6]],               Cycles[{{1,3,5},{2,4},{6,8,7}}]
[[0,4],[1,3],[2],[5,7],[6]]],          Cycles[{{1,5},{2,4},{6,8}}]
[[0],[1,3],[2],[4],[5],[6],[7]],
[[0],[1],[2,4],[3],[5,6],[7]],
[[0],[1,3],[2,4],[5,6],[7]],

Verificando la corrección del algoritmo en la poda con automorfismos

En los ejemplos de grafos vistos hemos venido ejecutando el test de isomorfismos con testIsomorphisms() para verificar la corrección del algoritmo getPartitionTree() que obtiene el árbol de particiones y el etiquetado canónico. Esos ejemplos provienen de los documentos de referencia que muchas veces también nos presentaban el árbol de particiones, lo que permitía visualmente verificar la corrección. Para tener una mayor certeza de que el algoritmo es correcto vamos a realizar más verificaciones.

Usaremos el documento de referencia [D5], que es la página web nauty and Traces de Brendan McKay y Adolfo Piperno, donde en la sección de Graphs podemos encontrar una lista de grafos duros para probar. He probado con 35 familias grafos, tomando un grafo de cierto tamaño en cada familia, no siempre los más pequeños, a los que hemos aplicado el test isomorfismos con 100 permutaciones aleatorias y limitadas a un tiempo máximo de 60 segundos. También hay en esa web grafos muy grandes, tanto que no se pueden importar en la aplicación pues se colapsa el navegador, recordando que primero hay que importar el grafo con su correspondiente traslado al grafo en SVG en pantalla, para luego ejecutar los algoritmos.

En las siguientes tablas se reflejan los resultados del árbol de particiones del grafo inicial, indicando en la última columna los tests realizados, resultando siempre todos isomórficos y no encontrando ninguno donde esto no se verifique. Hemos aplicado refinamiento y solo poda automorfismos, con estos argumentos:

"useRefine":true,
"orderRefine":"neighbors-desc-lengths-desc",
"targetCell":"max-length-first",
"useMcr":true,
"useMcrPlus":false,
"useMcrBreak":false,
"typeIndicator":"none"

Con objeto de reducir los tiempos de ejecución esos valores podrían ser otros y en muchos casos aplicar la poda con indicadores que veremos en un tema posterior. Pero ahora más que mirar la eficiencia lo que interesa es verificar la corrección del algoritmo. Sin embargo hay dos excepciones donde aplicamos otros valores para obtener un resultado en un tiempo inferior, que vemos a continuación. Por ejemplo, el último kef10 no sale en un tiempo razonable si no se aplica la poda con indicadores.

mz-aug-10 (*) "targetCell":"min-length-first"
kef10 (**) targetCell":"max-length-last", "typeIndicator":"lengths"

Se trata de verificar con 100 tests con permutaciones aleatorias limitando toda la prueba a 60 segundos, por eso por ejemplo con el primer grafo latin-sw-10-1 solo pudo realizar 6 tests en ese tiempo. Volvemos a recordar que todos los tests resultaron isomórficos y en ningún caso encontramos alguno no isomórfico.

En esta primera tabla agrupamos los grafos que no tienen automorfismos, a excepción del trivial por supuesto. Así que toda la poda del árbol se basa en el refinamiento. Observe como los cuatro últimos tiene un árbol con solo 2 nodos, con lo que al aplicar el refinamiento inicial ya obtenemos una hoja, con lo que no entra en el recursivo y por tanto no hay más hojas. Puede ver un ejemplo en un tema anterior generando también un árbol con 2 nodos.

En esta tabla están los que se podan con automorfismos (podas que se indican en Prunning MCR) pero no se reconstruye el MCR, recordando que en estos grafos la primera hoja es la partición canónica "f*" y el resto son todas "=".

Y por último los que necesitan reconstruir el MCR, indicándose las veces que se reconstruye en Rebuilt MCR: