New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Nauty interface for isomorphism checking and automorphism group computing #25506
Comments
Commit: |
comment:2
Notice that it still lacks properly formatted comments, so it's still not ready for review New commits:
|
Changed keywords from graphs nauty pynauty automorphism isomorphism to graphs nauty pynauty automorphism isomorphism, gsoc2018 |
comment:4
Thanks for the contribution. I'm not expert in nauty or creating interfaces, but instead of creating a new file Concerning the method itself, you don't need to convert the graph to a (slow and space consuming) dictionary. You can access the list of multiple edges of the graph with
Another issue is that you assume edge labels to be integers, but we can have floats, rationals, list, dict, etc. It's clearly easier to use pynauty, but it's a petty we cannot convert the graph directly to the data structure used by nauty. |
comment:5
Thanks for your input. Regarding the file with the multiedge conversion, I admit the name is not the best, but I didn't put it inside the nauty interface because it's a general method, it converts a sage multigraph in a suitable sage graph with only single edges, following the method outlined in the provided link. I was thinking of moving it inside generic_graph.pyx, but didn't want to take the decision all on my own. If you think it's better, I'll gladly move it though. Also, thanks for the suggestion on the method. I don't recall why I chose to use a dictionary, probably because I didn't think to use the multiple_edges -> edge_label combo, and I wanted to be able to quickly find the multiplicity of any edge in the graph. I'll rework that part to avoid transforming the graph into a dictionary. About the import, it's mostly due to experiments I've been running to understand how the importing works in sagemath. Without that line (or any line about pynauty) in all.py, I had to manually import the module in sagemath, but even with that line I wasn't able to limit what sage imports, getting instead the entire list of all the objects inside the module. If the method is moved in generic_graph.pyx I'll have to remove the entry anyway. I don't think I ever assume edge labels to be integers, could you show me where I did that? It's probably an error or bug if I did. Actually, that's the reason why I said I can't use edge_labels at the moment, because I'm trying to see if substituting edge labels with integers (to use the technique suggested in section 14 of the nauty guide) would cause any issues. Lastly, while I started with converting the graph in pynauty format and then letting pynauty do its thing, in this version the sage graph is actually converted directly into nauty format (but this is done for every call to automorphism_group or is_isomorphic, so there's that). Nonetheless, the main skeleton of the module, all the code that manages calling nauty and setting up data structures, etc. is still pynauty's, I just switched out its graph format for sage's and set the output format accordingly, so that's why I still call it pynauty, and it's still based on its source code. If you have any other suggestions or issues, please tell me, I'll be working on the problems you highlighted in the meantime. |
comment:6
Replying to @sagetrac-Vaush:
Yes, do it.
You call |
comment:7
Replying to @dcoudert:
I see how that might be misleading, but I think I only call that function on a dictionary that I created, that associates each edge in the graph with its multiplicity, so I am sure that "label" is an int because that's the multiplicity of the edge |
Branch pushed to git repo; I updated commit sha1. New commits:
|
comment:9
Could you explain what's the goal of this method and what it does. You will have to add a description of the method anyway. Also, shouldn't original edge labels be added somewhere ? |
comment:10
Replying to @dcoudert:
So the entire goal of this method is to account for the impossibility of managing multiple edges (and in the future, edge labels) in a graph with nauty. So right now it works with multiplicities, I am trying to find a way to include arbitrary edge labels, but since it's an auxiliary graph I didn't see the point in adding the edge labels. I can do it, but they would just become a nice ornament, not really used for anything (at least not in nauty). |
comment:11
As far as I understand, it's more or less the code written by stumpc5 - although for bliss rather than for nauty, and the idea is to make it more general, so that it can be used for nauty as well as for bliss as "backends" to compute automorphisms etc. |
comment:12
Right, but with bliss we are at Cython/C level so it might be faster. We'll see if the performances are OK. |
comment:13
I don't really know how pynauty, the interface used, works (Dario, the ticket's author, knows better). My limited understanding that it's also an interface on the level of C, thus it should be fast. |
comment:14
Actually, while the conversion to a nauty graph and the computation is in c, the relabeling and eventual conversion of the multigraph are done in python. I could easily move the relabeling to C++, the multigraph part would be a little more difficult, but still doable. I don't know if this would be that much of an improvement in performance though, that's why I didn't do it in the first place. |
comment:16
So, I commented and added doctests. I run into a quite nasty bug though, which I couldn't really pinpoint or fix, I could just find a workaround. |
Branch pushed to git repo; I updated commit sha1. New commits:
|
comment:18
So, dimpase made me notice that the code I wrote had a few issues for people who don't actually have pynauty installed or even downloaded. |
comment:19
the tarball will be mirrored once the ticket id merged. |
Dependencies: #25391 |
comment:21
Replying to @sagetrac-Vaush: Why do you need this dependence? This is potentially misleading, and won't get this ticket in before #25391. This is certainly not what we want. |
comment:22
I see, I added it because on my system I needed #25391 to compile sage, so the branch is initially merged with the one from that ticket. Since the branches are merged, and since I can't have them not merged because otherwise sage won't compile at all for me, I thought I had to list it as a dependency. Is there another way to go about it? |
comment:23
Replying to @sagetrac-Vaush:
Sure, just don't merge these branches on trac, only merge them on your machine. |
Branch pushed to git repo; I updated commit sha1. New commits:
|
comment:25
Ok, I just deleted the old branch, and created a new one that doesn't merge with ticket #25391. If anyone has checked out the branch previously, could you please delete your copy and check it out again. |
comment:26
What exactly the need for that mega-patch of |
Changed dependencies from #25391 to none |
comment:28
Replying to @dimpase:
The mega patch is my work, basically all the changes I made to pynauty so that it could interact with sage graphs directly, use multigraphs and labelled graphs, output automorphism groups in a decent format, etc. |
comment:29
I have the following comments on method
In fact we use:
|
Branch pushed to git repo; I updated commit sha1. New commits:
|
comment:31
Replying to @dcoudert:
Sure, I don't see any particular upside to making this changes, but if you think they're for the better, I don't see any downsides either, so I made them. |
comment:34
(without it, tests fail in |
Branch pushed to git repo; I updated commit sha1. New commits:
|
comment:37
red branch => needs work |
I used the pynauty library (https://web.cs.dal.ca/~peter/software/pynauty/html/intro.html#), which has GPLv3+ license by the way, to interface with our pynauty package and use it to check for isomorphism and compute automorphisms through the standard sage methods.
In particular, I am actually copying the package from upstream, patching it and recompiling it, since pynauty wrappers require to be compiled with nauty's own source code.
A lot of modifications where required to make the transition from sage's own graph representation to one that nauty was able to understand.
At the moment this interface doesn't support arbitrary edge labels, but it supports multi-edge graphs through an helper function that converts them in equivalent single-edge graphs (http://pallini.di.uniroma1.it/Guide.html section 14) that I put in sage.graphs.multiedge for everyone to use.
The efficiency is not exactly spectacular, since the graph needs to be relabeled with labels going from 0 to n-1 (where n is the number of vertices), and thus a copy needs to be made and the relabel function needs to be called. If, by chance, the graph is already labelled in that way, there is an option to tell the interface not to relabel the graph. If the relabeling is found to be too inefficient, it could be implemented in the C++ part of the interface, but then a lot of the conversions done to return sensible results (i.e. return automorphism group generators listing the actual nodes' labels, and not arbitrary labels in {0..n-1}) would have to be moved too.
Modifications were made to also output results in the exact same format of the standard sage methods.
Last, I noted that a version of the same algorithm I used to convert multi-edged graphs to their single edge version was implemented in the Bliss module (but only for Bliss graphs), in #24924; it might be worth it to change it to use this more general version, if needs allow it.
CC: @dimpase @stumpc5 @dcoudert
Component: graph theory
Keywords: graphs nauty pynauty automorphism isomorphism, gsoc2018
Branch/Commit: u/Vaush/nauty_interface_automorphism_isomorphism @
a907f60
Issue created by migration from https://trac.sagemath.org/ticket/25506
The text was updated successfully, but these errors were encountered: