in extra/boost/boost_1_85_0/boost/graph/planar_detail/boyer_myrvold_impl.hpp [1021:1742]
void extract_kuratowski_subgraph(OutputIterator o_itr, EdgeIndexMap em)
{
// If the main algorithm has failed to embed one of the back-edges from
// a vertex v, we can use the current state of the algorithm to isolate
// a Kuratowksi subgraph. The isolation process breaks down into five
// cases, A - E. The general configuration of all five cases is shown in
// figure 1. There is a vertex v from which the planar
// v embedding process could not proceed. This means that
// | there exists some bicomp containing three vertices
// ----- x,y, and z as shown such that x and y are externally
// | | active with respect to v (which means that there are
// x y two vertices x_0 and y_0 such that (1) both x_0 and
// | | y_0 are proper depth-first search ancestors of v and
// --z-- (2) there are two disjoint paths, one connecting x
// and x_0 and one connecting y and y_0, both
// consisting
// fig. 1 entirely of unembedded edges). Furthermore, there
// exists a vertex z_0 such that z is a depth-first
// search ancestor of z_0 and (v,z_0) is an unembedded back-edge from v.
// x,y and z all exist on the same bicomp, which consists entirely of
// embedded edges. The five subcases break down as follows, and are
// handled by the algorithm logically in the order A-E: First, if v is
// not on the same bicomp as x,y, and z, a K_3_3 can be isolated - this
// is case A. So, we'll assume that v is on the same bicomp as x,y, and
// z. If z_0 is on a different bicomp than x,y, and z, a K_3_3 can also
// be isolated - this is a case B - so we'll assume from now on that v
// is on the same bicomp as x, y, and z=z_0. In this case, one can use
// properties of the Boyer-Myrvold algorithm to show the existence of an
// "x-y path" connecting some vertex on the "left side" of the x,y,z
// bicomp with some vertex on the "right side" of the bicomp (where the
// left and right are split by a line drawn through v and z.If either of
// the endpoints of the x-y path is above x or y on the bicomp, a K_3_3
// can be isolated - this is a case C. Otherwise, both endpoints are at
// or below x and y on the bicomp. If there is a vertex alpha on the x-y
// path such that alpha is not x or y and there's a path from alpha to v
// that's disjoint from any of the edges on the bicomp and the x-y path,
// a K_3_3 can be isolated - this is a case D. Otherwise, properties of
// the Boyer-Myrvold algorithm can be used to show that another vertex
// w exists on the lower half of the bicomp such that w is externally
// active with respect to v. w can then be used to isolate a K_5 - this
// is the configuration of case E.
vertex_iterator_t vi, vi_end;
edge_iterator_t ei, ei_end;
out_edge_iterator_t oei, oei_end;
typename std::vector< edge_t >::iterator xi, xi_end;
// Clear the short-circuit edges - these are needed for the planar
// testing/embedding algorithm to run in linear time, but they'll
// complicate the kuratowski subgraph isolation
for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
{
face_handles[*vi].reset_vertex_cache();
dfs_child_handles[*vi].reset_vertex_cache();
}
vertex_t v = kuratowski_v;
vertex_t x = kuratowski_x;
vertex_t y = kuratowski_y;
typedef iterator_property_map< typename std::vector< bool >::iterator,
EdgeIndexMap >
edge_to_bool_map_t;
std::vector< bool > is_in_subgraph_vector(num_edges(g), false);
edge_to_bool_map_t is_in_subgraph(is_in_subgraph_vector.begin(), em);
std::vector< bool > is_embedded_vector(num_edges(g), false);
edge_to_bool_map_t is_embedded(is_embedded_vector.begin(), em);
typename std::vector< edge_t >::iterator embedded_itr, embedded_end;
embedded_end = embedded_edges.end();
for (embedded_itr = embedded_edges.begin();
embedded_itr != embedded_end; ++embedded_itr)
is_embedded[*embedded_itr] = true;
// upper_face_vertex is true for x,y, and all vertices above x and y in
// the bicomp
std::vector< bool > upper_face_vertex_vector(num_vertices(g), false);
vertex_to_bool_map_t upper_face_vertex(
upper_face_vertex_vector.begin(), vm);
std::vector< bool > lower_face_vertex_vector(num_vertices(g), false);
vertex_to_bool_map_t lower_face_vertex(
lower_face_vertex_vector.begin(), vm);
// These next few variable declarations are all things that we need
// to find.
vertex_t z = graph_traits< Graph >::null_vertex();
vertex_t bicomp_root;
vertex_t w = graph_traits< Graph >::null_vertex();
face_handle_t w_handle;
face_handle_t v_dfchild_handle;
vertex_t first_x_y_path_endpoint = graph_traits< Graph >::null_vertex();
vertex_t second_x_y_path_endpoint
= graph_traits< Graph >::null_vertex();
vertex_t w_ancestor = v;
detail::bm_case_t chosen_case = detail::BM_NO_CASE_CHOSEN;
std::vector< edge_t > x_external_path;
std::vector< edge_t > y_external_path;
std::vector< edge_t > case_d_edges;
std::vector< edge_t > z_v_path;
std::vector< edge_t > w_path;
// first, use a walkup to find a path from V that starts with a
// backedge from V, then goes up until it hits either X or Y
//(but doesn't find X or Y as the root of a bicomp)
typename face_vertex_iterator<>::type x_upper_itr(
x, face_handles, first_side());
typename face_vertex_iterator<>::type x_lower_itr(
x, face_handles, second_side());
typename face_vertex_iterator<>::type face_itr, face_end;
// Don't know which path from x is the upper or lower path -
// we'll find out here
for (face_itr = x_upper_itr; face_itr != face_end; ++face_itr)
{
if (*face_itr == y)
{
std::swap(x_upper_itr, x_lower_itr);
break;
}
}
upper_face_vertex[x] = true;
vertex_t current_vertex = x;
vertex_t previous_vertex;
for (face_itr = x_upper_itr; face_itr != face_end; ++face_itr)
{
previous_vertex = current_vertex;
current_vertex = *face_itr;
upper_face_vertex[current_vertex] = true;
}
v_dfchild_handle
= dfs_child_handles[canonical_dfs_child[previous_vertex]];
for (face_itr = x_lower_itr; *face_itr != y; ++face_itr)
{
vertex_t current_vertex(*face_itr);
lower_face_vertex[current_vertex] = true;
typename face_handle_list_t::iterator roots_itr, roots_end;
if (w == graph_traits< Graph >::null_vertex()) // haven't found a w
// yet
{
roots_end = pertinent_roots[current_vertex]->end();
for (roots_itr = pertinent_roots[current_vertex]->begin();
roots_itr != roots_end; ++roots_itr)
{
if (low_point
[canonical_dfs_child[roots_itr->first_vertex()]]
< dfs_number[v])
{
w = current_vertex;
w_handle = *roots_itr;
break;
}
}
}
}
for (; face_itr != face_end; ++face_itr)
{
vertex_t current_vertex(*face_itr);
upper_face_vertex[current_vertex] = true;
bicomp_root = current_vertex;
}
typedef typename face_edge_iterator<>::type walkup_itr_t;
std::vector< bool > outer_face_edge_vector(num_edges(g), false);
edge_to_bool_map_t outer_face_edge(outer_face_edge_vector.begin(), em);
walkup_itr_t walkup_end;
for (walkup_itr_t walkup_itr(x, face_handles, first_side());
walkup_itr != walkup_end; ++walkup_itr)
{
outer_face_edge[*walkup_itr] = true;
is_in_subgraph[*walkup_itr] = true;
}
for (walkup_itr_t walkup_itr(x, face_handles, second_side());
walkup_itr != walkup_end; ++walkup_itr)
{
outer_face_edge[*walkup_itr] = true;
is_in_subgraph[*walkup_itr] = true;
}
std::vector< bool > forbidden_edge_vector(num_edges(g), false);
edge_to_bool_map_t forbidden_edge(forbidden_edge_vector.begin(), em);
std::vector< bool > goal_edge_vector(num_edges(g), false);
edge_to_bool_map_t goal_edge(goal_edge_vector.begin(), em);
// Find external path to x and to y
for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
{
edge_t e(*ei);
goal_edge[e] = !outer_face_edge[e]
&& (source(e, g) == x || target(e, g) == x);
forbidden_edge[*ei] = outer_face_edge[*ei];
}
vertex_t x_ancestor = v;
vertex_t x_endpoint = graph_traits< Graph >::null_vertex();
while (x_endpoint == graph_traits< Graph >::null_vertex())
{
x_ancestor = dfs_parent[x_ancestor];
x_endpoint = kuratowski_walkup(x_ancestor, forbidden_edge,
goal_edge, is_embedded, x_external_path);
}
for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
{
edge_t e(*ei);
goal_edge[e] = !outer_face_edge[e]
&& (source(e, g) == y || target(e, g) == y);
forbidden_edge[*ei] = outer_face_edge[*ei];
}
vertex_t y_ancestor = v;
vertex_t y_endpoint = graph_traits< Graph >::null_vertex();
while (y_endpoint == graph_traits< Graph >::null_vertex())
{
y_ancestor = dfs_parent[y_ancestor];
y_endpoint = kuratowski_walkup(y_ancestor, forbidden_edge,
goal_edge, is_embedded, y_external_path);
}
vertex_t parent, child;
// If v isn't on the same bicomp as x and y, it's a case A
if (bicomp_root != v)
{
chosen_case = detail::BM_CASE_A;
for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
if (lower_face_vertex[*vi])
for (boost::tie(oei, oei_end) = out_edges(*vi, g);
oei != oei_end; ++oei)
if (!outer_face_edge[*oei])
goal_edge[*oei] = true;
for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
forbidden_edge[*ei] = outer_face_edge[*ei];
z = kuratowski_walkup(
v, forbidden_edge, goal_edge, is_embedded, z_v_path);
}
else if (w != graph_traits< Graph >::null_vertex())
{
chosen_case = detail::BM_CASE_B;
for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
{
edge_t e(*ei);
goal_edge[e] = false;
forbidden_edge[e] = outer_face_edge[e];
}
goal_edge[w_handle.first_edge()] = true;
goal_edge[w_handle.second_edge()] = true;
z = kuratowski_walkup(
v, forbidden_edge, goal_edge, is_embedded, z_v_path);
for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
{
forbidden_edge[*ei] = outer_face_edge[*ei];
}
typename std::vector< edge_t >::iterator pi, pi_end;
pi_end = z_v_path.end();
for (pi = z_v_path.begin(); pi != pi_end; ++pi)
{
goal_edge[*pi] = true;
}
w_ancestor = v;
vertex_t w_endpoint = graph_traits< Graph >::null_vertex();
while (w_endpoint == graph_traits< Graph >::null_vertex())
{
w_ancestor = dfs_parent[w_ancestor];
w_endpoint = kuratowski_walkup(
w_ancestor, forbidden_edge, goal_edge, is_embedded, w_path);
}
// We really want both the w walkup and the z walkup to finish on
// exactly the same edge, but for convenience (since we don't have
// control over which side of a bicomp a walkup moves up) we've
// defined the walkup to either end at w_handle.first_edge() or
// w_handle.second_edge(). If both walkups ended at different edges,
// we'll do a little surgery on the w walkup path to make it follow
// the other side of the final bicomp.
if ((w_path.back() == w_handle.first_edge()
&& z_v_path.back() == w_handle.second_edge())
|| (w_path.back() == w_handle.second_edge()
&& z_v_path.back() == w_handle.first_edge()))
{
walkup_itr_t wi, wi_end;
edge_t final_edge = w_path.back();
vertex_t anchor = source(final_edge, g) == w_handle.get_anchor()
? target(final_edge, g)
: source(final_edge, g);
if (face_handles[anchor].first_edge() == final_edge)
wi = walkup_itr_t(anchor, face_handles, second_side());
else
wi = walkup_itr_t(anchor, face_handles, first_side());
w_path.pop_back();
for (; wi != wi_end; ++wi)
{
edge_t e(*wi);
if (w_path.back() == e)
w_path.pop_back();
else
w_path.push_back(e);
}
}
}
else
{
// We need to find a valid z, since the x-y path re-defines the
// lower face, and the z we found earlier may now be on the upper
// face.
chosen_case = detail::BM_CASE_E;
// The z we've used so far is just an externally active vertex on
// the lower face path, but may not be the z we need for a case C,
// D, or E subgraph. the z we need now is any externally active
// vertex on the lower face path with both old_face_handles edges on
// the outer face. Since we know an x-y path exists, such a z must
// also exist.
// TODO: find this z in the first place.
// find the new z
for (face_itr = x_lower_itr; *face_itr != y; ++face_itr)
{
vertex_t possible_z(*face_itr);
if (pertinent(possible_z, v)
&& outer_face_edge[face_handles[possible_z]
.old_first_edge()]
&& outer_face_edge[face_handles[possible_z]
.old_second_edge()])
{
z = possible_z;
break;
}
}
// find x-y path, and a w if one exists.
if (externally_active(z, v))
w = z;
typedef typename face_edge_iterator< single_side,
previous_iteration >::type old_face_iterator_t;
old_face_iterator_t first_old_face_itr(
z, face_handles, first_side());
old_face_iterator_t second_old_face_itr(
z, face_handles, second_side());
old_face_iterator_t old_face_itr, old_face_end;
std::vector< old_face_iterator_t > old_face_iterators;
old_face_iterators.push_back(first_old_face_itr);
old_face_iterators.push_back(second_old_face_itr);
std::vector< bool > x_y_path_vertex_vector(num_vertices(g), false);
vertex_to_bool_map_t x_y_path_vertex(
x_y_path_vertex_vector.begin(), vm);
typename std::vector< old_face_iterator_t >::iterator of_itr,
of_itr_end;
of_itr_end = old_face_iterators.end();
for (of_itr = old_face_iterators.begin(); of_itr != of_itr_end;
++of_itr)
{
old_face_itr = *of_itr;
vertex_t previous_vertex;
bool seen_x_or_y = false;
vertex_t current_vertex = z;
for (; old_face_itr != old_face_end; ++old_face_itr)
{
edge_t e(*old_face_itr);
previous_vertex = current_vertex;
current_vertex = source(e, g) == current_vertex
? target(e, g)
: source(e, g);
if (current_vertex == x || current_vertex == y)
seen_x_or_y = true;
if (w == graph_traits< Graph >::null_vertex()
&& externally_active(current_vertex, v)
&& outer_face_edge[e]
&& outer_face_edge[*boost::next(old_face_itr)]
&& !seen_x_or_y)
{
w = current_vertex;
}
if (!outer_face_edge[e])
{
if (!upper_face_vertex[current_vertex]
&& !lower_face_vertex[current_vertex])
{
x_y_path_vertex[current_vertex] = true;
}
is_in_subgraph[e] = true;
if (upper_face_vertex[source(e, g)]
|| lower_face_vertex[source(e, g)])
{
if (first_x_y_path_endpoint
== graph_traits< Graph >::null_vertex())
first_x_y_path_endpoint = source(e, g);
else
second_x_y_path_endpoint = source(e, g);
}
if (upper_face_vertex[target(e, g)]
|| lower_face_vertex[target(e, g)])
{
if (first_x_y_path_endpoint
== graph_traits< Graph >::null_vertex())
first_x_y_path_endpoint = target(e, g);
else
second_x_y_path_endpoint = target(e, g);
}
}
else if (previous_vertex == x || previous_vertex == y)
{
chosen_case = detail::BM_CASE_C;
}
}
}
// Look for a case D - one of v's embedded edges will connect to the
// x-y path along an inner face path.
// First, get a list of all of v's embedded child edges
out_edge_iterator_t v_edge_itr, v_edge_end;
for (boost::tie(v_edge_itr, v_edge_end) = out_edges(v, g);
v_edge_itr != v_edge_end; ++v_edge_itr)
{
edge_t embedded_edge(*v_edge_itr);
if (!is_embedded[embedded_edge]
|| embedded_edge == dfs_parent_edge[v])
continue;
case_d_edges.push_back(embedded_edge);
vertex_t current_vertex = source(embedded_edge, g) == v
? target(embedded_edge, g)
: source(embedded_edge, g);
typename face_edge_iterator<>::type internal_face_itr,
internal_face_end;
if (face_handles[current_vertex].first_vertex() == v)
{
internal_face_itr = typename face_edge_iterator<>::type(
current_vertex, face_handles, second_side());
}
else
{
internal_face_itr = typename face_edge_iterator<>::type(
current_vertex, face_handles, first_side());
}
while (internal_face_itr != internal_face_end
&& !outer_face_edge[*internal_face_itr]
&& !x_y_path_vertex[current_vertex])
{
edge_t e(*internal_face_itr);
case_d_edges.push_back(e);
current_vertex = source(e, g) == current_vertex
? target(e, g)
: source(e, g);
++internal_face_itr;
}
if (x_y_path_vertex[current_vertex])
{
chosen_case = detail::BM_CASE_D;
break;
}
else
{
case_d_edges.clear();
}
}
}
if (chosen_case != detail::BM_CASE_B
&& chosen_case != detail::BM_CASE_A)
{
// Finding z and w.
for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
{
edge_t e(*ei);
goal_edge[e] = !outer_face_edge[e]
&& (source(e, g) == z || target(e, g) == z);
forbidden_edge[e] = outer_face_edge[e];
}
kuratowski_walkup(
v, forbidden_edge, goal_edge, is_embedded, z_v_path);
if (chosen_case == detail::BM_CASE_E)
{
for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
{
forbidden_edge[*ei] = outer_face_edge[*ei];
goal_edge[*ei] = !outer_face_edge[*ei]
&& (source(*ei, g) == w || target(*ei, g) == w);
}
for (boost::tie(oei, oei_end) = out_edges(w, g); oei != oei_end;
++oei)
{
if (!outer_face_edge[*oei])
goal_edge[*oei] = true;
}
typename std::vector< edge_t >::iterator pi, pi_end;
pi_end = z_v_path.end();
for (pi = z_v_path.begin(); pi != pi_end; ++pi)
{
goal_edge[*pi] = true;
}
w_ancestor = v;
vertex_t w_endpoint = graph_traits< Graph >::null_vertex();
while (w_endpoint == graph_traits< Graph >::null_vertex())
{
w_ancestor = dfs_parent[w_ancestor];
w_endpoint = kuratowski_walkup(w_ancestor, forbidden_edge,
goal_edge, is_embedded, w_path);
}
}
}
// We're done isolating the Kuratowski subgraph at this point -
// but there's still some cleaning up to do.
// Update is_in_subgraph with the paths we just found
xi_end = x_external_path.end();
for (xi = x_external_path.begin(); xi != xi_end; ++xi)
is_in_subgraph[*xi] = true;
xi_end = y_external_path.end();
for (xi = y_external_path.begin(); xi != xi_end; ++xi)
is_in_subgraph[*xi] = true;
xi_end = z_v_path.end();
for (xi = z_v_path.begin(); xi != xi_end; ++xi)
is_in_subgraph[*xi] = true;
xi_end = case_d_edges.end();
for (xi = case_d_edges.begin(); xi != xi_end; ++xi)
is_in_subgraph[*xi] = true;
xi_end = w_path.end();
for (xi = w_path.begin(); xi != xi_end; ++xi)
is_in_subgraph[*xi] = true;
child = bicomp_root;
parent = dfs_parent[child];
while (child != parent)
{
is_in_subgraph[dfs_parent_edge[child]] = true;
boost::tie(parent, child)
= std::make_pair(dfs_parent[parent], parent);
}
// At this point, we've already isolated the Kuratowski subgraph and
// collected all of the edges that compose it in the is_in_subgraph
// property map. But we want the verification of such a subgraph to be
// a deterministic process, and we can simplify the function
// is_kuratowski_subgraph by cleaning up some edges here.
if (chosen_case == detail::BM_CASE_B)
{
is_in_subgraph[dfs_parent_edge[v]] = false;
}
else if (chosen_case == detail::BM_CASE_C)
{
// In a case C subgraph, at least one of the x-y path endpoints
// (call it alpha) is above either x or y on the outer face. The
// other endpoint may be attached at x or y OR above OR below. In
// any of these three cases, we can form a K_3_3 by removing the
// edge attached to v on the outer face that is NOT on the path to
// alpha.
typename face_vertex_iterator< single_side, follow_visitor >::type
face_itr,
face_end;
if (face_handles[v_dfchild_handle.first_vertex()].first_edge()
== v_dfchild_handle.first_edge())
{
face_itr = typename face_vertex_iterator< single_side,
follow_visitor >::type(v_dfchild_handle.first_vertex(),
face_handles, second_side());
}
else
{
face_itr = typename face_vertex_iterator< single_side,
follow_visitor >::type(v_dfchild_handle.first_vertex(),
face_handles, first_side());
}
for (; true; ++face_itr)
{
vertex_t current_vertex(*face_itr);
if (current_vertex == x || current_vertex == y)
{
is_in_subgraph[v_dfchild_handle.first_edge()] = false;
break;
}
else if (current_vertex == first_x_y_path_endpoint
|| current_vertex == second_x_y_path_endpoint)
{
is_in_subgraph[v_dfchild_handle.second_edge()] = false;
break;
}
}
}
else if (chosen_case == detail::BM_CASE_D)
{
// Need to remove both of the edges adjacent to v on the outer face.
// remove the connecting edges from v to bicomp, then
// is_kuratowski_subgraph will shrink vertices of degree 1
// automatically...
is_in_subgraph[v_dfchild_handle.first_edge()] = false;
is_in_subgraph[v_dfchild_handle.second_edge()] = false;
}
else if (chosen_case == detail::BM_CASE_E)
{
// Similarly to case C, if the endpoints of the x-y path are both
// below x and y, we should remove an edge to allow the subgraph to
// contract to a K_3_3.
if ((first_x_y_path_endpoint != x && first_x_y_path_endpoint != y)
|| (second_x_y_path_endpoint != x
&& second_x_y_path_endpoint != y))
{
is_in_subgraph[dfs_parent_edge[v]] = false;
vertex_t deletion_endpoint, other_endpoint;
if (lower_face_vertex[first_x_y_path_endpoint])
{
deletion_endpoint = second_x_y_path_endpoint;
other_endpoint = first_x_y_path_endpoint;
}
else
{
deletion_endpoint = first_x_y_path_endpoint;
other_endpoint = second_x_y_path_endpoint;
}
typename face_edge_iterator<>::type face_itr, face_end;
bool found_other_endpoint = false;
for (face_itr = typename face_edge_iterator<>::type(
deletion_endpoint, face_handles, first_side());
face_itr != face_end; ++face_itr)
{
edge_t e(*face_itr);
if (source(e, g) == other_endpoint
|| target(e, g) == other_endpoint)
{
found_other_endpoint = true;
break;
}
}
if (found_other_endpoint)
{
is_in_subgraph[face_handles[deletion_endpoint].first_edge()]
= false;
}
else
{
is_in_subgraph[face_handles[deletion_endpoint]
.second_edge()]
= false;
}
}
}
for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
if (is_in_subgraph[*ei])
*o_itr = *ei;
}