Re: [boost] [BGL] Testing a graph for bipartiteness

Subject: Re: [boost] [BGL] Testing a graph for bipartiteness
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-03-06 12:36:42

On Sat, 6 Mar 2010, Matthias Walter wrote:

>>> I experimented with some solutions and don't really like the
>>> hook-calling by hand. As you seem to like something really generic, I
>>> finally decided to go with the VisitorEventList, i.e. I split the
>>> functionality into bipartition_colorize, bipartiton_check and
>>> property_put functors which are then thrown together in the DFS call.
>>>
>>> The latter might be worth including into visitors.hpp, I think: It takes
>>> a property map plus a value of it and just sets the value when called. I
>>> use this to initialize the start vertex to be white, but it doesn't
>>> require the property map to be a color map and can work on vertices and
>>> edges and thus all possible visitors. But this is up to you to move it
>>> to visitors.hpp if you like it.
>>
>> I put it in visitors.hpp and added documentation in
>> libs/graph/doc/property_put.html; please see what you think of it.
>
> Looks good! Modified the version on Boost Vault to use it from there.

OK.  I'm looking at the mismatch version of common ancestor removal and
it's starting to look overly complicated.  I think it would be better if
you put back the first version (that does iterated pop_back()s); maybe
change it so it keeps two iterators that walk backwards and then you do
a single erase() to the end of each container (or only copy up to each
iterator).  Here is the sort of thing I'm thinking of (not tested):

template <typename SeqA, typename SeqB>
void remove_common_suffix(SeqA& a, SeqB& b) {
   if (a.empty() || b.empty()) return;
   typename SeqA::iterator ai = a.end();
   typename SeqB::iterator bi = b.end();
   while (true) {
     // Invariant: a.end() - ai == b.end() - bi
     --ai;
     --bi;
     if (*ai != *bi) {++ai; ++bi; break;}
     if (ai == a.begin()) break; // a is a suffix of or equal to b
     if (bi == b.begin()) break; // b is a suffix of a
   }
   // Possible cases when we get here:
   // a == b: ai == a.begin() && bi == b.begin()
   // a is a suffix of b: ai == a.begin() && bi == b.end() - a.size()
   // b is a suffix of a: ai == a.end() - b.size() && bi == b.begin()
   // Otherwise: ai and bi point to the first element of the common
   // suffix
   a.erase(ai, a.end());
   b.erase(bi, b.end());
}

-- Jeremiah Willcock