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

Vimos en un tema anterior el apartado para verificar la corrección del algoritmo que obtiene el árbol de particiones usando sólo la poda con automorfismos, para lo que usamos el algoritmo testIsomorphisms() como se observa en la Figura. Recordemos que este algoritmo nos permite verificar que la obtención del etiquetadocanónico es correcta. Se trata de obtener el etiquetado canónico del grafo y luego permutarlo aleatoriamente tantas veces como especifique el campo número de tests, aunque limitado con el campo tiempo total tests (segundos), pues cuando se supere ese tiempo finalizará devolviendo los resultados alcanzados. Con cada permutación del grafo se obtiene su etiquetado canónico y se comprueba que sea igual que el del grafo original.

En esas pruebas agrupábamos los grafos en tres grupos: los que no tenían automorfismos y, por tanto, no se podaban por este concepto y el resto los separábamos según reconstruyeran el MCR. He comprobado que sólo algunos de los que reconstruyen el MCR también son impactados por la poda con indicadores.

En los tests usamos las mismas opciones para todos los grafos:

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

A excepción de estos dos grafos:

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

En la siguiente tabla se observan los resultados, donde los valores en color rojo son los obtenidos con la poda sólo con automorfismos y sin indicadores que obteníamos en aquel tema anterior, realizando 100 tests de isomorfismos limitados a un tiempo máximo de 60 segundos, resultando todos isomórficos indicándose en la columna Tests iso., lo que evidencia la corrección del uso del algoritmo con poda automorfismos e indicadores.

Las podas con indicadores son "prunningIndicators" que en la tabla se indica con Prunning Ind.1 y "prunningIndicators2" que se indica con Prunning Ind.2. La segunda es la que reduce significativamente el tamaño del árbol, por ejemplo, con el primer grafo cfi-20 tenemos 84 podas reduciendo el tamaño del árbol Size tree de 1288 a 292 nodos, lo que supone que se reduzcan también las iteraciones y el tiempo de ejecución.

La poda Prunning Ind.1 no reduce el tamaño del árbol, como vemos para sts-25 con 2335 nodos, pero si reduce algo las iteraciones de 2664 a 2625 y más el tiempo de ejecución de 3426 a 1609 ms. Ya comentamos esto más arriba, pues esta acción evita obtener y comparar canones que es más costoso que comparar indicadores. Para este grafo no se producen podas del segundo tipo Prunning Ind.2, igual que para usr(1)_29-1 con descenso en iteraciones y tiempo sin afectar al tamaño del árbol.

No es frecuente encontrar grafos donde se produzcan esos dos tipos de podas. Sólo detecté que sucede con la serie latin, donde más abajo analizaremos el grafo latin-6 con 36 nodos, más pequeño que el de la tabla que tiene 100 nodos, pero el primero de la serie donde se observa esto.

Para el grafo kef-10 también usábamos poda con indicador de longitudes en los test que hicimos para poda con automorfismos, pues este grafo sin poda indicadores no finaliza en un tiempo inferior a 5 minutos. En aquella prueba no usábamos Prunning MCR break y que ahora si usamos, observando que reduce el número de iteraciones pasando de 54964 a 47041 lo que incide en una leve reducción del tiempo pero no del tamaño del árbol.

En la Figura vemos el grafo LATIN-6 con 36 nodos y 270 aristas que puede importar en la aplicación con graph-latin-6.txt

Ejecutando el árbol de particiones con poda indicadores de longitudes obervamos que se realizan 2 podas del tipo "prunningIndicator" y 1 del tipo "prunningIndicators2".

Time: 7 ms

