Re: [boost] [BGL] New isomorphism test algorithm contribution

Subject: Re: [boost] [BGL] New isomorphism test algorithm contribution
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2011-01-17 01:56:11

On Mon, 17 Jan 2011, Carlos Cardeñosa Pérez wrote:

> Hi Jeremiah,
>
> Any feedback regarding our isomorphism detection algorithm?

No -- I probably forgot about it while I was busy.  I'll take a look in 
the next few days.

-- 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
>