Contribution to graph isomorphism

Abstract

Partiendo de la versión existente de conauto se ha desarrollado una nueva versión en la que se han incluido nuevos conceptos. Por un lado, se ha terminado de realizar la gestión del grupo de automorfismo generando un array que permite saber que serie de permutaciones habría que realizar para que cualquier vértice se convirtiera en líder de orbita. También se ha añadido el sistema de fusión de orbitas aprovechando la información almacenada y generando el menor numero de cambios para aumentar
la eficiencia. Por otro lado, la gestión de los subgrupos también ha sido añadida. Permitiendo que durante la exploración de los niveles al profundizar se prueben un menor número de vértices, permitiendo la poda del árbol de búsqueda, minimizando los nodos y aumentando el rendimiento al evitar comprobaciones redundantes. Esto es posible gracias al uso de la información almacenada de la simetrías encontradas con anterioridad. Gracias a estos conceptos se consigue mejorar el rendimiento, con respecto a la versión anterior.
Abstract:
Starting from the existing version of conauto, a new version has been developed in which new concepts have been included. On the one hand, the management of the automorphism group has been completed generating an array that allows us to know which series of permutations would have to be produced for any vertex to become an orbit leader. The orbit fusion system has also been added, taking advantage of the stored information and generating the least number of changes to increase efficiency. On the other hand, the management of subgroups has also been added. Allowing fewer vertices to be tested during the exploration of the levels when drilling down, pruning the searching tree, minimizing nodes and increasing performance by avoiding redundant checks. This is possible thanks to the use of the stored information of the previously found symmetries. Thanks to these concepts, performance is improved in comparison to the previous version.