Obtener árbol particiones (McKay): {
"useRefine":true,"orderRefine":"neighbors-desc-lengths-desc","targetCell":"max-length-first","typeCanon":"edges","useMcr":true,"useMcrPlus":false,"useMcrBreak":true,"typeIndicator":"lengths",
"timeTotal":7,"timeIni":2,"timeRef":4,
"iter":29,"refine":15,"indexTree":14,
"leaves":7,
"prunningMcr":8,"prunningMcrBreak":3,
"prunningIndicators":2,"prunningIndicators2":1,
"firstCanonicalPartition":[[0],[7],[22],[27],[14],[35],[20],[15],[34],[29],[32],[17],[19],[9],[10],[25],[28],[8],[13],[23],[33],[18],[3],[4],[24],[21],[30],[5],[16],[26],[31],[11],[2],[12],[6],[1]],
"firstCanon":true,
"canonicalPartition":[[0],[7],[22],[27],[14],[35],[20],[15],[34],[29],[32],[17],[19],[9],[10],[25],[28],[8],[13],[23],[33],[18],[3],[4],[24],[21],[30],[5],[16],[26],[31],[11],[2],[12],[6],[1]],
"firstCanonicalLabel":[[0,21],[0,22],[0,23],[0,24],[0,25],[0,26],[0,27],[0,28],[0,29],[0,30],[0,31],[0,32],[0,33],[0,34],[0,35],[1,12],[1,13],[1,14],[1,15],[1,16],[1,17],[1,18],[1,19],[1,20],[1,30],[1,31],[1,32],[1,33],[1,34],[1,35],[2,3],[2,6],[2,8],[2,10],[2,11],[2,12],[2,14],[2,16],[2,19],[2,21],[2,23],[2,25],[2,28],[2,34],[2,35],[3,7],[3,9],[3,10],[3,11],[3,13],[3,15],[3,16],[3,20],[3,22],[3,24],[3,25],[3,29],[3,34],[3,35],[4,5],[4,6],[4,7],[4,10],[4,11],[4,12],[4,13],[4,17],[4,18],[4,23],[4,24],[4,28],[4,29],[4,32],[4,33],[5,8],[5,9],[5,10],[5,11],[5,12],[5,13],[5,19],[5,20],[5,23],[5,24],[5,26],[5,27],[5,30],[5,31],[6,7],[6,10],[6,12],[6,14],[6,15],[6,17],[6,19],[6,21],[6,25],[6,26],[6,27],[6,29],[6,32],[7,11],[7,13],[7,14],[7,15],[7,18],[7,20],[7,22],[7,25],[7,26],[7,27],[7,28],[7,33],[8,9],[8,10],[8,14],[8,16],[8,17],[8,18],[8,20],[8,21],[8,22],[8,23],[8,26],[8,28],[8,30],[9,11],[9,15],[9,16],[9,17],[9,18],[9,19],[9,21],[9,22],[9,24],[9,27],[9,29],[9,31],[10,11],[10,17],[10,20],[10,26],[10,29],[10,30],[10,32],[10,34],[10,35],[11,18],[11,19],[11,27],[11,28],[11,31],[11,33],[11,34],[11,35],[12,13],[12,15],[12,18],[12,19],[12,21],[12,23],[12,24],[12,25],[12,30],[12,35],[13,14],[13,17],[13,20],[13,22],[13,23],[13,24],[13,25],[13,31],[13,34],[14,15],[14,16],[14,17],[14,23],[14,26],[14,27],[14,28],[14,31],[14,34],[15,16],[15,18],[15,24],[15,26],[15,27],[15,29],[15,30],[15,35],[16,19],[16,20],[16,23],[16,24],[16,28],[16,29],[16,32],[16,33],[17,18],[17,21],[17,22],[17,29],[17,31],[17,32],[17,34],[18,21],[18,22],[18,28],[18,30],[18,33],[18,35],[19,20],[19,21],[19,25],[19,27],[19,31],[19,32],[19,33],[20,22],[20,25],[20,26],[20,30],[20,32],[20,33],[21,22],[21,24],[21,25],[21,26],[21,33],[21,34],[22,23],[22,25],[22,27],[22,32],[22,35],[23,24],[23,27],[23,28],[23,32],[23,35],[24,26],[24,29],[24,33],[24,34],[25,28],[25,29],[25,30],[25,31],[26,27],[26,30],[26,33],[26,34],[27,31],[27,32],[27,35],[28,29],[28,30],[28,31],[28,33],[29,30],[29,31],[29,32],[30,31],[30,35],[31,34],[32,33],[32,35],[33,34],[34,35]],
"canonicalLabel":[[0,21],[0,22],[0,23],[0,24],[0,25],[0,26],[0,27],[0,28],[0,29],[0,30],[0,31],[0,32],[0,33],[0,34],[0,35],[1,12],[1,13],[1,14],[1,15],[1,16],[1,17],[1,18],[1,19],[1,20],[1,30],[1,31],[1,32],[1,33],[1,34],[1,35],[2,3],[2,6],[2,8],[2,10],[2,11],[2,12],[2,14],[2,16],[2,19],[2,21],[2,23],[2,25],[2,28],[2,34],[2,35],[3,7],[3,9],[3,10],[3,11],[3,13],[3,15],[3,16],[3,20],[3,22],[3,24],[3,25],[3,29],[3,34],[3,35],[4,5],[4,6],[4,7],[4,10],[4,11],[4,12],[4,13],[4,17],[4,18],[4,23],[4,24],[4,28],[4,29],[4,32],[4,33],[5,8],[5,9],[5,10],[5,11],[5,12],[5,13],[5,19],[5,20],[5,23],[5,24],[5,26],[5,27],[5,30],[5,31],[6,7],[6,10],[6,12],[6,14],[6,15],[6,17],[6,19],[6,21],[6,25],[6,26],[6,27],[6,29],[6,32],[7,11],[7,13],[7,14],[7,15],[7,18],[7,20],[7,22],[7,25],[7,26],[7,27],[7,28],[7,33],[8,9],[8,10],[8,14],[8,16],[8,17],[8,18],[8,20],[8,21],[8,22],[8,23],[8,26],[8,28],[8,30],[9,11],[9,15],[9,16],[9,17],[9,18],[9,19],[9,21],[9,22],[9,24],[9,27],[9,29],[9,31],[10,11],[10,17],[10,20],[10,26],[10,29],[10,30],[10,32],[10,34],[10,35],[11,18],[11,19],[11,27],[11,28],[11,31],[11,33],[11,34],[11,35],[12,13],[12,15],[12,18],[12,19],[12,21],[12,23],[12,24],[12,25],[12,30],[12,35],[13,14],[13,17],[13,20],[13,22],[13,23],[13,24],[13,25],[13,31],[13,34],[14,15],[14,16],[14,17],[14,23],[14,26],[14,27],[14,28],[14,31],[14,34],[15,16],[15,18],[15,24],[15,26],[15,27],[15,29],[15,30],[15,35],[16,19],[16,20],[16,23],[16,24],[16,28],[16,29],[16,32],[16,33],[17,18],[17,21],[17,22],[17,29],[17,31],[17,32],[17,34],[18,21],[18,22],[18,28],[18,30],[18,33],[18,35],[19,20],[19,21],[19,25],[19,27],[19,31],[19,32],[19,33],[20,22],[20,25],[20,26],[20,30],[20,32],[20,33],[21,22],[21,24],[21,25],[21,26],[21,33],[21,34],[22,23],[22,25],[22,27],[22,32],[22,35],[23,24],[23,27],[23,28],[23,32],[23,35],[24,26],[24,29],[24,33],[24,34],[25,28],[25,29],[25,30],[25,31],[26,27],[26,30],[26,33],[26,34],[27,31],[27,32],[27,35],[28,29],[28,30],[28,31],[28,33],[29,30],[29,31],[29,32],[30,31],[30,35],[31,34],[32,33],[32,35],[33,34],[34,35]],
"canonicalIndicator":[1,3,21,0],
"nodes":
[[[-1,[],[1],"PA","PA33"]],
[[0,[0],[1,3],"R9","R10","PA","PA","PA","PA11"],[0,[1],[1,3],"PA","PA18"]],
[[0,[0,7],[1,3,21]],[0,[0,8],[1,3,0],"<"],[0,[0,9],[1,3,0],"<"],[0,[0,10],[1,3,21],"PA"],[0,[0,14],[1,3,7],"PI"],[0,[0,17],[1,3,21],"PA"],[1,[1,8],[1,3,21],"PA"]],
[[0,[0,7,22],[1,3,21,0],"f*"],[0,[0,7,27],[1,3,21,0],"==(1 6)(2 12)(3 18)(4 24)(5 30)(8 13)(9 19)(10 25)(11 31)(15 20)(16 26)(17 32)(22 27)(23 33)(29 34)"],[3,[0,10,23],[1,3,21,0],"==(1 5)(2 4)(6 11)(7 10)(8 9)(12 16)(13 15)(18 21)(19 20)(22 23)(24 26)(27 29)(30 31)(32 35)(33 34)"],[5,[0,17,8],[1,3,21,0],"==(1 11)(2 16)(3 21)(4 26)(5 31)(7 17)(8 22)(9 27)(10 32)(13 23)(14 28)(15 33)(19 29)(20 34)(25 35)"],[6,[1,8,23],[1,3,21,0],"==(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 26 27 28 29)(30 31 32 33 34 35)"]]],
"nodeBest":[3,0],
"mcr":[0],
"fixMcr":
[[[0,7,14,21,28,35],[0,1,2,3,4,5,7,8,9,10,11,14,15,16,17,21,22,23,28,29,35]],
[[0,3,14,17,25,28],[0,1,2,3,6,7,8,12,13,14,17,18,19,22,24,25,27,28,30,32,33]],
[[0,6,12,18,24,30],[0,1,2,3,4,5,6,7,8,9,10,12,13,14,15,18,19,20,24,25,30]],
[[],[0,6,12,18,24,30]]],
"lastEqual":true,"rebuiltMcr":2,"nonRebuiltMcr":12,
"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 26 27 28 29 30 31 32 33 34 35)","parent":-1},
{"index":1,"value":"(0)(7 8 9 10 13 14 15 17 19 20 22 23 25 27 28 29 32 33 34 35)(1 2 3 4 5 6 11 12 16 18 21 24 26 30 31)","parent":[{"index":0,"value":"０"}]},
{"index":2,"value":"(0)(7)(22 27)(14)(35)(15 20)(29 34)(17 32)(9 19)(10 25)(28)(8 13)(23 33)(3 18)(4 24)(21)(5 30)(16 26)(11 31)(2 12)(1 6)","parent":[{"index":1,"value":"７"}]},
{"index":3,"value":"(0)(7)(22)(27)(14)(35)(20)(15)(34)(29)(32)(17)(19)(9)(10)(25)(28)(8)(13)(23)(33)(18)(3)(4)(24)(21)(30)(5)(16)(26)(31)(11)(2)(12)(6)(1)","parent":[{"index":2,"value":"２２"}]},
{"index":4,"value":"(0)(7)(27)(22)(14)(35)(15)(20)(29)(34)(17)(32)(9)(19)(25)(10)(28)(13)(8)(33)(23)(3)(18)(24)(4)(21)(5)(30)(26)(16)(11)(31)(12)(2)(1)(6)","parent":[{"index":2,"value":"２７"}]},
{"index":5,"value":"(0)(8)(22)(33)(17)(28)(15)(19)(25)(35)(27)(23)(20)(9)(7)(32)(14)(10)(13)(34)(29)(12)(1)(5)(24)(16)(31)(4)(30)(21)(26)(11)(3)(18)(6)(2)","parent":[{"index":1,"value":"８"}]},
{"index":6,"value":"(0)(9)(23)(34)(17)(28)(13)(20)(25)(32)(29)(22)(19)(8)(10)(35)(14)(7)(15)(33)(27)(16)(5)(1)(26)(12)(30)(2)(31)(18)(24)(6)(3)(21)(11)(4)","parent":[{"index":1,"value":"９"}]},
{"index":7,"value":"(0)(10)(23 29)(14)(32)(13 19)(27 33)(17 35)(8 20)(7 25)(28)(9 15)(22 34)(3 21)(2 26)(18)(1 31)(12 24)(6 30)(4 16)(5 11)","parent":[{"index":1,"value":"１０"}]},
{"index":8,"value":"(0)(10)(23)(29)(14)(32)(19)(13)(33)(27)(35)(17)(20)(8)(7)(25)(28)(9)(15)(22)(34)(21)(3)(2)(26)(18)(31)(1)(12)(24)(30)(6)(4)(16)(11)(5)","parent":[{"index":7,"value":"２３"}]},
{"index":9,"value":"(0)(14)(7 10 22 23 25 27 29 33 34)(28)(8 9 13 15 17 19 20 32 35)(1 3 5 6 11 18 21 30 31)(2 4 12 16 24 26)","parent":[{"index":1,"value":"１４"}]},
{"index":10,"value":"(0)(17)(8 9)(28)(25)(33 34)(19 20)(7 10)(27 29)(32 35)(14)(22 23)(13 15)(18 21)(24 26)(3)(30 31)(2 4)(1 5)(12 16)(6 11)","parent":[{"index":1,"value":"１７"}]},
{"index":11,"value":"(0)(17)(8)(9)(28)(25)(34)(33)(20)(19)(10)(7)(29)(27)(32)(35)(14)(22)(23)(13)(15)(18)(21)(26)(24)(3)(30)(31)(2)(4)(5)(1)(16)(12)(6)(11)","parent":[{"index":10,"value":"８"}]},
{"index":12,"value":"(1)(8 9 10 11 12 14 15 16 18 20 21 23 24 26 28 29 30 33 34 35)(0 2 3 4 5 6 7 13 17 19 22 25 27 31 32)","parent":[{"index":0,"value":"１"}]},
{"index":13,"value":"(1)(8)(23 28)(15)(30)(16 21)(24 35)(12 33)(10 20)(11 26)(29)(9 14)(18 34)(4 19)(5 25)(22)(0 31)(17 27)(6 32)(3 13)(2 7)","parent":[{"index":12,"value":"８"}]},
{"index":14,"value":"(1)(8)(23)(28)(15)(30)(21)(16)(35)(24)(33)(12)(20)(10)(11)(26)(29)(9)(14)(18)(34)(19)(4)(5)(25)(22)(31)(0)(17)(27)(32)(6)(3)(13)(7)(2)","parent":[{"index":13,"value":"２３"}]}],
"automorphisms":
[[[0],[1,6],[2,12],[3,18],[4,24],[5,30],[7],[8,13],[9,19],[10,25],[11,31],[14],[15,20],[16,26],[17,32],[21],[22,27],[23,33],[28],[29,34],[35]],
[[0],[1,5],[2,4],[3],[6,11],[7,10],[8,9],[12,16],[13,15],[14],[17],[18,21],[19,20],[22,23],[24,26],[25],[27,29],[28],[30,31],[32,35],[33,34]],
[[0],[1,11],[2,16],[3,21],[4,26],[5,31],[6],[7,17],[8,22],[9,27],[10,32],[12],[13,23],[14,28],[15,33],[18],[19,29],[20,34],[24],[25,35],[30]],
[[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,26,27,28,29],[30,31,32,33,34,35]]],
"automorphismsPlus":0} 

