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>
29 enum bm_case_t{BM_NO_CASE_CHOSEN, BM_CASE_A, BM_CASE_B, BM_CASE_C, BM_CASE_D, BM_CASE_E};
32 template<typename LowPointMap, typename DFSParentMap,
33 typename DFSNumberMap, typename LeastAncestorMap,
34 typename DFSParentEdgeMap, typename SizeType>
35 struct planar_dfs_visitor : public dfs_visitor<>
37 planar_dfs_visitor(LowPointMap lpm, DFSParentMap dfs_p,
38 DFSNumberMap dfs_n, LeastAncestorMap lam,
39 DFSParentEdgeMap dfs_edge)
49 template <typename Vertex, typename Graph>
50 void start_vertex(const Vertex& u, Graph&)
53 put(least_ancestor, u, count);
57 template <typename Vertex, typename Graph>
58 void discover_vertex(const Vertex& u, Graph&)
61 put(df_number, u, count);
65 template <typename Edge, typename Graph>
66 void tree_edge(const Edge& e, Graph& g)
68 typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
69 vertex_t s(source(e,g));
70 vertex_t t(target(e,g));
74 put(least_ancestor, t, get(df_number, s));
77 template <typename Edge, typename Graph>
78 void back_edge(const Edge& e, Graph& g)
80 typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
81 typedef typename graph_traits<Graph>::vertices_size_type v_size_t;
83 vertex_t s(source(e,g));
84 vertex_t t(target(e,g));
85 BOOST_USING_STD_MIN();
87 if ( t != get(parent, s) ) {
88 v_size_t s_low_df_number = get(low, s);
89 v_size_t t_df_number = get(df_number, t);
90 v_size_t s_least_ancestor_df_number = get(least_ancestor, s);
93 min BOOST_PREVENT_MACRO_SUBSTITUTION(s_low_df_number,
97 put(least_ancestor, s,
98 min BOOST_PREVENT_MACRO_SUBSTITUTION(s_least_ancestor_df_number,
106 template <typename Vertex, typename Graph>
107 void finish_vertex(const Vertex& u, Graph&)
109 typedef typename graph_traits<Graph>::vertices_size_type v_size_t;
111 Vertex u_parent = get(parent, u);
112 v_size_t u_parent_lowpoint = get(low, u_parent);
113 v_size_t u_lowpoint = get(low, u);
114 BOOST_USING_STD_MIN();
119 min BOOST_PREVENT_MACRO_SUBSTITUTION(u_lowpoint,
128 DFSNumberMap df_number;
129 LeastAncestorMap least_ancestor;
130 DFSParentEdgeMap df_edge;
140 template <typename Graph,
141 typename VertexIndexMap,
142 typename StoreOldHandlesPolicy = graph::detail::store_old_handles,
143 typename StoreEmbeddingPolicy = graph::detail::recursive_lazy_list
145 class boyer_myrvold_impl
148 typedef typename graph_traits<Graph>::vertices_size_type v_size_t;
149 typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
150 typedef typename graph_traits<Graph>::edge_descriptor edge_t;
151 typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator_t;
152 typedef typename graph_traits<Graph>::edge_iterator edge_iterator_t;
153 typedef typename graph_traits<Graph>::out_edge_iterator
155 typedef graph::detail::face_handle
156 <Graph, StoreOldHandlesPolicy, StoreEmbeddingPolicy> face_handle_t;
157 typedef std::vector<vertex_t> vertex_vector_t;
158 typedef std::vector<edge_t> edge_vector_t;
159 typedef std::list<vertex_t> vertex_list_t;
160 typedef std::list< face_handle_t > face_handle_list_t;
161 typedef boost::shared_ptr< face_handle_list_t > face_handle_list_ptr_t;
162 typedef boost::shared_ptr< vertex_list_t > vertex_list_ptr_t;
163 typedef boost::tuple<vertex_t, bool, bool> merge_stack_frame_t;
164 typedef std::vector<merge_stack_frame_t> merge_stack_t;
166 template <typename T>
167 struct map_vertex_to_
169 typedef iterator_property_map
170 <typename std::vector<T>::iterator, VertexIndexMap> type;
173 typedef typename map_vertex_to_<v_size_t>::type vertex_to_v_size_map_t;
174 typedef typename map_vertex_to_<vertex_t>::type vertex_to_vertex_map_t;
175 typedef typename map_vertex_to_<edge_t>::type vertex_to_edge_map_t;
176 typedef typename map_vertex_to_<vertex_list_ptr_t>::type
177 vertex_to_vertex_list_ptr_map_t;
178 typedef typename map_vertex_to_< edge_vector_t >::type
179 vertex_to_edge_vector_map_t;
180 typedef typename map_vertex_to_<bool>::type vertex_to_bool_map_t;
181 typedef typename map_vertex_to_<face_handle_t>::type
182 vertex_to_face_handle_map_t;
183 typedef typename map_vertex_to_<face_handle_list_ptr_t>::type
184 vertex_to_face_handle_list_ptr_map_t;
185 typedef typename map_vertex_to_<typename vertex_list_t::iterator>::type
186 vertex_to_separated_node_map_t;
188 template <typename BicompSideToTraverse = single_side,
189 typename VisitorType = lead_visitor,
190 typename Time = current_iteration>
191 struct face_vertex_iterator
193 typedef face_iterator<Graph,
194 vertex_to_face_handle_map_t,
196 BicompSideToTraverse,
202 template <typename BicompSideToTraverse = single_side,
203 typename Time = current_iteration>
204 struct face_edge_iterator
206 typedef face_iterator<Graph,
207 vertex_to_face_handle_map_t,
209 BicompSideToTraverse,
221 boyer_myrvold_impl(const Graph& arg_g, VertexIndexMap arg_vm):
225 low_point_vector(num_vertices(g)),
226 dfs_parent_vector(num_vertices(g)),
227 dfs_number_vector(num_vertices(g)),
228 least_ancestor_vector(num_vertices(g)),
229 pertinent_roots_vector(num_vertices(g)),
230 backedge_flag_vector(num_vertices(g), num_vertices(g) + 1),
231 visited_vector(num_vertices(g), num_vertices(g) + 1),
232 face_handles_vector(num_vertices(g)),
233 dfs_child_handles_vector(num_vertices(g)),
234 separated_dfs_child_list_vector(num_vertices(g)),
235 separated_node_in_parent_list_vector(num_vertices(g)),
236 canonical_dfs_child_vector(num_vertices(g)),
237 flipped_vector(num_vertices(g), false),
238 backedges_vector(num_vertices(g)),
239 dfs_parent_edge_vector(num_vertices(g)),
241 vertices_by_dfs_num(num_vertices(g)),
243 low_point(low_point_vector.begin(), vm),
244 dfs_parent(dfs_parent_vector.begin(), vm),
245 dfs_number(dfs_number_vector.begin(), vm),
246 least_ancestor(least_ancestor_vector.begin(), vm),
247 pertinent_roots(pertinent_roots_vector.begin(), vm),
248 backedge_flag(backedge_flag_vector.begin(), vm),
249 visited(visited_vector.begin(), vm),
250 face_handles(face_handles_vector.begin(), vm),
251 dfs_child_handles(dfs_child_handles_vector.begin(), vm),
252 separated_dfs_child_list(separated_dfs_child_list_vector.begin(), vm),
253 separated_node_in_parent_list
254 (separated_node_in_parent_list_vector.begin(), vm),
255 canonical_dfs_child(canonical_dfs_child_vector.begin(), vm),
256 flipped(flipped_vector.begin(), vm),
257 backedges(backedges_vector.begin(), vm),
258 dfs_parent_edge(dfs_parent_edge_vector.begin(), vm)
263 <vertex_to_v_size_map_t, vertex_to_vertex_map_t,
264 vertex_to_v_size_map_t, vertex_to_v_size_map_t,
265 vertex_to_edge_map_t, v_size_t> vis
266 (low_point, dfs_parent, dfs_number, least_ancestor, dfs_parent_edge);
268 // Perform a depth-first search to find each vertex's low point, least
269 // ancestor, and dfs tree information
270 depth_first_search(g, visitor(vis).vertex_index_map(vm));
272 // Sort vertices by their lowpoint - need this later in the constructor
273 vertex_vector_t vertices_by_lowpoint(num_vertices(g));
274 std::copy( vertices(g).first, vertices(g).second,
275 vertices_by_lowpoint.begin()
277 bucket_sort(vertices_by_lowpoint.begin(),
278 vertices_by_lowpoint.end(),
283 // Sort vertices by their dfs number - need this to iterate by reverse
284 // DFS number in the main loop.
285 std::copy( vertices(g).first, vertices(g).second,
286 vertices_by_dfs_num.begin()
288 bucket_sort(vertices_by_dfs_num.begin(),
289 vertices_by_dfs_num.end(),
294 // Initialize face handles. A face handle is an abstraction that serves
295 // two uses in our implementation - it allows us to efficiently move
296 // along the outer face of embedded bicomps in a partially embedded
297 // graph, and it provides storage for the planar embedding. Face
298 // handles are implemented by a sequence of edges and are associated
299 // with a particular vertex - the sequence of edges represents the
300 // current embedding of edges around that vertex, and the first and
301 // last edges in the sequence represent the pair of edges on the outer
302 // face that are adjacent to the associated vertex. This lets us embed
303 // edges in the graph by just pushing them on the front or back of the
304 // sequence of edges held by the face handles.
306 // Our algorithm starts with a DFS tree of edges (where every vertex is
307 // an articulation point and every edge is a singleton bicomp) and
308 // repeatedly merges bicomps by embedding additional edges. Note that
309 // any bicomp at any point in the algorithm can be associated with a
310 // unique edge connecting the vertex of that bicomp with the lowest DFS
311 // number (which we refer to as the "root" of the bicomp) with its DFS
312 // child in the bicomp: the existence of two such edges would contradict
313 // the properties of a DFS tree. We refer to the DFS child of the root
314 // of a bicomp as the "canonical DFS child" of the bicomp. Note that a
315 // vertex can be the root of more than one bicomp.
317 // We move around the external faces of a bicomp using a few property
318 // maps, which we'll initialize presently:
320 // - face_handles: maps a vertex to a face handle that can be used to
321 // move "up" a bicomp. For a vertex that isn't an articulation point,
322 // this holds the face handles that can be used to move around that
323 // vertex's unique bicomp. For a vertex that is an articulation point,
324 // this holds the face handles associated with the unique bicomp that
325 // the vertex is NOT the root of. These handles can therefore be used
326 // to move from any point on the outer face of the tree of bicomps
327 // around the current outer face towards the root of the DFS tree.
329 // - dfs_child_handles: these are used to hold face handles for
330 // vertices that are articulation points - dfs_child_handles[v] holds
331 // the face handles corresponding to vertex u in the bicomp with root
332 // u and canonical DFS child v.
334 // - canonical_dfs_child: this property map allows one to determine the
335 // canonical DFS child of a bicomp while traversing the outer face.
336 // This property map is only valid when applied to one of the two
337 // vertices adjacent to the root of the bicomp on the outer face. To
338 // be more precise, if v is the canonical DFS child of a bicomp,
339 // canonical_dfs_child[dfs_child_handles[v].first_vertex()] == v and
340 // canonical_dfs_child[dfs_child_handles[v].second_vertex()] == v.
342 // - pertinent_roots: given a vertex v, pertinent_roots[v] contains a
343 // list of face handles pointing to the top of bicomps that need to
344 // be visited by the current walkdown traversal (since they lead to
345 // backedges that need to be embedded). These lists are populated by
346 // the walkup and consumed by the walkdown.
348 vertex_iterator_t vi, vi_end;
349 for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
352 vertex_t parent = dfs_parent[v];
356 edge_t parent_edge = dfs_parent_edge[v];
357 add_to_embedded_edges(parent_edge, StoreOldHandlesPolicy());
358 face_handles[v] = face_handle_t(v, parent_edge, g);
359 dfs_child_handles[v] = face_handle_t(parent, parent_edge, g);
363 face_handles[v] = face_handle_t(v);
364 dfs_child_handles[v] = face_handle_t(parent);
367 canonical_dfs_child[v] = v;
368 pertinent_roots[v] = face_handle_list_ptr_t(new face_handle_list_t);
369 separated_dfs_child_list[v] = vertex_list_ptr_t(new vertex_list_t);
373 // We need to create a list of not-yet-merged depth-first children for
374 // each vertex that will be updated as bicomps get merged. We sort each
375 // list by ascending lowpoint, which allows the externally_active
376 // function to run in constant time, and we keep a pointer to each
377 // vertex's representation in its parent's list, which allows merging
380 for(typename vertex_vector_t::iterator itr =
381 vertices_by_lowpoint.begin();
382 itr != vertices_by_lowpoint.end(); ++itr)
385 vertex_t parent(dfs_parent[v]);
388 separated_node_in_parent_list[v] =
389 separated_dfs_child_list[parent]->insert
390 (separated_dfs_child_list[parent]->end(), v);
394 // The merge stack holds path information during a walkdown iteration
395 merge_stack.reserve(num_vertices(g));
407 // This is the main algorithm: starting with a DFS tree of embedded
408 // edges (which, since it's a tree, is planar), iterate through all
409 // vertices by reverse DFS number, attempting to embed all backedges
410 // connecting the current vertex to vertices with higher DFS numbers.
412 // The walkup is a procedure that examines all such backedges and sets
413 // up the required data structures so that they can be searched by the
414 // walkdown in linear time. The walkdown does the actual work of
415 // embedding edges and flipping bicomps, and can identify when it has
416 // come across a kuratowski subgraph.
418 // store_old_face_handles caches face handles from the previous
419 // iteration - this is used only for the kuratowski subgraph isolation,
420 // and is therefore dispatched based on the StoreOldHandlesPolicy.
422 // clean_up_embedding does some clean-up and fills in values that have
423 // to be computed lazily during the actual execution of the algorithm
424 // (for instance, whether or not a bicomp is flipped in the final
425 // embedding). It's dispatched on the the StoreEmbeddingPolicy, since
426 // it's not needed if an embedding isn't desired.
428 typename vertex_vector_t::reverse_iterator vi, vi_end;
430 vi_end = vertices_by_dfs_num.rend();
431 for(vi = vertices_by_dfs_num.rbegin(); vi != vi_end; ++vi)
434 store_old_face_handles(StoreOldHandlesPolicy());
445 clean_up_embedding(StoreEmbeddingPolicy());
462 void walkup(vertex_t v)
465 // The point of the walkup is to follow all backedges from v to
466 // vertices with higher DFS numbers, and update pertinent_roots
467 // for the bicomp roots on the path from backedge endpoints up
468 // to v. This will set the stage for the walkdown to efficiently
469 // traverse the graph of bicomps down from v.
471 typedef typename face_vertex_iterator<both_sides>::type walkup_iterator_t;
473 out_edge_iterator_t oi, oi_end;
474 for(boost::tie(oi,oi_end) = out_edges(v,g); oi != oi_end; ++oi)
477 vertex_t e_source(source(e,g));
478 vertex_t e_target(target(e,g));
480 if (e_source == e_target)
482 self_loops.push_back(e);
486 vertex_t w(e_source == v ? e_target : e_source);
488 //continue if not a back edge or already embedded
489 if (dfs_number[w] < dfs_number[v] || e == dfs_parent_edge[w])
492 backedges[w].push_back(e);
494 v_size_t timestamp = dfs_number[v];
495 backedge_flag[w] = timestamp;
497 walkup_iterator_t walkup_itr(w, face_handles);
498 walkup_iterator_t walkup_end;
499 vertex_t lead_vertex = w;
504 // Move to the root of the current bicomp or the first visited
505 // vertex on the bicomp by going up each side in parallel
507 while(walkup_itr != walkup_end &&
508 visited[*walkup_itr] != timestamp
511 lead_vertex = *walkup_itr;
512 visited[lead_vertex] = timestamp;
516 // If we've found the root of a bicomp through a path we haven't
517 // seen before, update pertinent_roots with a handle to the
518 // current bicomp. Otherwise, we've just seen a path we've been
519 // up before, so break out of the main while loop.
521 if (walkup_itr == walkup_end)
523 vertex_t dfs_child = canonical_dfs_child[lead_vertex];
524 vertex_t parent = dfs_parent[dfs_child];
526 visited[dfs_child_handles[dfs_child].first_vertex()]
528 visited[dfs_child_handles[dfs_child].second_vertex()]
531 if (low_point[dfs_child] < dfs_number[v] ||
532 least_ancestor[dfs_child] < dfs_number[v]
535 pertinent_roots[parent]->push_back
536 (dfs_child_handles[dfs_child]);
540 pertinent_roots[parent]->push_front
541 (dfs_child_handles[dfs_child]);
544 if (parent != v && visited[parent] != timestamp)
546 walkup_itr = walkup_iterator_t(parent, face_handles);
547 lead_vertex = parent;
566 bool walkdown(vertex_t v)
568 // This procedure is where all of the action is - pertinent_roots
569 // has already been set up by the walkup, so we just need to move
570 // down bicomps from v until we find vertices that have been
571 // labeled as backedge endpoints. Once we find such a vertex, we
572 // embed the corresponding edge and glue together the bicomps on
573 // the path connecting the two vertices in the edge. This may
574 // involve flipping bicomps along the way.
576 vertex_t w; //the other endpoint of the edge we're embedding
578 while (!pertinent_roots[v]->empty())
581 face_handle_t root_face_handle = pertinent_roots[v]->front();
582 face_handle_t curr_face_handle = root_face_handle;
583 pertinent_roots[v]->pop_front();
590 typename face_vertex_iterator<>::type
591 first_face_itr, second_face_itr, face_end;
592 vertex_t first_side_vertex
593 = graph_traits<Graph>::null_vertex();
594 vertex_t second_side_vertex;
595 vertex_t first_tail, second_tail;
597 first_tail = second_tail = curr_face_handle.get_anchor();
598 first_face_itr = typename face_vertex_iterator<>::type
599 (curr_face_handle, face_handles, first_side());
600 second_face_itr = typename face_vertex_iterator<>::type
601 (curr_face_handle, face_handles, second_side());
603 for(; first_face_itr != face_end; ++first_face_itr)
605 vertex_t face_vertex(*first_face_itr);
606 if (pertinent(face_vertex, v) ||
607 externally_active(face_vertex, v)
610 first_side_vertex = face_vertex;
611 second_side_vertex = face_vertex;
614 first_tail = face_vertex;
617 if (first_side_vertex == graph_traits<Graph>::null_vertex() ||
618 first_side_vertex == curr_face_handle.get_anchor()
622 for(;second_face_itr != face_end; ++second_face_itr)
624 vertex_t face_vertex(*second_face_itr);
625 if (pertinent(face_vertex, v) ||
626 externally_active(face_vertex, v)
629 second_side_vertex = face_vertex;
632 second_tail = face_vertex;
636 bool chose_first_upper_path;
637 if (internally_active(first_side_vertex, v))
639 chosen = first_side_vertex;
640 chose_first_upper_path = true;
642 else if (internally_active(second_side_vertex, v))
644 chosen = second_side_vertex;
645 chose_first_upper_path = false;
647 else if (pertinent(first_side_vertex, v))
649 chosen = first_side_vertex;
650 chose_first_upper_path = true;
652 else if (pertinent(second_side_vertex, v))
654 chosen = second_side_vertex;
655 chose_first_upper_path = false;
660 // If there's a pertinent vertex on the lower face
661 // between the first_face_itr and the second_face_itr,
662 // this graph isn't planar.
664 *first_face_itr != second_side_vertex;
668 vertex_t p(*first_face_itr);
671 //Found a Kuratowski subgraph
673 kuratowski_x = first_side_vertex;
674 kuratowski_y = second_side_vertex;
679 // Otherwise, the fact that we didn't find a pertinent
680 // vertex on this face is fine - we should set the
681 // short-circuit edges and break out of this loop to
682 // start looking at a different pertinent root.
684 if (first_side_vertex == second_side_vertex)
689 = face_handles[first_tail].first_vertex();
691 = face_handles[first_tail].second_vertex();
692 boost::tie(first_side_vertex, first_tail)
693 = make_tuple(first_tail,
694 first == first_side_vertex ?
698 else if (second_tail != v)
701 = face_handles[second_tail].first_vertex();
703 = face_handles[second_tail].second_vertex();
704 boost::tie(second_side_vertex, second_tail)
705 = make_tuple(second_tail,
706 first == second_side_vertex ?
713 canonical_dfs_child[first_side_vertex]
714 = canonical_dfs_child[root_face_handle.first_vertex()];
715 canonical_dfs_child[second_side_vertex]
716 = canonical_dfs_child[root_face_handle.second_vertex()];
717 root_face_handle.set_first_vertex(first_side_vertex);
718 root_face_handle.set_second_vertex(second_side_vertex);
720 if (face_handles[first_side_vertex].first_vertex() ==
723 face_handles[first_side_vertex].set_first_vertex(v);
725 face_handles[first_side_vertex].set_second_vertex(v);
727 if (face_handles[second_side_vertex].first_vertex() ==
730 face_handles[second_side_vertex].set_first_vertex(v);
732 face_handles[second_side_vertex].set_second_vertex(v);
739 // When we unwind the stack, we need to know which direction
740 // we came down from on the top face handle
742 bool chose_first_lower_path =
743 (chose_first_upper_path &&
744 face_handles[chosen].first_vertex() == first_tail)
746 (!chose_first_upper_path &&
747 face_handles[chosen].first_vertex() == second_tail);
749 //If there's a backedge at the chosen vertex, embed it now
750 if (backedge_flag[chosen] == dfs_number[v])
754 backedge_flag[chosen] = num_vertices(g) + 1;
755 add_to_merge_points(chosen, StoreOldHandlesPolicy());
757 typename edge_vector_t::iterator ei, ei_end;
758 ei_end = backedges[chosen].end();
759 for(ei = backedges[chosen].begin(); ei != ei_end; ++ei)
762 add_to_embedded_edges(e, StoreOldHandlesPolicy());
764 if (chose_first_lower_path)
765 face_handles[chosen].push_first(e, g);
767 face_handles[chosen].push_second(e, g);
773 merge_stack.push_back(make_tuple
774 (chosen, chose_first_upper_path, chose_first_lower_path)
776 curr_face_handle = *pertinent_roots[chosen]->begin();
780 //Unwind the merge stack to the root, merging all bicomps
782 bool bottom_path_follows_first;
783 bool top_path_follows_first;
784 bool next_bottom_follows_first = chose_first_upper_path;
786 vertex_t merge_point = chosen;
788 while(!merge_stack.empty())
791 bottom_path_follows_first = next_bottom_follows_first;
792 boost::tie(merge_point,
793 next_bottom_follows_first,
794 top_path_follows_first
795 ) = merge_stack.back();
796 merge_stack.pop_back();
798 face_handle_t top_handle(face_handles[merge_point]);
799 face_handle_t bottom_handle
800 (*pertinent_roots[merge_point]->begin());
802 vertex_t bottom_dfs_child = canonical_dfs_child
803 [pertinent_roots[merge_point]->begin()->first_vertex()];
805 remove_vertex_from_separated_dfs_child_list(
807 [pertinent_roots[merge_point]->begin()->first_vertex()]
810 pertinent_roots[merge_point]->pop_front();
812 add_to_merge_points(top_handle.get_anchor(),
813 StoreOldHandlesPolicy()
816 if (top_path_follows_first && bottom_path_follows_first)
818 bottom_handle.flip();
819 top_handle.glue_first_to_second(bottom_handle);
821 else if (!top_path_follows_first &&
822 bottom_path_follows_first
825 flipped[bottom_dfs_child] = true;
826 top_handle.glue_second_to_first(bottom_handle);
828 else if (top_path_follows_first &&
829 !bottom_path_follows_first
832 flipped[bottom_dfs_child] = true;
833 top_handle.glue_first_to_second(bottom_handle);
835 else //!top_path_follows_first && !bottom_path_follows_first
837 bottom_handle.flip();
838 top_handle.glue_second_to_first(bottom_handle);
843 //Finally, embed all edges (v,w) at their upper end points
844 canonical_dfs_child[w]
845 = canonical_dfs_child[root_face_handle.first_vertex()];
847 add_to_merge_points(root_face_handle.get_anchor(),
848 StoreOldHandlesPolicy()
851 typename edge_vector_t::iterator ei, ei_end;
852 ei_end = backedges[chosen].end();
853 for(ei = backedges[chosen].begin(); ei != ei_end; ++ei)
855 if (next_bottom_follows_first)
856 root_face_handle.push_first(*ei, g);
858 root_face_handle.push_second(*ei, g);
861 backedges[chosen].clear();
862 curr_face_handle = root_face_handle;
866 }//while(!pertinent_roots[v]->empty())
877 void store_old_face_handles(graph::detail::no_old_handles) {}
879 void store_old_face_handles(graph::detail::store_old_handles)
881 for(typename std::vector<vertex_t>::iterator mp_itr
882 = current_merge_points.begin();
883 mp_itr != current_merge_points.end(); ++mp_itr)
885 face_handles[*mp_itr].store_old_face_handles();
887 current_merge_points.clear();
891 void add_to_merge_points(vertex_t, graph::detail::no_old_handles) {}
893 void add_to_merge_points(vertex_t v, graph::detail::store_old_handles)
895 current_merge_points.push_back(v);
899 void add_to_embedded_edges(edge_t, graph::detail::no_old_handles) {}
901 void add_to_embedded_edges(edge_t e, graph::detail::store_old_handles)
903 embedded_edges.push_back(e);
909 void clean_up_embedding(graph::detail::no_embedding) {}
911 void clean_up_embedding(graph::detail::store_embedding)
914 // If the graph isn't biconnected, we'll still have entries
915 // in the separated_dfs_child_list for some vertices. Since
916 // these represent articulation points, we can obtain a
917 // planar embedding no matter what order we embed them in.
919 vertex_iterator_t xi, xi_end;
920 for(boost::tie(xi,xi_end) = vertices(g); xi != xi_end; ++xi)
922 if (!separated_dfs_child_list[*xi]->empty())
924 typename vertex_list_t::iterator yi, yi_end;
925 yi_end = separated_dfs_child_list[*xi]->end();
926 for(yi = separated_dfs_child_list[*xi]->begin();
930 dfs_child_handles[*yi].flip();
931 face_handles[*xi].glue_first_to_second
932 (dfs_child_handles[*yi]);
937 // Up until this point, we've flipped bicomps lazily by setting
938 // flipped[v] to true if the bicomp rooted at v was flipped (the
939 // lazy aspect of this flip is that all descendents of that vertex
940 // need to have their orientations reversed as well). Now, we
941 // traverse the DFS tree by DFS number and perform the actual
942 // flipping as needed
944 typedef typename vertex_vector_t::iterator vertex_vector_itr_t;
945 vertex_vector_itr_t vi_end = vertices_by_dfs_num.end();
946 for(vertex_vector_itr_t vi = vertices_by_dfs_num.begin();
951 bool v_flipped = flipped[v];
952 bool p_flipped = flipped[dfs_parent[v]];
953 if (v_flipped && !p_flipped)
955 face_handles[v].flip();
957 else if (p_flipped && !v_flipped)
959 face_handles[v].flip();
968 // If there are any self-loops in the graph, they were flagged
969 // during the walkup, and we should add them to the embedding now.
970 // Adding a self loop anywhere in the embedding could never
971 // invalidate the embedding, but they would complicate the traversal
972 // if they were added during the walkup/walkdown.
974 typename edge_vector_t::iterator ei, ei_end;
975 ei_end = self_loops.end();
976 for(ei = self_loops.begin(); ei != ei_end; ++ei)
979 face_handles[source(e,g)].push_second(e,g);
988 bool pertinent(vertex_t w, vertex_t v)
990 // w is pertinent with respect to v if there is a backedge (v,w) or if
991 // w is the root of a bicomp that contains a pertinent vertex.
993 return backedge_flag[w] == dfs_number[v] || !pertinent_roots[w]->empty();
998 bool externally_active(vertex_t w, vertex_t v)
1000 // Let a be any proper depth-first search ancestor of v. w is externally
1001 // active with respect to v if there exists a backedge (a,w) or a
1002 // backedge (a,w_0) for some w_0 in a descendent bicomp of w.
1004 v_size_t dfs_number_of_v = dfs_number[v];
1005 return (least_ancestor[w] < dfs_number_of_v) ||
1006 (!separated_dfs_child_list[w]->empty() &&
1007 low_point[separated_dfs_child_list[w]->front()] < dfs_number_of_v);
1012 bool internally_active(vertex_t w, vertex_t v)
1014 return pertinent(w,v) && !externally_active(w,v);
1020 void remove_vertex_from_separated_dfs_child_list(vertex_t v)
1022 typename vertex_list_t::iterator to_delete
1023 = separated_node_in_parent_list[v];
1024 garbage.splice(garbage.end(),
1025 *separated_dfs_child_list[dfs_parent[v]],
1027 boost::next(to_delete)
1035 // End of the implementation of the basic Boyer-Myrvold Algorithm. The rest
1036 // of the code below implements the isolation of a Kuratowski subgraph in
1037 // the case that the input graph is not planar. This is by far the most
1038 // complicated part of the implementation.
1048 template <typename EdgeToBoolPropertyMap, typename EdgeContainer>
1049 vertex_t kuratowski_walkup(vertex_t v,
1050 EdgeToBoolPropertyMap forbidden_edge,
1051 EdgeToBoolPropertyMap goal_edge,
1052 EdgeToBoolPropertyMap is_embedded,
1053 EdgeContainer& path_edges
1056 vertex_t current_endpoint;
1057 bool seen_goal_edge = false;
1058 out_edge_iterator_t oi, oi_end;
1060 for(boost::tie(oi,oi_end) = out_edges(v,g); oi != oi_end; ++oi)
1061 forbidden_edge[*oi] = true;
1063 for(boost::tie(oi,oi_end) = out_edges(v,g); oi != oi_end; ++oi)
1068 current_endpoint = target(*oi,g) == v ?
1069 source(*oi,g) : target(*oi,g);
1071 if (dfs_number[current_endpoint] < dfs_number[v] ||
1073 v == current_endpoint //self-loop
1080 path_edges.push_back(e);
1083 return current_endpoint;
1086 typedef typename face_edge_iterator<>::type walkup_itr_t;
1089 walkup_itr(current_endpoint, face_handles, first_side());
1090 walkup_itr_t walkup_end;
1092 seen_goal_edge = false;
1097 if (walkup_itr != walkup_end && forbidden_edge[*walkup_itr])
1100 while(walkup_itr != walkup_end &&
1101 !goal_edge[*walkup_itr] &&
1102 !forbidden_edge[*walkup_itr]
1105 edge_t f(*walkup_itr);
1106 forbidden_edge[f] = true;
1107 path_edges.push_back(f);
1109 source(f, g) == current_endpoint ?
1115 if (walkup_itr != walkup_end && goal_edge[*walkup_itr])
1117 path_edges.push_back(*walkup_itr);
1118 seen_goal_edge = true;
1123 = walkup_itr_t(current_endpoint, face_handles, first_side());
1133 return current_endpoint;
1135 return graph_traits<Graph>::null_vertex();
1146 template <typename OutputIterator, typename EdgeIndexMap>
1147 void extract_kuratowski_subgraph(OutputIterator o_itr, EdgeIndexMap em)
1150 // If the main algorithm has failed to embed one of the back-edges from
1151 // a vertex v, we can use the current state of the algorithm to isolate
1152 // a Kuratowksi subgraph. The isolation process breaks down into five
1153 // cases, A - E. The general configuration of all five cases is shown in
1154 // figure 1. There is a vertex v from which the planar
1155 // v embedding process could not proceed. This means that
1156 // | there exists some bicomp containing three vertices
1157 // ----- x,y, and z as shown such that x and y are externally
1158 // | | active with respect to v (which means that there are
1159 // x y two vertices x_0 and y_0 such that (1) both x_0 and
1160 // | | y_0 are proper depth-first search ancestors of v and
1161 // --z-- (2) there are two disjoint paths, one connecting x
1162 // and x_0 and one connecting y and y_0, both consisting
1163 // fig. 1 entirely of unembedded edges). Furthermore, there
1164 // exists a vertex z_0 such that z is a depth-first
1165 // search ancestor of z_0 and (v,z_0) is an unembedded back-edge from v.
1166 // x,y and z all exist on the same bicomp, which consists entirely of
1167 // embedded edges. The five subcases break down as follows, and are
1168 // handled by the algorithm logically in the order A-E: First, if v is
1169 // not on the same bicomp as x,y, and z, a K_3_3 can be isolated - this
1170 // is case A. So, we'll assume that v is on the same bicomp as x,y, and
1171 // z. If z_0 is on a different bicomp than x,y, and z, a K_3_3 can also
1172 // be isolated - this is a case B - so we'll assume from now on that v
1173 // is on the same bicomp as x, y, and z=z_0. In this case, one can use
1174 // properties of the Boyer-Myrvold algorithm to show the existence of an
1175 // "x-y path" connecting some vertex on the "left side" of the x,y,z
1176 // bicomp with some vertex on the "right side" of the bicomp (where the
1177 // left and right are split by a line drawn through v and z.If either of
1178 // the endpoints of the x-y path is above x or y on the bicomp, a K_3_3
1179 // can be isolated - this is a case C. Otherwise, both endpoints are at
1180 // or below x and y on the bicomp. If there is a vertex alpha on the x-y
1181 // path such that alpha is not x or y and there's a path from alpha to v
1182 // that's disjoint from any of the edges on the bicomp and the x-y path,
1183 // a K_3_3 can be isolated - this is a case D. Otherwise, properties of
1184 // the Boyer-Myrvold algorithm can be used to show that another vertex
1185 // w exists on the lower half of the bicomp such that w is externally
1186 // active with respect to v. w can then be used to isolate a K_5 - this
1187 // is the configuration of case E.
1189 vertex_iterator_t vi, vi_end;
1190 edge_iterator_t ei, ei_end;
1191 out_edge_iterator_t oei, oei_end;
1192 typename std::vector<edge_t>::iterator xi, xi_end;
1194 // Clear the short-circuit edges - these are needed for the planar
1195 // testing/embedding algorithm to run in linear time, but they'll
1196 // complicate the kuratowski subgraph isolation
1197 for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
1199 face_handles[*vi].reset_vertex_cache();
1200 dfs_child_handles[*vi].reset_vertex_cache();
1203 vertex_t v = kuratowski_v;
1204 vertex_t x = kuratowski_x;
1205 vertex_t y = kuratowski_y;
1207 typedef iterator_property_map
1208 <typename std::vector<bool>::iterator, EdgeIndexMap>
1211 std::vector<bool> is_in_subgraph_vector(num_edges(g), false);
1212 edge_to_bool_map_t is_in_subgraph(is_in_subgraph_vector.begin(), em);
1214 std::vector<bool> is_embedded_vector(num_edges(g), false);
1215 edge_to_bool_map_t is_embedded(is_embedded_vector.begin(), em);
1217 typename std::vector<edge_t>::iterator embedded_itr, embedded_end;
1218 embedded_end = embedded_edges.end();
1219 for(embedded_itr = embedded_edges.begin();
1220 embedded_itr != embedded_end; ++embedded_itr
1222 is_embedded[*embedded_itr] = true;
1224 // upper_face_vertex is true for x,y, and all vertices above x and y in
1226 std::vector<bool> upper_face_vertex_vector(num_vertices(g), false);
1227 vertex_to_bool_map_t upper_face_vertex
1228 (upper_face_vertex_vector.begin(), vm);
1230 std::vector<bool> lower_face_vertex_vector(num_vertices(g), false);
1231 vertex_to_bool_map_t lower_face_vertex
1232 (lower_face_vertex_vector.begin(), vm);
1234 // These next few variable declarations are all things that we need
1236 vertex_t z = graph_traits<Graph>::null_vertex();
1237 vertex_t bicomp_root;
1238 vertex_t w = graph_traits<Graph>::null_vertex();
1239 face_handle_t w_handle;
1240 face_handle_t v_dfchild_handle;
1241 vertex_t first_x_y_path_endpoint = graph_traits<Graph>::null_vertex();
1242 vertex_t second_x_y_path_endpoint = graph_traits<Graph>::null_vertex();
1243 vertex_t w_ancestor = v;
1245 detail::bm_case_t chosen_case = detail::BM_NO_CASE_CHOSEN;
1247 std::vector<edge_t> x_external_path;
1248 std::vector<edge_t> y_external_path;
1249 std::vector<edge_t> case_d_edges;
1251 std::vector<edge_t> z_v_path;
1252 std::vector<edge_t> w_path;
1254 //first, use a walkup to find a path from V that starts with a
1255 //backedge from V, then goes up until it hits either X or Y
1256 //(but doesn't find X or Y as the root of a bicomp)
1258 typename face_vertex_iterator<>::type
1259 x_upper_itr(x, face_handles, first_side());
1260 typename face_vertex_iterator<>::type
1261 x_lower_itr(x, face_handles, second_side());
1262 typename face_vertex_iterator<>::type face_itr, face_end;
1264 // Don't know which path from x is the upper or lower path -
1265 // we'll find out here
1266 for(face_itr = x_upper_itr; face_itr != face_end; ++face_itr)
1270 std::swap(x_upper_itr, x_lower_itr);
1275 upper_face_vertex[x] = true;
1277 vertex_t current_vertex = x;
1278 vertex_t previous_vertex;
1279 for(face_itr = x_upper_itr; face_itr != face_end; ++face_itr)
1281 previous_vertex = current_vertex;
1282 current_vertex = *face_itr;
1283 upper_face_vertex[current_vertex] = true;
1287 = dfs_child_handles[canonical_dfs_child[previous_vertex]];
1289 for(face_itr = x_lower_itr; *face_itr != y; ++face_itr)
1291 vertex_t current_vertex(*face_itr);
1292 lower_face_vertex[current_vertex] = true;
1294 typename face_handle_list_t::iterator roots_itr, roots_end;
1296 if (w == graph_traits<Graph>::null_vertex()) //haven't found a w yet
1298 roots_end = pertinent_roots[current_vertex]->end();
1299 for(roots_itr = pertinent_roots[current_vertex]->begin();
1300 roots_itr != roots_end; ++roots_itr
1303 if (low_point[canonical_dfs_child[roots_itr->first_vertex()]]
1308 w_handle = *roots_itr;
1316 for(; face_itr != face_end; ++face_itr)
1318 vertex_t current_vertex(*face_itr);
1319 upper_face_vertex[current_vertex] = true;
1320 bicomp_root = current_vertex;
1323 typedef typename face_edge_iterator<>::type walkup_itr_t;
1325 std::vector<bool> outer_face_edge_vector(num_edges(g), false);
1326 edge_to_bool_map_t outer_face_edge(outer_face_edge_vector.begin(), em);
1328 walkup_itr_t walkup_end;
1329 for(walkup_itr_t walkup_itr(x, face_handles, first_side());
1330 walkup_itr != walkup_end; ++walkup_itr
1333 outer_face_edge[*walkup_itr] = true;
1334 is_in_subgraph[*walkup_itr] = true;
1337 for(walkup_itr_t walkup_itr(x, face_handles, second_side());
1338 walkup_itr != walkup_end; ++walkup_itr
1341 outer_face_edge[*walkup_itr] = true;
1342 is_in_subgraph[*walkup_itr] = true;
1345 std::vector<bool> forbidden_edge_vector(num_edges(g), false);
1346 edge_to_bool_map_t forbidden_edge(forbidden_edge_vector.begin(), em);
1348 std::vector<bool> goal_edge_vector(num_edges(g), false);
1349 edge_to_bool_map_t goal_edge(goal_edge_vector.begin(), em);
1352 //Find external path to x and to y
1354 for(boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
1358 = !outer_face_edge[e] && (source(e,g) == x || target(e,g) == x);
1359 forbidden_edge[*ei] = outer_face_edge[*ei];
1362 vertex_t x_ancestor = v;
1363 vertex_t x_endpoint = graph_traits<Graph>::null_vertex();
1365 while(x_endpoint == graph_traits<Graph>::null_vertex())
1367 x_ancestor = dfs_parent[x_ancestor];
1368 x_endpoint = kuratowski_walkup(x_ancestor,
1378 for(boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
1382 = !outer_face_edge[e] && (source(e,g) == y || target(e,g) == y);
1383 forbidden_edge[*ei] = outer_face_edge[*ei];
1386 vertex_t y_ancestor = v;
1387 vertex_t y_endpoint = graph_traits<Graph>::null_vertex();
1389 while(y_endpoint == graph_traits<Graph>::null_vertex())
1391 y_ancestor = dfs_parent[y_ancestor];
1392 y_endpoint = kuratowski_walkup(y_ancestor,
1402 vertex_t parent, child;
1404 //If v isn't on the same bicomp as x and y, it's a case A
1405 if (bicomp_root != v)
1407 chosen_case = detail::BM_CASE_A;
1409 for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
1410 if (lower_face_vertex[*vi])
1411 for(boost::tie(oei,oei_end) = out_edges(*vi,g); oei != oei_end; ++oei)
1412 if(!outer_face_edge[*oei])
1413 goal_edge[*oei] = true;
1415 for(boost::tie(ei,ei_end) = edges(g); ei != ei_end; ++ei)
1416 forbidden_edge[*ei] = outer_face_edge[*ei];
1418 z = kuratowski_walkup
1419 (v, forbidden_edge, goal_edge, is_embedded, z_v_path);
1422 else if (w != graph_traits<Graph>::null_vertex())
1424 chosen_case = detail::BM_CASE_B;
1426 for(boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
1429 goal_edge[e] = false;
1430 forbidden_edge[e] = outer_face_edge[e];
1433 goal_edge[w_handle.first_edge()] = true;
1434 goal_edge[w_handle.second_edge()] = true;
1436 z = kuratowski_walkup(v,
1444 for(boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
1446 forbidden_edge[*ei] = outer_face_edge[*ei];
1449 typename std::vector<edge_t>::iterator pi, pi_end;
1450 pi_end = z_v_path.end();
1451 for(pi = z_v_path.begin(); pi != pi_end; ++pi)
1453 goal_edge[*pi] = true;
1457 vertex_t w_endpoint = graph_traits<Graph>::null_vertex();
1459 while(w_endpoint == graph_traits<Graph>::null_vertex())
1461 w_ancestor = dfs_parent[w_ancestor];
1462 w_endpoint = kuratowski_walkup(w_ancestor,
1471 // We really want both the w walkup and the z walkup to finish on
1472 // exactly the same edge, but for convenience (since we don't have
1473 // control over which side of a bicomp a walkup moves up) we've
1474 // defined the walkup to either end at w_handle.first_edge() or
1475 // w_handle.second_edge(). If both walkups ended at different edges,
1476 // we'll do a little surgery on the w walkup path to make it follow
1477 // the other side of the final bicomp.
1479 if ((w_path.back() == w_handle.first_edge() &&
1480 z_v_path.back() == w_handle.second_edge())
1482 (w_path.back() == w_handle.second_edge() &&
1483 z_v_path.back() == w_handle.first_edge())
1486 walkup_itr_t wi, wi_end;
1487 edge_t final_edge = w_path.back();
1489 = source(final_edge, g) == w_handle.get_anchor() ?
1490 target(final_edge, g) : source(final_edge, g);
1491 if (face_handles[anchor].first_edge() == final_edge)
1492 wi = walkup_itr_t(anchor, face_handles, second_side());
1494 wi = walkup_itr_t(anchor, face_handles, first_side());
1498 for(; wi != wi_end; ++wi)
1501 if (w_path.back() == e)
1504 w_path.push_back(e);
1513 //We need to find a valid z, since the x-y path re-defines the lower
1514 //face, and the z we found earlier may now be on the upper face.
1516 chosen_case = detail::BM_CASE_E;
1519 // The z we've used so far is just an externally active vertex on the
1520 // lower face path, but may not be the z we need for a case C, D, or
1521 // E subgraph. the z we need now is any externally active vertex on
1522 // the lower face path with both old_face_handles edges on the outer
1523 // face. Since we know an x-y path exists, such a z must also exist.
1525 //TODO: find this z in the first place.
1529 for(face_itr = x_lower_itr; *face_itr != y; ++face_itr)
1531 vertex_t possible_z(*face_itr);
1532 if (pertinent(possible_z,v) &&
1533 outer_face_edge[face_handles[possible_z].old_first_edge()] &&
1534 outer_face_edge[face_handles[possible_z].old_second_edge()]
1542 //find x-y path, and a w if one exists.
1544 if (externally_active(z,v))
1548 typedef typename face_edge_iterator
1549 <single_side, previous_iteration>::type old_face_iterator_t;
1552 first_old_face_itr(z, face_handles, first_side());
1554 second_old_face_itr(z, face_handles, second_side());
1555 old_face_iterator_t old_face_itr, old_face_end;
1557 std::vector<old_face_iterator_t> old_face_iterators;
1558 old_face_iterators.push_back(first_old_face_itr);
1559 old_face_iterators.push_back(second_old_face_itr);
1561 std::vector<bool> x_y_path_vertex_vector(num_vertices(g), false);
1562 vertex_to_bool_map_t x_y_path_vertex
1563 (x_y_path_vertex_vector.begin(), vm);
1565 typename std::vector<old_face_iterator_t>::iterator
1567 of_itr_end = old_face_iterators.end();
1568 for(of_itr = old_face_iterators.begin();
1569 of_itr != of_itr_end; ++of_itr
1573 old_face_itr = *of_itr;
1575 vertex_t previous_vertex;
1576 bool seen_x_or_y = false;
1577 vertex_t current_vertex = z;
1578 for(; old_face_itr != old_face_end; ++old_face_itr)
1580 edge_t e(*old_face_itr);
1581 previous_vertex = current_vertex;
1582 current_vertex = source(e,g) == current_vertex ?
1583 target(e,g) : source(e,g);
1585 if (current_vertex == x || current_vertex == y)
1588 if (w == graph_traits<Graph>::null_vertex() &&
1589 externally_active(current_vertex,v) &&
1590 outer_face_edge[e] &&
1591 outer_face_edge[*boost::next(old_face_itr)] &&
1598 if (!outer_face_edge[e])
1600 if (!upper_face_vertex[current_vertex] &&
1601 !lower_face_vertex[current_vertex]
1604 x_y_path_vertex[current_vertex] = true;
1607 is_in_subgraph[e] = true;
1608 if (upper_face_vertex[source(e,g)] ||
1609 lower_face_vertex[source(e,g)]
1612 if (first_x_y_path_endpoint ==
1613 graph_traits<Graph>::null_vertex()
1615 first_x_y_path_endpoint = source(e,g);
1617 second_x_y_path_endpoint = source(e,g);
1619 if (upper_face_vertex[target(e,g)] ||
1620 lower_face_vertex[target(e,g)]
1623 if (first_x_y_path_endpoint ==
1624 graph_traits<Graph>::null_vertex()
1626 first_x_y_path_endpoint = target(e,g);
1628 second_x_y_path_endpoint = target(e,g);
1633 else if (previous_vertex == x || previous_vertex == y)
1635 chosen_case = detail::BM_CASE_C;
1642 // Look for a case D - one of v's embedded edges will connect to the
1643 // x-y path along an inner face path.
1645 //First, get a list of all of v's embedded child edges
1647 out_edge_iterator_t v_edge_itr, v_edge_end;
1648 for(boost::tie(v_edge_itr,v_edge_end) = out_edges(v,g);
1649 v_edge_itr != v_edge_end; ++v_edge_itr
1652 edge_t embedded_edge(*v_edge_itr);
1654 if (!is_embedded[embedded_edge] ||
1655 embedded_edge == dfs_parent_edge[v]
1659 case_d_edges.push_back(embedded_edge);
1661 vertex_t current_vertex
1662 = source(embedded_edge,g) == v ?
1663 target(embedded_edge,g) : source(embedded_edge,g);
1665 typename face_edge_iterator<>::type
1666 internal_face_itr, internal_face_end;
1667 if (face_handles[current_vertex].first_vertex() == v)
1669 internal_face_itr = typename face_edge_iterator<>::type
1670 (current_vertex, face_handles, second_side());
1674 internal_face_itr = typename face_edge_iterator<>::type
1675 (current_vertex, face_handles, first_side());
1678 while(internal_face_itr != internal_face_end &&
1679 !outer_face_edge[*internal_face_itr] &&
1680 !x_y_path_vertex[current_vertex]
1683 edge_t e(*internal_face_itr);
1684 case_d_edges.push_back(e);
1686 source(e,g) == current_vertex ? target(e,g) : source(e,g);
1687 ++internal_face_itr;
1690 if (x_y_path_vertex[current_vertex])
1692 chosen_case = detail::BM_CASE_D;
1697 case_d_edges.clear();
1708 if (chosen_case != detail::BM_CASE_B && chosen_case != detail::BM_CASE_A)
1713 for(boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
1716 goal_edge[e] = !outer_face_edge[e] &&
1717 (source(e,g) == z || target(e,g) == z);
1718 forbidden_edge[e] = outer_face_edge[e];
1721 kuratowski_walkup(v,
1728 if (chosen_case == detail::BM_CASE_E)
1731 for(boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
1733 forbidden_edge[*ei] = outer_face_edge[*ei];
1734 goal_edge[*ei] = !outer_face_edge[*ei] &&
1735 (source(*ei,g) == w || target(*ei,g) == w);
1738 for(boost::tie(oei, oei_end) = out_edges(w,g); oei != oei_end; ++oei)
1740 if (!outer_face_edge[*oei])
1741 goal_edge[*oei] = true;
1744 typename std::vector<edge_t>::iterator pi, pi_end;
1745 pi_end = z_v_path.end();
1746 for(pi = z_v_path.begin(); pi != pi_end; ++pi)
1748 goal_edge[*pi] = true;
1752 vertex_t w_endpoint = graph_traits<Graph>::null_vertex();
1754 while(w_endpoint == graph_traits<Graph>::null_vertex())
1756 w_ancestor = dfs_parent[w_ancestor];
1757 w_endpoint = kuratowski_walkup(w_ancestor,
1772 //We're done isolating the Kuratowski subgraph at this point -
1773 //but there's still some cleaning up to do.
1775 //Update is_in_subgraph with the paths we just found
1777 xi_end = x_external_path.end();
1778 for(xi = x_external_path.begin(); xi != xi_end; ++xi)
1779 is_in_subgraph[*xi] = true;
1781 xi_end = y_external_path.end();
1782 for(xi = y_external_path.begin(); xi != xi_end; ++xi)
1783 is_in_subgraph[*xi] = true;
1785 xi_end = z_v_path.end();
1786 for(xi = z_v_path.begin(); xi != xi_end; ++xi)
1787 is_in_subgraph[*xi] = true;
1789 xi_end = case_d_edges.end();
1790 for(xi = case_d_edges.begin(); xi != xi_end; ++xi)
1791 is_in_subgraph[*xi] = true;
1793 xi_end = w_path.end();
1794 for(xi = w_path.begin(); xi != xi_end; ++xi)
1795 is_in_subgraph[*xi] = true;
1797 child = bicomp_root;
1798 parent = dfs_parent[child];
1799 while(child != parent)
1801 is_in_subgraph[dfs_parent_edge[child]] = true;
1802 boost::tie(parent, child) = std::make_pair( dfs_parent[parent], parent );
1808 // At this point, we've already isolated the Kuratowski subgraph and
1809 // collected all of the edges that compose it in the is_in_subgraph
1810 // property map. But we want the verification of such a subgraph to be
1811 // a deterministic process, and we can simplify the function
1812 // is_kuratowski_subgraph by cleaning up some edges here.
1814 if (chosen_case == detail::BM_CASE_B)
1816 is_in_subgraph[dfs_parent_edge[v]] = false;
1818 else if (chosen_case == detail::BM_CASE_C)
1820 // In a case C subgraph, at least one of the x-y path endpoints
1821 // (call it alpha) is above either x or y on the outer face. The
1822 // other endpoint may be attached at x or y OR above OR below. In
1823 // any of these three cases, we can form a K_3_3 by removing the
1824 // edge attached to v on the outer face that is NOT on the path to
1827 typename face_vertex_iterator<single_side, follow_visitor>::type
1829 if (face_handles[v_dfchild_handle.first_vertex()].first_edge() ==
1830 v_dfchild_handle.first_edge()
1833 face_itr = typename face_vertex_iterator
1834 <single_side, follow_visitor>::type
1835 (v_dfchild_handle.first_vertex(), face_handles, second_side());
1839 face_itr = typename face_vertex_iterator
1840 <single_side, follow_visitor>::type
1841 (v_dfchild_handle.first_vertex(), face_handles, first_side());
1844 for(; true; ++face_itr)
1846 vertex_t current_vertex(*face_itr);
1847 if (current_vertex == x || current_vertex == y)
1849 is_in_subgraph[v_dfchild_handle.first_edge()] = false;
1852 else if (current_vertex == first_x_y_path_endpoint ||
1853 current_vertex == second_x_y_path_endpoint)
1855 is_in_subgraph[v_dfchild_handle.second_edge()] = false;
1861 else if (chosen_case == detail::BM_CASE_D)
1863 // Need to remove both of the edges adjacent to v on the outer face.
1864 // remove the connecting edges from v to bicomp, then
1865 // is_kuratowski_subgraph will shrink vertices of degree 1
1868 is_in_subgraph[v_dfchild_handle.first_edge()] = false;
1869 is_in_subgraph[v_dfchild_handle.second_edge()] = false;
1872 else if (chosen_case == detail::BM_CASE_E)
1874 // Similarly to case C, if the endpoints of the x-y path are both
1875 // below x and y, we should remove an edge to allow the subgraph to
1876 // contract to a K_3_3.
1879 if ((first_x_y_path_endpoint != x && first_x_y_path_endpoint != y) ||
1880 (second_x_y_path_endpoint != x && second_x_y_path_endpoint != y)
1883 is_in_subgraph[dfs_parent_edge[v]] = false;
1885 vertex_t deletion_endpoint, other_endpoint;
1886 if (lower_face_vertex[first_x_y_path_endpoint])
1888 deletion_endpoint = second_x_y_path_endpoint;
1889 other_endpoint = first_x_y_path_endpoint;
1893 deletion_endpoint = first_x_y_path_endpoint;
1894 other_endpoint = second_x_y_path_endpoint;
1897 typename face_edge_iterator<>::type face_itr, face_end;
1899 bool found_other_endpoint = false;
1900 for(face_itr = typename face_edge_iterator<>::type
1901 (deletion_endpoint, face_handles, first_side());
1902 face_itr != face_end; ++face_itr
1905 edge_t e(*face_itr);
1906 if (source(e,g) == other_endpoint ||
1907 target(e,g) == other_endpoint
1910 found_other_endpoint = true;
1915 if (found_other_endpoint)
1917 is_in_subgraph[face_handles[deletion_endpoint].first_edge()]
1922 is_in_subgraph[face_handles[deletion_endpoint].second_edge()]
1930 for(boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
1931 if (is_in_subgraph[*ei])
1938 template<typename EdgePermutation>
1939 void make_edge_permutation(EdgePermutation perm)
1941 vertex_iterator_t vi, vi_end;
1942 for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
1946 face_handles[v].get_list(std::back_inserter(perm[v]));
1956 vertex_t kuratowski_v;
1957 vertex_t kuratowski_x;
1958 vertex_t kuratowski_y;
1960 vertex_list_t garbage; // we delete items from linked lists by
1961 // splicing them into garbage
1963 //only need these two for kuratowski subgraph isolation
1964 std::vector<vertex_t> current_merge_points;
1965 std::vector<edge_t> embedded_edges;
1967 //property map storage
1968 std::vector<v_size_t> low_point_vector;
1969 std::vector<vertex_t> dfs_parent_vector;
1970 std::vector<v_size_t> dfs_number_vector;
1971 std::vector<v_size_t> least_ancestor_vector;
1972 std::vector<face_handle_list_ptr_t> pertinent_roots_vector;
1973 std::vector<v_size_t> backedge_flag_vector;
1974 std::vector<v_size_t> visited_vector;
1975 std::vector< face_handle_t > face_handles_vector;
1976 std::vector< face_handle_t > dfs_child_handles_vector;
1977 std::vector< vertex_list_ptr_t > separated_dfs_child_list_vector;
1978 std::vector< typename vertex_list_t::iterator >
1979 separated_node_in_parent_list_vector;
1980 std::vector<vertex_t> canonical_dfs_child_vector;
1981 std::vector<bool> flipped_vector;
1982 std::vector<edge_vector_t> backedges_vector;
1983 edge_vector_t self_loops;
1984 std::vector<edge_t> dfs_parent_edge_vector;
1985 vertex_vector_t vertices_by_dfs_num;
1988 vertex_to_v_size_map_t low_point;
1989 vertex_to_vertex_map_t dfs_parent;
1990 vertex_to_v_size_map_t dfs_number;
1991 vertex_to_v_size_map_t least_ancestor;
1992 vertex_to_face_handle_list_ptr_map_t pertinent_roots;
1993 vertex_to_v_size_map_t backedge_flag;
1994 vertex_to_v_size_map_t visited;
1995 vertex_to_face_handle_map_t face_handles;
1996 vertex_to_face_handle_map_t dfs_child_handles;
1997 vertex_to_vertex_list_ptr_map_t separated_dfs_child_list;
1998 vertex_to_separated_node_map_t separated_node_in_parent_list;
1999 vertex_to_vertex_map_t canonical_dfs_child;
2000 vertex_to_bool_map_t flipped;
2001 vertex_to_edge_vector_map_t backedges;
2002 vertex_to_edge_map_t dfs_parent_edge; //only need for kuratowski
2004 merge_stack_t merge_stack;
2011 #endif //__BOYER_MYRVOLD_IMPL_HPP__