igraph
A Function to Compute Topologically Equivalent Vertices ("Orbits")
What is the feature or improvement you would like to see?
A function for computing which vertices are topologically equivalent, or "orbits"? For reference, this can be accomplished using pynauty using the following command:
pynauty.autgrp(g)[3]
where g is a pynauty graph object. The ideal function would reduce computation by reporting both:
- Canonical ordering/permutation
- Orbit assignment as a vector, where each vertex is assigned a number, and vertices with the same number are topologically equivalent.
A function that reports both would likely be most performant in my application, where I need both. Nonetheless, even a standalone function that just reports orbits would be very useful.
Use cases for the feature
This, in conjunction with canonical labeling, is required for some graph canonization tasks. igraph_canonical_permutation is great for determining the canonical permutation of graph vertices, but we often want to also know which of these vertices are topologically equivalent.
At the moment, inability to compute orbits prevents me from using igraph.
References
See pynauty's autogrp function: https://pypi.org/project/pynauty/
Very likely, this is already being computed by BLISS, and bindings just needsto be added to the igraph API.
I have some efficient orbit computation code in IGraph/M, it could be ported to the C core. It's currently in C++. https://github.com/szhorvat/IGraphM/blob/master/IGraphM/LibraryResources/Source/IG.cpp#L464
Looks like orbits can be comptued from automorphism groups, e.g those computed from igraph_automorphism_group.
However, it looks like those aren't available in the python bindings. I added a request in the igraph-python github.
@ntamas I think you accidentally closed the wrong issue. This is a feature request for the C core, and it hasn't been implemented yet.
Isn't this basically the same as igraph_automorphism_group()? What are the key differences?
igraph_automorphism_group() returns a list of permutations, a generating set of the automorphism group. Computing the orbits of the group means partitioning the vertices into equivalence classes so that vertices within the same class can be transformed into each other by applying some group element (permuting vertices according to that group element). To compute the orbits, we need to take each vertex one by one, apply each generator to see what it transforms that vertex into, and merge equivalence classes accordingly.
To be fair, finding the orbits is in the realm of group theory, not graph theory. My recommendation to @swamidass is to find a group theory package, and use that to work with the group computed by igraph. However, the two fields are not entirely separable, and there are of course graph theory concepts that depend on orbits, e.g. checking if a graph is vertex transitive. Given that computing orbits is not hard, I'd be in favour of including this in C/igraph. In fact it's already in IGraph/M. But we can't possibly provide full group theory functionality—there are good specialized packages for that.
igraph_automorphism_group is not the same as computing the topological equivalence. However, it is fairly straightfoward to compute the equivalence groups from the automorphism groups. I can implement this myself.
@szhorvat thank you for adding the bindings to igraph_automorphism_group. I can take it from here. If you'd like code to show how to convert groups to equivance labels, let me know. I'm happy to share it.
Thanks for the wishlist! Could I ask if it is possible to have a function to identify node orbits and edge orbits? Very eager for this implementation in R!