El test isomorfismos resulta correcto para todos los 10000 tests que se ejecutan.

Time: 54935 ms

Test isomorfismos (McKay): {"useRefine":true,"orderRefine":"neighbors-desc-lengths-desc","typeCanon":"edges","targetCell":"max-length-first","useMcr":true,"useMcrPlus":false,"useMcrBreak":true,"typeIndicator":"lengths",
"isomorphic":10000,"nonIsomorphic":0,
"firstTime":2,"minTime":2,"averageTime":5,"maxTime":21,
"iter1":29,"iter2":57,
"indexTree1":14,"indexTree2":33,
"minIndexTree":10,"maxIndexTree":121,
"refine1":15,"refine2":34,
"numAut1":4,"numAut2":9,"numAutPlus1":0,"numAutPlus2":0,
"prunningMcr1":8,"prunningMcr2":13,"prunningMcrBreak1":3,"prunningMcrBreak2":5,
"rebuiltMcr1":2,"rebuiltMcr2":13,
"prunningIndicators1":2,"prunningIndicators2":10,
"prunningIndicators1b":1,"prunningIndicators2b":2,
"canonical":[[0,21],[0,22],[0,23],[0,24],[0,25],[0,26],[0,27],[0,28],[0,29],[0,30],[0,31],[0,32],[0,33],[0,34],[0,35],[1,12],[1,13],[1,14],[1,15],[1,16],[1,17],[1,18],[1,19],[1,20],[1,30],[1,31],[1,32],[1,33],[1,34],[1,35],[2,3],[2,6],[2,8],[2,10],[2,11],[2,12],[2,14],[2,16],[2,19],[2,21],[2,23],[2,25],[2,28],[2,34],[2,35],[3,7],[3,9],[3,10],[3,11],[3,13],[3,15],[3,16],[3,20],[3,22],[3,24],[3,25],[3,29],[3,34],[3,35],[4,5],[4,6],[4,7],[4,10],[4,11],[4,12],[4,13],[4,17],[4,18],[4,23],[4,24],[4,28],[4,29],[4,32],[4,33],[5,8],[5,9],[5,10],[5,11],[5,12],[5,13],[5,19],[5,20],[5,23],[5,24],[5,26],[5,27],[5,30],[5,31],[6,7],[6,10],[6,12],[6,14],[6,15],[6,17],[6,19],[6,21],[6,25],[6,26],[6,27],[6,29],[6,32],[7,11],[7,13],[7,14],[7,15],[7,18],[7,20],[7,22],[7,25],[7,26],[7,27],[7,28],[7,33],[8,9],[8,10],[8,14],[8,16],[8,17],[8,18],[8,20],[8,21],[8,22],[8,23],[8,26],[8,28],[8,30],[9,11],[9,15],[9,16],[9,17],[9,18],[9,19],[9,21],[9,22],[9,24],[9,27],[9,29],[9,31],[10,11],[10,17],[10,20],[10,26],[10,29],[10,30],[10,32],[10,34],[10,35],[11,18],[11,19],[11,27],[11,28],[11,31],[11,33],[11,34],[11,35],[12,13],[12,15],[12,18],[12,19],[12,21],[12,23],[12,24],[12,25],[12,30],[12,35],[13,14],[13,17],[13,20],[13,22],[13,23],[13,24],[13,25],[13,31],[13,34],[14,15],[14,16],[14,17],[14,23],[14,26],[14,27],[14,28],[14,31],[14,34],[15,16],[15,18],[15,24],[15,26],[15,27],[15,29],[15,30],[15,35],[16,19],[16,20],[16,23],[16,24],[16,28],[16,29],[16,32],[16,33],[17,18],[17,21],[17,22],[17,29],[17,31],[17,32],[17,34],[18,21],[18,22],[18,28],[18,30],[18,33],[18,35],[19,20],[19,21],[19,25],[19,27],[19,31],[19,32],[19,33],[20,22],[20,25],[20,26],[20,30],[20,32],[20,33],[21,22],[21,24],[21,25],[21,26],[21,33],[21,34],[22,23],[22,25],[22,27],[22,32],[22,35],[23,24],[23,27],[23,28],[23,32],[23,35],[24,26],[24,29],[24,33],[24,34],[25,28],[25,29],[25,30],[25,31],[26,27],[26,30],[26,33],[26,34],[27,31],[27,32],[27,35],[28,29],[28,30],[28,31],[28,33],[29,30],[29,31],[29,32],[30,31],[30,35],[31,34],[32,33],[32,35],[33,34],[34,35]]}

