Boost C++ Libraries: Ticket #3807: Documentation improvement for graph/planar_canonical_ordering.hpp.

owner, component, severity, summary changed

Thu, 31 Dec 2009 16:10:39 GMT

owner changed from Andrew Sutton to Matias Capeletto
component graph → Documentation
severity Problem → Cosmetic
summary Logic error in graph/planar_canonical_ordering.hpp. → Documentation improvement for graph/planar_canonical_ordering.hpp.

It appears that the algorithm simply requires that the first two supplied vertices are exterior and adjacent. I couldn't find this in the documentation, but it seemed apparent from the description of the algorithm that I found in "Drawing Planar Graphs using Canonical Ordering" by Goos Kant.

owner, component changed

anonymous — Thu, 31 Dec 2009 16:12:43 GMT

owner changed from Matias Capeletto to Andrew Sutton
component Documentation → graph

Jeremiah Willcock — Tue, 16 Mar 2010 18:18:52 GMT

Is "is biconnected and contains the edge {v1, v2} on its outer face." (what is in the current documentation) inadequate in your opinion? I.e., is this bug already fixed?

anonymous — Tue, 16 Mar 2010 18:51:46 GMT

Just checked: http://www.boost.org/doc/libs/1_42_0/libs/graph/doc/planar_canonical_ordering.html

Sorry, no I don't think the current documentation is adequate. The description of the algorithm output is accurate and clear (as described in the first paragraph), but the pre-requisites for the algorithm are not clear. This is particularly important, as if the inputs are not supplied correctly, the algorithm doesn't degrade nicely (it just produces a bogus ordering).

The input graph must: a) Be maximal planar. b) Have at least two vertices. c) Must contain contain the edge {v1, v2} on its outer face.

The documentation makes it clear that c) is true of the output - but isn't clear that it is also necessary in the input.

*Also, I should note that my original example didn't meet criteria (a) as it was planar triangular and maximal planar (requires [0,3] to be maximal). That's my own fault for not originally understanding the difference.

status changed; resolution set

Jeremiah Willcock — Sun, 28 Mar 2010 18:16:54 GMT

status new → closed
resolution → fixed

(In [60899]) Added preconditions on graph listed in #3807; fixes #3807

status changed; resolution deleted

patcher@… — Wed, 19 May 2010 12:39:48 GMT

status closed → reopened
resolution fixed

The change of documentation is to confusing. The condition c) is not necessary!

In fact, the documentation says, that the embedding used for planar_canonical_ordering is a combinatorical embedding, not a geometrical (topological) embedding. Hence, there aren't any faces yet.

In starting with the first two vertices, the algorithm defines these both vertices to be on the outer face of an geometrical embedding, which one gets implicitly by the canonical order, see the documentation.

So the condition c) is always met and hence not needed to be mentioned. So delete this condition?

status changed; resolution set

Jeremiah Willcock — Wed, 19 May 2010 16:57:53 GMT

status reopened → closed
resolution → fixed

(In [62098]) Removed third condition from list of preconditions; fixes #3807 again