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

Subject: Re: [boost] [BGL] Testing a graph for bipartiteness
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2010-02-18 19:58:20

> > Maybe the version taking the out_iterator should be a different function?
>
> Taking the suggestion of Andrew, I'd imagine the case where
> you won't get back a bool from the odd-cycle-version of the
> bipartiteness test, but the final iterator. Then the graph
> would be bipartite if and only if nothing was written to
> that iterator. Testing would then mean to compare both or
> look at your odd_cycle_vector.
>
> Maybe returning both in a std::pair would be another (more
> elegant?) solution.
>

After looking a little more closely at the algorithm, I think there are
definitey two versions of it. The first is a simple is_bipartite function,
the other is find_odd_cycle, and the latter should definitely take an output
iterator.

I think that breaking this into two will also let you get rid of the helper
classes and simplify some of implementation a little bit.

It would be /really/ nice if BFS allowed the visitor to parameterize some of
the control points so you didn't have to throw an exception :) Of course,
this is a well known problem.

Andrew Sutton
andrew.n.sutton_at_[hidden]