]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | //======================================================================= |
2 | // Copyright (c) Aaron Windsor 2007 | |
3 | // | |
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__ | |
10 | ||
11 | #include <vector> | |
12 | #include <list> | |
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> | |
23 | ||
24 | ||
25 | ||
26 | namespace boost | |
27 | { | |
28 | namespace detail { | |
29 | enum bm_case_t{BM_NO_CASE_CHOSEN, BM_CASE_A, BM_CASE_B, BM_CASE_C, BM_CASE_D, BM_CASE_E}; | |
30 | } | |
31 | ||
32 | template<typename LowPointMap, typename DFSParentMap, | |
33 | typename DFSNumberMap, typename LeastAncestorMap, | |
34 | typename DFSParentEdgeMap, typename SizeType> | |
35 | struct planar_dfs_visitor : public dfs_visitor<> | |
36 | { | |
37 | planar_dfs_visitor(LowPointMap lpm, DFSParentMap dfs_p, | |
38 | DFSNumberMap dfs_n, LeastAncestorMap lam, | |
39 | DFSParentEdgeMap dfs_edge) | |
40 | : low(lpm), | |
41 | parent(dfs_p), | |
42 | df_number(dfs_n), | |
43 | least_ancestor(lam), | |
44 | df_edge(dfs_edge), | |
45 | count(0) | |
46 | {} | |
47 | ||
48 | ||
49 | template <typename Vertex, typename Graph> | |
50 | void start_vertex(const Vertex& u, Graph&) | |
51 | { | |
52 | put(parent, u, u); | |
53 | put(least_ancestor, u, count); | |
54 | } | |
55 | ||
56 | ||
57 | template <typename Vertex, typename Graph> | |
58 | void discover_vertex(const Vertex& u, Graph&) | |
59 | { | |
60 | put(low, u, count); | |
61 | put(df_number, u, count); | |
62 | ++count; | |
63 | } | |
64 | ||
65 | template <typename Edge, typename Graph> | |
66 | void tree_edge(const Edge& e, Graph& g) | |
67 | { | |
68 | typedef typename graph_traits<Graph>::vertex_descriptor vertex_t; | |
69 | vertex_t s(source(e,g)); | |
70 | vertex_t t(target(e,g)); | |
71 | ||
72 | put(parent, t, s); | |
73 | put(df_edge, t, e); | |
74 | put(least_ancestor, t, get(df_number, s)); | |
75 | } | |
76 | ||
77 | template <typename Edge, typename Graph> | |
78 | void back_edge(const Edge& e, Graph& g) | |
79 | { | |
80 | typedef typename graph_traits<Graph>::vertex_descriptor vertex_t; | |
81 | typedef typename graph_traits<Graph>::vertices_size_type v_size_t; | |
82 | ||
83 | vertex_t s(source(e,g)); | |
84 | vertex_t t(target(e,g)); | |
85 | BOOST_USING_STD_MIN(); | |
86 | ||
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); | |
91 | ||
92 | put(low, s, | |
93 | min BOOST_PREVENT_MACRO_SUBSTITUTION(s_low_df_number, | |
94 | t_df_number) | |
95 | ); | |
96 | ||
97 | put(least_ancestor, s, | |
98 | min BOOST_PREVENT_MACRO_SUBSTITUTION(s_least_ancestor_df_number, | |
99 | t_df_number | |
100 | ) | |
101 | ); | |
102 | ||
103 | } | |
104 | } | |
105 | ||
106 | template <typename Vertex, typename Graph> | |
107 | void finish_vertex(const Vertex& u, Graph&) | |
108 | { | |
109 | typedef typename graph_traits<Graph>::vertices_size_type v_size_t; | |
110 | ||
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(); | |
115 | ||
116 | if (u_parent != u) | |
117 | { | |
118 | put(low, u_parent, | |
119 | min BOOST_PREVENT_MACRO_SUBSTITUTION(u_lowpoint, | |
120 | u_parent_lowpoint | |
121 | ) | |
122 | ); | |
123 | } | |
124 | } | |
125 | ||
126 | LowPointMap low; | |
127 | DFSParentMap parent; | |
128 | DFSNumberMap df_number; | |
129 | LeastAncestorMap least_ancestor; | |
130 | DFSParentEdgeMap df_edge; | |
131 | SizeType count; | |
132 | ||
133 | }; | |
134 | ||
135 | ||
136 | ||
137 | ||
138 | ||
139 | ||
140 | template <typename Graph, | |
141 | typename VertexIndexMap, | |
142 | typename StoreOldHandlesPolicy = graph::detail::store_old_handles, | |
143 | typename StoreEmbeddingPolicy = graph::detail::recursive_lazy_list | |
144 | > | |
145 | class boyer_myrvold_impl | |
146 | { | |
147 | ||
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 | |
154 | out_edge_iterator_t; | |
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; | |
165 | ||
166 | template <typename T> | |
167 | struct map_vertex_to_ | |
168 | { | |
169 | typedef iterator_property_map | |
170 | <typename std::vector<T>::iterator, VertexIndexMap> type; | |
171 | }; | |
172 | ||
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; | |
187 | ||
188 | template <typename BicompSideToTraverse = single_side, | |
189 | typename VisitorType = lead_visitor, | |
190 | typename Time = current_iteration> | |
191 | struct face_vertex_iterator | |
192 | { | |
193 | typedef face_iterator<Graph, | |
194 | vertex_to_face_handle_map_t, | |
195 | vertex_t, | |
196 | BicompSideToTraverse, | |
197 | VisitorType, | |
198 | Time> | |
199 | type; | |
200 | }; | |
201 | ||
202 | template <typename BicompSideToTraverse = single_side, | |
203 | typename Time = current_iteration> | |
204 | struct face_edge_iterator | |
205 | { | |
206 | typedef face_iterator<Graph, | |
207 | vertex_to_face_handle_map_t, | |
208 | edge_t, | |
209 | BicompSideToTraverse, | |
210 | lead_visitor, | |
211 | Time> | |
212 | type; | |
213 | }; | |
214 | ||
215 | ||
216 | ||
217 | public: | |
218 | ||
219 | ||
220 | ||
221 | boyer_myrvold_impl(const Graph& arg_g, VertexIndexMap arg_vm): | |
222 | g(arg_g), | |
223 | vm(arg_vm), | |
224 | ||
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)), | |
240 | ||
241 | vertices_by_dfs_num(num_vertices(g)), | |
242 | ||
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) | |
259 | ||
260 | { | |
261 | ||
262 | planar_dfs_visitor | |
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); | |
267 | ||
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)); | |
271 | ||
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() | |
276 | ); | |
277 | bucket_sort(vertices_by_lowpoint.begin(), | |
278 | vertices_by_lowpoint.end(), | |
279 | low_point, | |
280 | num_vertices(g) | |
281 | ); | |
282 | ||
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() | |
287 | ); | |
288 | bucket_sort(vertices_by_dfs_num.begin(), | |
289 | vertices_by_dfs_num.end(), | |
290 | dfs_number, | |
291 | num_vertices(g) | |
292 | ); | |
293 | ||
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. | |
305 | // | |
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. | |
316 | // | |
317 | // We move around the external faces of a bicomp using a few property | |
318 | // maps, which we'll initialize presently: | |
319 | // | |
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. | |
328 | // | |
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. | |
333 | // | |
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. | |
341 | // | |
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. | |
347 | ||
348 | vertex_iterator_t vi, vi_end; | |
349 | for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi) | |
350 | { | |
351 | vertex_t v(*vi); | |
352 | vertex_t parent = dfs_parent[v]; | |
353 | ||
354 | if (parent != v) | |
355 | { | |
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); | |
360 | } | |
361 | else | |
362 | { | |
363 | face_handles[v] = face_handle_t(v); | |
364 | dfs_child_handles[v] = face_handle_t(parent); | |
365 | } | |
366 | ||
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); | |
370 | ||
371 | } | |
372 | ||
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 | |
378 | //in constant time. | |
379 | ||
380 | for(typename vertex_vector_t::iterator itr = | |
381 | vertices_by_lowpoint.begin(); | |
382 | itr != vertices_by_lowpoint.end(); ++itr) | |
383 | { | |
384 | vertex_t v(*itr); | |
385 | vertex_t parent(dfs_parent[v]); | |
386 | if (v != parent) | |
387 | { | |
388 | separated_node_in_parent_list[v] = | |
389 | separated_dfs_child_list[parent]->insert | |
390 | (separated_dfs_child_list[parent]->end(), v); | |
391 | } | |
392 | } | |
393 | ||
394 | // The merge stack holds path information during a walkdown iteration | |
395 | merge_stack.reserve(num_vertices(g)); | |
396 | ||
397 | } | |
398 | ||
399 | ||
400 | ||
401 | ||
402 | ||
403 | ||
404 | bool is_planar() | |
405 | { | |
406 | ||
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. | |
411 | // | |
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. | |
417 | // | |
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. | |
421 | // | |
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. | |
427 | ||
428 | typename vertex_vector_t::reverse_iterator vi, vi_end; | |
429 | ||
430 | vi_end = vertices_by_dfs_num.rend(); | |
431 | for(vi = vertices_by_dfs_num.rbegin(); vi != vi_end; ++vi) | |
432 | { | |
433 | ||
434 | store_old_face_handles(StoreOldHandlesPolicy()); | |
435 | ||
436 | vertex_t v(*vi); | |
437 | ||
438 | walkup(v); | |
439 | ||
440 | if (!walkdown(v)) | |
441 | return false; | |
442 | ||
443 | } | |
444 | ||
445 | clean_up_embedding(StoreEmbeddingPolicy()); | |
446 | ||
447 | return true; | |
448 | ||
449 | } | |
450 | ||
451 | ||
452 | ||
453 | ||
454 | ||
455 | ||
456 | private: | |
457 | ||
458 | ||
459 | ||
460 | ||
461 | ||
462 | void walkup(vertex_t v) | |
463 | { | |
464 | ||
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. | |
470 | ||
471 | typedef typename face_vertex_iterator<both_sides>::type walkup_iterator_t; | |
472 | ||
473 | out_edge_iterator_t oi, oi_end; | |
474 | for(boost::tie(oi,oi_end) = out_edges(v,g); oi != oi_end; ++oi) | |
475 | { | |
476 | edge_t e(*oi); | |
477 | vertex_t e_source(source(e,g)); | |
478 | vertex_t e_target(target(e,g)); | |
479 | ||
480 | if (e_source == e_target) | |
481 | { | |
482 | self_loops.push_back(e); | |
483 | continue; | |
484 | } | |
485 | ||
486 | vertex_t w(e_source == v ? e_target : e_source); | |
487 | ||
488 | //continue if not a back edge or already embedded | |
489 | if (dfs_number[w] < dfs_number[v] || e == dfs_parent_edge[w]) | |
490 | continue; | |
491 | ||
492 | backedges[w].push_back(e); | |
493 | ||
494 | v_size_t timestamp = dfs_number[v]; | |
495 | backedge_flag[w] = timestamp; | |
496 | ||
497 | walkup_iterator_t walkup_itr(w, face_handles); | |
498 | walkup_iterator_t walkup_end; | |
499 | vertex_t lead_vertex = w; | |
500 | ||
501 | while (true) | |
502 | { | |
503 | ||
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 | |
506 | ||
507 | while(walkup_itr != walkup_end && | |
508 | visited[*walkup_itr] != timestamp | |
509 | ) | |
510 | { | |
511 | lead_vertex = *walkup_itr; | |
512 | visited[lead_vertex] = timestamp; | |
513 | ++walkup_itr; | |
514 | } | |
515 | ||
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. | |
520 | ||
521 | if (walkup_itr == walkup_end) | |
522 | { | |
523 | vertex_t dfs_child = canonical_dfs_child[lead_vertex]; | |
524 | vertex_t parent = dfs_parent[dfs_child]; | |
525 | ||
526 | visited[dfs_child_handles[dfs_child].first_vertex()] | |
527 | = timestamp; | |
528 | visited[dfs_child_handles[dfs_child].second_vertex()] | |
529 | = timestamp; | |
530 | ||
531 | if (low_point[dfs_child] < dfs_number[v] || | |
532 | least_ancestor[dfs_child] < dfs_number[v] | |
533 | ) | |
534 | { | |
535 | pertinent_roots[parent]->push_back | |
536 | (dfs_child_handles[dfs_child]); | |
537 | } | |
538 | else | |
539 | { | |
540 | pertinent_roots[parent]->push_front | |
541 | (dfs_child_handles[dfs_child]); | |
542 | } | |
543 | ||
544 | if (parent != v && visited[parent] != timestamp) | |
545 | { | |
546 | walkup_itr = walkup_iterator_t(parent, face_handles); | |
547 | lead_vertex = parent; | |
548 | } | |
549 | else | |
550 | break; | |
551 | } | |
552 | else | |
553 | break; | |
554 | } | |
555 | ||
556 | } | |
557 | ||
558 | } | |
559 | ||
560 | ||
561 | ||
562 | ||
563 | ||
564 | ||
565 | ||
566 | bool walkdown(vertex_t v) | |
567 | { | |
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. | |
575 | ||
576 | vertex_t w; //the other endpoint of the edge we're embedding | |
577 | ||
578 | while (!pertinent_roots[v]->empty()) | |
579 | { | |
580 | ||
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(); | |
584 | ||
585 | merge_stack.clear(); | |
586 | ||
587 | while(true) | |
588 | { | |
589 | ||
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; | |
596 | ||
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()); | |
602 | ||
603 | for(; first_face_itr != face_end; ++first_face_itr) | |
604 | { | |
605 | vertex_t face_vertex(*first_face_itr); | |
606 | if (pertinent(face_vertex, v) || | |
607 | externally_active(face_vertex, v) | |
608 | ) | |
609 | { | |
610 | first_side_vertex = face_vertex; | |
611 | second_side_vertex = face_vertex; | |
612 | break; | |
613 | } | |
614 | first_tail = face_vertex; | |
615 | } | |
616 | ||
617 | if (first_side_vertex == graph_traits<Graph>::null_vertex() || | |
618 | first_side_vertex == curr_face_handle.get_anchor() | |
619 | ) | |
620 | break; | |
621 | ||
622 | for(;second_face_itr != face_end; ++second_face_itr) | |
623 | { | |
624 | vertex_t face_vertex(*second_face_itr); | |
625 | if (pertinent(face_vertex, v) || | |
626 | externally_active(face_vertex, v) | |
627 | ) | |
628 | { | |
629 | second_side_vertex = face_vertex; | |
630 | break; | |
631 | } | |
632 | second_tail = face_vertex; | |
633 | } | |
634 | ||
635 | vertex_t chosen; | |
636 | bool chose_first_upper_path; | |
637 | if (internally_active(first_side_vertex, v)) | |
638 | { | |
639 | chosen = first_side_vertex; | |
640 | chose_first_upper_path = true; | |
641 | } | |
642 | else if (internally_active(second_side_vertex, v)) | |
643 | { | |
644 | chosen = second_side_vertex; | |
645 | chose_first_upper_path = false; | |
646 | } | |
647 | else if (pertinent(first_side_vertex, v)) | |
648 | { | |
649 | chosen = first_side_vertex; | |
650 | chose_first_upper_path = true; | |
651 | } | |
652 | else if (pertinent(second_side_vertex, v)) | |
653 | { | |
654 | chosen = second_side_vertex; | |
655 | chose_first_upper_path = false; | |
656 | } | |
657 | else | |
658 | { | |
659 | ||
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. | |
663 | for(; | |
664 | *first_face_itr != second_side_vertex; | |
665 | ++first_face_itr | |
666 | ) | |
667 | { | |
668 | vertex_t p(*first_face_itr); | |
669 | if (pertinent(p,v)) | |
670 | { | |
671 | //Found a Kuratowski subgraph | |
672 | kuratowski_v = v; | |
673 | kuratowski_x = first_side_vertex; | |
674 | kuratowski_y = second_side_vertex; | |
675 | return false; | |
676 | } | |
677 | } | |
678 | ||
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. | |
683 | ||
684 | if (first_side_vertex == second_side_vertex) | |
685 | { | |
686 | if (first_tail != v) | |
687 | { | |
688 | vertex_t first | |
689 | = face_handles[first_tail].first_vertex(); | |
690 | vertex_t second | |
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 ? | |
695 | second : first | |
696 | ); | |
697 | } | |
698 | else if (second_tail != v) | |
699 | { | |
700 | vertex_t first | |
701 | = face_handles[second_tail].first_vertex(); | |
702 | vertex_t second | |
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 ? | |
707 | second : first); | |
708 | } | |
709 | else | |
710 | break; | |
711 | } | |
712 | ||
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); | |
719 | ||
720 | if (face_handles[first_side_vertex].first_vertex() == | |
721 | first_tail | |
722 | ) | |
723 | face_handles[first_side_vertex].set_first_vertex(v); | |
724 | else | |
725 | face_handles[first_side_vertex].set_second_vertex(v); | |
726 | ||
727 | if (face_handles[second_side_vertex].first_vertex() == | |
728 | second_tail | |
729 | ) | |
730 | face_handles[second_side_vertex].set_first_vertex(v); | |
731 | else | |
732 | face_handles[second_side_vertex].set_second_vertex(v); | |
733 | ||
734 | break; | |
735 | ||
736 | } | |
737 | ||
738 | ||
739 | // When we unwind the stack, we need to know which direction | |
740 | // we came down from on the top face handle | |
741 | ||
742 | bool chose_first_lower_path = | |
743 | (chose_first_upper_path && | |
744 | face_handles[chosen].first_vertex() == first_tail) | |
745 | || | |
746 | (!chose_first_upper_path && | |
747 | face_handles[chosen].first_vertex() == second_tail); | |
748 | ||
749 | //If there's a backedge at the chosen vertex, embed it now | |
750 | if (backedge_flag[chosen] == dfs_number[v]) | |
751 | { | |
752 | w = chosen; | |
753 | ||
754 | backedge_flag[chosen] = num_vertices(g) + 1; | |
755 | add_to_merge_points(chosen, StoreOldHandlesPolicy()); | |
756 | ||
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) | |
760 | { | |
761 | edge_t e(*ei); | |
762 | add_to_embedded_edges(e, StoreOldHandlesPolicy()); | |
763 | ||
764 | if (chose_first_lower_path) | |
765 | face_handles[chosen].push_first(e, g); | |
766 | else | |
767 | face_handles[chosen].push_second(e, g); | |
768 | } | |
769 | ||
770 | } | |
771 | else | |
772 | { | |
773 | merge_stack.push_back(make_tuple | |
774 | (chosen, chose_first_upper_path, chose_first_lower_path) | |
775 | ); | |
776 | curr_face_handle = *pertinent_roots[chosen]->begin(); | |
777 | continue; | |
778 | } | |
779 | ||
780 | //Unwind the merge stack to the root, merging all bicomps | |
781 | ||
782 | bool bottom_path_follows_first; | |
783 | bool top_path_follows_first; | |
784 | bool next_bottom_follows_first = chose_first_upper_path; | |
785 | ||
786 | vertex_t merge_point = chosen; | |
787 | ||
788 | while(!merge_stack.empty()) | |
789 | { | |
790 | ||
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(); | |
797 | ||
798 | face_handle_t top_handle(face_handles[merge_point]); | |
799 | face_handle_t bottom_handle | |
800 | (*pertinent_roots[merge_point]->begin()); | |
801 | ||
802 | vertex_t bottom_dfs_child = canonical_dfs_child | |
803 | [pertinent_roots[merge_point]->begin()->first_vertex()]; | |
804 | ||
805 | remove_vertex_from_separated_dfs_child_list( | |
806 | canonical_dfs_child | |
807 | [pertinent_roots[merge_point]->begin()->first_vertex()] | |
808 | ); | |
809 | ||
810 | pertinent_roots[merge_point]->pop_front(); | |
811 | ||
812 | add_to_merge_points(top_handle.get_anchor(), | |
813 | StoreOldHandlesPolicy() | |
814 | ); | |
815 | ||
816 | if (top_path_follows_first && bottom_path_follows_first) | |
817 | { | |
818 | bottom_handle.flip(); | |
819 | top_handle.glue_first_to_second(bottom_handle); | |
820 | } | |
821 | else if (!top_path_follows_first && | |
822 | bottom_path_follows_first | |
823 | ) | |
824 | { | |
825 | flipped[bottom_dfs_child] = true; | |
826 | top_handle.glue_second_to_first(bottom_handle); | |
827 | } | |
828 | else if (top_path_follows_first && | |
829 | !bottom_path_follows_first | |
830 | ) | |
831 | { | |
832 | flipped[bottom_dfs_child] = true; | |
833 | top_handle.glue_first_to_second(bottom_handle); | |
834 | } | |
835 | else //!top_path_follows_first && !bottom_path_follows_first | |
836 | { | |
837 | bottom_handle.flip(); | |
838 | top_handle.glue_second_to_first(bottom_handle); | |
839 | } | |
840 | ||
841 | } | |
842 | ||
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()]; | |
846 | ||
847 | add_to_merge_points(root_face_handle.get_anchor(), | |
848 | StoreOldHandlesPolicy() | |
849 | ); | |
850 | ||
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) | |
854 | { | |
855 | if (next_bottom_follows_first) | |
856 | root_face_handle.push_first(*ei, g); | |
857 | else | |
858 | root_face_handle.push_second(*ei, g); | |
859 | } | |
860 | ||
861 | backedges[chosen].clear(); | |
862 | curr_face_handle = root_face_handle; | |
863 | ||
864 | }//while(true) | |
865 | ||
866 | }//while(!pertinent_roots[v]->empty()) | |
867 | ||
868 | return true; | |
869 | ||
870 | } | |
871 | ||
872 | ||
873 | ||
874 | ||
875 | ||
876 | ||
877 | void store_old_face_handles(graph::detail::no_old_handles) {} | |
878 | ||
879 | void store_old_face_handles(graph::detail::store_old_handles) | |
880 | { | |
881 | for(typename std::vector<vertex_t>::iterator mp_itr | |
882 | = current_merge_points.begin(); | |
883 | mp_itr != current_merge_points.end(); ++mp_itr) | |
884 | { | |
885 | face_handles[*mp_itr].store_old_face_handles(); | |
886 | } | |
887 | current_merge_points.clear(); | |
888 | } | |
889 | ||
890 | ||
891 | void add_to_merge_points(vertex_t, graph::detail::no_old_handles) {} | |
892 | ||
893 | void add_to_merge_points(vertex_t v, graph::detail::store_old_handles) | |
894 | { | |
895 | current_merge_points.push_back(v); | |
896 | } | |
897 | ||
898 | ||
899 | void add_to_embedded_edges(edge_t, graph::detail::no_old_handles) {} | |
900 | ||
901 | void add_to_embedded_edges(edge_t e, graph::detail::store_old_handles) | |
902 | { | |
903 | embedded_edges.push_back(e); | |
904 | } | |
905 | ||
906 | ||
907 | ||
908 | ||
909 | void clean_up_embedding(graph::detail::no_embedding) {} | |
910 | ||
911 | void clean_up_embedding(graph::detail::store_embedding) | |
912 | { | |
913 | ||
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. | |
918 | ||
919 | vertex_iterator_t xi, xi_end; | |
920 | for(boost::tie(xi,xi_end) = vertices(g); xi != xi_end; ++xi) | |
921 | { | |
922 | if (!separated_dfs_child_list[*xi]->empty()) | |
923 | { | |
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(); | |
927 | yi != yi_end; ++yi | |
928 | ) | |
929 | { | |
930 | dfs_child_handles[*yi].flip(); | |
931 | face_handles[*xi].glue_first_to_second | |
932 | (dfs_child_handles[*yi]); | |
933 | } | |
934 | } | |
935 | } | |
936 | ||
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 | |
943 | ||
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(); | |
947 | vi != vi_end; ++vi | |
948 | ) | |
949 | { | |
950 | vertex_t v(*vi); | |
951 | bool v_flipped = flipped[v]; | |
952 | bool p_flipped = flipped[dfs_parent[v]]; | |
953 | if (v_flipped && !p_flipped) | |
954 | { | |
955 | face_handles[v].flip(); | |
956 | } | |
957 | else if (p_flipped && !v_flipped) | |
958 | { | |
959 | face_handles[v].flip(); | |
960 | flipped[v] = true; | |
961 | } | |
962 | else | |
963 | { | |
964 | flipped[v] = false; | |
965 | } | |
966 | } | |
967 | ||
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. | |
973 | ||
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) | |
977 | { | |
978 | edge_t e(*ei); | |
979 | face_handles[source(e,g)].push_second(e,g); | |
980 | } | |
981 | ||
982 | } | |
983 | ||
984 | ||
985 | ||
986 | ||
987 | ||
988 | bool pertinent(vertex_t w, vertex_t v) | |
989 | { | |
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. | |
992 | ||
993 | return backedge_flag[w] == dfs_number[v] || !pertinent_roots[w]->empty(); | |
994 | } | |
995 | ||
996 | ||
997 | ||
998 | bool externally_active(vertex_t w, vertex_t v) | |
999 | { | |
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. | |
1003 | ||
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); | |
1008 | } | |
1009 | ||
1010 | ||
1011 | ||
1012 | bool internally_active(vertex_t w, vertex_t v) | |
1013 | { | |
1014 | return pertinent(w,v) && !externally_active(w,v); | |
1015 | } | |
1016 | ||
1017 | ||
1018 | ||
1019 | ||
1020 | void remove_vertex_from_separated_dfs_child_list(vertex_t v) | |
1021 | { | |
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]], | |
1026 | to_delete, | |
1027 | boost::next(to_delete) | |
1028 | ); | |
1029 | } | |
1030 | ||
1031 | ||
1032 | ||
1033 | ||
1034 | ||
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. | |
1039 | ||
1040 | ||
1041 | ||
1042 | ||
1043 | public: | |
1044 | ||
1045 | ||
1046 | ||
1047 | ||
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 | |
1054 | ) | |
1055 | { | |
1056 | vertex_t current_endpoint; | |
1057 | bool seen_goal_edge = false; | |
1058 | out_edge_iterator_t oi, oi_end; | |
1059 | ||
1060 | for(boost::tie(oi,oi_end) = out_edges(v,g); oi != oi_end; ++oi) | |
1061 | forbidden_edge[*oi] = true; | |
1062 | ||
1063 | for(boost::tie(oi,oi_end) = out_edges(v,g); oi != oi_end; ++oi) | |
1064 | { | |
1065 | path_edges.clear(); | |
1066 | ||
1067 | edge_t e(*oi); | |
1068 | current_endpoint = target(*oi,g) == v ? | |
1069 | source(*oi,g) : target(*oi,g); | |
1070 | ||
1071 | if (dfs_number[current_endpoint] < dfs_number[v] || | |
1072 | is_embedded[e] || | |
1073 | v == current_endpoint //self-loop | |
1074 | ) | |
1075 | { | |
1076 | //Not a backedge | |
1077 | continue; | |
1078 | } | |
1079 | ||
1080 | path_edges.push_back(e); | |
1081 | if (goal_edge[e]) | |
1082 | { | |
1083 | return current_endpoint; | |
1084 | } | |
1085 | ||
1086 | typedef typename face_edge_iterator<>::type walkup_itr_t; | |
1087 | ||
1088 | walkup_itr_t | |
1089 | walkup_itr(current_endpoint, face_handles, first_side()); | |
1090 | walkup_itr_t walkup_end; | |
1091 | ||
1092 | seen_goal_edge = false; | |
1093 | ||
1094 | while (true) | |
1095 | { | |
1096 | ||
1097 | if (walkup_itr != walkup_end && forbidden_edge[*walkup_itr]) | |
1098 | break; | |
1099 | ||
1100 | while(walkup_itr != walkup_end && | |
1101 | !goal_edge[*walkup_itr] && | |
1102 | !forbidden_edge[*walkup_itr] | |
1103 | ) | |
1104 | { | |
1105 | edge_t f(*walkup_itr); | |
1106 | forbidden_edge[f] = true; | |
1107 | path_edges.push_back(f); | |
1108 | current_endpoint = | |
1109 | source(f, g) == current_endpoint ? | |
1110 | target(f, g) : | |
1111 | source(f,g); | |
1112 | ++walkup_itr; | |
1113 | } | |
1114 | ||
1115 | if (walkup_itr != walkup_end && goal_edge[*walkup_itr]) | |
1116 | { | |
1117 | path_edges.push_back(*walkup_itr); | |
1118 | seen_goal_edge = true; | |
1119 | break; | |
1120 | } | |
1121 | ||
1122 | walkup_itr | |
1123 | = walkup_itr_t(current_endpoint, face_handles, first_side()); | |
1124 | ||
1125 | } | |
1126 | ||
1127 | if (seen_goal_edge) | |
1128 | break; | |
1129 | ||
1130 | } | |
1131 | ||
1132 | if (seen_goal_edge) | |
1133 | return current_endpoint; | |
1134 | else | |
1135 | return graph_traits<Graph>::null_vertex(); | |
1136 | ||
1137 | } | |
1138 | ||
1139 | ||
1140 | ||
1141 | ||
1142 | ||
1143 | ||
1144 | ||
1145 | ||
1146 | template <typename OutputIterator, typename EdgeIndexMap> | |
1147 | void extract_kuratowski_subgraph(OutputIterator o_itr, EdgeIndexMap em) | |
1148 | { | |
1149 | ||
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. | |
1188 | ||
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; | |
1193 | ||
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) | |
1198 | { | |
1199 | face_handles[*vi].reset_vertex_cache(); | |
1200 | dfs_child_handles[*vi].reset_vertex_cache(); | |
1201 | } | |
1202 | ||
1203 | vertex_t v = kuratowski_v; | |
1204 | vertex_t x = kuratowski_x; | |
1205 | vertex_t y = kuratowski_y; | |
1206 | ||
1207 | typedef iterator_property_map | |
1208 | <typename std::vector<bool>::iterator, EdgeIndexMap> | |
1209 | edge_to_bool_map_t; | |
1210 | ||
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); | |
1213 | ||
1214 | std::vector<bool> is_embedded_vector(num_edges(g), false); | |
1215 | edge_to_bool_map_t is_embedded(is_embedded_vector.begin(), em); | |
1216 | ||
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 | |
1221 | ) | |
1222 | is_embedded[*embedded_itr] = true; | |
1223 | ||
1224 | // upper_face_vertex is true for x,y, and all vertices above x and y in | |
1225 | // the bicomp | |
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); | |
1229 | ||
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); | |
1233 | ||
1234 | // These next few variable declarations are all things that we need | |
1235 | // to find. | |
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; | |
1244 | ||
1245 | detail::bm_case_t chosen_case = detail::BM_NO_CASE_CHOSEN; | |
1246 | ||
1247 | std::vector<edge_t> x_external_path; | |
1248 | std::vector<edge_t> y_external_path; | |
1249 | std::vector<edge_t> case_d_edges; | |
1250 | ||
1251 | std::vector<edge_t> z_v_path; | |
1252 | std::vector<edge_t> w_path; | |
1253 | ||
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) | |
1257 | ||
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; | |
1263 | ||
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) | |
1267 | { | |
1268 | if (*face_itr == y) | |
1269 | { | |
1270 | std::swap(x_upper_itr, x_lower_itr); | |
1271 | break; | |
1272 | } | |
1273 | } | |
1274 | ||
1275 | upper_face_vertex[x] = true; | |
1276 | ||
1277 | vertex_t current_vertex = x; | |
1278 | vertex_t previous_vertex; | |
1279 | for(face_itr = x_upper_itr; face_itr != face_end; ++face_itr) | |
1280 | { | |
1281 | previous_vertex = current_vertex; | |
1282 | current_vertex = *face_itr; | |
1283 | upper_face_vertex[current_vertex] = true; | |
1284 | } | |
1285 | ||
1286 | v_dfchild_handle | |
1287 | = dfs_child_handles[canonical_dfs_child[previous_vertex]]; | |
1288 | ||
1289 | for(face_itr = x_lower_itr; *face_itr != y; ++face_itr) | |
1290 | { | |
1291 | vertex_t current_vertex(*face_itr); | |
1292 | lower_face_vertex[current_vertex] = true; | |
1293 | ||
1294 | typename face_handle_list_t::iterator roots_itr, roots_end; | |
1295 | ||
1296 | if (w == graph_traits<Graph>::null_vertex()) //haven't found a w yet | |
1297 | { | |
1298 | roots_end = pertinent_roots[current_vertex]->end(); | |
1299 | for(roots_itr = pertinent_roots[current_vertex]->begin(); | |
1300 | roots_itr != roots_end; ++roots_itr | |
1301 | ) | |
1302 | { | |
1303 | if (low_point[canonical_dfs_child[roots_itr->first_vertex()]] | |
1304 | < dfs_number[v] | |
1305 | ) | |
1306 | { | |
1307 | w = current_vertex; | |
1308 | w_handle = *roots_itr; | |
1309 | break; | |
1310 | } | |
1311 | } | |
1312 | } | |
1313 | ||
1314 | } | |
1315 | ||
1316 | for(; face_itr != face_end; ++face_itr) | |
1317 | { | |
1318 | vertex_t current_vertex(*face_itr); | |
1319 | upper_face_vertex[current_vertex] = true; | |
1320 | bicomp_root = current_vertex; | |
1321 | } | |
1322 | ||
1323 | typedef typename face_edge_iterator<>::type walkup_itr_t; | |
1324 | ||
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); | |
1327 | ||
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 | |
1331 | ) | |
1332 | { | |
1333 | outer_face_edge[*walkup_itr] = true; | |
1334 | is_in_subgraph[*walkup_itr] = true; | |
1335 | } | |
1336 | ||
1337 | for(walkup_itr_t walkup_itr(x, face_handles, second_side()); | |
1338 | walkup_itr != walkup_end; ++walkup_itr | |
1339 | ) | |
1340 | { | |
1341 | outer_face_edge[*walkup_itr] = true; | |
1342 | is_in_subgraph[*walkup_itr] = true; | |
1343 | } | |
1344 | ||
1345 | std::vector<bool> forbidden_edge_vector(num_edges(g), false); | |
1346 | edge_to_bool_map_t forbidden_edge(forbidden_edge_vector.begin(), em); | |
1347 | ||
1348 | std::vector<bool> goal_edge_vector(num_edges(g), false); | |
1349 | edge_to_bool_map_t goal_edge(goal_edge_vector.begin(), em); | |
1350 | ||
1351 | ||
1352 | //Find external path to x and to y | |
1353 | ||
1354 | for(boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) | |
1355 | { | |
1356 | edge_t e(*ei); | |
1357 | goal_edge[e] | |
1358 | = !outer_face_edge[e] && (source(e,g) == x || target(e,g) == x); | |
1359 | forbidden_edge[*ei] = outer_face_edge[*ei]; | |
1360 | } | |
1361 | ||
1362 | vertex_t x_ancestor = v; | |
1363 | vertex_t x_endpoint = graph_traits<Graph>::null_vertex(); | |
1364 | ||
1365 | while(x_endpoint == graph_traits<Graph>::null_vertex()) | |
1366 | { | |
1367 | x_ancestor = dfs_parent[x_ancestor]; | |
1368 | x_endpoint = kuratowski_walkup(x_ancestor, | |
1369 | forbidden_edge, | |
1370 | goal_edge, | |
1371 | is_embedded, | |
1372 | x_external_path | |
1373 | ); | |
1374 | ||
1375 | } | |
1376 | ||
1377 | ||
1378 | for(boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) | |
1379 | { | |
1380 | edge_t e(*ei); | |
1381 | goal_edge[e] | |
1382 | = !outer_face_edge[e] && (source(e,g) == y || target(e,g) == y); | |
1383 | forbidden_edge[*ei] = outer_face_edge[*ei]; | |
1384 | } | |
1385 | ||
1386 | vertex_t y_ancestor = v; | |
1387 | vertex_t y_endpoint = graph_traits<Graph>::null_vertex(); | |
1388 | ||
1389 | while(y_endpoint == graph_traits<Graph>::null_vertex()) | |
1390 | { | |
1391 | y_ancestor = dfs_parent[y_ancestor]; | |
1392 | y_endpoint = kuratowski_walkup(y_ancestor, | |
1393 | forbidden_edge, | |
1394 | goal_edge, | |
1395 | is_embedded, | |
1396 | y_external_path | |
1397 | ); | |
1398 | ||
1399 | } | |
1400 | ||
1401 | ||
1402 | vertex_t parent, child; | |
1403 | ||
1404 | //If v isn't on the same bicomp as x and y, it's a case A | |
1405 | if (bicomp_root != v) | |
1406 | { | |
1407 | chosen_case = detail::BM_CASE_A; | |
1408 | ||
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; | |
1414 | ||
1415 | for(boost::tie(ei,ei_end) = edges(g); ei != ei_end; ++ei) | |
1416 | forbidden_edge[*ei] = outer_face_edge[*ei]; | |
1417 | ||
1418 | z = kuratowski_walkup | |
1419 | (v, forbidden_edge, goal_edge, is_embedded, z_v_path); | |
1420 | ||
1421 | } | |
1422 | else if (w != graph_traits<Graph>::null_vertex()) | |
1423 | { | |
1424 | chosen_case = detail::BM_CASE_B; | |
1425 | ||
1426 | for(boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) | |
1427 | { | |
1428 | edge_t e(*ei); | |
1429 | goal_edge[e] = false; | |
1430 | forbidden_edge[e] = outer_face_edge[e]; | |
1431 | } | |
1432 | ||
1433 | goal_edge[w_handle.first_edge()] = true; | |
1434 | goal_edge[w_handle.second_edge()] = true; | |
1435 | ||
1436 | z = kuratowski_walkup(v, | |
1437 | forbidden_edge, | |
1438 | goal_edge, | |
1439 | is_embedded, | |
1440 | z_v_path | |
1441 | ); | |
1442 | ||
1443 | ||
1444 | for(boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) | |
1445 | { | |
1446 | forbidden_edge[*ei] = outer_face_edge[*ei]; | |
1447 | } | |
1448 | ||
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) | |
1452 | { | |
1453 | goal_edge[*pi] = true; | |
1454 | } | |
1455 | ||
1456 | w_ancestor = v; | |
1457 | vertex_t w_endpoint = graph_traits<Graph>::null_vertex(); | |
1458 | ||
1459 | while(w_endpoint == graph_traits<Graph>::null_vertex()) | |
1460 | { | |
1461 | w_ancestor = dfs_parent[w_ancestor]; | |
1462 | w_endpoint = kuratowski_walkup(w_ancestor, | |
1463 | forbidden_edge, | |
1464 | goal_edge, | |
1465 | is_embedded, | |
1466 | w_path | |
1467 | ); | |
1468 | ||
1469 | } | |
1470 | ||
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. | |
1478 | ||
1479 | if ((w_path.back() == w_handle.first_edge() && | |
1480 | z_v_path.back() == w_handle.second_edge()) | |
1481 | || | |
1482 | (w_path.back() == w_handle.second_edge() && | |
1483 | z_v_path.back() == w_handle.first_edge()) | |
1484 | ) | |
1485 | { | |
1486 | walkup_itr_t wi, wi_end; | |
1487 | edge_t final_edge = w_path.back(); | |
1488 | vertex_t anchor | |
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()); | |
1493 | else | |
1494 | wi = walkup_itr_t(anchor, face_handles, first_side()); | |
1495 | ||
1496 | w_path.pop_back(); | |
1497 | ||
1498 | for(; wi != wi_end; ++wi) | |
1499 | { | |
1500 | edge_t e(*wi); | |
1501 | if (w_path.back() == e) | |
1502 | w_path.pop_back(); | |
1503 | else | |
1504 | w_path.push_back(e); | |
1505 | } | |
1506 | } | |
1507 | ||
1508 | ||
1509 | } | |
1510 | else | |
1511 | { | |
1512 | ||
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. | |
1515 | ||
1516 | chosen_case = detail::BM_CASE_E; | |
1517 | ||
1518 | ||
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. | |
1524 | ||
1525 | //TODO: find this z in the first place. | |
1526 | ||
1527 | //find the new z | |
1528 | ||
1529 | for(face_itr = x_lower_itr; *face_itr != y; ++face_itr) | |
1530 | { | |
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()] | |
1535 | ) | |
1536 | { | |
1537 | z = possible_z; | |
1538 | break; | |
1539 | } | |
1540 | } | |
1541 | ||
1542 | //find x-y path, and a w if one exists. | |
1543 | ||
1544 | if (externally_active(z,v)) | |
1545 | w = z; | |
1546 | ||
1547 | ||
1548 | typedef typename face_edge_iterator | |
1549 | <single_side, previous_iteration>::type old_face_iterator_t; | |
1550 | ||
1551 | old_face_iterator_t | |
1552 | first_old_face_itr(z, face_handles, first_side()); | |
1553 | old_face_iterator_t | |
1554 | second_old_face_itr(z, face_handles, second_side()); | |
1555 | old_face_iterator_t old_face_itr, old_face_end; | |
1556 | ||
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); | |
1560 | ||
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); | |
1564 | ||
1565 | typename std::vector<old_face_iterator_t>::iterator | |
1566 | of_itr, of_itr_end; | |
1567 | of_itr_end = old_face_iterators.end(); | |
1568 | for(of_itr = old_face_iterators.begin(); | |
1569 | of_itr != of_itr_end; ++of_itr | |
1570 | ) | |
1571 | { | |
1572 | ||
1573 | old_face_itr = *of_itr; | |
1574 | ||
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) | |
1579 | { | |
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); | |
1584 | ||
1585 | if (current_vertex == x || current_vertex == y) | |
1586 | seen_x_or_y = true; | |
1587 | ||
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)] && | |
1592 | !seen_x_or_y | |
1593 | ) | |
1594 | { | |
1595 | w = current_vertex; | |
1596 | } | |
1597 | ||
1598 | if (!outer_face_edge[e]) | |
1599 | { | |
1600 | if (!upper_face_vertex[current_vertex] && | |
1601 | !lower_face_vertex[current_vertex] | |
1602 | ) | |
1603 | { | |
1604 | x_y_path_vertex[current_vertex] = true; | |
1605 | } | |
1606 | ||
1607 | is_in_subgraph[e] = true; | |
1608 | if (upper_face_vertex[source(e,g)] || | |
1609 | lower_face_vertex[source(e,g)] | |
1610 | ) | |
1611 | { | |
1612 | if (first_x_y_path_endpoint == | |
1613 | graph_traits<Graph>::null_vertex() | |
1614 | ) | |
1615 | first_x_y_path_endpoint = source(e,g); | |
1616 | else | |
1617 | second_x_y_path_endpoint = source(e,g); | |
1618 | } | |
1619 | if (upper_face_vertex[target(e,g)] || | |
1620 | lower_face_vertex[target(e,g)] | |
1621 | ) | |
1622 | { | |
1623 | if (first_x_y_path_endpoint == | |
1624 | graph_traits<Graph>::null_vertex() | |
1625 | ) | |
1626 | first_x_y_path_endpoint = target(e,g); | |
1627 | else | |
1628 | second_x_y_path_endpoint = target(e,g); | |
1629 | } | |
1630 | ||
1631 | ||
1632 | } | |
1633 | else if (previous_vertex == x || previous_vertex == y) | |
1634 | { | |
1635 | chosen_case = detail::BM_CASE_C; | |
1636 | } | |
1637 | ||
1638 | } | |
1639 | ||
1640 | } | |
1641 | ||
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. | |
1644 | ||
1645 | //First, get a list of all of v's embedded child edges | |
1646 | ||
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 | |
1650 | ) | |
1651 | { | |
1652 | edge_t embedded_edge(*v_edge_itr); | |
1653 | ||
1654 | if (!is_embedded[embedded_edge] || | |
1655 | embedded_edge == dfs_parent_edge[v] | |
1656 | ) | |
1657 | continue; | |
1658 | ||
1659 | case_d_edges.push_back(embedded_edge); | |
1660 | ||
1661 | vertex_t current_vertex | |
1662 | = source(embedded_edge,g) == v ? | |
1663 | target(embedded_edge,g) : source(embedded_edge,g); | |
1664 | ||
1665 | typename face_edge_iterator<>::type | |
1666 | internal_face_itr, internal_face_end; | |
1667 | if (face_handles[current_vertex].first_vertex() == v) | |
1668 | { | |
1669 | internal_face_itr = typename face_edge_iterator<>::type | |
1670 | (current_vertex, face_handles, second_side()); | |
1671 | } | |
1672 | else | |
1673 | { | |
1674 | internal_face_itr = typename face_edge_iterator<>::type | |
1675 | (current_vertex, face_handles, first_side()); | |
1676 | } | |
1677 | ||
1678 | while(internal_face_itr != internal_face_end && | |
1679 | !outer_face_edge[*internal_face_itr] && | |
1680 | !x_y_path_vertex[current_vertex] | |
1681 | ) | |
1682 | { | |
1683 | edge_t e(*internal_face_itr); | |
1684 | case_d_edges.push_back(e); | |
1685 | current_vertex = | |
1686 | source(e,g) == current_vertex ? target(e,g) : source(e,g); | |
1687 | ++internal_face_itr; | |
1688 | } | |
1689 | ||
1690 | if (x_y_path_vertex[current_vertex]) | |
1691 | { | |
1692 | chosen_case = detail::BM_CASE_D; | |
1693 | break; | |
1694 | } | |
1695 | else | |
1696 | { | |
1697 | case_d_edges.clear(); | |
1698 | } | |
1699 | ||
1700 | } | |
1701 | ||
1702 | ||
1703 | } | |
1704 | ||
1705 | ||
1706 | ||
1707 | ||
1708 | if (chosen_case != detail::BM_CASE_B && chosen_case != detail::BM_CASE_A) | |
1709 | { | |
1710 | ||
1711 | //Finding z and w. | |
1712 | ||
1713 | for(boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) | |
1714 | { | |
1715 | edge_t e(*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]; | |
1719 | } | |
1720 | ||
1721 | kuratowski_walkup(v, | |
1722 | forbidden_edge, | |
1723 | goal_edge, | |
1724 | is_embedded, | |
1725 | z_v_path | |
1726 | ); | |
1727 | ||
1728 | if (chosen_case == detail::BM_CASE_E) | |
1729 | { | |
1730 | ||
1731 | for(boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) | |
1732 | { | |
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); | |
1736 | } | |
1737 | ||
1738 | for(boost::tie(oei, oei_end) = out_edges(w,g); oei != oei_end; ++oei) | |
1739 | { | |
1740 | if (!outer_face_edge[*oei]) | |
1741 | goal_edge[*oei] = true; | |
1742 | } | |
1743 | ||
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) | |
1747 | { | |
1748 | goal_edge[*pi] = true; | |
1749 | } | |
1750 | ||
1751 | w_ancestor = v; | |
1752 | vertex_t w_endpoint = graph_traits<Graph>::null_vertex(); | |
1753 | ||
1754 | while(w_endpoint == graph_traits<Graph>::null_vertex()) | |
1755 | { | |
1756 | w_ancestor = dfs_parent[w_ancestor]; | |
1757 | w_endpoint = kuratowski_walkup(w_ancestor, | |
1758 | forbidden_edge, | |
1759 | goal_edge, | |
1760 | is_embedded, | |
1761 | w_path | |
1762 | ); | |
1763 | ||
1764 | } | |
1765 | ||
1766 | } | |
1767 | ||
1768 | ||
1769 | } | |
1770 | ||
1771 | ||
1772 | //We're done isolating the Kuratowski subgraph at this point - | |
1773 | //but there's still some cleaning up to do. | |
1774 | ||
1775 | //Update is_in_subgraph with the paths we just found | |
1776 | ||
1777 | xi_end = x_external_path.end(); | |
1778 | for(xi = x_external_path.begin(); xi != xi_end; ++xi) | |
1779 | is_in_subgraph[*xi] = true; | |
1780 | ||
1781 | xi_end = y_external_path.end(); | |
1782 | for(xi = y_external_path.begin(); xi != xi_end; ++xi) | |
1783 | is_in_subgraph[*xi] = true; | |
1784 | ||
1785 | xi_end = z_v_path.end(); | |
1786 | for(xi = z_v_path.begin(); xi != xi_end; ++xi) | |
1787 | is_in_subgraph[*xi] = true; | |
1788 | ||
1789 | xi_end = case_d_edges.end(); | |
1790 | for(xi = case_d_edges.begin(); xi != xi_end; ++xi) | |
1791 | is_in_subgraph[*xi] = true; | |
1792 | ||
1793 | xi_end = w_path.end(); | |
1794 | for(xi = w_path.begin(); xi != xi_end; ++xi) | |
1795 | is_in_subgraph[*xi] = true; | |
1796 | ||
1797 | child = bicomp_root; | |
1798 | parent = dfs_parent[child]; | |
1799 | while(child != parent) | |
1800 | { | |
1801 | is_in_subgraph[dfs_parent_edge[child]] = true; | |
1802 | boost::tie(parent, child) = std::make_pair( dfs_parent[parent], parent ); | |
1803 | } | |
1804 | ||
1805 | ||
1806 | ||
1807 | ||
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. | |
1813 | ||
1814 | if (chosen_case == detail::BM_CASE_B) | |
1815 | { | |
1816 | is_in_subgraph[dfs_parent_edge[v]] = false; | |
1817 | } | |
1818 | else if (chosen_case == detail::BM_CASE_C) | |
1819 | { | |
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 | |
1825 | // alpha. | |
1826 | ||
1827 | typename face_vertex_iterator<single_side, follow_visitor>::type | |
1828 | face_itr, face_end; | |
1829 | if (face_handles[v_dfchild_handle.first_vertex()].first_edge() == | |
1830 | v_dfchild_handle.first_edge() | |
1831 | ) | |
1832 | { | |
1833 | face_itr = typename face_vertex_iterator | |
1834 | <single_side, follow_visitor>::type | |
1835 | (v_dfchild_handle.first_vertex(), face_handles, second_side()); | |
1836 | } | |
1837 | else | |
1838 | { | |
1839 | face_itr = typename face_vertex_iterator | |
1840 | <single_side, follow_visitor>::type | |
1841 | (v_dfchild_handle.first_vertex(), face_handles, first_side()); | |
1842 | } | |
1843 | ||
1844 | for(; true; ++face_itr) | |
1845 | { | |
1846 | vertex_t current_vertex(*face_itr); | |
1847 | if (current_vertex == x || current_vertex == y) | |
1848 | { | |
1849 | is_in_subgraph[v_dfchild_handle.first_edge()] = false; | |
1850 | break; | |
1851 | } | |
1852 | else if (current_vertex == first_x_y_path_endpoint || | |
1853 | current_vertex == second_x_y_path_endpoint) | |
1854 | { | |
1855 | is_in_subgraph[v_dfchild_handle.second_edge()] = false; | |
1856 | break; | |
1857 | } | |
1858 | } | |
1859 | ||
1860 | } | |
1861 | else if (chosen_case == detail::BM_CASE_D) | |
1862 | { | |
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 | |
1866 | // automatically... | |
1867 | ||
1868 | is_in_subgraph[v_dfchild_handle.first_edge()] = false; | |
1869 | is_in_subgraph[v_dfchild_handle.second_edge()] = false; | |
1870 | ||
1871 | } | |
1872 | else if (chosen_case == detail::BM_CASE_E) | |
1873 | { | |
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. | |
1877 | ||
1878 | ||
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) | |
1881 | ) | |
1882 | { | |
1883 | is_in_subgraph[dfs_parent_edge[v]] = false; | |
1884 | ||
1885 | vertex_t deletion_endpoint, other_endpoint; | |
1886 | if (lower_face_vertex[first_x_y_path_endpoint]) | |
1887 | { | |
1888 | deletion_endpoint = second_x_y_path_endpoint; | |
1889 | other_endpoint = first_x_y_path_endpoint; | |
1890 | } | |
1891 | else | |
1892 | { | |
1893 | deletion_endpoint = first_x_y_path_endpoint; | |
1894 | other_endpoint = second_x_y_path_endpoint; | |
1895 | } | |
1896 | ||
1897 | typename face_edge_iterator<>::type face_itr, face_end; | |
1898 | ||
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 | |
1903 | ) | |
1904 | { | |
1905 | edge_t e(*face_itr); | |
1906 | if (source(e,g) == other_endpoint || | |
1907 | target(e,g) == other_endpoint | |
1908 | ) | |
1909 | { | |
1910 | found_other_endpoint = true; | |
1911 | break; | |
1912 | } | |
1913 | } | |
1914 | ||
1915 | if (found_other_endpoint) | |
1916 | { | |
1917 | is_in_subgraph[face_handles[deletion_endpoint].first_edge()] | |
1918 | = false; | |
1919 | } | |
1920 | else | |
1921 | { | |
1922 | is_in_subgraph[face_handles[deletion_endpoint].second_edge()] | |
1923 | = false; | |
1924 | } | |
1925 | } | |
1926 | ||
1927 | } | |
1928 | ||
1929 | ||
1930 | for(boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) | |
1931 | if (is_in_subgraph[*ei]) | |
1932 | *o_itr = *ei; | |
1933 | ||
1934 | } | |
1935 | ||
1936 | ||
1937 | ||
1938 | template<typename EdgePermutation> | |
1939 | void make_edge_permutation(EdgePermutation perm) | |
1940 | { | |
1941 | vertex_iterator_t vi, vi_end; | |
1942 | for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi) | |
1943 | { | |
1944 | vertex_t v(*vi); | |
1945 | perm[v].clear(); | |
1946 | face_handles[v].get_list(std::back_inserter(perm[v])); | |
1947 | } | |
1948 | } | |
1949 | ||
1950 | ||
1951 | private: | |
1952 | ||
1953 | const Graph& g; | |
1954 | VertexIndexMap vm; | |
1955 | ||
1956 | vertex_t kuratowski_v; | |
1957 | vertex_t kuratowski_x; | |
1958 | vertex_t kuratowski_y; | |
1959 | ||
1960 | vertex_list_t garbage; // we delete items from linked lists by | |
1961 | // splicing them into garbage | |
1962 | ||
1963 | //only need these two for kuratowski subgraph isolation | |
1964 | std::vector<vertex_t> current_merge_points; | |
1965 | std::vector<edge_t> embedded_edges; | |
1966 | ||
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; | |
1986 | ||
1987 | //property maps | |
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 | |
2003 | ||
2004 | merge_stack_t merge_stack; | |
2005 | ||
2006 | }; | |
2007 | ||
2008 | ||
2009 | } //namespace boost | |
2010 | ||
2011 | #endif //__BOYER_MYRVOLD_IMPL_HPP__ |