Subject: Re: [boost] [BGL] New isomorphism test algorithm contribution
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2011-01-17 15:07:08
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
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
> 2010/12/6 Carlos Cardeñosa Pérez <ccardenosa_at_[hidden]>
>> 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
>> 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.
>> Carlos Cardeñosa.
>> On Mon, Nov 8, 2010 at 10:07 AM, Jeremiah Willcock <jewillco_at_[hidden]>wrote:
>>> On Sun, 7 Nov 2010, Carlos Cardeñosa Pérez wrote:
>>>> I have been developing a new implementation for test graphs isomorphism,
>>>> named conauto <http://sites.google.com/site/giconauto/> algorithm (based
>>>> José Luis López Presa thesis). I would like to contribute it to BGL. This
>>>> a more efficient algorithm than the current one. You can study all its
>>>> details from conauto thesis at
>>>> Once developed the first conauto BGL-style version, I am sure that there
>>>> many advises and comments that could help to enhance it and eventually
>>>> 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.
>>> Thank you for your contribution. I may not have a chance to look through
>>> it in the next couple of days, though; I'll get back to you later in the
>>> -- Jeremiah Willcock
>>> Unsubscribe & other changes:
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk