[Boost-bugs] [Boost C++ Libraries] #5636: BGL isomorphism vertex invariant interface change

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