Re: [Boost-users] graph planar_face_traversal

Subject: Re: [Boost-users] graph planar_face_traversal
From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2012-02-13 21:47:12

On Mon, Feb 13, 2012 at 10:36 AM, Aaron Windsor <aaron.windsor_at_[hidden]>wrote:

> On Mon, Feb 13, 2012 at 3:59 AM, Andreas Fabri <
> andreas.fabri_at_[hidden]> wrote:
>
>>
>> Hello,
>>
>> I am wondering about the output of the example on the page
>> http://www.boost.org/doc/libs/**1_48_0/libs/graph/doc/planar_**
>> face_traversal.html<http://www.boost.org/doc/libs/1_48_0/libs/graph/doc/planar_face_traversal.html>
>>
>> I would expect that the  vertices on the border of the
>> outer or unbounded face got reported in reverse order.
>>
>> The vertices of inner faces are reported in clockwise order
>> which makes that for each edge shared by inner faces, we
>> traverse it once from source to target, and once from target
>> to source.  This does not hold for edges on the outer face.
>>
>> Is this intentional, or just a documentation bug?
>>
>>
> Hi Andreas,
>
> This may just be a documentation bug - if memory serves me correctly, I
> didn't necessarily run the traversal to create that output, although I
> think you could easily modify the example code on that page (
> http://www.boost.org/doc/libs/1_48_0/libs/graph/example/planar_face_traversal.cpp)
> to generate similar output.
>
> I don't have a boost checkout handy right now to verify that it's just a
> documentation bug, but I'll try it out tonight and reply to this thread
> again.
>
> -Aaron
>

Hi Andreas,

This is indeed a doc bug - I changed the graph in the example code I
referenced above so that it described the graph in the docs, like this:

  graph g(6);

  add_edge(0,1,g);
  add_edge(1,4,g);
  add_edge(4,3,g);
  add_edge(3,0,g);

  add_edge(4,5,g);
  add_edge(5,2,g);
  add_edge(1,2,g);
  add_edge(2,3,g);

and the vertices came out in the correct order:

Vertices on the faces:
New face: 0 1 4 3
New face: 1 0 3 2
New face: 4 1 2 5
New face: 3 4 5 2

I just committed the doc fix to trunk, it should show up in the next boost
release. Thanks for carefully reading the documentation and reporting this!

-Aaron