{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T01:39:51Z","timestamp":1760146791727,"version":"build-2065373602"},"reference-count":57,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2024,12,11]],"date-time":"2024-12-11T00:00:00Z","timestamp":1733875200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12371508"],"award-info":[{"award-number":["12371508"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>Practical algorithms for computing canonical forms of multi-digraphs do not exist in the literature. This paper proposes two practical approaches for finding canonical forms, from the perspective of nD symbolic computation. Initially, the approaches turn the problem of finding canonical forms of multi-digraphs into computing canonical forms of indexed monomials in computer algebra. Then, the first approach utilizes the double coset representative method in computational group theory for canonicalization of indexed monomials and shows that finding the canonical forms of a class of multi-digraphs in practice has polynomial complexity of approximately O((k+p)2) or O(k2.1) by the computer algebra system (CAS) tool Tensor-canonicalizer. The second approach verifies the equivalence of canonicalization of indexed monomials and finding canonical forms of (simple) colored tripartite graphs. It is found that the proposed algorithm takes approximately O((k+2p)4.803) time for a class of multi-digraphs in practical implementation, combined with one of the best known graph isomorphism tools Traces, where k and p are the vertex number and edge number of a multi-digraph, respectively.<\/jats:p>","DOI":"10.3390\/sym16121638","type":"journal-article","created":{"date-parts":[[2024,12,11]],"date-time":"2024-12-11T06:44:05Z","timestamp":1733899445000},"page":"1638","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Practical Canonical Labeling of Multi-Digraphs via Computer Algebra"],"prefix":"10.3390","volume":"16","author":[{"given":"Jiang","family":"Liu","sequence":"first","affiliation":[{"name":"Department of Systems Science, University of Shanghai for Science and Technology, Shanghai 200093, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Siyu","family":"Yang","sequence":"additional","affiliation":[{"name":"Business School, University of Shanghai for Science and Technology, Shanghai 200093, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wencheng","family":"Liu","sequence":"additional","affiliation":[{"name":"School of Environment and Architecture, University of Shanghai for Science and Technology, Shanghai 200093, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Feng","family":"Ni","sequence":"additional","affiliation":[{"name":"Department of Systems Science, University of Shanghai for Science and Technology, Shanghai 200093, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chenfan","family":"Zhu","sequence":"additional","affiliation":[{"name":"Business School, University of Shanghai for Science and Technology, Shanghai 200093, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2024,12,11]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1016\/j.jsc.2013.09.003","article-title":"Practical graph isomorphism, II","volume":"60","author":"McKay","year":"2014","journal-title":"J. Symb. Comput."},{"key":"ref_2","unstructured":"Babai, L., and Luks, E.M. (1983, January 25\u201327). Canonical labeling of graphs. Proceedings of the 15th Annual ACM Symposium on Theory of Computing, Boston, MA, USA."},{"key":"ref_3","unstructured":"Ivanciuc, O. (2008). Canonical numbering and constitutional symmetry. Handbook of Chemoinformatics, Wiley\u2013VCH Verlag GmbH."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1109\/TSMC.1974.5409142","article-title":"Optimum featurs and graph isomorphism","volume":"3","author":"Shah","year":"1974","journal-title":"IEEE Trans. Syst. Man Cybern."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1145\/3372123","article-title":"The graph isomorphism problem","volume":"63","author":"Grohe","year":"2020","journal-title":"Commun. ACM"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Babai, L. (2019, January 23\u201326). Canonical form for graphs in quasipolynomial time. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, Phoenix, AZ, USA.","DOI":"10.1145\/3313276.3316356"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Babai, L. (2016, January 19\u201321). Graph isomorphism in quasipolynomial time. Proceedings of the 48th Annual ACM Symposium on Theory of Computing, Cambridge, MA, USA.","DOI":"10.1145\/2897518.2897542"},{"key":"ref_8","unstructured":"Huan, J., Wang, W., and Prins, J. (2003, January 19\u201322). Efficient mining of frequent subgraphs in the presence of isomorphism. Proceedings of the 3rd IEEE International Conference on Data Mining, Melbourne, FL, USA."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1007\/s10618-005-0003-9","article-title":"Finding frequent patterns in a large sparse graph","volume":"11","author":"Kuramochi","year":"2005","journal-title":"Data Min. Knowl. Discov."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1038","DOI":"10.1109\/TKDE.2004.33","article-title":"An efficient algorithm for discovering frequent subgraphs","volume":"16","author":"Kuramochi","year":"2004","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"657","DOI":"10.1016\/j.jfranklin.2005.04.006","article-title":"Some further development on the eigensystem approach for graph isomorphism detection","volume":"342","author":"He","year":"2005","journal-title":"J. Frankl. Inst. Eng. Appl. Math."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Kashani, Z., Ahrabian, H., Elahi, E., Nowzari\u2013Dalini, A., Ansari, E., Asadi, S., Mohammadi, S., Schreiber, F., and Masoudi-Nejad, A. (2009). Kavosh: A new algorithm for finding network motifs. BMC Bioinform., 10.","DOI":"10.1186\/1471-2105-10-318"},{"key":"ref_13","unstructured":"Arvind, V., Das, B., and K\u00f6bler, J. (2008, January 7\u201312). A logspace algorithm for partial 2\u2013tree canonization. Proceedings of the 3rd International Computer Science Symposium in Russia, Moscow, Russia."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1007\/BF01994877","article-title":"Canonical representations of partial 2\u2013 and 3\u2013trees","volume":"32","author":"Arnborg","year":"1992","journal-title":"BIT"},{"key":"ref_15","unstructured":"Parris, R., and Read, R.C. (1969). A Coding Procedure for Graphs, University of West Indies Computer Centre. Scientific Report UWI\/CC 10."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1145\/321556.321562","article-title":"An efficient algorithm for graph isomorphism","volume":"17","author":"Corneil","year":"1970","journal-title":"J. ACM"},{"key":"ref_17","first-page":"737","article-title":"An algorithm for the reduction of finite non\u2013oriented graphs to canonical form","volume":"14","author":"Arlazarov","year":"1974","journal-title":"\u017d. Vycisl. Mat. Mat. Fiz."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1007\/BFb0062536","article-title":"Computing automorphisms and canonical labellings of graphs","volume":"Volume 686","author":"McKay","year":"1978","journal-title":"Combinatorial Mathematics"},{"key":"ref_19","first-page":"45","article-title":"Practical graph isomorphism","volume":"30","author":"McKay","year":"1980","journal-title":"Congr. Numer."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Junttila, T., and Kaski, P. (2007, January 6). Engineering an efficient canonical labeling tool for large and sparse graphs. Proceedings of the 9th Workshop on Algorithm Engineering and Experiments and the 4th Workshop on Analytic Algorithms and Combinatorics, New Orleans, LA, USA.","DOI":"10.1137\/1.9781611972870.13"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Junttila, T., and Kaski, P. (2011, January 18\u201320). Conflict propagation and component recursion for canonical labeling. Proceedings of the 1st International ICST Conference on Theory and Practice of Algorithms, Rome, Italy.","DOI":"10.1007\/978-3-642-19754-3_16"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"L\u00f3pez\u2013Presa, J.L., and Fern\u00e1ndez Anta, A. (2009, January 4\u20136). Fast algorithm for graph isomorphism testing. Proceedings of the 8th International Symposium on Experimental Algorithms, Dortmund, Germany.","DOI":"10.1007\/978-3-642-02011-7_21"},{"key":"ref_23","unstructured":"L\u00f3pez\u2013Presa, J.L., Fern\u00e1ndez Anta, A., and N\u00fa\u00f1ez Chiroque, L. (2011). Conauto\u20132.0: Fast isomorphism testing and automorphism group computation. arXiv."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Darga, P.T., Liffiton, M.H., Sakallah, K.A., and Markov, I.L. (2004, January 7\u201311). Exploiting structure in symmetry detection for CNF. Proceedings of the 41st Design Automation Conference, San Diego, CA, USA.","DOI":"10.1145\/996566.996712"},{"key":"ref_25","unstructured":"Piperno, A. (2008). Search space contraction in canonical labeling of graphs. arXiv."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Hao, J., Gong, Y., Wang, Y., Tan, L., and Sun, J. (2017). Using k\u2013mix\u2013neighborhood subdigraphs to compute canonical labelings of digraphs. Entropy, 19.","DOI":"10.3390\/e19020079"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"3475","DOI":"10.1016\/j.dam.2008.02.002","article-title":"An efficient distributed algorithm for canonical labeling on directed split\u2013stars","volume":"156","author":"Wang","year":"2008","journal-title":"Discret. Appl. Math."},{"key":"ref_28","first-page":"89","article-title":"Groebner bases and graph colorings","volume":"36","year":"1995","journal-title":"Beitr. Algebra Geom."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"De Loera, J.A., Lee, J., Malkin, P.N., and Margulies, S. (2008, January 20\u201323). Hilbert\u2019s Nullstellensatz and an algorithm for proving combinatorial infeasibility. Proceedings of the 21st Annual Meeting of the International Symposium on Symbolic Computation, ISSAC, Linz, Austria.","DOI":"10.1145\/1390768.1390797"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1017\/S0963548309009894","article-title":"Expressing combinatorial optimization problems by systems of polynomial equations and the Nullstellensatz","volume":"18","author":"Lee","year":"2009","journal-title":"Comb. Probab. Comput."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"De Loera, J.A., Margulies, S., Pernpeintner, M., Riedl, E., Rolnick, D., Spencer, G., Stasi, D., and Swenson, J. (2015, January 6\u20139). Graph\u2013coloring ideals: Nullstellensatz certificates: Groebner bases for chordal graphs, and hardness of Groebner bases. Proceedings of the 40th ACM International Symposium on Symbolic and Algebraic Computation, ISSAC, Bath, UK.","DOI":"10.1145\/2755996.2756639"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"103","DOI":"10.18514\/MMN.2013.428","article-title":"Note on Groebner bases and graph colorings","volume":"14","author":"Hashemi","year":"2013","journal-title":"Miskolc Math. Notes"},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Mnuk, M. (2001, January 22\u201326). Representing graph properties by polynomial ideals. Proceedings of the 4th International Workshop on Computer Algebra in Scientific Computing (CASC), Constance, Germany.","DOI":"10.1007\/978-3-642-56666-0_33"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"2401","DOI":"10.1023\/B:JOTH.0000024621.54839.40","article-title":"Some algebraic methods for calculation of the number of colorings of a graph","volume":"121","author":"Matiyasevich","year":"2004","journal-title":"J. Math. Sci."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1016\/j.jctb.2007.08.004","article-title":"Algebraic characterization of uniquely vertex colorable graphs","volume":"98","author":"Hillar","year":"2008","journal-title":"J. Comb. Theory Ser. B"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"P3.33","DOI":"10.37236\/6156","article-title":"Groebner bases techniques for an S\u2013packing k\u2013coloring of a graph","volume":"24","author":"Maarouf","year":"2017","journal-title":"Electron. J. Comb."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/BF02579177","article-title":"Independence number of graphs and generators of ideals","volume":"1","author":"Li","year":"1981","journal-title":"Combinatorica"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/BF01204715","article-title":"Colorings and orientations of graphs","volume":"12","author":"Alon","year":"1992","journal-title":"Combinatorica"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/0012-365X(88)90051-9","article-title":"Symmetric polynomials and Hall\u2019s theorem","volume":"69","author":"Fischer","year":"1988","journal-title":"Discret. Math."},{"key":"ref_40","unstructured":"Obeid, N. (2001). On the Simplification of Tensor Expressions. [Master\u2019s Thesis, Department of Computer Science, University of Western Ontario]."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"569","DOI":"10.1007\/s11424-017-6325-z","article-title":"Normalization in Riemann tensor polynomial ring","volume":"31","author":"Liu","year":"2018","journal-title":"J. Syst. Sci. Complex."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"1708","DOI":"10.1007\/s11424-020-9135-7","article-title":"An extension of Gr\u00f6bner basis theory to indexed polynomials without eliminations","volume":"33","author":"Liu","year":"2020","journal-title":"J. Syst. Sci. Complex."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"2016","DOI":"10.1007\/s11424-021-0302-2","article-title":"Normalization of indexed differentials by extending Gr\u00f6bner basis theory","volume":"35","author":"Liu","year":"2022","journal-title":"J. Syst. Sci. Complex."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/S0010-4655(98)00117-9","article-title":"An algorithm to simplify tensor expressions","volume":"115","author":"Portugal","year":"1998","journal-title":"Comput. Phys. Commun."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"7779","DOI":"10.1088\/0305-4470\/32\/44\/313","article-title":"Algorithmic simplification of tensor expressions","volume":"32","author":"Portugal","year":"1999","journal-title":"J. Phys. A Math. Gen."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/S0010-4655(99)00480-4","article-title":"The Riegeom package: Abstract tensor calculation","volume":"126","author":"Portugal","year":"2000","journal-title":"Comput. Phys. Commun."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"859","DOI":"10.1142\/S0129183102004571","article-title":"Group-theoretic approach for symbolic tensor manipulation","volume":"13","author":"Manssur","year":"2002","journal-title":"Internat. J. Modern Phys. C"},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/S0010-4655(03)00494-6","article-title":"The Canon package: A fast kernel for tensor manipulators","volume":"157","author":"Manssur","year":"2004","journal-title":"Comput. Phys. Commun."},{"key":"ref_49","unstructured":"Li, Z., Shao, S., and Liu, W. (2016). Classifications and canonical forms of tensor product expressions in the presence of permutation symmetries. arXiv."},{"key":"ref_50","doi-asserted-by":"crossref","unstructured":"Li, H.B., Li, Z., and Li, Y. (2017, January 25\u201328). Riemann tensor polynomial canonicalization by graph algebra extension. Proceedings of the 42th ACM International Symposium on Symbolic and Algebraic Computation, Kaiserslautern, Germany.","DOI":"10.1145\/3087604.3087625"},{"key":"ref_51","doi-asserted-by":"crossref","unstructured":"Liu, J. (2017, January 18\u201322). Normalization of indexed differentials based on function distance invariants. Proceedings of the 19th International Workshop on Computer Algebra in Scientific Computing, Beijing, China.","DOI":"10.1007\/978-3-319-66320-3_21"},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1145\/3377006.3377019","article-title":"Block distance invariant method for monoterm canonicalization of Riemann tensor polynomials","volume":"53","author":"Liu","year":"2019","journal-title":"ACM Commun. Comput. Algebra"},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/j.jsc.2020.05.001","article-title":"Distance invariant method for normalization of indexed differentials","volume":"104","author":"Liu","year":"2021","journal-title":"J. Symb. Comput."},{"key":"ref_54","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1016\/j.cpc.2008.05.009","article-title":"xPerm: Fast index canonicalization for tensor computer algebra","volume":"179","year":"2008","journal-title":"Comput. Phys. Commun."},{"key":"ref_55","doi-asserted-by":"crossref","first-page":"550","DOI":"10.1016\/j.cpc.2007.01.003","article-title":"A field-theory motivated approach to symbolic computer algebra","volume":"176","author":"Peeters","year":"2007","journal-title":"Comput. Phys. Commun."},{"key":"ref_56","doi-asserted-by":"crossref","first-page":"e103","DOI":"10.7717\/peerj-cs.103","article-title":"SymPy: Symbolic computing in Python","volume":"3","author":"Meurer","year":"2017","journal-title":"PeerJ Comput. Sci."},{"key":"ref_57","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/j.cpc.2018.02.014","article-title":"Faster tensor canonicalization","volume":"228","author":"Niehoff","year":"2018","journal-title":"Comput. Phys. Commun."}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/16\/12\/1638\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T16:52:22Z","timestamp":1760115142000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/16\/12\/1638"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,11]]},"references-count":57,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2024,12]]}},"alternative-id":["sym16121638"],"URL":"https:\/\/doi.org\/10.3390\/sym16121638","relation":{},"ISSN":["2073-8994"],"issn-type":[{"type":"electronic","value":"2073-8994"}],"subject":[],"published":{"date-parts":[[2024,12,11]]}}}