{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,22]],"date-time":"2025-12-22T11:01:12Z","timestamp":1766401272715,"version":"3.41.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2020,4,11]],"date-time":"2020-04-11T00:00:00Z","timestamp":1586563200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Energy Research Scientific Computing Center, a DOE Office of Science User Facility supported by the Office of Science of the U.S. Department of Energy","award":["DE-AC02-05CH11231"],"award-info":[{"award-number":["DE-AC02-05CH11231"]}]},{"name":"Independent Research Fund Denmark, Natural Sciences","award":["DFF-7014-00041"],"award-info":[{"award-number":["DFF-7014-00041"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2020,12,6]]},"abstract":"<jats:p>The state-of-the-art tools for practical graph canonization are all based on the individualization-refinement paradigm, and their difference is primarily in the choice of heuristics they include and in the actual tool implementation. It is thus not possible to make a direct comparison of how individual algorithmic ideas affect the performance on different graph classes.<\/jats:p>\n          <jats:p>We present an algorithmic software framework that facilitates implementation of heuristics as independent extensions to a common core algorithm. It therefore becomes easy to perform a detailed comparison of the performance and behavior of different algorithmic ideas. Implementations are provided of a range of algorithms for tree traversal, target cell selection, and node invariant, including choices from the literature and new variations. The framework readily supports extraction and visualization of detailed data from separate algorithm executions for subsequent analysis and development of new heuristics.<\/jats:p>\n          <jats:p>Using collections of different graph classes, we investigate the effect of varying the selections of heuristics, often revealing exactly which individual algorithmic choice is responsible for particularly good or bad performance. On several benchmark collections, including a newly proposed class of difficult instances, we additionally find that our implementation performs better than the current state-of-the-art tools.<\/jats:p>","DOI":"10.1145\/3356020","type":"journal-article","created":{"date-parts":[[2020,4,11]],"date-time":"2020-04-11T19:42:46Z","timestamp":1586634166000},"page":"1-26","source":"Crossref","is-referenced-by-count":2,"title":["A Generic Framework for Engineering Graph Canonization Algorithms"],"prefix":"10.1145","volume":"25","author":[{"given":"Jakob L.","family":"Andersen","sequence":"first","affiliation":[{"name":"University of Southern Denmark, Odense, Denmark"}]},{"given":"Daniel","family":"Merkle","sequence":"additional","affiliation":[{"name":"University of Southern Denmark, Odense, Denmark"}]}],"member":"320","published-online":{"date-parts":[[2020,4,11]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Retrieved","author":"Andersen Jakob L.","year":"2019","unstructured":"Jakob L. Andersen . 2019 . Benchmark Results on GitHub . Retrieved February 20, 2020 from https:\/\/github.com\/jakobandersen\/graph_canon_res. Jakob L. Andersen. 2019. Benchmark Results on GitHub. Retrieved February 20, 2020 from https:\/\/github.com\/jakobandersen\/graph_canon_res."},{"key":"e_1_2_1_2_1","volume-title":"Retrieved","author":"Andersen Jakob L.","year":"2019","unstructured":"Jakob L. Andersen . 2019 . GraphCanon Repository on GitHub . Retrieved February 20, 2020 from http:\/\/github.com\/jakobandersen\/graph_canon. Jakob L. Andersen. 2019. GraphCanon Repository on GitHub. Retrieved February 20, 2020 from http:\/\/github.com\/jakobandersen\/graph_canon."},{"key":"e_1_2_1_3_1","volume-title":"Retrieved","author":"Andersen Jakob L.","year":"2019","unstructured":"Jakob L. Andersen . 2019 . GraphCanon Visualizer on GitHub . Retrieved February 20, 2020 from http:\/\/jakobandersen.github.io\/graph_canon_vis. Jakob L. Andersen. 2019. GraphCanon Visualizer on GitHub. Retrieved February 20, 2020 from http:\/\/jakobandersen.github.io\/graph_canon_vis."},{"key":"e_1_2_1_4_1","volume-title":"Retrieved","author":"Andersen Jakob L.","year":"2019","unstructured":"Jakob L. Andersen . 2019 . Med\u00d8lDatschgerl (M\u00d8D) . Retrieved February 20, 2020 from http:\/\/mod.imada.sdu.dk. Jakob L. Andersen. 2019. Med\u00d8lDatschgerl (M\u00d8D). Retrieved February 20, 2020 from http:\/\/mod.imada.sdu.dk."},{"key":"e_1_2_1_5_1","volume-title":"Retrieved","author":"Andersen Jakob L.","year":"2019","unstructured":"Jakob L. Andersen . 2019 . PermGroup Repository on GitHub . Retrieved February 20, 2020 from http:\/\/github.com\/jakobandersen\/perm_group. Jakob L. Andersen. 2019. PermGroup Repository on GitHub. Retrieved February 20, 2020 from http:\/\/github.com\/jakobandersen\/perm_group."},{"key":"e_1_2_1_6_1","volume-title":"Retrieved","author":"Andersen Jakob L.","year":"2019","unstructured":"Jakob L. Andersen . 2019 . GraphCanon Results . Retrieved February 20, 2020 from https:\/\/jakobandersen.github.io\/graph_canon_res. Jakob L. Andersen. 2019. GraphCanon Results. Retrieved February 20, 2020 from https:\/\/jakobandersen.github.io\/graph_canon_res."},{"key":"e_1_2_1_7_1","volume-title":"Stadler","author":"Andersen Jakob L.","year":"2016","unstructured":"Jakob L. Andersen , Christoph Flamm , Daniel Merkle , and Peter F . Stadler . 2016 . A software package for chemically inspired graph transformation. In Graph Transformation, R. Echahed and M. Minas (Eds.). Lecture Notes in Computer Science, Vol. 9761 . Springer , 73--88. DOI:https:\/\/doi.org\/10.1007\/978-3-319-40530-8_5 10.1007\/978-3-319-40530-8_5 Jakob L. Andersen, Christoph Flamm, Daniel Merkle, and Peter F. Stadler. 2016. A software package for chemically inspired graph transformation. In Graph Transformation, R. Echahed and M. Minas (Eds.). Lecture Notes in Computer Science, Vol. 9761. Springer, 73--88. DOI:https:\/\/doi.org\/10.1007\/978-3-319-40530-8_5"},{"volume-title":"Proceedings of the 10th International Conference on Graph Transformation (ICGT\u201917), Held as Part of STAF 2017. 54--69","author":"Andersen Jakob L.","key":"e_1_2_1_8_1","unstructured":"Jakob L. Andersen , Christoph Flamm , Daniel Merkle , and Peter F. Stadler . 2017. Chemical graph transformation with stereo-information . In Proceedings of the 10th International Conference on Graph Transformation (ICGT\u201917), Held as Part of STAF 2017. 54--69 . DOI:https:\/\/doi.org\/10.1007\/978-3-319-61470-0_4 10.1007\/978-3-319-61470-0_4 Jakob L. Andersen, Christoph Flamm, Daniel Merkle, and Peter F. Stadler. 2017. Chemical graph transformation with stereo-information. In Proceedings of the 10th International Conference on Graph Transformation (ICGT\u201917), Held as Part of STAF 2017. 54--69. DOI:https:\/\/doi.org\/10.1007\/978-3-319-61470-0_4"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2017.2781724"},{"volume-title":"Handbook of Combinatorics.","author":"Babai L\u00e1szl\u00f3","key":"e_1_2_1_10_1","unstructured":"L\u00e1szl\u00f3 Babai . 1996. Automorphism groups, isomorphism, reconstruction . In Handbook of Combinatorics. Vol. 2 . MIT Press , Cambridge, MA , 1447--1540. L\u00e1szl\u00f3 Babai. 1996. Automorphism groups, isomorphism, reconstruction. In Handbook of Combinatorics. Vol. 2. MIT Press, Cambridge, MA, 1447--1540."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897542"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316356"},{"volume-title":"Proceedings of the 15th Annual ACM Symposium on Theory of Computing (STOC\u201983)","author":"Babai L\u00e1szl\u00f3","key":"e_1_2_1_13_1","unstructured":"L\u00e1szl\u00f3 Babai and Eugene M. Luks . 1983. Canonical labeling of graphs . In Proceedings of the 15th Annual ACM Symposium on Theory of Computing (STOC\u201983) . ACM, New York, NY, 171--183. DOI:https:\/\/doi.org\/10.1145\/800061.808746 10.1145\/800061.808746 L\u00e1szl\u00f3 Babai and Eugene M. Luks. 1983. Canonical labeling of graphs. In Proceedings of the 15th Annual ACM Symposium on Theory of Computing (STOC\u201983). ACM, New York, NY, 171--183. DOI:https:\/\/doi.org\/10.1145\/800061.808746"},{"volume-title":"Proceedings of the 45th Annual Design Automation Conference (DAC\u201908)","author":"Darga Paul T.","key":"e_1_2_1_14_1","unstructured":"Paul T. Darga , Karem A. Sakallah , and Igor L. Markov . 2008. Faster symmetry discovery using sparsity of symmetries . In Proceedings of the 45th Annual Design Automation Conference (DAC\u201908) . ACM, New York, NY, 149--154. DOI:https:\/\/doi.org\/10.1145\/1391469.1391509 10.1145\/1391469.1391509 Paul T. Darga, Karem A. Sakallah, and Igor L. Markov. 2008. Faster symmetry discovery using sparsity of symmetries. In Proceedings of the 45th Annual Design Automation Conference (DAC\u201908). ACM, New York, NY, 149--154. DOI:https:\/\/doi.org\/10.1145\/1391469.1391509"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1186\/s13321-015-0068-4"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972870.13"},{"volume-title":"Conflict Propagation and Component Recursion for Canonical Labeling","author":"Junttila Tommi","key":"e_1_2_1_17_1","unstructured":"Tommi Junttila and Petteri Kaski . 2011. Conflict Propagation and Component Recursion for Canonical Labeling . Springer, Berlin , Germany , 151--162. DOI:https:\/\/doi.org\/10.1007\/978-3-642-19754-3_16 10.1007\/978-3-642-19754-3_16 Tommi Junttila and Petteri Kaski. 2011. Conflict Propagation and Component Recursion for Canonical Labeling. Springer, Berlin, Germany, 151--162. DOI:https:\/\/doi.org\/10.1007\/978-3-642-19754-3_16"},{"key":"e_1_2_1_18_1","volume-title":"Markov","author":"Katebi Hadi","year":"2010","unstructured":"Hadi Katebi , Karem A. Sakallah , and Igor L . Markov . 2010 . Symmetry and satisfiability: An update. In Theory and Applications of Satisfiability Testing\u2014SAT 2010. Springer , 113--127. Hadi Katebi, Karem A. Sakallah, and Igor L. Markov. 2010. Symmetry and satisfiability: An update. In Theory and Applications of Satisfiability Testing\u2014SAT 2010. Springer, 113--127."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/320385.320428"},{"volume-title":"Fast Algorithm for Graph Isomorphism Testing","author":"L\u00f3pez-Presa Jos\u00e9 Luis","key":"e_1_2_1_20_1","unstructured":"Jos\u00e9 Luis L\u00f3pez-Presa and Antonio Fern\u00e1ndez Anta . 2009. Fast Algorithm for Graph Isomorphism Testing . Springer , Berlin, Germany , 221--232. DOI:https:\/\/doi.org\/10.1007\/978-3-642-02011-7_21 10.1007\/978-3-642-02011-7_21 Jos\u00e9 Luis L\u00f3pez-Presa and Antonio Fern\u00e1ndez Anta. 2009. Fast Algorithm for Graph Isomorphism Testing. Springer, Berlin, Germany, 221--232. DOI:https:\/\/doi.org\/10.1007\/978-3-642-02011-7_21"},{"key":"e_1_2_1_21_1","volume-title":"Congressus Numerantium.","volume":"30","author":"McKay Brendan D.","year":"1981","unstructured":"Brendan D. McKay . 1981 . Practical graph isomorphism . In Congressus Numerantium. Vol. 30 . Utilitas Mathematica Publishing Inc., Winnipeg, Manatoba, Canada, 45--97. http:\/\/cs.anu.edu.au\/\u223cbdm\/papers\/pgi.pdf. Brendan D. McKay. 1981. Practical graph isomorphism. In Congressus Numerantium. Vol. 30. Utilitas Mathematica Publishing Inc., Winnipeg, Manatoba, Canada, 45--97. http:\/\/cs.anu.edu.au\/\u223cbdm\/papers\/pgi.pdf."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2013.09.003"},{"key":"e_1_2_1_23_1","volume-title":"Nauty and Traces. Retrieved","author":"Brendan","year":"2020","unstructured":"Brendan D. McKay and Adolfo Piperno. 2017 . Nauty and Traces. Retrieved February 20, 2020 from http:\/\/pallini.di.uniroma1.it\/Graphs.html. Brendan D. McKay and Adolfo Piperno. 2017. Nauty and Traces. Retrieved February 20, 2020 from http:\/\/pallini.di.uniroma1.it\/Graphs.html."},{"volume-title":"Proceedings of the International Symposium on Symbolic and Algebraic Computation. 13--25","author":"David","key":"e_1_2_1_24_1","unstructured":"David R. Musser and Alexander A. Stepanov. 1988. Generic programming . In Proceedings of the International Symposium on Symbolic and Algebraic Computation. 13--25 . David R. Musser and Alexander A. Stepanov. 1988. Generic programming. In Proceedings of the International Symposium on Symbolic and Algebraic Computation. 13--25."},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 25th Annual European Symposium on Algorithms (ESA\u201917)","author":"Neuen Daniel","year":"2017","unstructured":"Daniel Neuen and Pascal Schweitzer . 2017 . Benchmark graphs for practical graph isomorphism . In Proceedings of the 25th Annual European Symposium on Algorithms (ESA\u201917) . Article 60, 14 pages. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ESA. 2017.60 10.4230\/LIPIcs.ESA.2017.60 Daniel Neuen and Pascal Schweitzer. 2017. Benchmark graphs for practical graph isomorphism. In Proceedings of the 25th Annual European Symposium on Algorithms (ESA\u201917). Article 60, 14 pages. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2017.60"},{"key":"e_1_2_1_26_1","volume-title":"Retrieved","author":"Neuen Daniel","year":"2017","unstructured":"Daniel Neuen and Pascal Schweitzer . 2017 . Benchmark Graphs for Practical Graph Isomorphism . Retrieved February 20, 2020 from https:\/\/www.lii.rwth-aachen.de\/research\/95-benchmarks.html. Daniel Neuen and Pascal Schweitzer. 2017. Benchmark Graphs for Practical Graph Isomorphism. Retrieved February 20, 2020 from https:\/\/www.lii.rwth-aachen.de\/research\/95-benchmarks.html."},{"key":"e_1_2_1_27_1","unstructured":"Adolfo Piperno. 2008. Search space contraction in canonical labeling of graphs (preliminary version). arXiv:0804.4881.  Adolfo Piperno. 2008. Search space contraction in canonical labeling of graphs (preliminary version). arXiv:0804.4881."},{"key":"e_1_2_1_28_1","volume-title":"17th International Symposium on Experimental Algorithms (SEA 2018). Leibniz International Proceedings in Informatics","volume":"103","author":"Piperno Adolfo","year":"2018","unstructured":"Adolfo Piperno . 2018 . Isomorphism test for digraphs with weighted edges . In 17th International Symposium on Experimental Algorithms (SEA 2018). Leibniz International Proceedings in Informatics , Vol. 103 , G. D\u2019Angelo (Ed.). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, Article 30, 13 pages. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.SEA. 2018.30 10.4230\/LIPIcs.SEA.2018.30 Adolfo Piperno. 2018. Isomorphism test for digraphs with weighted edges. In 17th International Symposium on Experimental Algorithms (SEA 2018). Leibniz International Proceedings in Informatics, Vol. 103, G. D\u2019Angelo (Ed.). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, Article 30, 13 pages. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.SEA.2018.30"},{"volume-title":"Permutation Group Algorithms","author":"Seress \u00c1koss","key":"e_1_2_1_29_1","unstructured":"\u00c1koss Seress . 2003. Permutation Group Algorithms . Cambridge University Press . \u00c1koss Seress. 2003. Permutation Group Algorithms. Cambridge University Press."},{"key":"e_1_2_1_30_1","unstructured":"Jeremy G. Siek Lie-Quan Lee and Andrew Lumsdaine. 2001. Boost Graph Library: The User Guide and Reference Manual. Pearson Education. http:\/\/www.boost.org\/libs\/graph\/.  Jeremy G. Siek Lie-Quan Lee and Andrew Lumsdaine. 2001. Boost Graph Library: The User Guide and Reference Manual. Pearson Education. http:\/\/www.boost.org\/libs\/graph\/."},{"key":"e_1_2_1_31_1","series-title":"Lecture Notes in Mathematics","volume-title":"On Construction and Identification of Graphs","author":"Weisfeiler Boris","unstructured":"Boris Weisfeiler . 2006. On Construction and Identification of Graphs . Lecture Notes in Mathematics , Vol. 558 . Springer . Boris Weisfeiler. 2006. On Construction and Identification of Graphs. Lecture Notes in Mathematics, Vol. 558. Springer."}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3356020","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3356020","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:13:30Z","timestamp":1750202010000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3356020"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,11]]},"references-count":31,"alternative-id":["10.1145\/3356020"],"URL":"https:\/\/doi.org\/10.1145\/3356020","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2020,4,11]]}}}