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