Subject: [Boost-bugs] [Boost C++ Libraries] #5636: BGL isomorphism vertex invariant interface change
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2011-06-23 22:48:35
#5636: BGL isomorphism vertex invariant interface change
--------------------------------------------------+-------------------------
Reporter: Evan Driscoll <driscoll@â¦> | Owner: asutton
Type: Feature Requests | Status: new
Milestone: To Be Determined | Component: graph
Version: Boost 1.46.1 | Severity: Problem
Keywords: |
--------------------------------------------------+-------------------------
(This is the last isomorphism ticket I think. :-))
I have one more suggestion about how to handle vertex invariants. To
determine whether `u` and `v` should be considered equivalent by the
isomorphism, instead of providing two functors `f` and `g`, calling `f(u)`
and `g(v)` to get a pair of integers, and finally comparing the result, I
think it would be cleaner to have a "binary" predicate `p` which would be
called as `p(u,v)`. (In reality of course you'd probably want to have it
receive `g1` and `g2` as well, so it'd really be a 4-arg function.) This
should also let you get rid of the `vertex_max_invariant` parameter
perhaps.
I'm not sure of how this would impact the performance or how you'd do
sorting, but you could probably do it by doing an N^2 traversal and
recording for each `u` in `g1` how many `v`s in `g2` are considered
equivalent. This is a bit different from what you're doing now, I think.
(The benefit of this would be it becomes easier to impose extra conditions
on the isomorphism. Instead of figuring out how to encode everything into
an integer -- and worrying about the fact that you make an array of size
`vertex_max_invariant`, so you can't even use all that much of that size
-- you can just test it directly.)
-- Ticket URL: <https://svn.boost.org/trac/boost/ticket/5636> Boost C++ Libraries <http://www.boost.org/> Boost provides free peer-reviewed portable C++ source libraries.
This archive was generated by hypermail 2.1.7 : 2017-02-16 18:50:06 UTC