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

Subject: Re: [boost] [BGL] New isomorphism test algorithm contribution
From: Carlos Cardeñosa Pérez (ccardenosa_at_[hidden])
Date: 2010-12-06 06:06:27

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
>