Libcanon is a C++ library for canonicalizing combinatorial objects with lightening speed by full utilization of the isomorphism of the combinatorial objects.
In addition to being a fully-templated generic library for the canonicalization of any combinatorial objects, from its root in symbolic manipulation of tensorial quantities, libcanon has direct support for the canonicalization of strings and edge-labelled directed acyclic graphs (ELDAG).
Here a string over an alphabet is any sequence of elements in that alphabet. By giving any string and a group of allowed permutations, libcanon is able to get the lexicographically minimal form of the string by using only the allowed permutations.
ELDAGs are special kind of DAGs where each edge comes with an label such that
the children of any node all has distinct labels. This structure is a
specialization of common DAGs and is defined for the storage and manipulation
mathematical expressions with non-commutative operations. For instance, to
store the mathematical expression of a simple function call, f(1, 2), we can
have an ELDAG with nodes for f, 1, and 2, an edge from f to 1 with
label 0, and an edge from f to 2 with label 1. Then libcanon is able to
give a unique canonical form for any ELDAG given the allowed permutations on
each internal node. Canonicalization of normal directed and undirected graphs
can also be reduced to ELDAG canonicalized. Actual direct support of plain
graph canonicalization is to be implemented.
This project uses release-please for automated release management. Releases are automatically created when changes are merged to the master branch following Conventional Commits format. The CHANGELOG is automatically maintained based on commit messages.
Libcanon was developed by Jinmo Zhao at Rice University, under the supervision of Prof. Gustavo E. Scuseria, as a component of the symbolic tensorial algebra system drudge. It was supported as part of the Center for the Computational Design of Functional Layered Materials, an Energy Frontier Research Center funded by the U.S. Department of Energy, Office of Science, Basic Energy Sciences under Award DE-SC0012575. The package is currently maintained by Guo P. Chen and other members of the Scuseria group.