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 01:50:42


Hi Jeremiah,

Any feedback regarding our isomorphism detection algorithm?

BR,
Carlos.

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk