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-04 17:40:43

On Thu, 4 Mar 2010, Matthias Walter wrote:

>> That makes sense.  Maybe you want your visitor to be a wrapper around an
>> arbitrary visitor, though?  I.e., you would call the nested visitor on
>> all event points, even those you don't handle.
>
> I must admin that I don't really understand, what you mean. Around what
> other visitor shall I wrap it? Or shall I split the current visitor into
> more smaller ones which wrap each other somehow?

I mean that your visitor takes another arbitrary visitor as a template
parameter, stores it, and then invokes its methods after you run your
hooks.  Basically, it's a generalization of what you do now with
predecessor recorders but working with any visitor.

>> But would you ever have anything to remove to begin with?  In the logic
>> of your code, I do not see a way to have a common tail between the two
>> paths
>
> In the case, a monochromatic non-tree edge is found, the exception is
> thrown. The paths are from the endpoints to the root-node (of the rooted
> tree, DFS already has constructed) in the component in which which both
> vertices reside. As there is an edge, they definitely are in one
> component and thus share at least the root node.

OK.  I thought you were pulling from the end of the path closest to
where the coloring failure occured, not the other end.  Now I understand
why you need to do it.

-- Jeremiah Willcock