Saucy3: Fast Symmetry Discovery in Graphs. Many computational tools have recently begun to benefit from the use of the symmetry inherent in the tasks they solve, and use general-purpose graph symmetry tools to uncover this symmetry. Common applications include organic chemistry, constraint solvers, logistics, optimization, bio-informatics, and finite group theory. However, older symmetry-finding tools often suffer quadratic runtime (or worse!) in the number of symmetries explicitly returned and are therefore of limited use on very large, sparse, symmetric graphs. Over the last 10+ years, we developed a symmetry-discovery algorithm which exploits the sparsity present not only in the input but also the output, i.e., the symmetry generators themselves. By avoiding quadratic runtime on large graphs, it improved state-of-the-art runtimes from several days to less than a second. Recent improvements to our algorithm include additional pruning that quickly solves the hard Miyazaki graphs. Our implementation has been stable and reliable for many years. While it accounts for several types of sparsity, it works well on dense graphs too. As we continue looking for performance improvements, please send us any graphs on which saucy takes long time. If you find saucy useful in your applications, check this page for future updates. Also, consider citing some of our publications listed below, along with this URL
Keywords for this software
References in zbMATH (referenced in 2 articles )
Showing results 1 to 2 of 2.
- Itzhakov, Avraham; Codish, Michael: Breaking symmetries in graph search with canonizing sets (2016)
- Hinow, Peter; Rietman, Edward A.; Omar, Sara Ibrahim; Tuszyński, Jack A.: Algebraic and topological indices of molecular pathway networks in human cancers (2015)