1 //=======================================================================
2 // Copyright (c) Aaron Windsor 2007
4 // Distributed under the Boost Software License, Version 1.0. (See
5 // accompanying file LICENSE_1_0.txt or copy at
6 // http://www.boost.org/LICENSE_1_0.txt)
7 //=======================================================================
8 #ifndef __BOYER_MYRVOLD_IMPL_HPP__
9 #define __BOYER_MYRVOLD_IMPL_HPP__
13 #include <boost/next_prior.hpp>
14 #include <boost/config.hpp> //for std::min macros
15 #include <boost/shared_ptr.hpp>
16 #include <boost/tuple/tuple.hpp>
17 #include <boost/property_map/property_map.hpp>
18 #include <boost/graph/graph_traits.hpp>
19 #include <boost/graph/depth_first_search.hpp>
20 #include <boost/graph/planar_detail/face_handles.hpp>
21 #include <boost/graph/planar_detail/face_iterators.hpp>
22 #include <boost/graph/planar_detail/bucket_sort.hpp>
39 template < typename LowPointMap, typename DFSParentMap, typename DFSNumberMap,
40 typename LeastAncestorMap, typename DFSParentEdgeMap, typename SizeType >
41 struct planar_dfs_visitor : public dfs_visitor<>
43 planar_dfs_visitor(LowPointMap lpm, DFSParentMap dfs_p, DFSNumberMap dfs_n,
44 LeastAncestorMap lam, DFSParentEdgeMap dfs_edge)
54 template < typename Vertex, typename Graph >
55 void start_vertex(const Vertex& u, Graph&)
58 put(least_ancestor, u, count);
61 template < typename Vertex, typename Graph >
62 void discover_vertex(const Vertex& u, Graph&)
65 put(df_number, u, count);
69 template < typename Edge, typename Graph >
70 void tree_edge(const Edge& e, Graph& g)
72 typedef typename graph_traits< Graph >::vertex_descriptor vertex_t;
73 vertex_t s(source(e, g));
74 vertex_t t(target(e, g));
78 put(least_ancestor, t, get(df_number, s));
81 template < typename Edge, typename Graph >
82 void back_edge(const Edge& e, Graph& g)
84 typedef typename graph_traits< Graph >::vertex_descriptor vertex_t;
85 typedef typename graph_traits< Graph >::vertices_size_type v_size_t;
87 vertex_t s(source(e, g));
88 vertex_t t(target(e, g));
89 BOOST_USING_STD_MIN();
91 if (t != get(parent, s))
93 v_size_t s_low_df_number = get(low, s);
94 v_size_t t_df_number = get(df_number, t);
95 v_size_t s_least_ancestor_df_number = get(least_ancestor, s);
98 min BOOST_PREVENT_MACRO_SUBSTITUTION(
99 s_low_df_number, t_df_number));
101 put(least_ancestor, s,
102 min BOOST_PREVENT_MACRO_SUBSTITUTION(
103 s_least_ancestor_df_number, t_df_number));
107 template < typename Vertex, typename Graph >
108 void finish_vertex(const Vertex& u, Graph&)
110 typedef typename graph_traits< Graph >::vertices_size_type v_size_t;
112 Vertex u_parent = get(parent, u);
113 v_size_t u_parent_lowpoint = get(low, u_parent);
114 v_size_t u_lowpoint = get(low, u);
115 BOOST_USING_STD_MIN();
120 min BOOST_PREVENT_MACRO_SUBSTITUTION(
121 u_lowpoint, u_parent_lowpoint));
127 DFSNumberMap df_number;
128 LeastAncestorMap least_ancestor;
129 DFSParentEdgeMap df_edge;
133 template < typename Graph, typename VertexIndexMap,
134 typename StoreOldHandlesPolicy = graph::detail::store_old_handles,
135 typename StoreEmbeddingPolicy = graph::detail::recursive_lazy_list >
136 class boyer_myrvold_impl
139 typedef typename graph_traits< Graph >::vertices_size_type v_size_t;
140 typedef typename graph_traits< Graph >::vertex_descriptor vertex_t;
141 typedef typename graph_traits< Graph >::edge_descriptor edge_t;
142 typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator_t;
143 typedef typename graph_traits< Graph >::edge_iterator edge_iterator_t;
145 typename graph_traits< Graph >::out_edge_iterator out_edge_iterator_t;
146 typedef graph::detail::face_handle< Graph, StoreOldHandlesPolicy,
147 StoreEmbeddingPolicy >
149 typedef std::vector< vertex_t > vertex_vector_t;
150 typedef std::vector< edge_t > edge_vector_t;
151 typedef std::list< vertex_t > vertex_list_t;
152 typedef std::list< face_handle_t > face_handle_list_t;
153 typedef boost::shared_ptr< face_handle_list_t > face_handle_list_ptr_t;
154 typedef boost::shared_ptr< vertex_list_t > vertex_list_ptr_t;
155 typedef boost::tuple< vertex_t, bool, bool > merge_stack_frame_t;
156 typedef std::vector< merge_stack_frame_t > merge_stack_t;
158 template < typename T > struct map_vertex_to_
160 typedef iterator_property_map< typename std::vector< T >::iterator,
165 typedef typename map_vertex_to_< v_size_t >::type vertex_to_v_size_map_t;
166 typedef typename map_vertex_to_< vertex_t >::type vertex_to_vertex_map_t;
167 typedef typename map_vertex_to_< edge_t >::type vertex_to_edge_map_t;
168 typedef typename map_vertex_to_< vertex_list_ptr_t >::type
169 vertex_to_vertex_list_ptr_map_t;
170 typedef typename map_vertex_to_< edge_vector_t >::type
171 vertex_to_edge_vector_map_t;
172 typedef typename map_vertex_to_< bool >::type vertex_to_bool_map_t;
173 typedef typename map_vertex_to_< face_handle_t >::type
174 vertex_to_face_handle_map_t;
175 typedef typename map_vertex_to_< face_handle_list_ptr_t >::type
176 vertex_to_face_handle_list_ptr_map_t;
177 typedef typename map_vertex_to_< typename vertex_list_t::iterator >::type
178 vertex_to_separated_node_map_t;
180 template < typename BicompSideToTraverse = single_side,
181 typename VisitorType = lead_visitor, typename Time = current_iteration >
182 struct face_vertex_iterator
184 typedef face_iterator< Graph, vertex_to_face_handle_map_t, vertex_t,
185 BicompSideToTraverse, VisitorType, Time >
189 template < typename BicompSideToTraverse = single_side,
190 typename Time = current_iteration >
191 struct face_edge_iterator
193 typedef face_iterator< Graph, vertex_to_face_handle_map_t, edge_t,
194 BicompSideToTraverse, lead_visitor, Time >
199 boyer_myrvold_impl(const Graph& arg_g, VertexIndexMap arg_vm)
204 low_point_vector(num_vertices(g))
205 , dfs_parent_vector(num_vertices(g))
206 , dfs_number_vector(num_vertices(g))
207 , least_ancestor_vector(num_vertices(g))
208 , pertinent_roots_vector(num_vertices(g))
209 , backedge_flag_vector(num_vertices(g), num_vertices(g) + 1)
210 , visited_vector(num_vertices(g), num_vertices(g) + 1)
211 , face_handles_vector(num_vertices(g))
212 , dfs_child_handles_vector(num_vertices(g))
213 , separated_dfs_child_list_vector(num_vertices(g))
214 , separated_node_in_parent_list_vector(num_vertices(g))
215 , canonical_dfs_child_vector(num_vertices(g))
216 , flipped_vector(num_vertices(g), false)
217 , backedges_vector(num_vertices(g))
218 , dfs_parent_edge_vector(num_vertices(g))
221 vertices_by_dfs_num(num_vertices(g))
224 low_point(low_point_vector.begin(), vm)
225 , dfs_parent(dfs_parent_vector.begin(), vm)
226 , dfs_number(dfs_number_vector.begin(), vm)
227 , least_ancestor(least_ancestor_vector.begin(), vm)
228 , pertinent_roots(pertinent_roots_vector.begin(), vm)
229 , backedge_flag(backedge_flag_vector.begin(), vm)
230 , visited(visited_vector.begin(), vm)
231 , face_handles(face_handles_vector.begin(), vm)
232 , dfs_child_handles(dfs_child_handles_vector.begin(), vm)
233 , separated_dfs_child_list(separated_dfs_child_list_vector.begin(), vm)
234 , separated_node_in_parent_list(
235 separated_node_in_parent_list_vector.begin(), vm)
236 , canonical_dfs_child(canonical_dfs_child_vector.begin(), vm)
237 , flipped(flipped_vector.begin(), vm)
238 , backedges(backedges_vector.begin(), vm)
239 , dfs_parent_edge(dfs_parent_edge_vector.begin(), vm)
243 planar_dfs_visitor< vertex_to_v_size_map_t, vertex_to_vertex_map_t,
244 vertex_to_v_size_map_t, vertex_to_v_size_map_t,
245 vertex_to_edge_map_t, v_size_t >
246 vis(low_point, dfs_parent, dfs_number, least_ancestor,
249 // Perform a depth-first search to find each vertex's low point, least
250 // ancestor, and dfs tree information
251 depth_first_search(g, visitor(vis).vertex_index_map(vm));
253 // Sort vertices by their lowpoint - need this later in the constructor
254 vertex_vector_t vertices_by_lowpoint(num_vertices(g));
255 std::copy(vertices(g).first, vertices(g).second,
256 vertices_by_lowpoint.begin());
257 bucket_sort(vertices_by_lowpoint.begin(), vertices_by_lowpoint.end(),
258 low_point, num_vertices(g));
260 // Sort vertices by their dfs number - need this to iterate by reverse
261 // DFS number in the main loop.
263 vertices(g).first, vertices(g).second, vertices_by_dfs_num.begin());
264 bucket_sort(vertices_by_dfs_num.begin(), vertices_by_dfs_num.end(),
265 dfs_number, num_vertices(g));
267 // Initialize face handles. A face handle is an abstraction that serves
268 // two uses in our implementation - it allows us to efficiently move
269 // along the outer face of embedded bicomps in a partially embedded
270 // graph, and it provides storage for the planar embedding. Face
271 // handles are implemented by a sequence of edges and are associated
272 // with a particular vertex - the sequence of edges represents the
273 // current embedding of edges around that vertex, and the first and
274 // last edges in the sequence represent the pair of edges on the outer
275 // face that are adjacent to the associated vertex. This lets us embed
276 // edges in the graph by just pushing them on the front or back of the
277 // sequence of edges held by the face handles.
279 // Our algorithm starts with a DFS tree of edges (where every vertex is
280 // an articulation point and every edge is a singleton bicomp) and
281 // repeatedly merges bicomps by embedding additional edges. Note that
282 // any bicomp at any point in the algorithm can be associated with a
283 // unique edge connecting the vertex of that bicomp with the lowest DFS
284 // number (which we refer to as the "root" of the bicomp) with its DFS
285 // child in the bicomp: the existence of two such edges would contradict
286 // the properties of a DFS tree. We refer to the DFS child of the root
287 // of a bicomp as the "canonical DFS child" of the bicomp. Note that a
288 // vertex can be the root of more than one bicomp.
290 // We move around the external faces of a bicomp using a few property
291 // maps, which we'll initialize presently:
293 // - face_handles: maps a vertex to a face handle that can be used to
294 // move "up" a bicomp. For a vertex that isn't an articulation point,
295 // this holds the face handles that can be used to move around that
296 // vertex's unique bicomp. For a vertex that is an articulation point,
297 // this holds the face handles associated with the unique bicomp that
298 // the vertex is NOT the root of. These handles can therefore be used
299 // to move from any point on the outer face of the tree of bicomps
300 // around the current outer face towards the root of the DFS tree.
302 // - dfs_child_handles: these are used to hold face handles for
303 // vertices that are articulation points - dfs_child_handles[v] holds
304 // the face handles corresponding to vertex u in the bicomp with root
305 // u and canonical DFS child v.
307 // - canonical_dfs_child: this property map allows one to determine the
308 // canonical DFS child of a bicomp while traversing the outer face.
309 // This property map is only valid when applied to one of the two
310 // vertices adjacent to the root of the bicomp on the outer face. To
311 // be more precise, if v is the canonical DFS child of a bicomp,
312 // canonical_dfs_child[dfs_child_handles[v].first_vertex()] == v and
313 // canonical_dfs_child[dfs_child_handles[v].second_vertex()] == v.
315 // - pertinent_roots: given a vertex v, pertinent_roots[v] contains a
316 // list of face handles pointing to the top of bicomps that need to
317 // be visited by the current walkdown traversal (since they lead to
318 // backedges that need to be embedded). These lists are populated by
319 // the walkup and consumed by the walkdown.
321 vertex_iterator_t vi, vi_end;
322 for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
325 vertex_t parent = dfs_parent[v];
329 edge_t parent_edge = dfs_parent_edge[v];
330 add_to_embedded_edges(parent_edge, StoreOldHandlesPolicy());
331 face_handles[v] = face_handle_t(v, parent_edge, g);
332 dfs_child_handles[v] = face_handle_t(parent, parent_edge, g);
336 face_handles[v] = face_handle_t(v);
337 dfs_child_handles[v] = face_handle_t(parent);
340 canonical_dfs_child[v] = v;
341 pertinent_roots[v] = face_handle_list_ptr_t(new face_handle_list_t);
342 separated_dfs_child_list[v] = vertex_list_ptr_t(new vertex_list_t);
345 // We need to create a list of not-yet-merged depth-first children for
346 // each vertex that will be updated as bicomps get merged. We sort each
347 // list by ascending lowpoint, which allows the externally_active
348 // function to run in constant time, and we keep a pointer to each
349 // vertex's representation in its parent's list, which allows merging
352 for (typename vertex_vector_t::iterator itr
353 = vertices_by_lowpoint.begin();
354 itr != vertices_by_lowpoint.end(); ++itr)
357 vertex_t parent(dfs_parent[v]);
360 separated_node_in_parent_list[v]
361 = separated_dfs_child_list[parent]->insert(
362 separated_dfs_child_list[parent]->end(), v);
366 // The merge stack holds path information during a walkdown iteration
367 merge_stack.reserve(num_vertices(g));
373 // This is the main algorithm: starting with a DFS tree of embedded
374 // edges (which, since it's a tree, is planar), iterate through all
375 // vertices by reverse DFS number, attempting to embed all backedges
376 // connecting the current vertex to vertices with higher DFS numbers.
378 // The walkup is a procedure that examines all such backedges and sets
379 // up the required data structures so that they can be searched by the
380 // walkdown in linear time. The walkdown does the actual work of
381 // embedding edges and flipping bicomps, and can identify when it has
382 // come across a kuratowski subgraph.
384 // store_old_face_handles caches face handles from the previous
385 // iteration - this is used only for the kuratowski subgraph isolation,
386 // and is therefore dispatched based on the StoreOldHandlesPolicy.
388 // clean_up_embedding does some clean-up and fills in values that have
389 // to be computed lazily during the actual execution of the algorithm
390 // (for instance, whether or not a bicomp is flipped in the final
391 // embedding). It's dispatched on the the StoreEmbeddingPolicy, since
392 // it's not needed if an embedding isn't desired.
394 typename vertex_vector_t::reverse_iterator vi, vi_end;
396 vi_end = vertices_by_dfs_num.rend();
397 for (vi = vertices_by_dfs_num.rbegin(); vi != vi_end; ++vi)
400 store_old_face_handles(StoreOldHandlesPolicy());
410 clean_up_embedding(StoreEmbeddingPolicy());
416 void walkup(vertex_t v)
419 // The point of the walkup is to follow all backedges from v to
420 // vertices with higher DFS numbers, and update pertinent_roots
421 // for the bicomp roots on the path from backedge endpoints up
422 // to v. This will set the stage for the walkdown to efficiently
423 // traverse the graph of bicomps down from v.
426 typename face_vertex_iterator< both_sides >::type walkup_iterator_t;
428 out_edge_iterator_t oi, oi_end;
429 for (boost::tie(oi, oi_end) = out_edges(v, g); oi != oi_end; ++oi)
432 vertex_t e_source(source(e, g));
433 vertex_t e_target(target(e, g));
435 if (e_source == e_target)
437 self_loops.push_back(e);
441 vertex_t w(e_source == v ? e_target : e_source);
443 // continue if not a back edge or already embedded
444 if (dfs_number[w] < dfs_number[v] || e == dfs_parent_edge[w])
447 backedges[w].push_back(e);
449 v_size_t timestamp = dfs_number[v];
450 backedge_flag[w] = timestamp;
452 walkup_iterator_t walkup_itr(w, face_handles);
453 walkup_iterator_t walkup_end;
454 vertex_t lead_vertex = w;
459 // Move to the root of the current bicomp or the first visited
460 // vertex on the bicomp by going up each side in parallel
462 while (walkup_itr != walkup_end
463 && visited[*walkup_itr] != timestamp)
465 lead_vertex = *walkup_itr;
466 visited[lead_vertex] = timestamp;
470 // If we've found the root of a bicomp through a path we haven't
471 // seen before, update pertinent_roots with a handle to the
472 // current bicomp. Otherwise, we've just seen a path we've been
473 // up before, so break out of the main while loop.
475 if (walkup_itr == walkup_end)
477 vertex_t dfs_child = canonical_dfs_child[lead_vertex];
478 vertex_t parent = dfs_parent[dfs_child];
480 visited[dfs_child_handles[dfs_child].first_vertex()]
482 visited[dfs_child_handles[dfs_child].second_vertex()]
485 if (low_point[dfs_child] < dfs_number[v]
486 || least_ancestor[dfs_child] < dfs_number[v])
488 pertinent_roots[parent]->push_back(
489 dfs_child_handles[dfs_child]);
493 pertinent_roots[parent]->push_front(
494 dfs_child_handles[dfs_child]);
497 if (parent != v && visited[parent] != timestamp)
499 walkup_itr = walkup_iterator_t(parent, face_handles);
500 lead_vertex = parent;
511 bool walkdown(vertex_t v)
513 // This procedure is where all of the action is - pertinent_roots
514 // has already been set up by the walkup, so we just need to move
515 // down bicomps from v until we find vertices that have been
516 // labeled as backedge endpoints. Once we find such a vertex, we
517 // embed the corresponding edge and glue together the bicomps on
518 // the path connecting the two vertices in the edge. This may
519 // involve flipping bicomps along the way.
521 vertex_t w; // the other endpoint of the edge we're embedding
523 while (!pertinent_roots[v]->empty())
526 face_handle_t root_face_handle = pertinent_roots[v]->front();
527 face_handle_t curr_face_handle = root_face_handle;
528 pertinent_roots[v]->pop_front();
535 typename face_vertex_iterator<>::type first_face_itr,
536 second_face_itr, face_end;
537 vertex_t first_side_vertex
538 = graph_traits< Graph >::null_vertex();
539 vertex_t second_side_vertex
540 = graph_traits< Graph >::null_vertex();
541 vertex_t first_tail, second_tail;
543 first_tail = second_tail = curr_face_handle.get_anchor();
544 first_face_itr = typename face_vertex_iterator<>::type(
545 curr_face_handle, face_handles, first_side());
546 second_face_itr = typename face_vertex_iterator<>::type(
547 curr_face_handle, face_handles, second_side());
549 for (; first_face_itr != face_end; ++first_face_itr)
551 vertex_t face_vertex(*first_face_itr);
552 if (pertinent(face_vertex, v)
553 || externally_active(face_vertex, v))
555 first_side_vertex = face_vertex;
556 second_side_vertex = face_vertex;
559 first_tail = face_vertex;
562 if (first_side_vertex == graph_traits< Graph >::null_vertex()
563 || first_side_vertex == curr_face_handle.get_anchor())
566 for (; second_face_itr != face_end; ++second_face_itr)
568 vertex_t face_vertex(*second_face_itr);
569 if (pertinent(face_vertex, v)
570 || externally_active(face_vertex, v))
572 second_side_vertex = face_vertex;
575 second_tail = face_vertex;
579 bool chose_first_upper_path;
580 if (internally_active(first_side_vertex, v))
582 chosen = first_side_vertex;
583 chose_first_upper_path = true;
585 else if (internally_active(second_side_vertex, v))
587 chosen = second_side_vertex;
588 chose_first_upper_path = false;
590 else if (pertinent(first_side_vertex, v))
592 chosen = first_side_vertex;
593 chose_first_upper_path = true;
595 else if (pertinent(second_side_vertex, v))
597 chosen = second_side_vertex;
598 chose_first_upper_path = false;
603 // If there's a pertinent vertex on the lower face
604 // between the first_face_itr and the second_face_itr,
605 // this graph isn't planar.
606 for (; *first_face_itr != second_side_vertex;
609 vertex_t p(*first_face_itr);
612 // Found a Kuratowski subgraph
614 kuratowski_x = first_side_vertex;
615 kuratowski_y = second_side_vertex;
620 // Otherwise, the fact that we didn't find a pertinent
621 // vertex on this face is fine - we should set the
622 // short-circuit edges and break out of this loop to
623 // start looking at a different pertinent root.
625 if (first_side_vertex == second_side_vertex)
630 = face_handles[first_tail].first_vertex();
632 = face_handles[first_tail].second_vertex();
633 boost::tie(first_side_vertex, first_tail)
634 = make_tuple(first_tail,
635 first == first_side_vertex ? second
638 else if (second_tail != v)
641 = face_handles[second_tail].first_vertex();
643 = face_handles[second_tail].second_vertex();
644 boost::tie(second_side_vertex, second_tail)
645 = make_tuple(second_tail,
646 first == second_side_vertex ? second
653 canonical_dfs_child[first_side_vertex]
654 = canonical_dfs_child[root_face_handle.first_vertex()];
655 canonical_dfs_child[second_side_vertex]
656 = canonical_dfs_child[root_face_handle.second_vertex()];
657 root_face_handle.set_first_vertex(first_side_vertex);
658 root_face_handle.set_second_vertex(second_side_vertex);
660 if (face_handles[first_side_vertex].first_vertex()
662 face_handles[first_side_vertex].set_first_vertex(v);
664 face_handles[first_side_vertex].set_second_vertex(v);
666 if (face_handles[second_side_vertex].first_vertex()
668 face_handles[second_side_vertex].set_first_vertex(v);
670 face_handles[second_side_vertex].set_second_vertex(v);
675 // When we unwind the stack, we need to know which direction
676 // we came down from on the top face handle
678 bool chose_first_lower_path
679 = (chose_first_upper_path
680 && face_handles[chosen].first_vertex() == first_tail)
681 || (!chose_first_upper_path
682 && face_handles[chosen].first_vertex() == second_tail);
684 // If there's a backedge at the chosen vertex, embed it now
685 if (backedge_flag[chosen] == dfs_number[v])
689 backedge_flag[chosen] = num_vertices(g) + 1;
690 add_to_merge_points(chosen, StoreOldHandlesPolicy());
692 typename edge_vector_t::iterator ei, ei_end;
693 ei_end = backedges[chosen].end();
694 for (ei = backedges[chosen].begin(); ei != ei_end; ++ei)
697 add_to_embedded_edges(e, StoreOldHandlesPolicy());
699 if (chose_first_lower_path)
700 face_handles[chosen].push_first(e, g);
702 face_handles[chosen].push_second(e, g);
707 merge_stack.push_back(make_tuple(chosen,
708 chose_first_upper_path, chose_first_lower_path));
709 curr_face_handle = *pertinent_roots[chosen]->begin();
713 // Unwind the merge stack to the root, merging all bicomps
715 bool bottom_path_follows_first;
716 bool top_path_follows_first;
717 bool next_bottom_follows_first = chose_first_upper_path;
719 vertex_t merge_point = chosen;
721 while (!merge_stack.empty())
724 bottom_path_follows_first = next_bottom_follows_first;
725 boost::tie(merge_point, next_bottom_follows_first,
726 top_path_follows_first)
727 = merge_stack.back();
728 merge_stack.pop_back();
730 face_handle_t top_handle(face_handles[merge_point]);
731 face_handle_t bottom_handle(
732 *pertinent_roots[merge_point]->begin());
734 vertex_t bottom_dfs_child = canonical_dfs_child
735 [pertinent_roots[merge_point]->begin()->first_vertex()];
737 remove_vertex_from_separated_dfs_child_list(
738 canonical_dfs_child[pertinent_roots[merge_point]
742 pertinent_roots[merge_point]->pop_front();
745 top_handle.get_anchor(), StoreOldHandlesPolicy());
747 if (top_path_follows_first && bottom_path_follows_first)
749 bottom_handle.flip();
750 top_handle.glue_first_to_second(bottom_handle);
752 else if (!top_path_follows_first
753 && bottom_path_follows_first)
755 flipped[bottom_dfs_child] = true;
756 top_handle.glue_second_to_first(bottom_handle);
758 else if (top_path_follows_first
759 && !bottom_path_follows_first)
761 flipped[bottom_dfs_child] = true;
762 top_handle.glue_first_to_second(bottom_handle);
764 else //! top_path_follows_first &&
765 //! !bottom_path_follows_first
767 bottom_handle.flip();
768 top_handle.glue_second_to_first(bottom_handle);
772 // Finally, embed all edges (v,w) at their upper end points
773 canonical_dfs_child[w]
774 = canonical_dfs_child[root_face_handle.first_vertex()];
777 root_face_handle.get_anchor(), StoreOldHandlesPolicy());
779 typename edge_vector_t::iterator ei, ei_end;
780 ei_end = backedges[chosen].end();
781 for (ei = backedges[chosen].begin(); ei != ei_end; ++ei)
783 if (next_bottom_follows_first)
784 root_face_handle.push_first(*ei, g);
786 root_face_handle.push_second(*ei, g);
789 backedges[chosen].clear();
790 curr_face_handle = root_face_handle;
794 } // while(!pertinent_roots[v]->empty())
799 void store_old_face_handles(graph::detail::no_old_handles) {}
801 void store_old_face_handles(graph::detail::store_old_handles)
803 for (typename std::vector< vertex_t >::iterator mp_itr
804 = current_merge_points.begin();
805 mp_itr != current_merge_points.end(); ++mp_itr)
807 face_handles[*mp_itr].store_old_face_handles();
809 current_merge_points.clear();
812 void add_to_merge_points(vertex_t, graph::detail::no_old_handles) {}
814 void add_to_merge_points(vertex_t v, graph::detail::store_old_handles)
816 current_merge_points.push_back(v);
819 void add_to_embedded_edges(edge_t, graph::detail::no_old_handles) {}
821 void add_to_embedded_edges(edge_t e, graph::detail::store_old_handles)
823 embedded_edges.push_back(e);
826 void clean_up_embedding(graph::detail::no_embedding) {}
828 void clean_up_embedding(graph::detail::store_embedding)
831 // If the graph isn't biconnected, we'll still have entries
832 // in the separated_dfs_child_list for some vertices. Since
833 // these represent articulation points, we can obtain a
834 // planar embedding no matter what order we embed them in.
836 vertex_iterator_t xi, xi_end;
837 for (boost::tie(xi, xi_end) = vertices(g); xi != xi_end; ++xi)
839 if (!separated_dfs_child_list[*xi]->empty())
841 typename vertex_list_t::iterator yi, yi_end;
842 yi_end = separated_dfs_child_list[*xi]->end();
843 for (yi = separated_dfs_child_list[*xi]->begin(); yi != yi_end;
846 dfs_child_handles[*yi].flip();
847 face_handles[*xi].glue_first_to_second(
848 dfs_child_handles[*yi]);
853 // Up until this point, we've flipped bicomps lazily by setting
854 // flipped[v] to true if the bicomp rooted at v was flipped (the
855 // lazy aspect of this flip is that all descendents of that vertex
856 // need to have their orientations reversed as well). Now, we
857 // traverse the DFS tree by DFS number and perform the actual
858 // flipping as needed
860 typedef typename vertex_vector_t::iterator vertex_vector_itr_t;
861 vertex_vector_itr_t vi_end = vertices_by_dfs_num.end();
862 for (vertex_vector_itr_t vi = vertices_by_dfs_num.begin(); vi != vi_end;
866 bool v_flipped = flipped[v];
867 bool p_flipped = flipped[dfs_parent[v]];
868 if (v_flipped && !p_flipped)
870 face_handles[v].flip();
872 else if (p_flipped && !v_flipped)
874 face_handles[v].flip();
883 // If there are any self-loops in the graph, they were flagged
884 // during the walkup, and we should add them to the embedding now.
885 // Adding a self loop anywhere in the embedding could never
886 // invalidate the embedding, but they would complicate the traversal
887 // if they were added during the walkup/walkdown.
889 typename edge_vector_t::iterator ei, ei_end;
890 ei_end = self_loops.end();
891 for (ei = self_loops.begin(); ei != ei_end; ++ei)
894 face_handles[source(e, g)].push_second(e, g);
898 bool pertinent(vertex_t w, vertex_t v)
900 // w is pertinent with respect to v if there is a backedge (v,w) or if
901 // w is the root of a bicomp that contains a pertinent vertex.
903 return backedge_flag[w] == dfs_number[v]
904 || !pertinent_roots[w]->empty();
907 bool externally_active(vertex_t w, vertex_t v)
909 // Let a be any proper depth-first search ancestor of v. w is externally
910 // active with respect to v if there exists a backedge (a,w) or a
911 // backedge (a,w_0) for some w_0 in a descendent bicomp of w.
913 v_size_t dfs_number_of_v = dfs_number[v];
914 return (least_ancestor[w] < dfs_number_of_v)
915 || (!separated_dfs_child_list[w]->empty()
916 && low_point[separated_dfs_child_list[w]->front()]
920 bool internally_active(vertex_t w, vertex_t v)
922 return pertinent(w, v) && !externally_active(w, v);
925 void remove_vertex_from_separated_dfs_child_list(vertex_t v)
927 typename vertex_list_t::iterator to_delete
928 = separated_node_in_parent_list[v];
929 garbage.splice(garbage.end(), *separated_dfs_child_list[dfs_parent[v]],
930 to_delete, boost::next(to_delete));
933 // End of the implementation of the basic Boyer-Myrvold Algorithm. The rest
934 // of the code below implements the isolation of a Kuratowski subgraph in
935 // the case that the input graph is not planar. This is by far the most
936 // complicated part of the implementation.
939 template < typename EdgeToBoolPropertyMap, typename EdgeContainer >
940 vertex_t kuratowski_walkup(vertex_t v, EdgeToBoolPropertyMap forbidden_edge,
941 EdgeToBoolPropertyMap goal_edge, EdgeToBoolPropertyMap is_embedded,
942 EdgeContainer& path_edges)
944 vertex_t current_endpoint;
945 bool seen_goal_edge = false;
946 out_edge_iterator_t oi, oi_end;
948 for (boost::tie(oi, oi_end) = out_edges(v, g); oi != oi_end; ++oi)
949 forbidden_edge[*oi] = true;
951 for (boost::tie(oi, oi_end) = out_edges(v, g); oi != oi_end; ++oi)
957 = target(*oi, g) == v ? source(*oi, g) : target(*oi, g);
959 if (dfs_number[current_endpoint] < dfs_number[v] || is_embedded[e]
960 || v == current_endpoint // self-loop
967 path_edges.push_back(e);
970 return current_endpoint;
973 typedef typename face_edge_iterator<>::type walkup_itr_t;
975 walkup_itr_t walkup_itr(
976 current_endpoint, face_handles, first_side());
977 walkup_itr_t walkup_end;
979 seen_goal_edge = false;
984 if (walkup_itr != walkup_end && forbidden_edge[*walkup_itr])
987 while (walkup_itr != walkup_end && !goal_edge[*walkup_itr]
988 && !forbidden_edge[*walkup_itr])
990 edge_t f(*walkup_itr);
991 forbidden_edge[f] = true;
992 path_edges.push_back(f);
993 current_endpoint = source(f, g) == current_endpoint
999 if (walkup_itr != walkup_end && goal_edge[*walkup_itr])
1001 path_edges.push_back(*walkup_itr);
1002 seen_goal_edge = true;
1006 walkup_itr = walkup_itr_t(
1007 current_endpoint, face_handles, first_side());
1015 return current_endpoint;
1017 return graph_traits< Graph >::null_vertex();
1020 template < typename OutputIterator, typename EdgeIndexMap >
1021 void extract_kuratowski_subgraph(OutputIterator o_itr, EdgeIndexMap em)
1024 // If the main algorithm has failed to embed one of the back-edges from
1025 // a vertex v, we can use the current state of the algorithm to isolate
1026 // a Kuratowksi subgraph. The isolation process breaks down into five
1027 // cases, A - E. The general configuration of all five cases is shown in
1028 // figure 1. There is a vertex v from which the planar
1029 // v embedding process could not proceed. This means that
1030 // | there exists some bicomp containing three vertices
1031 // ----- x,y, and z as shown such that x and y are externally
1032 // | | active with respect to v (which means that there are
1033 // x y two vertices x_0 and y_0 such that (1) both x_0 and
1034 // | | y_0 are proper depth-first search ancestors of v and
1035 // --z-- (2) there are two disjoint paths, one connecting x
1036 // and x_0 and one connecting y and y_0, both
1038 // fig. 1 entirely of unembedded edges). Furthermore, there
1039 // exists a vertex z_0 such that z is a depth-first
1040 // search ancestor of z_0 and (v,z_0) is an unembedded back-edge from v.
1041 // x,y and z all exist on the same bicomp, which consists entirely of
1042 // embedded edges. The five subcases break down as follows, and are
1043 // handled by the algorithm logically in the order A-E: First, if v is
1044 // not on the same bicomp as x,y, and z, a K_3_3 can be isolated - this
1045 // is case A. So, we'll assume that v is on the same bicomp as x,y, and
1046 // z. If z_0 is on a different bicomp than x,y, and z, a K_3_3 can also
1047 // be isolated - this is a case B - so we'll assume from now on that v
1048 // is on the same bicomp as x, y, and z=z_0. In this case, one can use
1049 // properties of the Boyer-Myrvold algorithm to show the existence of an
1050 // "x-y path" connecting some vertex on the "left side" of the x,y,z
1051 // bicomp with some vertex on the "right side" of the bicomp (where the
1052 // left and right are split by a line drawn through v and z.If either of
1053 // the endpoints of the x-y path is above x or y on the bicomp, a K_3_3
1054 // can be isolated - this is a case C. Otherwise, both endpoints are at
1055 // or below x and y on the bicomp. If there is a vertex alpha on the x-y
1056 // path such that alpha is not x or y and there's a path from alpha to v
1057 // that's disjoint from any of the edges on the bicomp and the x-y path,
1058 // a K_3_3 can be isolated - this is a case D. Otherwise, properties of
1059 // the Boyer-Myrvold algorithm can be used to show that another vertex
1060 // w exists on the lower half of the bicomp such that w is externally
1061 // active with respect to v. w can then be used to isolate a K_5 - this
1062 // is the configuration of case E.
1064 vertex_iterator_t vi, vi_end;
1065 edge_iterator_t ei, ei_end;
1066 out_edge_iterator_t oei, oei_end;
1067 typename std::vector< edge_t >::iterator xi, xi_end;
1069 // Clear the short-circuit edges - these are needed for the planar
1070 // testing/embedding algorithm to run in linear time, but they'll
1071 // complicate the kuratowski subgraph isolation
1072 for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
1074 face_handles[*vi].reset_vertex_cache();
1075 dfs_child_handles[*vi].reset_vertex_cache();
1078 vertex_t v = kuratowski_v;
1079 vertex_t x = kuratowski_x;
1080 vertex_t y = kuratowski_y;
1082 typedef iterator_property_map< typename std::vector< bool >::iterator,
1086 std::vector< bool > is_in_subgraph_vector(num_edges(g), false);
1087 edge_to_bool_map_t is_in_subgraph(is_in_subgraph_vector.begin(), em);
1089 std::vector< bool > is_embedded_vector(num_edges(g), false);
1090 edge_to_bool_map_t is_embedded(is_embedded_vector.begin(), em);
1092 typename std::vector< edge_t >::iterator embedded_itr, embedded_end;
1093 embedded_end = embedded_edges.end();
1094 for (embedded_itr = embedded_edges.begin();
1095 embedded_itr != embedded_end; ++embedded_itr)
1096 is_embedded[*embedded_itr] = true;
1098 // upper_face_vertex is true for x,y, and all vertices above x and y in
1100 std::vector< bool > upper_face_vertex_vector(num_vertices(g), false);
1101 vertex_to_bool_map_t upper_face_vertex(
1102 upper_face_vertex_vector.begin(), vm);
1104 std::vector< bool > lower_face_vertex_vector(num_vertices(g), false);
1105 vertex_to_bool_map_t lower_face_vertex(
1106 lower_face_vertex_vector.begin(), vm);
1108 // These next few variable declarations are all things that we need
1110 vertex_t z = graph_traits< Graph >::null_vertex();
1111 vertex_t bicomp_root;
1112 vertex_t w = graph_traits< Graph >::null_vertex();
1113 face_handle_t w_handle;
1114 face_handle_t v_dfchild_handle;
1115 vertex_t first_x_y_path_endpoint = graph_traits< Graph >::null_vertex();
1116 vertex_t second_x_y_path_endpoint
1117 = graph_traits< Graph >::null_vertex();
1118 vertex_t w_ancestor = v;
1120 detail::bm_case_t chosen_case = detail::BM_NO_CASE_CHOSEN;
1122 std::vector< edge_t > x_external_path;
1123 std::vector< edge_t > y_external_path;
1124 std::vector< edge_t > case_d_edges;
1126 std::vector< edge_t > z_v_path;
1127 std::vector< edge_t > w_path;
1129 // first, use a walkup to find a path from V that starts with a
1130 // backedge from V, then goes up until it hits either X or Y
1131 //(but doesn't find X or Y as the root of a bicomp)
1133 typename face_vertex_iterator<>::type x_upper_itr(
1134 x, face_handles, first_side());
1135 typename face_vertex_iterator<>::type x_lower_itr(
1136 x, face_handles, second_side());
1137 typename face_vertex_iterator<>::type face_itr, face_end;
1139 // Don't know which path from x is the upper or lower path -
1140 // we'll find out here
1141 for (face_itr = x_upper_itr; face_itr != face_end; ++face_itr)
1145 std::swap(x_upper_itr, x_lower_itr);
1150 upper_face_vertex[x] = true;
1152 vertex_t current_vertex = x;
1153 vertex_t previous_vertex;
1154 for (face_itr = x_upper_itr; face_itr != face_end; ++face_itr)
1156 previous_vertex = current_vertex;
1157 current_vertex = *face_itr;
1158 upper_face_vertex[current_vertex] = true;
1162 = dfs_child_handles[canonical_dfs_child[previous_vertex]];
1164 for (face_itr = x_lower_itr; *face_itr != y; ++face_itr)
1166 vertex_t current_vertex(*face_itr);
1167 lower_face_vertex[current_vertex] = true;
1169 typename face_handle_list_t::iterator roots_itr, roots_end;
1171 if (w == graph_traits< Graph >::null_vertex()) // haven't found a w
1174 roots_end = pertinent_roots[current_vertex]->end();
1175 for (roots_itr = pertinent_roots[current_vertex]->begin();
1176 roots_itr != roots_end; ++roots_itr)
1179 [canonical_dfs_child[roots_itr->first_vertex()]]
1183 w_handle = *roots_itr;
1190 for (; face_itr != face_end; ++face_itr)
1192 vertex_t current_vertex(*face_itr);
1193 upper_face_vertex[current_vertex] = true;
1194 bicomp_root = current_vertex;
1197 typedef typename face_edge_iterator<>::type walkup_itr_t;
1199 std::vector< bool > outer_face_edge_vector(num_edges(g), false);
1200 edge_to_bool_map_t outer_face_edge(outer_face_edge_vector.begin(), em);
1202 walkup_itr_t walkup_end;
1203 for (walkup_itr_t walkup_itr(x, face_handles, first_side());
1204 walkup_itr != walkup_end; ++walkup_itr)
1206 outer_face_edge[*walkup_itr] = true;
1207 is_in_subgraph[*walkup_itr] = true;
1210 for (walkup_itr_t walkup_itr(x, face_handles, second_side());
1211 walkup_itr != walkup_end; ++walkup_itr)
1213 outer_face_edge[*walkup_itr] = true;
1214 is_in_subgraph[*walkup_itr] = true;
1217 std::vector< bool > forbidden_edge_vector(num_edges(g), false);
1218 edge_to_bool_map_t forbidden_edge(forbidden_edge_vector.begin(), em);
1220 std::vector< bool > goal_edge_vector(num_edges(g), false);
1221 edge_to_bool_map_t goal_edge(goal_edge_vector.begin(), em);
1223 // Find external path to x and to y
1225 for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
1228 goal_edge[e] = !outer_face_edge[e]
1229 && (source(e, g) == x || target(e, g) == x);
1230 forbidden_edge[*ei] = outer_face_edge[*ei];
1233 vertex_t x_ancestor = v;
1234 vertex_t x_endpoint = graph_traits< Graph >::null_vertex();
1236 while (x_endpoint == graph_traits< Graph >::null_vertex())
1238 x_ancestor = dfs_parent[x_ancestor];
1239 x_endpoint = kuratowski_walkup(x_ancestor, forbidden_edge,
1240 goal_edge, is_embedded, x_external_path);
1243 for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
1246 goal_edge[e] = !outer_face_edge[e]
1247 && (source(e, g) == y || target(e, g) == y);
1248 forbidden_edge[*ei] = outer_face_edge[*ei];
1251 vertex_t y_ancestor = v;
1252 vertex_t y_endpoint = graph_traits< Graph >::null_vertex();
1254 while (y_endpoint == graph_traits< Graph >::null_vertex())
1256 y_ancestor = dfs_parent[y_ancestor];
1257 y_endpoint = kuratowski_walkup(y_ancestor, forbidden_edge,
1258 goal_edge, is_embedded, y_external_path);
1261 vertex_t parent, child;
1263 // If v isn't on the same bicomp as x and y, it's a case A
1264 if (bicomp_root != v)
1266 chosen_case = detail::BM_CASE_A;
1268 for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
1269 if (lower_face_vertex[*vi])
1270 for (boost::tie(oei, oei_end) = out_edges(*vi, g);
1271 oei != oei_end; ++oei)
1272 if (!outer_face_edge[*oei])
1273 goal_edge[*oei] = true;
1275 for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
1276 forbidden_edge[*ei] = outer_face_edge[*ei];
1278 z = kuratowski_walkup(
1279 v, forbidden_edge, goal_edge, is_embedded, z_v_path);
1281 else if (w != graph_traits< Graph >::null_vertex())
1283 chosen_case = detail::BM_CASE_B;
1285 for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
1288 goal_edge[e] = false;
1289 forbidden_edge[e] = outer_face_edge[e];
1292 goal_edge[w_handle.first_edge()] = true;
1293 goal_edge[w_handle.second_edge()] = true;
1295 z = kuratowski_walkup(
1296 v, forbidden_edge, goal_edge, is_embedded, z_v_path);
1298 for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
1300 forbidden_edge[*ei] = outer_face_edge[*ei];
1303 typename std::vector< edge_t >::iterator pi, pi_end;
1304 pi_end = z_v_path.end();
1305 for (pi = z_v_path.begin(); pi != pi_end; ++pi)
1307 goal_edge[*pi] = true;
1311 vertex_t w_endpoint = graph_traits< Graph >::null_vertex();
1313 while (w_endpoint == graph_traits< Graph >::null_vertex())
1315 w_ancestor = dfs_parent[w_ancestor];
1316 w_endpoint = kuratowski_walkup(
1317 w_ancestor, forbidden_edge, goal_edge, is_embedded, w_path);
1320 // We really want both the w walkup and the z walkup to finish on
1321 // exactly the same edge, but for convenience (since we don't have
1322 // control over which side of a bicomp a walkup moves up) we've
1323 // defined the walkup to either end at w_handle.first_edge() or
1324 // w_handle.second_edge(). If both walkups ended at different edges,
1325 // we'll do a little surgery on the w walkup path to make it follow
1326 // the other side of the final bicomp.
1328 if ((w_path.back() == w_handle.first_edge()
1329 && z_v_path.back() == w_handle.second_edge())
1330 || (w_path.back() == w_handle.second_edge()
1331 && z_v_path.back() == w_handle.first_edge()))
1333 walkup_itr_t wi, wi_end;
1334 edge_t final_edge = w_path.back();
1335 vertex_t anchor = source(final_edge, g) == w_handle.get_anchor()
1336 ? target(final_edge, g)
1337 : source(final_edge, g);
1338 if (face_handles[anchor].first_edge() == final_edge)
1339 wi = walkup_itr_t(anchor, face_handles, second_side());
1341 wi = walkup_itr_t(anchor, face_handles, first_side());
1345 for (; wi != wi_end; ++wi)
1348 if (w_path.back() == e)
1351 w_path.push_back(e);
1358 // We need to find a valid z, since the x-y path re-defines the
1359 // lower face, and the z we found earlier may now be on the upper
1362 chosen_case = detail::BM_CASE_E;
1364 // The z we've used so far is just an externally active vertex on
1365 // the lower face path, but may not be the z we need for a case C,
1366 // D, or E subgraph. the z we need now is any externally active
1367 // vertex on the lower face path with both old_face_handles edges on
1368 // the outer face. Since we know an x-y path exists, such a z must
1371 // TODO: find this z in the first place.
1375 for (face_itr = x_lower_itr; *face_itr != y; ++face_itr)
1377 vertex_t possible_z(*face_itr);
1378 if (pertinent(possible_z, v)
1379 && outer_face_edge[face_handles[possible_z]
1381 && outer_face_edge[face_handles[possible_z]
1382 .old_second_edge()])
1389 // find x-y path, and a w if one exists.
1391 if (externally_active(z, v))
1394 typedef typename face_edge_iterator< single_side,
1395 previous_iteration >::type old_face_iterator_t;
1397 old_face_iterator_t first_old_face_itr(
1398 z, face_handles, first_side());
1399 old_face_iterator_t second_old_face_itr(
1400 z, face_handles, second_side());
1401 old_face_iterator_t old_face_itr, old_face_end;
1403 std::vector< old_face_iterator_t > old_face_iterators;
1404 old_face_iterators.push_back(first_old_face_itr);
1405 old_face_iterators.push_back(second_old_face_itr);
1407 std::vector< bool > x_y_path_vertex_vector(num_vertices(g), false);
1408 vertex_to_bool_map_t x_y_path_vertex(
1409 x_y_path_vertex_vector.begin(), vm);
1411 typename std::vector< old_face_iterator_t >::iterator of_itr,
1413 of_itr_end = old_face_iterators.end();
1414 for (of_itr = old_face_iterators.begin(); of_itr != of_itr_end;
1418 old_face_itr = *of_itr;
1420 vertex_t previous_vertex;
1421 bool seen_x_or_y = false;
1422 vertex_t current_vertex = z;
1423 for (; old_face_itr != old_face_end; ++old_face_itr)
1425 edge_t e(*old_face_itr);
1426 previous_vertex = current_vertex;
1427 current_vertex = source(e, g) == current_vertex
1431 if (current_vertex == x || current_vertex == y)
1434 if (w == graph_traits< Graph >::null_vertex()
1435 && externally_active(current_vertex, v)
1436 && outer_face_edge[e]
1437 && outer_face_edge[*boost::next(old_face_itr)]
1443 if (!outer_face_edge[e])
1445 if (!upper_face_vertex[current_vertex]
1446 && !lower_face_vertex[current_vertex])
1448 x_y_path_vertex[current_vertex] = true;
1451 is_in_subgraph[e] = true;
1452 if (upper_face_vertex[source(e, g)]
1453 || lower_face_vertex[source(e, g)])
1455 if (first_x_y_path_endpoint
1456 == graph_traits< Graph >::null_vertex())
1457 first_x_y_path_endpoint = source(e, g);
1459 second_x_y_path_endpoint = source(e, g);
1461 if (upper_face_vertex[target(e, g)]
1462 || lower_face_vertex[target(e, g)])
1464 if (first_x_y_path_endpoint
1465 == graph_traits< Graph >::null_vertex())
1466 first_x_y_path_endpoint = target(e, g);
1468 second_x_y_path_endpoint = target(e, g);
1471 else if (previous_vertex == x || previous_vertex == y)
1473 chosen_case = detail::BM_CASE_C;
1478 // Look for a case D - one of v's embedded edges will connect to the
1479 // x-y path along an inner face path.
1481 // First, get a list of all of v's embedded child edges
1483 out_edge_iterator_t v_edge_itr, v_edge_end;
1484 for (boost::tie(v_edge_itr, v_edge_end) = out_edges(v, g);
1485 v_edge_itr != v_edge_end; ++v_edge_itr)
1487 edge_t embedded_edge(*v_edge_itr);
1489 if (!is_embedded[embedded_edge]
1490 || embedded_edge == dfs_parent_edge[v])
1493 case_d_edges.push_back(embedded_edge);
1495 vertex_t current_vertex = source(embedded_edge, g) == v
1496 ? target(embedded_edge, g)
1497 : source(embedded_edge, g);
1499 typename face_edge_iterator<>::type internal_face_itr,
1501 if (face_handles[current_vertex].first_vertex() == v)
1503 internal_face_itr = typename face_edge_iterator<>::type(
1504 current_vertex, face_handles, second_side());
1508 internal_face_itr = typename face_edge_iterator<>::type(
1509 current_vertex, face_handles, first_side());
1512 while (internal_face_itr != internal_face_end
1513 && !outer_face_edge[*internal_face_itr]
1514 && !x_y_path_vertex[current_vertex])
1516 edge_t e(*internal_face_itr);
1517 case_d_edges.push_back(e);
1518 current_vertex = source(e, g) == current_vertex
1521 ++internal_face_itr;
1524 if (x_y_path_vertex[current_vertex])
1526 chosen_case = detail::BM_CASE_D;
1531 case_d_edges.clear();
1536 if (chosen_case != detail::BM_CASE_B
1537 && chosen_case != detail::BM_CASE_A)
1542 for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
1545 goal_edge[e] = !outer_face_edge[e]
1546 && (source(e, g) == z || target(e, g) == z);
1547 forbidden_edge[e] = outer_face_edge[e];
1551 v, forbidden_edge, goal_edge, is_embedded, z_v_path);
1553 if (chosen_case == detail::BM_CASE_E)
1556 for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
1558 forbidden_edge[*ei] = outer_face_edge[*ei];
1559 goal_edge[*ei] = !outer_face_edge[*ei]
1560 && (source(*ei, g) == w || target(*ei, g) == w);
1563 for (boost::tie(oei, oei_end) = out_edges(w, g); oei != oei_end;
1566 if (!outer_face_edge[*oei])
1567 goal_edge[*oei] = true;
1570 typename std::vector< edge_t >::iterator pi, pi_end;
1571 pi_end = z_v_path.end();
1572 for (pi = z_v_path.begin(); pi != pi_end; ++pi)
1574 goal_edge[*pi] = true;
1578 vertex_t w_endpoint = graph_traits< Graph >::null_vertex();
1580 while (w_endpoint == graph_traits< Graph >::null_vertex())
1582 w_ancestor = dfs_parent[w_ancestor];
1583 w_endpoint = kuratowski_walkup(w_ancestor, forbidden_edge,
1584 goal_edge, is_embedded, w_path);
1589 // We're done isolating the Kuratowski subgraph at this point -
1590 // but there's still some cleaning up to do.
1592 // Update is_in_subgraph with the paths we just found
1594 xi_end = x_external_path.end();
1595 for (xi = x_external_path.begin(); xi != xi_end; ++xi)
1596 is_in_subgraph[*xi] = true;
1598 xi_end = y_external_path.end();
1599 for (xi = y_external_path.begin(); xi != xi_end; ++xi)
1600 is_in_subgraph[*xi] = true;
1602 xi_end = z_v_path.end();
1603 for (xi = z_v_path.begin(); xi != xi_end; ++xi)
1604 is_in_subgraph[*xi] = true;
1606 xi_end = case_d_edges.end();
1607 for (xi = case_d_edges.begin(); xi != xi_end; ++xi)
1608 is_in_subgraph[*xi] = true;
1610 xi_end = w_path.end();
1611 for (xi = w_path.begin(); xi != xi_end; ++xi)
1612 is_in_subgraph[*xi] = true;
1614 child = bicomp_root;
1615 parent = dfs_parent[child];
1616 while (child != parent)
1618 is_in_subgraph[dfs_parent_edge[child]] = true;
1619 boost::tie(parent, child)
1620 = std::make_pair(dfs_parent[parent], parent);
1623 // At this point, we've already isolated the Kuratowski subgraph and
1624 // collected all of the edges that compose it in the is_in_subgraph
1625 // property map. But we want the verification of such a subgraph to be
1626 // a deterministic process, and we can simplify the function
1627 // is_kuratowski_subgraph by cleaning up some edges here.
1629 if (chosen_case == detail::BM_CASE_B)
1631 is_in_subgraph[dfs_parent_edge[v]] = false;
1633 else if (chosen_case == detail::BM_CASE_C)
1635 // In a case C subgraph, at least one of the x-y path endpoints
1636 // (call it alpha) is above either x or y on the outer face. The
1637 // other endpoint may be attached at x or y OR above OR below. In
1638 // any of these three cases, we can form a K_3_3 by removing the
1639 // edge attached to v on the outer face that is NOT on the path to
1642 typename face_vertex_iterator< single_side, follow_visitor >::type
1645 if (face_handles[v_dfchild_handle.first_vertex()].first_edge()
1646 == v_dfchild_handle.first_edge())
1648 face_itr = typename face_vertex_iterator< single_side,
1649 follow_visitor >::type(v_dfchild_handle.first_vertex(),
1650 face_handles, second_side());
1654 face_itr = typename face_vertex_iterator< single_side,
1655 follow_visitor >::type(v_dfchild_handle.first_vertex(),
1656 face_handles, first_side());
1659 for (; true; ++face_itr)
1661 vertex_t current_vertex(*face_itr);
1662 if (current_vertex == x || current_vertex == y)
1664 is_in_subgraph[v_dfchild_handle.first_edge()] = false;
1667 else if (current_vertex == first_x_y_path_endpoint
1668 || current_vertex == second_x_y_path_endpoint)
1670 is_in_subgraph[v_dfchild_handle.second_edge()] = false;
1675 else if (chosen_case == detail::BM_CASE_D)
1677 // Need to remove both of the edges adjacent to v on the outer face.
1678 // remove the connecting edges from v to bicomp, then
1679 // is_kuratowski_subgraph will shrink vertices of degree 1
1682 is_in_subgraph[v_dfchild_handle.first_edge()] = false;
1683 is_in_subgraph[v_dfchild_handle.second_edge()] = false;
1685 else if (chosen_case == detail::BM_CASE_E)
1687 // Similarly to case C, if the endpoints of the x-y path are both
1688 // below x and y, we should remove an edge to allow the subgraph to
1689 // contract to a K_3_3.
1691 if ((first_x_y_path_endpoint != x && first_x_y_path_endpoint != y)
1692 || (second_x_y_path_endpoint != x
1693 && second_x_y_path_endpoint != y))
1695 is_in_subgraph[dfs_parent_edge[v]] = false;
1697 vertex_t deletion_endpoint, other_endpoint;
1698 if (lower_face_vertex[first_x_y_path_endpoint])
1700 deletion_endpoint = second_x_y_path_endpoint;
1701 other_endpoint = first_x_y_path_endpoint;
1705 deletion_endpoint = first_x_y_path_endpoint;
1706 other_endpoint = second_x_y_path_endpoint;
1709 typename face_edge_iterator<>::type face_itr, face_end;
1711 bool found_other_endpoint = false;
1712 for (face_itr = typename face_edge_iterator<>::type(
1713 deletion_endpoint, face_handles, first_side());
1714 face_itr != face_end; ++face_itr)
1716 edge_t e(*face_itr);
1717 if (source(e, g) == other_endpoint
1718 || target(e, g) == other_endpoint)
1720 found_other_endpoint = true;
1725 if (found_other_endpoint)
1727 is_in_subgraph[face_handles[deletion_endpoint].first_edge()]
1732 is_in_subgraph[face_handles[deletion_endpoint]
1739 for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
1740 if (is_in_subgraph[*ei])
1744 template < typename EdgePermutation >
1745 void make_edge_permutation(EdgePermutation perm)
1747 vertex_iterator_t vi, vi_end;
1748 for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
1752 face_handles[v].get_list(std::back_inserter(perm[v]));
1760 vertex_t kuratowski_v;
1761 vertex_t kuratowski_x;
1762 vertex_t kuratowski_y;
1764 vertex_list_t garbage; // we delete items from linked lists by
1765 // splicing them into garbage
1767 // only need these two for kuratowski subgraph isolation
1768 std::vector< vertex_t > current_merge_points;
1769 std::vector< edge_t > embedded_edges;
1771 // property map storage
1772 std::vector< v_size_t > low_point_vector;
1773 std::vector< vertex_t > dfs_parent_vector;
1774 std::vector< v_size_t > dfs_number_vector;
1775 std::vector< v_size_t > least_ancestor_vector;
1776 std::vector< face_handle_list_ptr_t > pertinent_roots_vector;
1777 std::vector< v_size_t > backedge_flag_vector;
1778 std::vector< v_size_t > visited_vector;
1779 std::vector< face_handle_t > face_handles_vector;
1780 std::vector< face_handle_t > dfs_child_handles_vector;
1781 std::vector< vertex_list_ptr_t > separated_dfs_child_list_vector;
1782 std::vector< typename vertex_list_t::iterator >
1783 separated_node_in_parent_list_vector;
1784 std::vector< vertex_t > canonical_dfs_child_vector;
1785 std::vector< bool > flipped_vector;
1786 std::vector< edge_vector_t > backedges_vector;
1787 edge_vector_t self_loops;
1788 std::vector< edge_t > dfs_parent_edge_vector;
1789 vertex_vector_t vertices_by_dfs_num;
1792 vertex_to_v_size_map_t low_point;
1793 vertex_to_vertex_map_t dfs_parent;
1794 vertex_to_v_size_map_t dfs_number;
1795 vertex_to_v_size_map_t least_ancestor;
1796 vertex_to_face_handle_list_ptr_map_t pertinent_roots;
1797 vertex_to_v_size_map_t backedge_flag;
1798 vertex_to_v_size_map_t visited;
1799 vertex_to_face_handle_map_t face_handles;
1800 vertex_to_face_handle_map_t dfs_child_handles;
1801 vertex_to_vertex_list_ptr_map_t separated_dfs_child_list;
1802 vertex_to_separated_node_map_t separated_node_in_parent_list;
1803 vertex_to_vertex_map_t canonical_dfs_child;
1804 vertex_to_bool_map_t flipped;
1805 vertex_to_edge_vector_map_t backedges;
1806 vertex_to_edge_map_t dfs_parent_edge; // only need for kuratowski
1808 merge_stack_t merge_stack;
1811 } // namespace boost
1813 #endif //__BOYER_MYRVOLD_IMPL_HPP__