Re: [Boost-users] graph library : isomorphism.hpp vertex invariant parameter

From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2007-06-13 08:56:38

On 6/12/07, Patrick A. La Fratta <plafratt_at_[hidden]> wrote:
> Setting the "vertex_invariant" parameter to the isomorphism function does
> not seem to have any affect on the behavior of the function. In
> isomorphism.hpp, it appears that the function "isomorphism_impl" is supposed
> to read the parameter at the return statement:
>
> return isomorphism(G1, G2, f,
> choose_param(get_param(params, vertex_invariant1_t()), invariant1),
> choose_param(get_param(params, vertex_invariant2_t()), invariant2),
> choose_param(get_param(params, vertex_max_invariant_t()), (
> invariant2.max)()),
> index_map1, index_map2
> );
>
> If "vertex_invariant1_t()" and "vertex_invariant2_t()" are both changed to
> "vertex_invariant_t()", the setting of the parameter then seems to have an
> affect. Has anyone been able to successfully set the vertex_invariant
> parameter using the named parameter version of the isomorphism function? I
> have had to resort to calling one of the internal isomorphism functions to
> set this parameter.
>
> any help is appreciated,
> Patrick

Hi Patrick,

It appears that the algorithm implementation diverged a little from
the documentation. The docs mention a "vertex_invariant" named
parameter whose operator() must work on both graphs passed in to the
isomorphism function - this was later replaced with two separate
vertex invariant functors - "vertex_invariant1" and
"vertex_invariant2", which could be applied to the first and second
input graph, respectively. You're right, though, the named parameter
mechanism wasn't fully set up to handle this when this change was
made.

If you'd like, use the diff I've appended to this email to patch the
file boost/graph/named_params.hpp. This patch just adds some necessary
definitions so that you can actually use vertex_invariant1 and
vertex_invariant2 as named parameters in the function, like so:

MyVertexInvariant1 my_invariant1;
MyVertexInvariant2 my_invariant2;

bool are_isomorphic = isomorphism(g1,g2, isomorphism_map(my_isomorphism_map)
                                .vertex_index1_map(my_vertex_index_map1)
                                .vertex_index2_map(my_vertex_index_map2)
                                .vertex_invariant1(my_invariant1)
                                .vertex_invariant2(my_invariant2));

Does anyone object if I commit this patch to HEAD and update the
documentation for isomorphism to reflect the two separate vertex
invariant named parameters?

Regards,
Aaron

----------------------------------------------------------------------------------------------------------

286a287,300
>     template <typename VertexInvar>
>     bgl_named_params<VertexInvar, vertex_invariant1_t, self>
>     vertex_invariant1(const VertexInvar& c) const {
>       typedef bgl_named_params<VertexInvar, vertex_invariant1_t, self> Params;
>       return Params(c, *this);
>     }
>
>     template <typename VertexInvar>
>     bgl_named_params<VertexInvar, vertex_invariant2_t, self>
>     vertex_invariant2(const VertexInvar& c) const {
>       typedef bgl_named_params<VertexInvar, vertex_invariant2_t, self> Params;
>       return Params(c, *this);
>     }
>
549a564,577
>   template <typename VertexInvar>
>   bgl_named_params<VertexInvar, vertex_invariant1_t>
>   vertex_invariant1(const VertexInvar& c) {
>     typedef bgl_named_params<VertexInvar, vertex_invariant1_t> Params;
>     return Params(c);
>   }
>
>   template <typename VertexInvar>
>   bgl_named_params<VertexInvar, vertex_invariant2_t>
>   vertex_invariant2(const VertexInvar& c) {
>     typedef bgl_named_params<VertexInvar, vertex_invariant2_t> Params;
>     return Params(c);
>   }
>