El árbol tiene 15 nodos, que presentamos a continuación a partir del campo "nodes" visualizado en posición vertical:

[-1,[],[1],"PA","PA33"]
    [0,[0],[1,3],"R9","R10","PA","PA","PA","PA11"]
        [0,[0,7],[1,3,21]]
            [0,[0,7,22],[1,3,21,0],"f*"]
            [0,[0,7,27],[1,3,21,0],"=="]
        [0,[0,8],[1,3,0],"<"]
        [0,[0,9],[1,3,0],"<"]
        [0,[0,10],[1,3,21],"PA"]
            [3,[0,10,23],[1,3,21,0],"=="]
        [0,[0,14],[1,3,7],"PI"]
        [0,[0,17],[1,3,21],"PA"]
            [5,[0,17,8],[1,3,21,0],"=="]
    [0,[1],[1,3],"PA","PA18"]
        [1,[1,8],[1,3,21],"PA"]
            [6,[1,8,23],[1,3,21,0],"=="]

Vemos la única poda "PI" que se produce con "prunningIndicators2" en una hoja no terminal. Mientras que las 2 con "prunningIndicators" se dan en particiones discretas que son menores que la canónica. Como dijimos antes, estas no reducen el tamaño del árbol pero si el tiempo de ejecución, pues evitan obtener y comparar canones que resulta más costoso que solo comparar indicadores. En la siguiente tabla vemos como las distintas podas van reduciendo los tamaños.

Con el grafo mz-12 si usamos el indicador aristas (edges) en lugar de longitudes (lengths) vemos que conseguimos 3 podas más (de 150 a 153), reduciéndose algo el tamaño del árbol y las iteraciones, pero el tiempo de ejecución se incrementa. Esto es debido a que construir el indicador aristas es más costoso que el de longitudes, como explicamos en el tema anterior.

La gran mayoría de los grafos comprobados no producen diferenciación con la poda con indicadores de longitudes, pues estos siempre son iguales para todas las particiones, incluso usando cualquiera de los otros implementados: celdas, vecinos y aristas. Tendría que buscar nuevos tipos de indicadores para ver si se consigue reducir en esos casos.

Obtener el árbol de particiones getPartitionTree()

En la sección de algoritmos de la aplicación Grafos SVG, como vemos en la Figura, encontramos los iconos que nos remite a una página de este sitio con información. Y con nos devuelve el código JavaScript actual del algoritmo implementado. El código que veremos después es una reducción del que finalmente se implementa en la aplicación, pues omitimos y simplificamos algunas partes (opciones de ejecución, trazados, controles de iteración) con objeto de que no sea muy extenso y que no aportan nada al fondo del asunto. En cualquier caso el que se implementa se puede consultar en ese enlace como indicamos antes.

Recordemos las versiones básicas previas que hemos venido exponiendo en los temas anteriores:

1. getPartitionTreeDfs para obtener el árbol de particiones y su etiquetado canónico sin podas.
2. getPartitionTreeRefine incluyendo refinamiento.
3. getPartitionTreeRefineMcr incluyendo podas con automorfismos.
4. getPartitionTreeRefineMcrIndicator() incluyendo poda con indicadores, que es el que veremos ahora y el que finalmente se implementa en la aplicación como getPartitionTree().

A continuación vemos el esquema en pseudocódigo del algoritmo para obtener el árbol de particiones usando refinamiento, poda automorfismos e indicadores. Es básicamente el que vimos en el tema de automorfismos agregando las partes que aplican a indicadores.

result = {
    canonicalIndicator:null,
    canonicalPartition:null,
    canonicalLabel:null,
    nodes:[],
    mcr:null,
    fixMcr:null,
    lastEqual:false
}

El resultado a devolver es el mismo que veiamos en el anterior agregando canonicalIndicator.

Function getPartitionTreeRefineMcrIndicator(matrix, partition, result)
    If partition.length===0  // INITIAL STEPS
        partition = Initial refinement
        Add first root node to nodes
        Apply order refine
    End If
    if (partition.length===n) // DISCRETE PARTITION  (after initial refinement)
        canon = get canon with this permutation
        result.canonicalPartition = partition
        result.canonicalLabel = canon
    Else
        cell = Select target cell
        While cell.size>0
            // Fix vertex
            vertex = minimum of cell
            indexCell = position of vertex in cell
            delete vertex in cell
            filter = indexCell===0 or result.mcr===null
            If not filter
                // Prunning MCR
                If not lastEqual
                    result.mcr = Rebuilt MCR with result.fixMcr and node fixed path
                End If
                filter = result.mcr has vertex
            End If
            If not filter 
                // Prunning MCR break
                return result if applicable
            End if
            If filter
                partition = individualize vertex and refine partition
                Add new node with this fixed path and vector indicator to result.nodes
                If partition.length===n  // DISCRETE PARTITION
                    If result.canonicalLabel===null
                        canon = get canon with this permutation
                        result.canonicalIndicator = vector
                        result.canonicalPartition = partition
                        result.canonicalLabel = canon
                    Else
                        // Compare indicator
                        Compare this indicator with result.canonicalIndicator
                        If vector > result.canonicalIndicator
                            canon = get canon with this permutation
                            result.canonicalIndicator = vector
                            result.canonicalPartition = partition
                            result.canonicalLabel = canon
                            result.lastEqual = false
                        Else If vector === result.canonicalIndicator
                            canon = get canon with this permutation
                            // Compare canon
                            If canon > result.canonicalLabel
                                result.canonicalPartition = partition
                                result.canonicalLabel = canon
                                result.lastEqual = false
                            Else if canon ===  result.canonicalLabel
                                Get automorphism with partition and result.canonicalPartition
                                and refresh result.mcr and result.fixMcr
                                result.lastEqual = true
                            Else
                                result.lastEqual = false
                            End If
                        Else if vector < result.canonicalIndicator
                            // Prunning indicator 1
                            result.lastEqual = false
                        End if
                    End If
                Else // NON-DISCRETE PARTITION
                    if vector ≥ result.canonicalIndicator
                        getPartitionTreeRefineMcrIndicator(matrix, partition, result)
                        // Else prunning indicator 2
                    End If
                End If
            End If
        End While
    End If
    return result
