Boost logo

Boost :

Subject: Re: [boost] [BGL] New isomorphism test algorithm contribution
From: Carlos Cardeñosa Pérez (ccardenosa_at_[hidden])
Date: 2011-01-17 16:06:29


Thanks a lot for your feedback.

I will send you all these thing as soon as possible.

BR,
Carlos.

On Mon, Jan 17, 2011 at 9:07 PM, Jeremiah Willcock <jewillco_at_[hidden]>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
>
>
>
> 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
>>> 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_at_[hidden]
>>> >wrote:
>>>
>>> On Sun, 7 Nov 2010, Carlos Cardeñosa Pérez wrote:
>>>>
>>>> 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.
>>>>>
>>>>>
>>>> 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
>>>> week.
>>>>
>>>> -- Jeremiah Willcock
>>>> _______________________________________________
>>>> Unsubscribe & other changes:
>>>> http://lists.boost.org/mailman/listinfo.cgi/boost
>>>>
>>>>
>>>
>>> _______________________________________________
>> Unsubscribe & other changes:
>> http://lists.boost.org/mailman/listinfo.cgi/boost
>>
>
> _______________________________________________
> 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