What are faces of two triangles by planar_face_traversal?
Nobody has claimed this yet.
Assessment
- Difficulty
- 3/5
- Estimated time
- 1-2 days
- Newbie friendliness
- 45/100
Research direction
Start with the supplied Godbolt example and the planar_face_traversal call, then inspect the Boost Graph documentation or source for planar_face_traversal and its visitor callbacks. Compare the reported vertex sequences with the disconnected two-triangle construction and determine whether the behavior matches the documented face definition. Done means a documented explanation or a confirmed issue with a focused regression case.
Written by the indexing model from the issue text.
Description
Suppose we have two triangles, one have vertexes 0, 1, 2, the other have vertexes 3, 4, 5, then we use planar_face_traversal to traversal it, we will get 4 faces:
New face: 0 1 2
New face: 1 0 2
New face: 3 4 5
New face: 4 3 5
But I think we should only have three faces, we only have three regions in fact.
Anybody can explain the result?
Here is the code (https://godbolt.org/z/eKKffh1Mx):
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/ref.hpp>
#include <vector>
#include <boost/graph/planar_face_traversal.hpp>
#include <boost/graph/boyer_myrvold_planar_test.hpp>
using namespace boost;
// Some planar face traversal visitors that will
// print the vertices and edges on the faces
struct output_visitor : public planar_face_traversal_visitor
{
void begin_face() { std::cout << "New face: "; }
void end_face() { std::cout << std::endl; }
};
struct vertex_output_visitor : public output_visitor
{
template < typename Vertex > void next_vertex(Vertex v)
{
std::cout << v << " ";
}
};
struct edge_output_visitor : public output_visitor
{
template < typename Edge > void next_edge(Edge e) { std::cout << e << " "; }
};
int main(int argc, char** argv)
{
typedef adjacency_list< vecS, vecS, undirectedS,
property< vertex_index_t, int >, property< edge_index_t, int > >
graph;
// Create a graph - this is a biconnected, 3 x 3 grid.
// It should have four small (four vertex/four edge) faces and
// one large face that contains all but the interior vertex
graph g(6);
add_edge(0, 1, g);
add_edge(1, 2, g);
add_edge(2, 0, g);
add_edge(3, 4, g);
add_edge(4, 5, g);
add_edge(5, 3, g);
// Initialize the interior edge index
property_map< graph, edge_index_t >::type e_index = get(edge_index, g);
graph_traits< graph >::edges_size_type edge_count = 0;
graph_traits< graph >::edge_iterator ei, ei_end;
for (auto [ei, ei_end] = edges(g); ei != ei_end; ++ei)
put(e_index, *ei, edge_count++);
// Test for planarity - we know it is planar, we just want to
// compute the planar embedding as a side-effect
typedef std::vector< graph_traits< graph >::edge_descriptor > vec_t;
std::vector< vec_t > embedding(num_vertices(g));
if (boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g,
boyer_myrvold_params::embedding = &embedding[0]))
std::cout << "Input graph is planar" << std::endl;
else
std::cout << "Input graph is not planar" << std::endl;
std::cout << std::endl << "Vertices on the faces: " << std::endl;
vertex_output_visitor v_vis;
planar_face_traversal(g, &embedding[0], v_vis);
std::cout << std::endl << "Edges on the faces: " << std::endl;
edge_output_visitor e_vis;
planar_face_traversal(g, &embedding[0], e_vis);
return 0;
}
- Dominant language
- C++
- Stars
- 395
- Forks
- 239
- Avg merge
- 18h 50m
- Merged PRs (30d)
- 20
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from boostorg/graph
-
beginner friendly
Difficulty 2/5 1-3 hours Newbie friendliness 76/100
-
algorithm beginner friendly priority: high
Difficulty 2/5 1-3 hours Newbie friendliness 68/100
-
Difficulty 5/5 Over a week Newbie friendliness 30/100
-
priority: high warning
-
algorithm
boostorg/graph#493 · 22 comments · 1 reaction · 2 assignees ·
Similar issues
-
Difficulty 1/5 Under an hour Newbie friendliness 90/100
AXERA-TECH/ax-llm#77 ·
-
Difficulty 1/5 Under an hour Newbie friendliness 90/100
games-on-whales/wolf#509 ·
-
Difficulty 2/5 1-3 hours Newbie friendliness 74/100
-
bug-unconfirmed
Difficulty 2/5 1-3 hours Newbie friendliness 76/100
-
Difficulty 2/5 1-3 hours Newbie friendliness 74/100
NVIDIA/cuda-samples#453 ·