End Function

Como explicamos más arriba con la anotación Prunning indicator 1 realmente no se produce una poda de ramas del árbol, pero reduce los tiempos de ejecución pues no hay que obtener o comparar canones. Vea que el código para obtener el canon (etiquetado canónico) en get canon así como el de compare canon no se produce en esta alternativa vector < result.canonicalIndicator, pues la única que hay que hacer en todos los casos es comparar indicadores que resulta mucho menos costoso.

Observe que cuando la partición no es discreta hacemos la nueva llamada al recursivo, pero sólo cuando el indicador es igual o mayor que el almacenado en result.canonicalIndicator. Así en otro caso aquí se producen las verdaderas podas con indicador Prunning indicator 2.

El algoritmo en JavaScript básico para obtener el etiquetado canónico con refinamiento, poda automorfismos y poda indicadores es el siguiente. Es la misma base del que vimos en el tema anterior, usando las mismas funciones auxiliares y agregando una nueva compareIndicators() que veremos después.

function getPartitionTreeRefineMcrIndicator({matrix=[], partition=[], level=-1, positionPrev=0, identity=null, 
    result={canonicalPartition:null, canonicalLabel:null, canonicalIndicator:null, nodes:[], mcr:null, fixMcr:null, lastEqual:false, automorphisms:[]}}) {
    try {
        level++;
        let n = matrix.length;
        if (partition.length===0) {
            // Initial refinement
            for (let index=0; index<n; index++) {
                let num = matrix.neighbors[index].length;
                let j = partition.findIndex(v => v.num===num);
                if (j===-1) {
                    j = partition.length;
                    let arr = [];
                    arr.num = num;
                    partition.push(arr);
                }
                partition[j].push(index);
            }
            // Add first root node to nodes with empty fix path and vector indicator
            result.nodes.push([[-1, [], [partition.length]]]);
            // For use with fixMcr
            identity = new Set(Array.from({length:n}, (v,i)=>i));
            // orderRefine (neighbors-desc-length-desc)
            partition.sort((v,w) => v.length===w.length ?  w.num-v.num : w.length-v.length);
        }
        if (partition.length===n) { // DISCRETE PARTITION  (after initial refinement)
            // Get canon with this permutation;
            if (temp = getCanon({matrix, partition}), typeof temp==="string") throw new Error(temp);
            result.canonicalLabel = temp;
            result.canonicalPartition = partition;
        } else {
            // Select target cell (max-length-first)
            let parts = partition.map((v,i) => [i, v]).filter(v => v[1].length>1);
            let [iMax, len] = [-1, 0];
            for (let j=0; j<parts.length; j++) {
                let [i,v] = parts[j];
                let vl = v.length;
                if (vl>len) [iMax, len] = [i, vl];
            }
            let index = iMax;
            if (index>-1) {
                let cell = partition[index];
                let sCell = new Set(cell);
                while (sCell.size>0) {
                    // Fix vertex
                    let vertex = Math.min(...sCell);
                    let indexCell = cell.indexOf(vertex);
                    sCell.delete(vertex);
                    let filter =  indexCell===0 || result.mcr===null;
                    if (!filter) {
                        // Prunning MCR
                        if (!result.lastEqual) {
                            let f = result.nodes[level][positionPrev][1];
                            let m = identity;
                            for (let j=0; j<result.fixMcr.length; j++) {
                                let [fix, mcr] = result.fixMcr[j];
                                if (f.every(v => fix.includes(v))){
                                    m = m.intersection(mcr);
                                }
                            }
                            result.mcr = m;
                        }
                        filter = result.mcr.has(vertex);
                    }
                    if (!filter) {
                        // Prunning MCR break
                        if (result.mcr!==null && sCell.size>0 && result.mcr.intersection(sCell).size===0) return result;
                    }
                    if (filter) {
                        let part = partition.map(v => v.slice(0));
                        part[index] = cell.toSpliced(indexCell, 1);
                        part = part.toSpliced(index, 0, [vertex]);
                        // Refine partition
                        if (part.length<n) {
                            let cells = [[vertex]];
                            part = refinePartition({matrix, partition:part, cells});
                            if (typeof part==="string") throw new Error(part);
                        }
                        // Add node to tree nodes
                        let lv = result.nodes[level].length-1;
                        if (result.nodes.length<level+2) result.nodes.push([]);
                        let prev = result.nodes[level][lv][1];
                        // Get fix path
                        let fix = [...prev, vertex];
                        // Get indicator "lengths"
                        let indicator = part.length===n ? 0 : part.length;
                        prev = result.nodes[level][lv][2];
                        let vector = [...prev, indicator];
                        result.nodes[level+1].push([lv, fix, vector]);
                        let position = result.nodes[level+1].length-1;
                        if (part.length===n) { // DISCRETE PARTITION
                            if (result.canonicalLabel===null) {
                                // Get canon with this permutation
                                if (temp = getCanon({matrix, partition:part}), typeof temp==="string") throw new Error(temp);
                                let canon = temp;
                                result.canonicalIndicator = vector;
                                result.canonicalPartition = part;
                                result.canonicalLabel = canon;
                            } else {
                                let ci = compareIndicators(result.canonicalIndicator, vector);
                                if (typeof ci==="string") throw new Error(ci);
                                if (ci===1) {
                                    // Get canon with this permutation
                                    if (temp = getCanon({matrix, partition:part}), typeof temp==="string") throw new Error(temp);
                                    let canon = temp;
                                    result.canonicalIndicator = vector;
                                    result.canonicalPartition = part;
                                    result.canonicalLabel = canon;
                                    result.lastEqual = false;
                                } else if (ci===0) {
                                    // Get canon with this permutation
                                    if (temp = getCanon({matrix, partition:part}), typeof temp==="string") throw new Error(temp);
                                    let canon = temp;
                                    // Compare canon
                                    let compCanon = 0;
                                    for (let i=0; i<canon.length; i++) {
                                        if (canon[i]<result.canonicalLabel[i]) {
                                            compCanon = 1;
                                            break;
                                        } else if (canon[i]>result.canonicalLabel[i]) {
                                            compCanon = -1;
                                            break;
                                        }
                                    }
                                    if (compCanon===1) {
                                        result.canonicalIndicator = vector;
                                        result.canonicalPartition = part;
                                        result.canonicalLabel = canon;
                                        result.lastEqual = false;
                                    } else if (compCanon===0) {
                                        if (temp = getAutomorphism({result, part}), typeof temp==="string") throw new Error(temp);
                                        result.lastEqual = true;
                                    } else {
                                        result.lastEqual = false;
                                    }
                                } else {
                                    // Prunning indicators 1
                                    result.lastEqual = false;
                                }
                            }
                        } else { // NON-DISCRETE PARTITION
                            let br = false;
                            if (result.canonicalIndicator!==null) {
                                // Prunning Indicators 2
                                let ci = compareIndicators(result.canonicalIndicator, vector);
                                if (typeof ci==="string") throw new Error(ci);
                                if (ci===-1)  br = true;
                            }
                            if (!br) {
                                let res = getPartitionTreeRefineMcrIndicator({matrix, partition:part, level, positionPrev:position, identity, result});
                                if (typeof res==="string") throw new Error(res);
                            }
                        }
                    }
                }
            }
        }
    } catch(e){result = "getPartitionTreeRefineMcrIndicator(): " + e.message}
    return result;
}

