[Boost][BGL] New isomorphism test algorithm contribution
Hi, I have been developing a new implementation for test graphs isomorphism, named conauto <http://sites.google.com/site/giconauto/> algorithm (based on José Luis López Presa thesis). I would like to contribute it to BGL. This is a more efficient algorithm than the current one. You can study all its details from conauto thesis at here<http://www.diatel.upm.es/jllopez/tesis/thesis.pdf> . Once developed the first conauto BGL-style version, I am sure that there are many advises and comments that could help to enhance it and eventually will be acceptable for BGL maintainers. Find attached both the source code and some measurements graphics. Please, do not hesitate ask me for any additional information. Best regards, Carlos Cardeñosa.
Hi Jeremiah, Sorry for my delayed answer. This work has been part of my graduate job and I had to write many documentation about that (Unfortunately this was only in Spanish). I am working with José Luis Lopez Presa that, as you can read, is the thesis' author. This just has been our first approach adapting conauto algorithm to BGL requirements, and we are sure that we can enhance it. I am sending you a patch to solve a mistake that avoid the algo detects properly isomorphism with adjacent_list graph. One of the think that conauto doesn't still support it's parallel arcs with directed graphs. I have added a static condition to detect that. You can check it out at line 92 of conauto_sequence_of_patitions.hpp file: // By now, conauto doesn't work for parallel directed graphs BOOST_STATIC_ASSERT((is_same<typename graph_traits<Graph>::directed_category, undirected_tag>::value)); There are others thinks that we want to improve in which we are working on. Once you have check the thesis out, please do not hesitate to ask us about any doubt regarding how conauto algorithm work. We have tested conauto against graphs thesis pool and compare the performance with them. I will send you all our result ASAP (if you consider this unnecessary, please, let me know it). Maybe you would like to compare conauto against your own pool of graphs. If you do so, please tell us your conclusions. Thank you in advance for your interest. BR, Carlos Cardeñosa. On Mon, Nov 8, 2010 at 10:07 AM, Jeremiah Willcock <jewillco@osl.iu.edu>wrote:
On Mon, 17 Jan 2011, Carlos Cardeñosa Pérez wrote:
Hi Jeremiah,
Any feedback regarding our isomorphism detection algorithm?
Do you have tests or documentation for the code? Could you please add in comments that state what the code is doing, data structures used, etc.? Also, could you please rename things (CamelCase and header guards mostly) that do not follow the rules at <URL:http://www.boost.org/development/requirements.html>? There are a few spelling errors in names: patition -> partition discarted -> discarded backtraking -> backtracking automorphims -> automorphisms Maps (such as std::map and std::multimap) from vertices or edges to values should usually be property maps for constant-time lookup. You don't need to use "typedef struct" in C++. In SequenceOfPartitionsList, you should not inherit from std::vector (that is not recommended practice); you can just have your class contain the vector instead. Some of the "this->" method calls would be cleaner that way, too. There should not be any tabs in your C++ files. There will probably be other comments after those are handled; please send a new version when you get a chance. -- Jeremiah Willcock
participants (2)
-
Carlos Cardeñosa Pérez -
Jeremiah Willcock