...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
template <typename Graph, typename ForwardIterator, typename VertexIndexMap> bool is_kuratowski_subgraph(const Graph& g, ForwardIterator begin, ForwardIterator end, VertexIndexMap vm)
is_kuratowski_subgraph(g, begin, end) returns true exactly when the sequence of edges defined by the range [begin, end) forms a Kuratowski subgraph in the graph g. If you need to verify that an arbitrary graph has a K5 or K3,3 minor, you should use the function boyer_myrvold_planarity_test to isolate such a minor instead of this function. is_kuratowski_subgraph exists to aid in testing and verification of the function boyer_myrvold_planarity_test, and for that reason, it expects its input to be a restricted set of edges forming a Kuratowski subgraph, as described in detail below.
is_kuratowski_subgraph creates a temporary graph out of the sequence of edges given and repeatedly contracts edges until it ends up with a graph with either all edges of degree 3 or all edges of degree 4. The final contracted graph is then checked against K5 or K3,3 using the Boost Graph Library's isomorphism function. The contraction process starts by choosing edges adjacent to a vertex of degree 1 and contracting those. When none are left, it moves on to edges adjacent to a vertex of degree 2. If only degree 3 vertices are left after this stage, the graph is checked against K3,3. Otherwise, if there's at least one degree 4 vertex, edges adjacent to degree 3 vertices are contracted as neeeded and the final graph is compared to K5.
In order for this process to be deterministic, we make the following two restrictions on the input graph given to is_kuratowski_subgraph:
boost/graph/is_kuratowski_subgraph.hpp
An undirected graph with no self-loops or parallel edges. The graph type must be a model of Vertex List Graph.IN: ForwardIterator
A ForwardIterator with value_type graph_traits<Graph>::edge_descriptor.IN: VertexIndexMap vm
A Readable Property Map that maps vertices from g to distinct integers in the range [0, num_vertices(g) )
Default: get(vertex_index,g)
examples/kuratowski_subgraph.cpp
Planar Graphs in the Boost Graph Library