Para ejecutar este algoritmo puede usarse la siguiente función que usa el ejemplo del grafo de la Figura. Hemos de pasarle la matriz de adyacencia construyendo su lista de aristas y de vecinos. Aquí lo hacemos manualmente, pero pueden usarse los algoritmos getEdges() y getNeighbors() que los obtiene a partir de la matriz de adyacencia. Puede descargar todo el código en el archivo de texto get-partition-tree-indicator.txt, copiar su contenido y pegarlo en la consola del navegador para su ejecución.

function runGetPartitionTreeRefineMcrIndicator() {
    let matrix;
    // Explained in https://www.wextensible.com/temas/grafos/isomorfismos-indicadores-2.html
    matrix = [[0,1,1,1,1,1,1,0,0,0,0,1,1,0,0,0,1,0,1,0,0,1,0,0,1,0,1,0,0,0,1,1,0,0,0,0],[1,0,1,1,1,1,1,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,1,0,0,1,0,1,0,0,0,1,1,0,0,0],[1,1,0,1,1,1,0,1,1,0,0,0,1,0,1,0,0,0,0,0,1,0,0,1,0,0,1,0,1,0,0,0,1,1,0,0],[1,1,1,0,1,1,0,0,1,1,0,0,0,1,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,1,0,0,0,1,1,0],[1,1,1,1,0,1,0,0,0,1,1,0,0,0,1,0,1,0,0,1,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,1],[1,1,1,1,1,0,0,0,0,0,1,1,0,0,0,1,0,1,0,0,1,0,0,1,0,1,0,0,0,1,1,0,0,0,0,1],[1,1,0,0,0,0,0,1,1,1,1,1,1,0,0,0,0,1,1,0,0,0,1,0,1,0,0,1,0,0,1,0,1,0,0,0],[0,1,1,0,0,0,1,0,1,1,1,1,1,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,1,0,0,1,0,1,0,0],[0,0,1,1,0,0,1,1,0,1,1,1,0,1,1,0,0,0,1,0,1,0,0,0,0,0,1,0,0,1,0,0,1,0,1,0],[0,0,0,1,1,0,1,1,1,0,1,1,0,0,1,1,0,0,0,1,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,1],[0,0,0,0,1,1,1,1,1,1,0,1,0,0,0,1,1,0,0,0,1,0,1,0,0,1,0,0,1,0,1,0,0,0,1,0],[1,0,0,0,0,1,1,1,1,1,1,0,0,0,0,0,1,1,0,0,0,1,0,1,0,0,1,0,0,1,0,1,0,0,0,1],[1,0,1,0,0,0,1,1,0,0,0,0,0,1,1,1,1,1,1,0,0,0,0,1,1,0,0,0,1,0,1,0,0,1,0,0],[0,1,0,1,0,0,0,1,1,0,0,0,1,0,1,1,1,1,1,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,1,0],[0,0,1,0,1,0,0,0,1,1,0,0,1,1,0,1,1,1,0,1,1,0,0,0,1,0,1,0,0,0,0,0,1,0,0,1],[0,0,0,1,0,1,0,0,0,1,1,0,1,1,1,0,1,1,0,0,1,1,0,0,0,1,0,1,0,0,1,0,0,1,0,0],[1,0,0,0,1,0,0,0,0,0,1,1,1,1,1,1,0,1,0,0,0,1,1,0,0,0,1,0,1,0,0,1,0,0,1,0],[0,1,0,0,0,1,1,0,0,0,0,1,1,1,1,1,1,0,0,0,0,0,1,1,0,0,0,1,0,1,0,0,1,0,0,1],[1,0,0,1,0,0,1,0,1,0,0,0,1,1,0,0,0,0,0,1,1,1,1,1,1,0,0,0,0,1,1,0,0,0,1,0],[0,1,0,0,1,0,0,1,0,1,0,0,0,1,1,0,0,0,1,0,1,1,1,1,1,1,0,0,0,0,0,1,0,0,0,1],[0,0,1,0,0,1,0,0,1,0,1,0,0,0,1,1,0,0,1,1,0,1,1,1,0,1,1,0,0,0,1,0,1,0,0,0],[1,0,0,1,0,0,0,0,0,1,0,1,0,0,0,1,1,0,1,1,1,0,1,1,0,0,1,1,0,0,0,1,0,1,0,0],[0,1,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,1,1,1,1,1,0,1,0,0,0,1,1,0,0,0,1,0,1,0],[0,0,1,0,0,1,0,1,0,0,0,1,1,0,0,0,0,1,1,1,1,1,1,0,0,0,0,0,1,1,0,0,0,1,0,1],[1,0,0,0,1,0,1,0,0,1,0,0,1,0,1,0,0,0,1,1,0,0,0,0,0,1,1,1,1,1,1,0,0,0,0,1],[0,1,0,0,0,1,0,1,0,0,1,0,0,1,0,1,0,0,0,1,1,0,0,0,1,0,1,1,1,1,1,1,0,0,0,0],[1,0,1,0,0,0,0,0,1,0,0,1,0,0,1,0,1,0,0,0,1,1,0,0,1,1,0,1,1,1,0,1,1,0,0,0],[0,1,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,1,0,0,0,1,1,0,1,1,1,0,1,1,0,0,1,1,0,0],[0,0,1,0,1,0,0,1,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,1,1,1,1,1,0,1,0,0,0,1,1,0],[0,0,0,1,0,1,0,0,1,0,0,1,0,1,0,0,0,1,1,0,0,0,0,1,1,1,1,1,1,0,0,0,0,0,1,1],[1,0,0,0,0,1,1,0,0,0,1,0,1,0,0,1,0,0,1,0,1,0,0,0,1,1,0,0,0,0,0,1,1,1,1,1],[1,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,1,0,0,1,0,1,0,0,0,1,1,0,0,0,1,0,1,1,1,1],[0,1,1,0,0,0,1,0,1,0,0,0,0,0,1,0,0,1,0,0,1,0,1,0,0,0,1,1,0,0,1,1,0,1,1,1],[0,0,1,1,0,0,0,1,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,1,0,0,0,1,1,0,1,1,1,0,1,1],[0,0,0,1,1,0,0,0,1,0,1,0,0,1,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,1,1,1,1,1,0,1],[0,0,0,0,1,1,0,0,0,1,0,1,0,0,1,0,0,1,0,1,0,0,0,1,1,0,0,0,0,1,1,1,1,1,1,0]];
    matrix.edges = [[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,11],[0,12],[0,16],[0,18],[0,21],[0,24],[0,26],[0,30],[0,31],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7],[1,13],[1,17],[1,19],[1,22],[1,25],[1,27],[1,31],[1,32],[2,3],[2,4],[2,5],[2,7],[2,8],[2,12],[2,14],[2,20],[2,23],[2,26],[2,28],[2,32],[2,33],[3,4],[3,5],[3,8],[3,9],[3,13],[3,15],[3,18],[3,21],[3,27],[3,29],[3,33],[3,34],[4,5],[4,9],[4,10],[4,14],[4,16],[4,19],[4,22],[4,24],[4,28],[4,34],[4,35],[5,10],[5,11],[5,15],[5,17],[5,20],[5,23],[5,25],[5,29],[5,30],[5,35],[6,7],[6,8],[6,9],[6,10],[6,11],[6,12],[6,17],[6,18],[6,22],[6,24],[6,27],[6,30],[6,32],[7,8],[7,9],[7,10],[7,11],[7,12],[7,13],[7,19],[7,23],[7,25],[7,28],[7,31],[7,33],[8,9],[8,10],[8,11],[8,13],[8,14],[8,18],[8,20],[8,26],[8,29],[8,32],[8,34],[9,10],[9,11],[9,14],[9,15],[9,19],[9,21],[9,24],[9,27],[9,33],[9,35],[10,11],[10,15],[10,16],[10,20],[10,22],[10,25],[10,28],[10,30],[10,34],[11,16],[11,17],[11,21],[11,23],[11,26],[11,29],[11,31],[11,35],[12,13],[12,14],[12,15],[12,16],[12,17],[12,18],[12,23],[12,24],[12,28],[12,30],[12,33],[13,14],[13,15],[13,16],[13,17],[13,18],[13,19],[13,25],[13,29],[13,31],[13,34],[14,15],[14,16],[14,17],[14,19],[14,20],[14,24],[14,26],[14,32],[14,35],[15,16],[15,17],[15,20],[15,21],[15,25],[15,27],[15,30],[15,33],[16,17],[16,21],[16,22],[16,26],[16,28],[16,31],[16,34],[17,22],[17,23],[17,27],[17,29],[17,32],[17,35],[18,19],[18,20],[18,21],[18,22],[18,23],[18,24],[18,29],[18,30],[18,34],[19,20],[19,21],[19,22],[19,23],[19,24],[19,25],[19,31],[19,35],[20,21],[20,22],[20,23],[20,25],[20,26],[20,30],[20,32],[21,22],[21,23],[21,26],[21,27],[21,31],[21,33],[22,23],[22,27],[22,28],[22,32],[22,34],[23,28],[23,29],[23,33],[23,35],[24,25],[24,26],[24,27],[24,28],[24,29],[24,30],[24,35],[25,26],[25,27],[25,28],[25,29],[25,30],[25,31],[26,27],[26,28],[26,29],[26,31],[26,32],[27,28],[27,29],[27,32],[27,33],[28,29],[28,33],[28,34],[29,34],[29,35],[30,31],[30,32],[30,33],[30,34],[30,35],[31,32],[31,33],[31,34],[31,35],[32,33],[32,34],[32,35],[33,34],[33,35],[34,35]];
    matrix.neighbors = [[1,2,3,4,5,6,11,12,16,18,21,24,26,30,31],[0,2,3,4,5,6,7,13,17,19,22,25,27,31,32],[0,1,3,4,5,7,8,12,14,20,23,26,28,32,33],[0,1,2,4,5,8,9,13,15,18,21,27,29,33,34],[0,1,2,3,5,9,10,14,16,19,22,24,28,34,35],[0,1,2,3,4,10,11,15,17,20,23,25,29,30,35],[0,1,7,8,9,10,11,12,17,18,22,24,27,30,32],[1,2,6,8,9,10,11,12,13,19,23,25,28,31,33],[2,3,6,7,9,10,11,13,14,18,20,26,29,32,34],[3,4,6,7,8,10,11,14,15,19,21,24,27,33,35],[4,5,6,7,8,9,11,15,16,20,22,25,28,30,34],[0,5,6,7,8,9,10,16,17,21,23,26,29,31,35],[0,2,6,7,13,14,15,16,17,18,23,24,28,30,33],[1,3,7,8,12,14,15,16,17,18,19,25,29,31,34],[2,4,8,9,12,13,15,16,17,19,20,24,26,32,35],[3,5,9,10,12,13,14,16,17,20,21,25,27,30,33],[0,4,10,11,12,13,14,15,17,21,22,26,28,31,34],[1,5,6,11,12,13,14,15,16,22,23,27,29,32,35],[0,3,6,8,12,13,19,20,21,22,23,24,29,30,34],[1,4,7,9,13,14,18,20,21,22,23,24,25,31,35],[2,5,8,10,14,15,18,19,21,22,23,25,26,30,32],[0,3,9,11,15,16,18,19,20,22,23,26,27,31,33],[1,4,6,10,16,17,18,19,20,21,23,27,28,32,34],[2,5,7,11,12,17,18,19,20,21,22,28,29,33,35],[0,4,6,9,12,14,18,19,25,26,27,28,29,30,35],[1,5,7,10,13,15,19,20,24,26,27,28,29,30,31],[0,2,8,11,14,16,20,21,24,25,27,28,29,31,32],[1,3,6,9,15,17,21,22,24,25,26,28,29,32,33],[2,4,7,10,12,16,22,23,24,25,26,27,29,33,34],[3,5,8,11,13,17,18,23,24,25,26,27,28,34,35],[0,5,6,10,12,15,18,20,24,25,31,32,33,34,35],[0,1,7,11,13,16,19,21,25,26,30,32,33,34,35],[1,2,6,8,14,17,20,22,26,27,30,31,33,34,35],[2,3,7,9,12,15,21,23,27,28,30,31,32,34,35],[3,4,8,10,13,16,18,22,28,29,30,31,32,33,35],[4,5,9,11,14,17,19,23,24,29,30,31,32,33,34]];
    let result = getPartitionTreeRefineMcrIndicator({matrix});
    if (typeof result!=="string") {
        // Only for view of Sets of JavaScript with JSON.stringify
        result.mcr = [...result.mcr];
        result.fixMcr = result.fixMcr.map(v => [v[0], [...v[1]]]);
    }
    return result;
}
console.log(JSON.stringify(runGetPartitionTreeRefineMcrIndicator()));

Se ha de obtener este resultado que es el mismo que vimos en la traza del grafo LATIN-6 en la Figura.

{"canonicalPartition":[[0],[7],[22],[27],[14],[35],[20],[15],[34],[29],[32],[17],[19],[9],[10],[25],[28],[8],[13],[23],[33],[18],[3],[4],[24],[21],[30],[5],[16],[26],[31],[11],[2],[12],[6],[1]],
"canonicalLabel":[[0,21],[0,22],[0,23],[0,24],[0,25],[0,26],[0,27],[0,28],[0,29],[0,30],[0,31],[0,32],[0,33],[0,34],[0,35],[1,12],[1,13],[1,14],[1,15],[1,16],[1,17],[1,18],[1,19],[1,20],[1,30],[1,31],[1,32],[1,33],[1,34],[1,35],[2,3],[2,6],[2,8],[2,10],[2,11],[2,12],[2,14],[2,16],[2,19],[2,21],[2,23],[2,25],[2,28],[2,34],[2,35],[3,7],[3,9],[3,10],[3,11],[3,13],[3,15],[3,16],[3,20],[3,22],[3,24],[3,25],[3,29],[3,34],[3,35],[4,5],[4,6],[4,7],[4,10],[4,11],[4,12],[4,13],[4,17],[4,18],[4,23],[4,24],[4,28],[4,29],[4,32],[4,33],[5,8],[5,9],[5,10],[5,11],[5,12],[5,13],[5,19],[5,20],[5,23],[5,24],[5,26],[5,27],[5,30],[5,31],[6,7],[6,10],[6,12],[6,14],[6,15],[6,17],[6,19],[6,21],[6,25],[6,26],[6,27],[6,29],[6,32],[7,11],[7,13],[7,14],[7,15],[7,18],[7,20],[7,22],[7,25],[7,26],[7,27],[7,28],[7,33],[8,9],[8,10],[8,14],[8,16],[8,17],[8,18],[8,20],[8,21],[8,22],[8,23],[8,26],[8,28],[8,30],[9,11],[9,15],[9,16],[9,17],[9,18],[9,19],[9,21],[9,22],[9,24],[9,27],[9,29],[9,31],[10,11],[10,17],[10,20],[10,26],[10,29],[10,30],[10,32],[10,34],[10,35],[11,18],[11,19],[11,27],[11,28],[11,31],[11,33],[11,34],[11,35],[12,13],[12,15],[12,18],[12,19],[12,21],[12,23],[12,24],[12,25],[12,30],[12,35],[13,14],[13,17],[13,20],[13,22],[13,23],[13,24],[13,25],[13,31],[13,34],[14,15],[14,16],[14,17],[14,23],[14,26],[14,27],[14,28],[14,31],[14,34],[15,16],[15,18],[15,24],[15,26],[15,27],[15,29],[15,30],[15,35],[16,19],[16,20],[16,23],[16,24],[16,28],[16,29],[16,32],[16,33],[17,18],[17,21],[17,22],[17,29],[17,31],[17,32],[17,34],[18,21],[18,22],[18,28],[18,30],[18,33],[18,35],[19,20],[19,21],[19,25],[19,27],[19,31],[19,32],[19,33],[20,22],[20,25],[20,26],[20,30],[20,32],[20,33],[21,22],[21,24],[21,25],[21,26],[21,33],[21,34],[22,23],[22,25],[22,27],[22,32],[22,35],[23,24],[23,27],[23,28],[23,32],[23,35],[24,26],[24,29],[24,33],[24,34],[25,28],[25,29],[25,30],[25,31],[26,27],[26,30],[26,33],[26,34],[27,31],[27,32],[27,35],[28,29],[28,30],[28,31],[28,33],[29,30],[29,31],[29,32],[30,31],[30,35],[31,34],[32,33],[32,35],[33,34],[34,35]],
"canonicalIndicator":[1,3,21,0],
"nodes":[[[-1,[],[1]]],
[[0,[0],[1,3]],[0,[1],[1,3]]],
[[0,[0,7],[1,3,21]],[0,[0,8],[1,3,0]],[0,[0,9],[1,3,0]],[0,[0,10],[1,3,21]],[0,[0,14],[1,3,7]],[0,[0,17],[1,3,21]],[1,[1,8],[1,3,21]]],
[[0,[0,7,22],[1,3,21,0]],[0,[0,7,27],[1,3,21,0]],[3,[0,10,23],[1,3,21,0]],[5,[0,17,8],[1,3,21,0]],[6,[1,8,23],[1,3,21,0]]]],
"mcr":[0],
"fixMcr":
[[[0,7,14,21,28,35],[0,1,2,3,4,5,7,8,9,10,11,14,15,16,17,21,22,23,28,29,35]]
[[0,3,14,17,25,28],[0,1,2,3,6,7,8,12,13,14,17,18,19,22,24,25,27,28,30,32,33]],
[[0,6,12,18,24,30],[0,1,2,3,4,5,6,7,8,9,10,12,13,14,15,18,19,20,24,25,30]],
[[],[0,6,12,18,24,30]]],
"lastEqual":true,
"automorphisms":
[[[0],[1,6],[2,12],[3,18],[4,24],[5,30],[7],[8,13],[9,19],[10,25],[11,31],[14],[15,20],[16,26],[17,32],[21],[22,27],[23,33],[28],[29,34],[35]],
[[0],[1,5],[2,4],[3],[6,11],[7,10],[8,9],[12,16],[13,15],[14],[17],[18,21],[19,20],[22,23],[24,26],[25],[27,29],[28],[30,31],[32,35],[33,34]],
[[0],[1,11],[2,16],[3,21],[4,26],[5,31],[6],[7,17],[8,22],[9,27],[10,32],[12],[13,23],[14,28],[15,33],[18],[19,29],[20,34],[24],[25,35],[30]],
[[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,26,27,28,29],[30,31,32,33,34,35]]]}

Funciones auxiliares del algorimo para obtener árbol particiones

El algoritmo getPartitionTree() usa las siguientes funciones auxiliares que ya hemos expuesto en temas anteriores:

• getCanon() para obtener el etiquetado canónico de una partición discreta.
• refinePartition() para refinar una partición.
• permutationsToCyclic() para usar en la siguiente, convirtiendo dos permutaciones discretas con igual etiquetado canónico en un automorfismo.
• getAutomorphism() para obtener automorfismo entre dos particiones discretas con igual etiquetado canónico.

En el código de getPartitionTree() tenemos un trozo para comparar dos etiquetados canónicos. Sin embargo en el algoritmo finalmente implementado usamos la siguiente función auxiliar:

function compareCanon(canon1, canon2, typeCanon){
    if (canon1.toString()===canon2.toString()) return 0;
    let [a, b] = typeCanon==="edges" ? [-1, 1] : [1, -1];
    for (let i=0; i<canon1.length; i++) {
        if (canon1[i]>canon2[i]) {
            return a;
        } else if (canon1[i]<canon2[i]) {
            return b;
        }
    }
    return 0;
}

Esta función auxiliar es para comparar dos indicadores:

function compareIndicators(indicator1=[], indicator2=[]) {
    try {
        if (indicator1.length===indicator2.length && indicator1.toString()===indicator2.toString()) return 0;
        if (indicator2.length>indicator1.length) return 1;
        for (let i=0; i<indicator2.length; i++) {
            if (indicator2[i]>indicator1[i]){
                return 1;
            } else if (indicator2[i]<indicator1[i]){
                return -1;
            }
        }
    } catch(e){return "compareIndicators(): " + e.message}
    return 0;
}