Chris@16: //======================================================================= Chris@16: // Copyright (c) Aaron Windsor 2007 Chris@16: // Chris@16: // Distributed under the Boost Software License, Version 1.0. (See Chris@16: // accompanying file LICENSE_1_0.txt or copy at Chris@16: // http://www.boost.org/LICENSE_1_0.txt) Chris@16: //======================================================================= Chris@16: #ifndef __BOYER_MYRVOLD_IMPL_HPP__ Chris@16: #define __BOYER_MYRVOLD_IMPL_HPP__ Chris@16: Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: #include //for std::min macros Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: Chris@16: Chris@16: Chris@16: namespace boost Chris@16: { Chris@16: namespace detail { Chris@16: enum bm_case_t{BM_NO_CASE_CHOSEN, BM_CASE_A, BM_CASE_B, BM_CASE_C, BM_CASE_D, BM_CASE_E}; Chris@16: } Chris@16: Chris@16: template Chris@16: struct planar_dfs_visitor : public dfs_visitor<> Chris@16: { Chris@16: planar_dfs_visitor(LowPointMap lpm, DFSParentMap dfs_p, Chris@16: DFSNumberMap dfs_n, LeastAncestorMap lam, Chris@16: DFSParentEdgeMap dfs_edge) Chris@16: : low(lpm), Chris@16: parent(dfs_p), Chris@16: df_number(dfs_n), Chris@16: least_ancestor(lam), Chris@16: df_edge(dfs_edge), Chris@16: count(0) Chris@16: {} Chris@16: Chris@16: Chris@16: template Chris@16: void start_vertex(const Vertex& u, Graph&) Chris@16: { Chris@16: put(parent, u, u); Chris@16: put(least_ancestor, u, count); Chris@16: } Chris@16: Chris@16: Chris@16: template Chris@16: void discover_vertex(const Vertex& u, Graph&) Chris@16: { Chris@16: put(low, u, count); Chris@16: put(df_number, u, count); Chris@16: ++count; Chris@16: } Chris@16: Chris@16: template Chris@16: void tree_edge(const Edge& e, Graph& g) Chris@16: { Chris@16: typedef typename graph_traits::vertex_descriptor vertex_t; Chris@16: vertex_t s(source(e,g)); Chris@16: vertex_t t(target(e,g)); Chris@16: Chris@16: put(parent, t, s); Chris@16: put(df_edge, t, e); Chris@16: put(least_ancestor, t, get(df_number, s)); Chris@16: } Chris@16: Chris@16: template Chris@16: void back_edge(const Edge& e, Graph& g) Chris@16: { Chris@16: typedef typename graph_traits::vertex_descriptor vertex_t; Chris@16: typedef typename graph_traits::vertices_size_type v_size_t; Chris@16: Chris@16: vertex_t s(source(e,g)); Chris@16: vertex_t t(target(e,g)); Chris@16: BOOST_USING_STD_MIN(); Chris@16: Chris@16: if ( t != get(parent, s) ) { Chris@16: v_size_t s_low_df_number = get(low, s); Chris@16: v_size_t t_df_number = get(df_number, t); Chris@16: v_size_t s_least_ancestor_df_number = get(least_ancestor, s); Chris@16: Chris@16: put(low, s, Chris@16: min BOOST_PREVENT_MACRO_SUBSTITUTION(s_low_df_number, Chris@16: t_df_number) Chris@16: ); Chris@16: Chris@16: put(least_ancestor, s, Chris@16: min BOOST_PREVENT_MACRO_SUBSTITUTION(s_least_ancestor_df_number, Chris@16: t_df_number Chris@16: ) Chris@16: ); Chris@16: Chris@16: } Chris@16: } Chris@16: Chris@16: template Chris@16: void finish_vertex(const Vertex& u, Graph&) Chris@16: { Chris@16: typedef typename graph_traits::vertices_size_type v_size_t; Chris@16: Chris@16: Vertex u_parent = get(parent, u); Chris@16: v_size_t u_parent_lowpoint = get(low, u_parent); Chris@16: v_size_t u_lowpoint = get(low, u); Chris@16: BOOST_USING_STD_MIN(); Chris@16: Chris@16: if (u_parent != u) Chris@16: { Chris@16: put(low, u_parent, Chris@16: min BOOST_PREVENT_MACRO_SUBSTITUTION(u_lowpoint, Chris@16: u_parent_lowpoint Chris@16: ) Chris@16: ); Chris@16: } Chris@16: } Chris@16: Chris@16: LowPointMap low; Chris@16: DFSParentMap parent; Chris@16: DFSNumberMap df_number; Chris@16: LeastAncestorMap least_ancestor; Chris@16: DFSParentEdgeMap df_edge; Chris@16: SizeType count; Chris@16: Chris@16: }; Chris@16: Chris@16: Chris@16: Chris@16: Chris@16: Chris@16: Chris@16: template Chris@16: class boyer_myrvold_impl Chris@16: { Chris@16: Chris@16: typedef typename graph_traits::vertices_size_type v_size_t; Chris@16: typedef typename graph_traits::vertex_descriptor vertex_t; Chris@16: typedef typename graph_traits::edge_descriptor edge_t; Chris@16: typedef typename graph_traits::vertex_iterator vertex_iterator_t; Chris@16: typedef typename graph_traits::edge_iterator edge_iterator_t; Chris@16: typedef typename graph_traits::out_edge_iterator Chris@16: out_edge_iterator_t; Chris@16: typedef graph::detail::face_handle Chris@16: face_handle_t; Chris@16: typedef std::vector vertex_vector_t; Chris@16: typedef std::vector edge_vector_t; Chris@16: typedef std::list vertex_list_t; Chris@16: typedef std::list< face_handle_t > face_handle_list_t; Chris@16: typedef boost::shared_ptr< face_handle_list_t > face_handle_list_ptr_t; Chris@16: typedef boost::shared_ptr< vertex_list_t > vertex_list_ptr_t; Chris@16: typedef boost::tuple merge_stack_frame_t; Chris@16: typedef std::vector merge_stack_t; Chris@16: Chris@16: template Chris@16: struct map_vertex_to_ Chris@16: { Chris@16: typedef iterator_property_map Chris@16: ::iterator, VertexIndexMap> type; Chris@16: }; Chris@16: Chris@16: typedef typename map_vertex_to_::type vertex_to_v_size_map_t; Chris@16: typedef typename map_vertex_to_::type vertex_to_vertex_map_t; Chris@16: typedef typename map_vertex_to_::type vertex_to_edge_map_t; Chris@16: typedef typename map_vertex_to_::type Chris@16: vertex_to_vertex_list_ptr_map_t; Chris@16: typedef typename map_vertex_to_< edge_vector_t >::type Chris@16: vertex_to_edge_vector_map_t; Chris@16: typedef typename map_vertex_to_::type vertex_to_bool_map_t; Chris@16: typedef typename map_vertex_to_::type Chris@16: vertex_to_face_handle_map_t; Chris@16: typedef typename map_vertex_to_::type Chris@16: vertex_to_face_handle_list_ptr_map_t; Chris@16: typedef typename map_vertex_to_::type Chris@16: vertex_to_separated_node_map_t; Chris@16: Chris@16: template Chris@16: struct face_vertex_iterator Chris@16: { Chris@16: typedef face_iterator Chris@16: type; Chris@16: }; Chris@16: Chris@16: template Chris@16: struct face_edge_iterator Chris@16: { Chris@16: typedef face_iterator Chris@16: type; Chris@16: }; Chris@16: Chris@16: Chris@16: Chris@16: public: Chris@16: Chris@16: Chris@16: Chris@16: boyer_myrvold_impl(const Graph& arg_g, VertexIndexMap arg_vm): Chris@16: g(arg_g), Chris@16: vm(arg_vm), Chris@16: Chris@16: low_point_vector(num_vertices(g)), Chris@16: dfs_parent_vector(num_vertices(g)), Chris@16: dfs_number_vector(num_vertices(g)), Chris@16: least_ancestor_vector(num_vertices(g)), Chris@16: pertinent_roots_vector(num_vertices(g)), Chris@16: backedge_flag_vector(num_vertices(g), num_vertices(g) + 1), Chris@16: visited_vector(num_vertices(g), num_vertices(g) + 1), Chris@16: face_handles_vector(num_vertices(g)), Chris@16: dfs_child_handles_vector(num_vertices(g)), Chris@16: separated_dfs_child_list_vector(num_vertices(g)), Chris@16: separated_node_in_parent_list_vector(num_vertices(g)), Chris@16: canonical_dfs_child_vector(num_vertices(g)), Chris@16: flipped_vector(num_vertices(g), false), Chris@16: backedges_vector(num_vertices(g)), Chris@16: dfs_parent_edge_vector(num_vertices(g)), Chris@16: Chris@16: vertices_by_dfs_num(num_vertices(g)), Chris@16: Chris@16: low_point(low_point_vector.begin(), vm), Chris@16: dfs_parent(dfs_parent_vector.begin(), vm), Chris@16: dfs_number(dfs_number_vector.begin(), vm), Chris@16: least_ancestor(least_ancestor_vector.begin(), vm), Chris@16: pertinent_roots(pertinent_roots_vector.begin(), vm), Chris@16: backedge_flag(backedge_flag_vector.begin(), vm), Chris@16: visited(visited_vector.begin(), vm), Chris@16: face_handles(face_handles_vector.begin(), vm), Chris@16: dfs_child_handles(dfs_child_handles_vector.begin(), vm), Chris@16: separated_dfs_child_list(separated_dfs_child_list_vector.begin(), vm), Chris@16: separated_node_in_parent_list Chris@16: (separated_node_in_parent_list_vector.begin(), vm), Chris@16: canonical_dfs_child(canonical_dfs_child_vector.begin(), vm), Chris@16: flipped(flipped_vector.begin(), vm), Chris@16: backedges(backedges_vector.begin(), vm), Chris@16: dfs_parent_edge(dfs_parent_edge_vector.begin(), vm) Chris@16: Chris@16: { Chris@16: Chris@16: planar_dfs_visitor Chris@16: vis Chris@16: (low_point, dfs_parent, dfs_number, least_ancestor, dfs_parent_edge); Chris@16: Chris@16: // Perform a depth-first search to find each vertex's low point, least Chris@16: // ancestor, and dfs tree information Chris@16: depth_first_search(g, visitor(vis).vertex_index_map(vm)); Chris@16: Chris@16: // Sort vertices by their lowpoint - need this later in the constructor Chris@16: vertex_vector_t vertices_by_lowpoint(num_vertices(g)); Chris@16: std::copy( vertices(g).first, vertices(g).second, Chris@16: vertices_by_lowpoint.begin() Chris@16: ); Chris@16: bucket_sort(vertices_by_lowpoint.begin(), Chris@16: vertices_by_lowpoint.end(), Chris@16: low_point, Chris@16: num_vertices(g) Chris@16: ); Chris@16: Chris@16: // Sort vertices by their dfs number - need this to iterate by reverse Chris@16: // DFS number in the main loop. Chris@16: std::copy( vertices(g).first, vertices(g).second, Chris@16: vertices_by_dfs_num.begin() Chris@16: ); Chris@16: bucket_sort(vertices_by_dfs_num.begin(), Chris@16: vertices_by_dfs_num.end(), Chris@16: dfs_number, Chris@16: num_vertices(g) Chris@16: ); Chris@16: Chris@16: // Initialize face handles. A face handle is an abstraction that serves Chris@16: // two uses in our implementation - it allows us to efficiently move Chris@16: // along the outer face of embedded bicomps in a partially embedded Chris@16: // graph, and it provides storage for the planar embedding. Face Chris@16: // handles are implemented by a sequence of edges and are associated Chris@16: // with a particular vertex - the sequence of edges represents the Chris@16: // current embedding of edges around that vertex, and the first and Chris@16: // last edges in the sequence represent the pair of edges on the outer Chris@16: // face that are adjacent to the associated vertex. This lets us embed Chris@16: // edges in the graph by just pushing them on the front or back of the Chris@16: // sequence of edges held by the face handles. Chris@16: // Chris@16: // Our algorithm starts with a DFS tree of edges (where every vertex is Chris@16: // an articulation point and every edge is a singleton bicomp) and Chris@16: // repeatedly merges bicomps by embedding additional edges. Note that Chris@16: // any bicomp at any point in the algorithm can be associated with a Chris@16: // unique edge connecting the vertex of that bicomp with the lowest DFS Chris@16: // number (which we refer to as the "root" of the bicomp) with its DFS Chris@16: // child in the bicomp: the existence of two such edges would contradict Chris@16: // the properties of a DFS tree. We refer to the DFS child of the root Chris@16: // of a bicomp as the "canonical DFS child" of the bicomp. Note that a Chris@16: // vertex can be the root of more than one bicomp. Chris@16: // Chris@16: // We move around the external faces of a bicomp using a few property Chris@16: // maps, which we'll initialize presently: Chris@16: // Chris@16: // - face_handles: maps a vertex to a face handle that can be used to Chris@16: // move "up" a bicomp. For a vertex that isn't an articulation point, Chris@16: // this holds the face handles that can be used to move around that Chris@16: // vertex's unique bicomp. For a vertex that is an articulation point, Chris@16: // this holds the face handles associated with the unique bicomp that Chris@16: // the vertex is NOT the root of. These handles can therefore be used Chris@16: // to move from any point on the outer face of the tree of bicomps Chris@16: // around the current outer face towards the root of the DFS tree. Chris@16: // Chris@16: // - dfs_child_handles: these are used to hold face handles for Chris@16: // vertices that are articulation points - dfs_child_handles[v] holds Chris@16: // the face handles corresponding to vertex u in the bicomp with root Chris@16: // u and canonical DFS child v. Chris@16: // Chris@16: // - canonical_dfs_child: this property map allows one to determine the Chris@16: // canonical DFS child of a bicomp while traversing the outer face. Chris@16: // This property map is only valid when applied to one of the two Chris@16: // vertices adjacent to the root of the bicomp on the outer face. To Chris@16: // be more precise, if v is the canonical DFS child of a bicomp, Chris@16: // canonical_dfs_child[dfs_child_handles[v].first_vertex()] == v and Chris@16: // canonical_dfs_child[dfs_child_handles[v].second_vertex()] == v. Chris@16: // Chris@16: // - pertinent_roots: given a vertex v, pertinent_roots[v] contains a Chris@16: // list of face handles pointing to the top of bicomps that need to Chris@16: // be visited by the current walkdown traversal (since they lead to Chris@16: // backedges that need to be embedded). These lists are populated by Chris@16: // the walkup and consumed by the walkdown. Chris@16: Chris@16: vertex_iterator_t vi, vi_end; Chris@16: for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi) Chris@16: { Chris@16: vertex_t v(*vi); Chris@16: vertex_t parent = dfs_parent[v]; Chris@16: Chris@16: if (parent != v) Chris@16: { Chris@16: edge_t parent_edge = dfs_parent_edge[v]; Chris@16: add_to_embedded_edges(parent_edge, StoreOldHandlesPolicy()); Chris@16: face_handles[v] = face_handle_t(v, parent_edge, g); Chris@16: dfs_child_handles[v] = face_handle_t(parent, parent_edge, g); Chris@16: } Chris@16: else Chris@16: { Chris@16: face_handles[v] = face_handle_t(v); Chris@16: dfs_child_handles[v] = face_handle_t(parent); Chris@16: } Chris@16: Chris@16: canonical_dfs_child[v] = v; Chris@16: pertinent_roots[v] = face_handle_list_ptr_t(new face_handle_list_t); Chris@16: separated_dfs_child_list[v] = vertex_list_ptr_t(new vertex_list_t); Chris@16: Chris@16: } Chris@16: Chris@16: // We need to create a list of not-yet-merged depth-first children for Chris@16: // each vertex that will be updated as bicomps get merged. We sort each Chris@16: // list by ascending lowpoint, which allows the externally_active Chris@16: // function to run in constant time, and we keep a pointer to each Chris@16: // vertex's representation in its parent's list, which allows merging Chris@16: //in constant time. Chris@16: Chris@16: for(typename vertex_vector_t::iterator itr = Chris@16: vertices_by_lowpoint.begin(); Chris@16: itr != vertices_by_lowpoint.end(); ++itr) Chris@16: { Chris@16: vertex_t v(*itr); Chris@16: vertex_t parent(dfs_parent[v]); Chris@16: if (v != parent) Chris@16: { Chris@16: separated_node_in_parent_list[v] = Chris@16: separated_dfs_child_list[parent]->insert Chris@16: (separated_dfs_child_list[parent]->end(), v); Chris@16: } Chris@16: } Chris@16: Chris@16: // The merge stack holds path information during a walkdown iteration Chris@16: merge_stack.reserve(num_vertices(g)); Chris@16: Chris@16: } Chris@16: Chris@16: Chris@16: Chris@16: Chris@16: Chris@16: Chris@16: bool is_planar() Chris@16: { Chris@16: Chris@16: // This is the main algorithm: starting with a DFS tree of embedded Chris@16: // edges (which, since it's a tree, is planar), iterate through all Chris@16: // vertices by reverse DFS number, attempting to embed all backedges Chris@16: // connecting the current vertex to vertices with higher DFS numbers. Chris@16: // Chris@16: // The walkup is a procedure that examines all such backedges and sets Chris@16: // up the required data structures so that they can be searched by the Chris@16: // walkdown in linear time. The walkdown does the actual work of Chris@16: // embedding edges and flipping bicomps, and can identify when it has Chris@16: // come across a kuratowski subgraph. Chris@16: // Chris@16: // store_old_face_handles caches face handles from the previous Chris@16: // iteration - this is used only for the kuratowski subgraph isolation, Chris@16: // and is therefore dispatched based on the StoreOldHandlesPolicy. Chris@16: // Chris@16: // clean_up_embedding does some clean-up and fills in values that have Chris@16: // to be computed lazily during the actual execution of the algorithm Chris@16: // (for instance, whether or not a bicomp is flipped in the final Chris@16: // embedding). It's dispatched on the the StoreEmbeddingPolicy, since Chris@16: // it's not needed if an embedding isn't desired. Chris@16: Chris@16: typename vertex_vector_t::reverse_iterator vi, vi_end; Chris@16: Chris@16: vi_end = vertices_by_dfs_num.rend(); Chris@16: for(vi = vertices_by_dfs_num.rbegin(); vi != vi_end; ++vi) Chris@16: { Chris@16: Chris@16: store_old_face_handles(StoreOldHandlesPolicy()); Chris@16: Chris@16: vertex_t v(*vi); Chris@16: Chris@16: walkup(v); Chris@16: Chris@16: if (!walkdown(v)) Chris@16: return false; Chris@16: Chris@16: } Chris@16: Chris@16: clean_up_embedding(StoreEmbeddingPolicy()); Chris@16: Chris@16: return true; Chris@16: Chris@16: } Chris@16: Chris@16: Chris@16: Chris@16: Chris@16: Chris@16: Chris@16: private: Chris@16: Chris@16: Chris@16: Chris@16: Chris@16: Chris@16: void walkup(vertex_t v) Chris@16: { Chris@16: Chris@16: // The point of the walkup is to follow all backedges from v to Chris@16: // vertices with higher DFS numbers, and update pertinent_roots Chris@16: // for the bicomp roots on the path from backedge endpoints up Chris@16: // to v. This will set the stage for the walkdown to efficiently Chris@16: // traverse the graph of bicomps down from v. Chris@16: Chris@16: typedef typename face_vertex_iterator::type walkup_iterator_t; Chris@16: Chris@16: out_edge_iterator_t oi, oi_end; Chris@16: for(boost::tie(oi,oi_end) = out_edges(v,g); oi != oi_end; ++oi) Chris@16: { Chris@16: edge_t e(*oi); Chris@16: vertex_t e_source(source(e,g)); Chris@16: vertex_t e_target(target(e,g)); Chris@16: Chris@16: if (e_source == e_target) Chris@16: { Chris@16: self_loops.push_back(e); Chris@16: continue; Chris@16: } Chris@16: Chris@16: vertex_t w(e_source == v ? e_target : e_source); Chris@16: Chris@16: //continue if not a back edge or already embedded Chris@16: if (dfs_number[w] < dfs_number[v] || e == dfs_parent_edge[w]) Chris@16: continue; Chris@16: Chris@16: backedges[w].push_back(e); Chris@16: Chris@16: v_size_t timestamp = dfs_number[v]; Chris@16: backedge_flag[w] = timestamp; Chris@16: Chris@16: walkup_iterator_t walkup_itr(w, face_handles); Chris@16: walkup_iterator_t walkup_end; Chris@16: vertex_t lead_vertex = w; Chris@16: Chris@16: while (true) Chris@16: { Chris@16: Chris@16: // Move to the root of the current bicomp or the first visited Chris@16: // vertex on the bicomp by going up each side in parallel Chris@16: Chris@16: while(walkup_itr != walkup_end && Chris@16: visited[*walkup_itr] != timestamp Chris@16: ) Chris@16: { Chris@16: lead_vertex = *walkup_itr; Chris@16: visited[lead_vertex] = timestamp; Chris@16: ++walkup_itr; Chris@16: } Chris@16: Chris@16: // If we've found the root of a bicomp through a path we haven't Chris@16: // seen before, update pertinent_roots with a handle to the Chris@16: // current bicomp. Otherwise, we've just seen a path we've been Chris@16: // up before, so break out of the main while loop. Chris@16: Chris@16: if (walkup_itr == walkup_end) Chris@16: { Chris@16: vertex_t dfs_child = canonical_dfs_child[lead_vertex]; Chris@16: vertex_t parent = dfs_parent[dfs_child]; Chris@16: Chris@16: visited[dfs_child_handles[dfs_child].first_vertex()] Chris@16: = timestamp; Chris@16: visited[dfs_child_handles[dfs_child].second_vertex()] Chris@16: = timestamp; Chris@16: Chris@16: if (low_point[dfs_child] < dfs_number[v] || Chris@16: least_ancestor[dfs_child] < dfs_number[v] Chris@16: ) Chris@16: { Chris@16: pertinent_roots[parent]->push_back Chris@16: (dfs_child_handles[dfs_child]); Chris@16: } Chris@16: else Chris@16: { Chris@16: pertinent_roots[parent]->push_front Chris@16: (dfs_child_handles[dfs_child]); Chris@16: } Chris@16: Chris@16: if (parent != v && visited[parent] != timestamp) Chris@16: { Chris@16: walkup_itr = walkup_iterator_t(parent, face_handles); Chris@16: lead_vertex = parent; Chris@16: } Chris@16: else Chris@16: break; Chris@16: } Chris@16: else Chris@16: break; Chris@16: } Chris@16: Chris@16: } Chris@16: Chris@16: } Chris@16: Chris@16: Chris@16: Chris@16: Chris@16: Chris@16: Chris@16: Chris@16: bool walkdown(vertex_t v) Chris@16: { Chris@16: // This procedure is where all of the action is - pertinent_roots Chris@16: // has already been set up by the walkup, so we just need to move Chris@16: // down bicomps from v until we find vertices that have been Chris@16: // labeled as backedge endpoints. Once we find such a vertex, we Chris@16: // embed the corresponding edge and glue together the bicomps on Chris@16: // the path connecting the two vertices in the edge. This may Chris@16: // involve flipping bicomps along the way. Chris@16: Chris@16: vertex_t w; //the other endpoint of the edge we're embedding Chris@16: Chris@16: while (!pertinent_roots[v]->empty()) Chris@16: { Chris@16: Chris@16: face_handle_t root_face_handle = pertinent_roots[v]->front(); Chris@16: face_handle_t curr_face_handle = root_face_handle; Chris@16: pertinent_roots[v]->pop_front(); Chris@16: Chris@16: merge_stack.clear(); Chris@16: Chris@16: while(true) Chris@16: { Chris@16: Chris@16: typename face_vertex_iterator<>::type Chris@16: first_face_itr, second_face_itr, face_end; Chris@16: vertex_t first_side_vertex Chris@16: = graph_traits::null_vertex(); Chris@16: vertex_t second_side_vertex; Chris@16: vertex_t first_tail, second_tail; Chris@16: Chris@16: first_tail = second_tail = curr_face_handle.get_anchor(); Chris@16: first_face_itr = typename face_vertex_iterator<>::type Chris@16: (curr_face_handle, face_handles, first_side()); Chris@16: second_face_itr = typename face_vertex_iterator<>::type Chris@16: (curr_face_handle, face_handles, second_side()); Chris@16: Chris@16: for(; first_face_itr != face_end; ++first_face_itr) Chris@16: { Chris@16: vertex_t face_vertex(*first_face_itr); Chris@16: if (pertinent(face_vertex, v) || Chris@16: externally_active(face_vertex, v) Chris@16: ) Chris@16: { Chris@16: first_side_vertex = face_vertex; Chris@16: second_side_vertex = face_vertex; Chris@16: break; Chris@16: } Chris@16: first_tail = face_vertex; Chris@16: } Chris@16: Chris@16: if (first_side_vertex == graph_traits::null_vertex() || Chris@16: first_side_vertex == curr_face_handle.get_anchor() Chris@16: ) Chris@16: break; Chris@16: Chris@16: for(;second_face_itr != face_end; ++second_face_itr) Chris@16: { Chris@16: vertex_t face_vertex(*second_face_itr); Chris@16: if (pertinent(face_vertex, v) || Chris@16: externally_active(face_vertex, v) Chris@16: ) Chris@16: { Chris@16: second_side_vertex = face_vertex; Chris@16: break; Chris@16: } Chris@16: second_tail = face_vertex; Chris@16: } Chris@16: Chris@16: vertex_t chosen; Chris@16: bool chose_first_upper_path; Chris@16: if (internally_active(first_side_vertex, v)) Chris@16: { Chris@16: chosen = first_side_vertex; Chris@16: chose_first_upper_path = true; Chris@16: } Chris@16: else if (internally_active(second_side_vertex, v)) Chris@16: { Chris@16: chosen = second_side_vertex; Chris@16: chose_first_upper_path = false; Chris@16: } Chris@16: else if (pertinent(first_side_vertex, v)) Chris@16: { Chris@16: chosen = first_side_vertex; Chris@16: chose_first_upper_path = true; Chris@16: } Chris@16: else if (pertinent(second_side_vertex, v)) Chris@16: { Chris@16: chosen = second_side_vertex; Chris@16: chose_first_upper_path = false; Chris@16: } Chris@16: else Chris@16: { Chris@16: Chris@16: // If there's a pertinent vertex on the lower face Chris@16: // between the first_face_itr and the second_face_itr, Chris@16: // this graph isn't planar. Chris@16: for(; Chris@16: *first_face_itr != second_side_vertex; Chris@16: ++first_face_itr Chris@16: ) Chris@16: { Chris@16: vertex_t p(*first_face_itr); Chris@16: if (pertinent(p,v)) Chris@16: { Chris@16: //Found a Kuratowski subgraph Chris@16: kuratowski_v = v; Chris@16: kuratowski_x = first_side_vertex; Chris@16: kuratowski_y = second_side_vertex; Chris@16: return false; Chris@16: } Chris@16: } Chris@16: Chris@16: // Otherwise, the fact that we didn't find a pertinent Chris@16: // vertex on this face is fine - we should set the Chris@16: // short-circuit edges and break out of this loop to Chris@16: // start looking at a different pertinent root. Chris@16: Chris@16: if (first_side_vertex == second_side_vertex) Chris@16: { Chris@16: if (first_tail != v) Chris@16: { Chris@16: vertex_t first Chris@16: = face_handles[first_tail].first_vertex(); Chris@16: vertex_t second Chris@16: = face_handles[first_tail].second_vertex(); Chris@16: boost::tie(first_side_vertex, first_tail) Chris@16: = make_tuple(first_tail, Chris@16: first == first_side_vertex ? Chris@16: second : first Chris@16: ); Chris@16: } Chris@16: else if (second_tail != v) Chris@16: { Chris@16: vertex_t first Chris@16: = face_handles[second_tail].first_vertex(); Chris@16: vertex_t second Chris@16: = face_handles[second_tail].second_vertex(); Chris@16: boost::tie(second_side_vertex, second_tail) Chris@16: = make_tuple(second_tail, Chris@16: first == second_side_vertex ? Chris@16: second : first); Chris@16: } Chris@16: else Chris@16: break; Chris@16: } Chris@16: Chris@16: canonical_dfs_child[first_side_vertex] Chris@16: = canonical_dfs_child[root_face_handle.first_vertex()]; Chris@16: canonical_dfs_child[second_side_vertex] Chris@16: = canonical_dfs_child[root_face_handle.second_vertex()]; Chris@16: root_face_handle.set_first_vertex(first_side_vertex); Chris@16: root_face_handle.set_second_vertex(second_side_vertex); Chris@16: Chris@16: if (face_handles[first_side_vertex].first_vertex() == Chris@16: first_tail Chris@16: ) Chris@16: face_handles[first_side_vertex].set_first_vertex(v); Chris@16: else Chris@16: face_handles[first_side_vertex].set_second_vertex(v); Chris@16: Chris@16: if (face_handles[second_side_vertex].first_vertex() == Chris@16: second_tail Chris@16: ) Chris@16: face_handles[second_side_vertex].set_first_vertex(v); Chris@16: else Chris@16: face_handles[second_side_vertex].set_second_vertex(v); Chris@16: Chris@16: break; Chris@16: Chris@16: } Chris@16: Chris@16: Chris@16: // When we unwind the stack, we need to know which direction Chris@16: // we came down from on the top face handle Chris@16: Chris@16: bool chose_first_lower_path = Chris@16: (chose_first_upper_path && Chris@16: face_handles[chosen].first_vertex() == first_tail) Chris@16: || Chris@16: (!chose_first_upper_path && Chris@16: face_handles[chosen].first_vertex() == second_tail); Chris@16: Chris@16: //If there's a backedge at the chosen vertex, embed it now Chris@16: if (backedge_flag[chosen] == dfs_number[v]) Chris@16: { Chris@16: w = chosen; Chris@16: Chris@16: backedge_flag[chosen] = num_vertices(g) + 1; Chris@16: add_to_merge_points(chosen, StoreOldHandlesPolicy()); Chris@16: Chris@16: typename edge_vector_t::iterator ei, ei_end; Chris@16: ei_end = backedges[chosen].end(); Chris@16: for(ei = backedges[chosen].begin(); ei != ei_end; ++ei) Chris@16: { Chris@16: edge_t e(*ei); Chris@16: add_to_embedded_edges(e, StoreOldHandlesPolicy()); Chris@16: Chris@16: if (chose_first_lower_path) Chris@16: face_handles[chosen].push_first(e, g); Chris@16: else Chris@16: face_handles[chosen].push_second(e, g); Chris@16: } Chris@16: Chris@16: } Chris@16: else Chris@16: { Chris@16: merge_stack.push_back(make_tuple Chris@16: (chosen, chose_first_upper_path, chose_first_lower_path) Chris@16: ); Chris@16: curr_face_handle = *pertinent_roots[chosen]->begin(); Chris@16: continue; Chris@16: } Chris@16: Chris@16: //Unwind the merge stack to the root, merging all bicomps Chris@16: Chris@16: bool bottom_path_follows_first; Chris@16: bool top_path_follows_first; Chris@16: bool next_bottom_follows_first = chose_first_upper_path; Chris@16: face_handle_t top_handle, bottom_handle; Chris@16: Chris@16: vertex_t merge_point = chosen; Chris@16: Chris@16: while(!merge_stack.empty()) Chris@16: { Chris@16: Chris@16: bottom_path_follows_first = next_bottom_follows_first; Chris@16: boost::tie(merge_point, Chris@16: next_bottom_follows_first, Chris@16: top_path_follows_first Chris@16: ) = merge_stack.back(); Chris@16: merge_stack.pop_back(); Chris@16: Chris@16: face_handle_t top_handle(face_handles[merge_point]); Chris@16: face_handle_t bottom_handle Chris@16: (*pertinent_roots[merge_point]->begin()); Chris@16: Chris@16: vertex_t bottom_dfs_child = canonical_dfs_child Chris@16: [pertinent_roots[merge_point]->begin()->first_vertex()]; Chris@16: Chris@16: remove_vertex_from_separated_dfs_child_list( Chris@16: canonical_dfs_child Chris@16: [pertinent_roots[merge_point]->begin()->first_vertex()] Chris@16: ); Chris@16: Chris@16: pertinent_roots[merge_point]->pop_front(); Chris@16: Chris@16: add_to_merge_points(top_handle.get_anchor(), Chris@16: StoreOldHandlesPolicy() Chris@16: ); Chris@16: Chris@16: if (top_path_follows_first && bottom_path_follows_first) Chris@16: { Chris@16: bottom_handle.flip(); Chris@16: top_handle.glue_first_to_second(bottom_handle); Chris@16: } Chris@16: else if (!top_path_follows_first && Chris@16: bottom_path_follows_first Chris@16: ) Chris@16: { Chris@16: flipped[bottom_dfs_child] = true; Chris@16: top_handle.glue_second_to_first(bottom_handle); Chris@16: } Chris@16: else if (top_path_follows_first && Chris@16: !bottom_path_follows_first Chris@16: ) Chris@16: { Chris@16: flipped[bottom_dfs_child] = true; Chris@16: top_handle.glue_first_to_second(bottom_handle); Chris@16: } Chris@16: else //!top_path_follows_first && !bottom_path_follows_first Chris@16: { Chris@16: bottom_handle.flip(); Chris@16: top_handle.glue_second_to_first(bottom_handle); Chris@16: } Chris@16: Chris@16: } Chris@16: Chris@16: //Finally, embed all edges (v,w) at their upper end points Chris@16: canonical_dfs_child[w] Chris@16: = canonical_dfs_child[root_face_handle.first_vertex()]; Chris@16: Chris@16: add_to_merge_points(root_face_handle.get_anchor(), Chris@16: StoreOldHandlesPolicy() Chris@16: ); Chris@16: Chris@16: typename edge_vector_t::iterator ei, ei_end; Chris@16: ei_end = backedges[chosen].end(); Chris@16: for(ei = backedges[chosen].begin(); ei != ei_end; ++ei) Chris@16: { Chris@16: if (next_bottom_follows_first) Chris@16: root_face_handle.push_first(*ei, g); Chris@16: else Chris@16: root_face_handle.push_second(*ei, g); Chris@16: } Chris@16: Chris@16: backedges[chosen].clear(); Chris@16: curr_face_handle = root_face_handle; Chris@16: Chris@16: }//while(true) Chris@16: Chris@16: }//while(!pertinent_roots[v]->empty()) Chris@16: Chris@16: return true; Chris@16: Chris@16: } Chris@16: Chris@16: Chris@16: Chris@16: Chris@16: Chris@16: Chris@16: void store_old_face_handles(graph::detail::no_old_handles) {} Chris@16: Chris@16: void store_old_face_handles(graph::detail::store_old_handles) Chris@16: { Chris@16: for(typename std::vector::iterator mp_itr Chris@16: = current_merge_points.begin(); Chris@16: mp_itr != current_merge_points.end(); ++mp_itr) Chris@16: { Chris@16: face_handles[*mp_itr].store_old_face_handles(); Chris@16: } Chris@16: current_merge_points.clear(); Chris@16: } Chris@16: Chris@16: Chris@16: void add_to_merge_points(vertex_t, graph::detail::no_old_handles) {} Chris@16: Chris@16: void add_to_merge_points(vertex_t v, graph::detail::store_old_handles) Chris@16: { Chris@16: current_merge_points.push_back(v); Chris@16: } Chris@16: Chris@16: Chris@16: void add_to_embedded_edges(edge_t, graph::detail::no_old_handles) {} Chris@16: Chris@16: void add_to_embedded_edges(edge_t e, graph::detail::store_old_handles) Chris@16: { Chris@16: embedded_edges.push_back(e); Chris@16: } Chris@16: Chris@16: Chris@16: Chris@16: Chris@16: void clean_up_embedding(graph::detail::no_embedding) {} Chris@16: Chris@16: void clean_up_embedding(graph::detail::store_embedding) Chris@16: { Chris@16: Chris@16: // If the graph isn't biconnected, we'll still have entries Chris@16: // in the separated_dfs_child_list for some vertices. Since Chris@16: // these represent articulation points, we can obtain a Chris@16: // planar embedding no matter what order we embed them in. Chris@16: Chris@16: vertex_iterator_t xi, xi_end; Chris@16: for(boost::tie(xi,xi_end) = vertices(g); xi != xi_end; ++xi) Chris@16: { Chris@16: if (!separated_dfs_child_list[*xi]->empty()) Chris@16: { Chris@16: typename vertex_list_t::iterator yi, yi_end; Chris@16: yi_end = separated_dfs_child_list[*xi]->end(); Chris@16: for(yi = separated_dfs_child_list[*xi]->begin(); Chris@16: yi != yi_end; ++yi Chris@16: ) Chris@16: { Chris@16: dfs_child_handles[*yi].flip(); Chris@16: face_handles[*xi].glue_first_to_second Chris@16: (dfs_child_handles[*yi]); Chris@16: } Chris@16: } Chris@16: } Chris@16: Chris@16: // Up until this point, we've flipped bicomps lazily by setting Chris@16: // flipped[v] to true if the bicomp rooted at v was flipped (the Chris@16: // lazy aspect of this flip is that all descendents of that vertex Chris@16: // need to have their orientations reversed as well). Now, we Chris@16: // traverse the DFS tree by DFS number and perform the actual Chris@16: // flipping as needed Chris@16: Chris@16: typedef typename vertex_vector_t::iterator vertex_vector_itr_t; Chris@16: vertex_vector_itr_t vi_end = vertices_by_dfs_num.end(); Chris@16: for(vertex_vector_itr_t vi = vertices_by_dfs_num.begin(); Chris@16: vi != vi_end; ++vi Chris@16: ) Chris@16: { Chris@16: vertex_t v(*vi); Chris@16: bool v_flipped = flipped[v]; Chris@16: bool p_flipped = flipped[dfs_parent[v]]; Chris@16: if (v_flipped && !p_flipped) Chris@16: { Chris@16: face_handles[v].flip(); Chris@16: } Chris@16: else if (p_flipped && !v_flipped) Chris@16: { Chris@16: face_handles[v].flip(); Chris@16: flipped[v] = true; Chris@16: } Chris@16: else Chris@16: { Chris@16: flipped[v] = false; Chris@16: } Chris@16: } Chris@16: Chris@16: // If there are any self-loops in the graph, they were flagged Chris@16: // during the walkup, and we should add them to the embedding now. Chris@16: // Adding a self loop anywhere in the embedding could never Chris@16: // invalidate the embedding, but they would complicate the traversal Chris@16: // if they were added during the walkup/walkdown. Chris@16: Chris@16: typename edge_vector_t::iterator ei, ei_end; Chris@16: ei_end = self_loops.end(); Chris@16: for(ei = self_loops.begin(); ei != ei_end; ++ei) Chris@16: { Chris@16: edge_t e(*ei); Chris@16: face_handles[source(e,g)].push_second(e,g); Chris@16: } Chris@16: Chris@16: } Chris@16: Chris@16: Chris@16: Chris@16: Chris@16: Chris@16: bool pertinent(vertex_t w, vertex_t v) Chris@16: { Chris@16: // w is pertinent with respect to v if there is a backedge (v,w) or if Chris@16: // w is the root of a bicomp that contains a pertinent vertex. Chris@16: Chris@16: return backedge_flag[w] == dfs_number[v] || !pertinent_roots[w]->empty(); Chris@16: } Chris@16: Chris@16: Chris@16: Chris@16: bool externally_active(vertex_t w, vertex_t v) Chris@16: { Chris@16: // Let a be any proper depth-first search ancestor of v. w is externally Chris@16: // active with respect to v if there exists a backedge (a,w) or a Chris@16: // backedge (a,w_0) for some w_0 in a descendent bicomp of w. Chris@16: Chris@16: v_size_t dfs_number_of_v = dfs_number[v]; Chris@16: return (least_ancestor[w] < dfs_number_of_v) || Chris@16: (!separated_dfs_child_list[w]->empty() && Chris@16: low_point[separated_dfs_child_list[w]->front()] < dfs_number_of_v); Chris@16: } Chris@16: Chris@16: Chris@16: Chris@16: bool internally_active(vertex_t w, vertex_t v) Chris@16: { Chris@16: return pertinent(w,v) && !externally_active(w,v); Chris@16: } Chris@16: Chris@16: Chris@16: Chris@16: Chris@16: void remove_vertex_from_separated_dfs_child_list(vertex_t v) Chris@16: { Chris@16: typename vertex_list_t::iterator to_delete Chris@16: = separated_node_in_parent_list[v]; Chris@16: garbage.splice(garbage.end(), Chris@16: *separated_dfs_child_list[dfs_parent[v]], Chris@16: to_delete, Chris@16: boost::next(to_delete) Chris@16: ); Chris@16: } Chris@16: Chris@16: Chris@16: Chris@16: Chris@16: Chris@16: // End of the implementation of the basic Boyer-Myrvold Algorithm. The rest Chris@16: // of the code below implements the isolation of a Kuratowski subgraph in Chris@16: // the case that the input graph is not planar. This is by far the most Chris@16: // complicated part of the implementation. Chris@16: Chris@16: Chris@16: Chris@16: Chris@16: public: Chris@16: Chris@16: Chris@16: Chris@16: Chris@16: template Chris@16: vertex_t kuratowski_walkup(vertex_t v, Chris@16: EdgeToBoolPropertyMap forbidden_edge, Chris@16: EdgeToBoolPropertyMap goal_edge, Chris@16: EdgeToBoolPropertyMap is_embedded, Chris@16: EdgeContainer& path_edges Chris@16: ) Chris@16: { Chris@16: vertex_t current_endpoint; Chris@16: bool seen_goal_edge = false; Chris@16: out_edge_iterator_t oi, oi_end; Chris@16: Chris@16: for(boost::tie(oi,oi_end) = out_edges(v,g); oi != oi_end; ++oi) Chris@16: forbidden_edge[*oi] = true; Chris@16: Chris@16: for(boost::tie(oi,oi_end) = out_edges(v,g); oi != oi_end; ++oi) Chris@16: { Chris@16: path_edges.clear(); Chris@16: Chris@16: edge_t e(*oi); Chris@16: current_endpoint = target(*oi,g) == v ? Chris@16: source(*oi,g) : target(*oi,g); Chris@16: Chris@16: if (dfs_number[current_endpoint] < dfs_number[v] || Chris@16: is_embedded[e] || Chris@16: v == current_endpoint //self-loop Chris@16: ) Chris@16: { Chris@16: //Not a backedge Chris@16: continue; Chris@16: } Chris@16: Chris@16: path_edges.push_back(e); Chris@16: if (goal_edge[e]) Chris@16: { Chris@16: return current_endpoint; Chris@16: } Chris@16: Chris@16: typedef typename face_edge_iterator<>::type walkup_itr_t; Chris@16: Chris@16: walkup_itr_t Chris@16: walkup_itr(current_endpoint, face_handles, first_side()); Chris@16: walkup_itr_t walkup_end; Chris@16: Chris@16: seen_goal_edge = false; Chris@16: Chris@16: while (true) Chris@16: { Chris@16: Chris@16: if (walkup_itr != walkup_end && forbidden_edge[*walkup_itr]) Chris@16: break; Chris@16: Chris@16: while(walkup_itr != walkup_end && Chris@16: !goal_edge[*walkup_itr] && Chris@16: !forbidden_edge[*walkup_itr] Chris@16: ) Chris@16: { Chris@16: edge_t f(*walkup_itr); Chris@16: forbidden_edge[f] = true; Chris@16: path_edges.push_back(f); Chris@16: current_endpoint = Chris@16: source(f, g) == current_endpoint ? Chris@16: target(f, g) : Chris@16: source(f,g); Chris@16: ++walkup_itr; Chris@16: } Chris@16: Chris@16: if (walkup_itr != walkup_end && goal_edge[*walkup_itr]) Chris@16: { Chris@16: path_edges.push_back(*walkup_itr); Chris@16: seen_goal_edge = true; Chris@16: break; Chris@16: } Chris@16: Chris@16: walkup_itr Chris@16: = walkup_itr_t(current_endpoint, face_handles, first_side()); Chris@16: Chris@16: } Chris@16: Chris@16: if (seen_goal_edge) Chris@16: break; Chris@16: Chris@16: } Chris@16: Chris@16: if (seen_goal_edge) Chris@16: return current_endpoint; Chris@16: else Chris@16: return graph_traits::null_vertex(); Chris@16: Chris@16: } Chris@16: Chris@16: Chris@16: Chris@16: Chris@16: Chris@16: Chris@16: Chris@16: Chris@16: template Chris@16: void extract_kuratowski_subgraph(OutputIterator o_itr, EdgeIndexMap em) Chris@16: { Chris@16: Chris@16: // If the main algorithm has failed to embed one of the back-edges from Chris@16: // a vertex v, we can use the current state of the algorithm to isolate Chris@16: // a Kuratowksi subgraph. The isolation process breaks down into five Chris@16: // cases, A - E. The general configuration of all five cases is shown in Chris@16: // figure 1. There is a vertex v from which the planar Chris@16: // v embedding process could not proceed. This means that Chris@16: // | there exists some bicomp containing three vertices Chris@16: // ----- x,y, and z as shown such that x and y are externally Chris@16: // | | active with respect to v (which means that there are Chris@16: // x y two vertices x_0 and y_0 such that (1) both x_0 and Chris@16: // | | y_0 are proper depth-first search ancestors of v and Chris@16: // --z-- (2) there are two disjoint paths, one connecting x Chris@16: // and x_0 and one connecting y and y_0, both consisting Chris@16: // fig. 1 entirely of unembedded edges). Furthermore, there Chris@16: // exists a vertex z_0 such that z is a depth-first Chris@16: // search ancestor of z_0 and (v,z_0) is an unembedded back-edge from v. Chris@16: // x,y and z all exist on the same bicomp, which consists entirely of Chris@16: // embedded edges. The five subcases break down as follows, and are Chris@16: // handled by the algorithm logically in the order A-E: First, if v is Chris@16: // not on the same bicomp as x,y, and z, a K_3_3 can be isolated - this Chris@16: // is case A. So, we'll assume that v is on the same bicomp as x,y, and Chris@16: // z. If z_0 is on a different bicomp than x,y, and z, a K_3_3 can also Chris@16: // be isolated - this is a case B - so we'll assume from now on that v Chris@16: // is on the same bicomp as x, y, and z=z_0. In this case, one can use Chris@16: // properties of the Boyer-Myrvold algorithm to show the existence of an Chris@16: // "x-y path" connecting some vertex on the "left side" of the x,y,z Chris@16: // bicomp with some vertex on the "right side" of the bicomp (where the Chris@16: // left and right are split by a line drawn through v and z.If either of Chris@16: // the endpoints of the x-y path is above x or y on the bicomp, a K_3_3 Chris@16: // can be isolated - this is a case C. Otherwise, both endpoints are at Chris@16: // or below x and y on the bicomp. If there is a vertex alpha on the x-y Chris@16: // path such that alpha is not x or y and there's a path from alpha to v Chris@16: // that's disjoint from any of the edges on the bicomp and the x-y path, Chris@16: // a K_3_3 can be isolated - this is a case D. Otherwise, properties of Chris@16: // the Boyer-Myrvold algorithm can be used to show that another vertex Chris@16: // w exists on the lower half of the bicomp such that w is externally Chris@16: // active with respect to v. w can then be used to isolate a K_5 - this Chris@16: // is the configuration of case E. Chris@16: Chris@16: vertex_iterator_t vi, vi_end; Chris@16: edge_iterator_t ei, ei_end; Chris@16: out_edge_iterator_t oei, oei_end; Chris@16: typename std::vector::iterator xi, xi_end; Chris@16: Chris@16: // Clear the short-circuit edges - these are needed for the planar Chris@16: // testing/embedding algorithm to run in linear time, but they'll Chris@16: // complicate the kuratowski subgraph isolation Chris@16: for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi) Chris@16: { Chris@16: face_handles[*vi].reset_vertex_cache(); Chris@16: dfs_child_handles[*vi].reset_vertex_cache(); Chris@16: } Chris@16: Chris@16: vertex_t v = kuratowski_v; Chris@16: vertex_t x = kuratowski_x; Chris@16: vertex_t y = kuratowski_y; Chris@16: Chris@16: typedef iterator_property_map Chris@16: ::iterator, EdgeIndexMap> Chris@16: edge_to_bool_map_t; Chris@16: Chris@16: std::vector is_in_subgraph_vector(num_edges(g), false); Chris@16: edge_to_bool_map_t is_in_subgraph(is_in_subgraph_vector.begin(), em); Chris@16: Chris@16: std::vector is_embedded_vector(num_edges(g), false); Chris@16: edge_to_bool_map_t is_embedded(is_embedded_vector.begin(), em); Chris@16: Chris@16: typename std::vector::iterator embedded_itr, embedded_end; Chris@16: embedded_end = embedded_edges.end(); Chris@16: for(embedded_itr = embedded_edges.begin(); Chris@16: embedded_itr != embedded_end; ++embedded_itr Chris@16: ) Chris@16: is_embedded[*embedded_itr] = true; Chris@16: Chris@16: // upper_face_vertex is true for x,y, and all vertices above x and y in Chris@16: // the bicomp Chris@16: std::vector upper_face_vertex_vector(num_vertices(g), false); Chris@16: vertex_to_bool_map_t upper_face_vertex Chris@16: (upper_face_vertex_vector.begin(), vm); Chris@16: Chris@16: std::vector lower_face_vertex_vector(num_vertices(g), false); Chris@16: vertex_to_bool_map_t lower_face_vertex Chris@16: (lower_face_vertex_vector.begin(), vm); Chris@16: Chris@16: // These next few variable declarations are all things that we need Chris@16: // to find. Chris@16: vertex_t z; Chris@16: vertex_t bicomp_root; Chris@16: vertex_t w = graph_traits::null_vertex(); Chris@16: face_handle_t w_handle; Chris@16: face_handle_t v_dfchild_handle; Chris@16: vertex_t first_x_y_path_endpoint = graph_traits::null_vertex(); Chris@16: vertex_t second_x_y_path_endpoint = graph_traits::null_vertex(); Chris@16: vertex_t w_ancestor = v; Chris@16: Chris@16: detail::bm_case_t chosen_case = detail::BM_NO_CASE_CHOSEN; Chris@16: Chris@16: std::vector x_external_path; Chris@16: std::vector y_external_path; Chris@16: std::vector case_d_edges; Chris@16: Chris@16: std::vector z_v_path; Chris@16: std::vector w_path; Chris@16: Chris@16: //first, use a walkup to find a path from V that starts with a Chris@16: //backedge from V, then goes up until it hits either X or Y Chris@16: //(but doesn't find X or Y as the root of a bicomp) Chris@16: Chris@16: typename face_vertex_iterator<>::type Chris@16: x_upper_itr(x, face_handles, first_side()); Chris@16: typename face_vertex_iterator<>::type Chris@16: x_lower_itr(x, face_handles, second_side()); Chris@16: typename face_vertex_iterator<>::type face_itr, face_end; Chris@16: Chris@16: // Don't know which path from x is the upper or lower path - Chris@16: // we'll find out here Chris@16: for(face_itr = x_upper_itr; face_itr != face_end; ++face_itr) Chris@16: { Chris@16: if (*face_itr == y) Chris@16: { Chris@16: std::swap(x_upper_itr, x_lower_itr); Chris@16: break; Chris@16: } Chris@16: } Chris@16: Chris@16: upper_face_vertex[x] = true; Chris@16: Chris@16: vertex_t current_vertex = x; Chris@16: vertex_t previous_vertex; Chris@16: for(face_itr = x_upper_itr; face_itr != face_end; ++face_itr) Chris@16: { Chris@16: previous_vertex = current_vertex; Chris@16: current_vertex = *face_itr; Chris@16: upper_face_vertex[current_vertex] = true; Chris@16: } Chris@16: Chris@16: v_dfchild_handle Chris@16: = dfs_child_handles[canonical_dfs_child[previous_vertex]]; Chris@16: Chris@16: for(face_itr = x_lower_itr; *face_itr != y; ++face_itr) Chris@16: { Chris@16: vertex_t current_vertex(*face_itr); Chris@16: lower_face_vertex[current_vertex] = true; Chris@16: Chris@16: typename face_handle_list_t::iterator roots_itr, roots_end; Chris@16: Chris@16: if (w == graph_traits::null_vertex()) //haven't found a w yet Chris@16: { Chris@16: roots_end = pertinent_roots[current_vertex]->end(); Chris@16: for(roots_itr = pertinent_roots[current_vertex]->begin(); Chris@16: roots_itr != roots_end; ++roots_itr Chris@16: ) Chris@16: { Chris@16: if (low_point[canonical_dfs_child[roots_itr->first_vertex()]] Chris@16: < dfs_number[v] Chris@16: ) Chris@16: { Chris@16: w = current_vertex; Chris@16: w_handle = *roots_itr; Chris@16: break; Chris@16: } Chris@16: } Chris@16: } Chris@16: Chris@16: } Chris@16: Chris@16: for(; face_itr != face_end; ++face_itr) Chris@16: { Chris@16: vertex_t current_vertex(*face_itr); Chris@16: upper_face_vertex[current_vertex] = true; Chris@16: bicomp_root = current_vertex; Chris@16: } Chris@16: Chris@16: typedef typename face_edge_iterator<>::type walkup_itr_t; Chris@16: Chris@16: std::vector outer_face_edge_vector(num_edges(g), false); Chris@16: edge_to_bool_map_t outer_face_edge(outer_face_edge_vector.begin(), em); Chris@16: Chris@16: walkup_itr_t walkup_end; Chris@16: for(walkup_itr_t walkup_itr(x, face_handles, first_side()); Chris@16: walkup_itr != walkup_end; ++walkup_itr Chris@16: ) Chris@16: { Chris@16: outer_face_edge[*walkup_itr] = true; Chris@16: is_in_subgraph[*walkup_itr] = true; Chris@16: } Chris@16: Chris@16: for(walkup_itr_t walkup_itr(x, face_handles, second_side()); Chris@16: walkup_itr != walkup_end; ++walkup_itr Chris@16: ) Chris@16: { Chris@16: outer_face_edge[*walkup_itr] = true; Chris@16: is_in_subgraph[*walkup_itr] = true; Chris@16: } Chris@16: Chris@16: std::vector forbidden_edge_vector(num_edges(g), false); Chris@16: edge_to_bool_map_t forbidden_edge(forbidden_edge_vector.begin(), em); Chris@16: Chris@16: std::vector goal_edge_vector(num_edges(g), false); Chris@16: edge_to_bool_map_t goal_edge(goal_edge_vector.begin(), em); Chris@16: Chris@16: Chris@16: //Find external path to x and to y Chris@16: Chris@16: for(boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) Chris@16: { Chris@16: edge_t e(*ei); Chris@16: goal_edge[e] Chris@16: = !outer_face_edge[e] && (source(e,g) == x || target(e,g) == x); Chris@16: forbidden_edge[*ei] = outer_face_edge[*ei]; Chris@16: } Chris@16: Chris@16: vertex_t x_ancestor = v; Chris@16: vertex_t x_endpoint = graph_traits::null_vertex(); Chris@16: Chris@16: while(x_endpoint == graph_traits::null_vertex()) Chris@16: { Chris@16: x_ancestor = dfs_parent[x_ancestor]; Chris@16: x_endpoint = kuratowski_walkup(x_ancestor, Chris@16: forbidden_edge, Chris@16: goal_edge, Chris@16: is_embedded, Chris@16: x_external_path Chris@16: ); Chris@16: Chris@16: } Chris@16: Chris@16: Chris@16: for(boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) Chris@16: { Chris@16: edge_t e(*ei); Chris@16: goal_edge[e] Chris@16: = !outer_face_edge[e] && (source(e,g) == y || target(e,g) == y); Chris@16: forbidden_edge[*ei] = outer_face_edge[*ei]; Chris@16: } Chris@16: Chris@16: vertex_t y_ancestor = v; Chris@16: vertex_t y_endpoint = graph_traits::null_vertex(); Chris@16: Chris@16: while(y_endpoint == graph_traits::null_vertex()) Chris@16: { Chris@16: y_ancestor = dfs_parent[y_ancestor]; Chris@16: y_endpoint = kuratowski_walkup(y_ancestor, Chris@16: forbidden_edge, Chris@16: goal_edge, Chris@16: is_embedded, Chris@16: y_external_path Chris@16: ); Chris@16: Chris@16: } Chris@16: Chris@16: Chris@16: vertex_t parent, child; Chris@16: Chris@16: //If v isn't on the same bicomp as x and y, it's a case A Chris@16: if (bicomp_root != v) Chris@16: { Chris@16: chosen_case = detail::BM_CASE_A; Chris@16: Chris@16: for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi) Chris@16: if (lower_face_vertex[*vi]) Chris@16: for(boost::tie(oei,oei_end) = out_edges(*vi,g); oei != oei_end; ++oei) Chris@16: if(!outer_face_edge[*oei]) Chris@16: goal_edge[*oei] = true; Chris@16: Chris@16: for(boost::tie(ei,ei_end) = edges(g); ei != ei_end; ++ei) Chris@16: forbidden_edge[*ei] = outer_face_edge[*ei]; Chris@16: Chris@16: z = kuratowski_walkup Chris@16: (v, forbidden_edge, goal_edge, is_embedded, z_v_path); Chris@16: Chris@16: } Chris@16: else if (w != graph_traits::null_vertex()) Chris@16: { Chris@16: chosen_case = detail::BM_CASE_B; Chris@16: Chris@16: for(boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) Chris@16: { Chris@16: edge_t e(*ei); Chris@16: goal_edge[e] = false; Chris@16: forbidden_edge[e] = outer_face_edge[e]; Chris@16: } Chris@16: Chris@16: goal_edge[w_handle.first_edge()] = true; Chris@16: goal_edge[w_handle.second_edge()] = true; Chris@16: Chris@16: z = kuratowski_walkup(v, Chris@16: forbidden_edge, Chris@16: goal_edge, Chris@16: is_embedded, Chris@16: z_v_path Chris@16: ); Chris@16: Chris@16: Chris@16: for(boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) Chris@16: { Chris@16: forbidden_edge[*ei] = outer_face_edge[*ei]; Chris@16: } Chris@16: Chris@16: typename std::vector::iterator pi, pi_end; Chris@16: pi_end = z_v_path.end(); Chris@16: for(pi = z_v_path.begin(); pi != pi_end; ++pi) Chris@16: { Chris@16: goal_edge[*pi] = true; Chris@16: } Chris@16: Chris@16: w_ancestor = v; Chris@16: vertex_t w_endpoint = graph_traits::null_vertex(); Chris@16: Chris@16: while(w_endpoint == graph_traits::null_vertex()) Chris@16: { Chris@16: w_ancestor = dfs_parent[w_ancestor]; Chris@16: w_endpoint = kuratowski_walkup(w_ancestor, Chris@16: forbidden_edge, Chris@16: goal_edge, Chris@16: is_embedded, Chris@16: w_path Chris@16: ); Chris@16: Chris@16: } Chris@16: Chris@16: // We really want both the w walkup and the z walkup to finish on Chris@16: // exactly the same edge, but for convenience (since we don't have Chris@16: // control over which side of a bicomp a walkup moves up) we've Chris@16: // defined the walkup to either end at w_handle.first_edge() or Chris@16: // w_handle.second_edge(). If both walkups ended at different edges, Chris@16: // we'll do a little surgery on the w walkup path to make it follow Chris@16: // the other side of the final bicomp. Chris@16: Chris@16: if ((w_path.back() == w_handle.first_edge() && Chris@16: z_v_path.back() == w_handle.second_edge()) Chris@16: || Chris@16: (w_path.back() == w_handle.second_edge() && Chris@16: z_v_path.back() == w_handle.first_edge()) Chris@16: ) Chris@16: { Chris@16: walkup_itr_t wi, wi_end; Chris@16: edge_t final_edge = w_path.back(); Chris@16: vertex_t anchor Chris@16: = source(final_edge, g) == w_handle.get_anchor() ? Chris@16: target(final_edge, g) : source(final_edge, g); Chris@16: if (face_handles[anchor].first_edge() == final_edge) Chris@16: wi = walkup_itr_t(anchor, face_handles, second_side()); Chris@16: else Chris@16: wi = walkup_itr_t(anchor, face_handles, first_side()); Chris@16: Chris@16: w_path.pop_back(); Chris@16: Chris@16: for(; wi != wi_end; ++wi) Chris@16: { Chris@16: edge_t e(*wi); Chris@16: if (w_path.back() == e) Chris@16: w_path.pop_back(); Chris@16: else Chris@16: w_path.push_back(e); Chris@16: } Chris@16: } Chris@16: Chris@16: Chris@16: } Chris@16: else Chris@16: { Chris@16: Chris@16: //We need to find a valid z, since the x-y path re-defines the lower Chris@16: //face, and the z we found earlier may now be on the upper face. Chris@16: Chris@16: chosen_case = detail::BM_CASE_E; Chris@16: Chris@16: Chris@16: // The z we've used so far is just an externally active vertex on the Chris@16: // lower face path, but may not be the z we need for a case C, D, or Chris@16: // E subgraph. the z we need now is any externally active vertex on Chris@16: // the lower face path with both old_face_handles edges on the outer Chris@16: // face. Since we know an x-y path exists, such a z must also exist. Chris@16: Chris@16: //TODO: find this z in the first place. Chris@16: Chris@16: //find the new z Chris@16: Chris@16: for(face_itr = x_lower_itr; *face_itr != y; ++face_itr) Chris@16: { Chris@16: vertex_t possible_z(*face_itr); Chris@16: if (pertinent(possible_z,v) && Chris@16: outer_face_edge[face_handles[possible_z].old_first_edge()] && Chris@16: outer_face_edge[face_handles[possible_z].old_second_edge()] Chris@16: ) Chris@16: { Chris@16: z = possible_z; Chris@16: break; Chris@16: } Chris@16: } Chris@16: Chris@16: //find x-y path, and a w if one exists. Chris@16: Chris@16: if (externally_active(z,v)) Chris@16: w = z; Chris@16: Chris@16: Chris@16: typedef typename face_edge_iterator Chris@16: ::type old_face_iterator_t; Chris@16: Chris@16: old_face_iterator_t Chris@16: first_old_face_itr(z, face_handles, first_side()); Chris@16: old_face_iterator_t Chris@16: second_old_face_itr(z, face_handles, second_side()); Chris@16: old_face_iterator_t old_face_itr, old_face_end; Chris@16: Chris@16: std::vector old_face_iterators; Chris@16: old_face_iterators.push_back(first_old_face_itr); Chris@16: old_face_iterators.push_back(second_old_face_itr); Chris@16: Chris@16: std::vector x_y_path_vertex_vector(num_vertices(g), false); Chris@16: vertex_to_bool_map_t x_y_path_vertex Chris@16: (x_y_path_vertex_vector.begin(), vm); Chris@16: Chris@16: typename std::vector::iterator Chris@16: of_itr, of_itr_end; Chris@16: of_itr_end = old_face_iterators.end(); Chris@16: for(of_itr = old_face_iterators.begin(); Chris@16: of_itr != of_itr_end; ++of_itr Chris@16: ) Chris@16: { Chris@16: Chris@16: old_face_itr = *of_itr; Chris@16: Chris@16: vertex_t previous_vertex; Chris@16: bool seen_x_or_y = false; Chris@16: vertex_t current_vertex = z; Chris@16: for(; old_face_itr != old_face_end; ++old_face_itr) Chris@16: { Chris@16: edge_t e(*old_face_itr); Chris@16: previous_vertex = current_vertex; Chris@16: current_vertex = source(e,g) == current_vertex ? Chris@16: target(e,g) : source(e,g); Chris@16: Chris@16: if (current_vertex == x || current_vertex == y) Chris@16: seen_x_or_y = true; Chris@16: Chris@16: if (w == graph_traits::null_vertex() && Chris@16: externally_active(current_vertex,v) && Chris@16: outer_face_edge[e] && Chris@16: outer_face_edge[*boost::next(old_face_itr)] && Chris@16: !seen_x_or_y Chris@16: ) Chris@16: { Chris@16: w = current_vertex; Chris@16: } Chris@16: Chris@16: if (!outer_face_edge[e]) Chris@16: { Chris@16: if (!upper_face_vertex[current_vertex] && Chris@16: !lower_face_vertex[current_vertex] Chris@16: ) Chris@16: { Chris@16: x_y_path_vertex[current_vertex] = true; Chris@16: } Chris@16: Chris@16: is_in_subgraph[e] = true; Chris@16: if (upper_face_vertex[source(e,g)] || Chris@16: lower_face_vertex[source(e,g)] Chris@16: ) Chris@16: { Chris@16: if (first_x_y_path_endpoint == Chris@16: graph_traits::null_vertex() Chris@16: ) Chris@16: first_x_y_path_endpoint = source(e,g); Chris@16: else Chris@16: second_x_y_path_endpoint = source(e,g); Chris@16: } Chris@16: if (upper_face_vertex[target(e,g)] || Chris@16: lower_face_vertex[target(e,g)] Chris@16: ) Chris@16: { Chris@16: if (first_x_y_path_endpoint == Chris@16: graph_traits::null_vertex() Chris@16: ) Chris@16: first_x_y_path_endpoint = target(e,g); Chris@16: else Chris@16: second_x_y_path_endpoint = target(e,g); Chris@16: } Chris@16: Chris@16: Chris@16: } Chris@16: else if (previous_vertex == x || previous_vertex == y) Chris@16: { Chris@16: chosen_case = detail::BM_CASE_C; Chris@16: } Chris@16: Chris@16: } Chris@16: Chris@16: } Chris@16: Chris@16: // Look for a case D - one of v's embedded edges will connect to the Chris@16: // x-y path along an inner face path. Chris@16: Chris@16: //First, get a list of all of v's embedded child edges Chris@16: Chris@16: out_edge_iterator_t v_edge_itr, v_edge_end; Chris@16: for(boost::tie(v_edge_itr,v_edge_end) = out_edges(v,g); Chris@16: v_edge_itr != v_edge_end; ++v_edge_itr Chris@16: ) Chris@16: { Chris@16: edge_t embedded_edge(*v_edge_itr); Chris@16: Chris@16: if (!is_embedded[embedded_edge] || Chris@16: embedded_edge == dfs_parent_edge[v] Chris@16: ) Chris@16: continue; Chris@16: Chris@16: case_d_edges.push_back(embedded_edge); Chris@16: Chris@16: vertex_t current_vertex Chris@16: = source(embedded_edge,g) == v ? Chris@16: target(embedded_edge,g) : source(embedded_edge,g); Chris@16: Chris@16: typename face_edge_iterator<>::type Chris@16: internal_face_itr, internal_face_end; Chris@16: if (face_handles[current_vertex].first_vertex() == v) Chris@16: { Chris@16: internal_face_itr = typename face_edge_iterator<>::type Chris@16: (current_vertex, face_handles, second_side()); Chris@16: } Chris@16: else Chris@16: { Chris@16: internal_face_itr = typename face_edge_iterator<>::type Chris@16: (current_vertex, face_handles, first_side()); Chris@16: } Chris@16: Chris@16: while(internal_face_itr != internal_face_end && Chris@16: !outer_face_edge[*internal_face_itr] && Chris@16: !x_y_path_vertex[current_vertex] Chris@16: ) Chris@16: { Chris@16: edge_t e(*internal_face_itr); Chris@16: case_d_edges.push_back(e); Chris@16: current_vertex = Chris@16: source(e,g) == current_vertex ? target(e,g) : source(e,g); Chris@16: ++internal_face_itr; Chris@16: } Chris@16: Chris@16: if (x_y_path_vertex[current_vertex]) Chris@16: { Chris@16: chosen_case = detail::BM_CASE_D; Chris@16: break; Chris@16: } Chris@16: else Chris@16: { Chris@16: case_d_edges.clear(); Chris@16: } Chris@16: Chris@16: } Chris@16: Chris@16: Chris@16: } Chris@16: Chris@16: Chris@16: Chris@16: Chris@16: if (chosen_case != detail::BM_CASE_B && chosen_case != detail::BM_CASE_A) Chris@16: { Chris@16: Chris@16: //Finding z and w. Chris@16: Chris@16: for(boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) Chris@16: { Chris@16: edge_t e(*ei); Chris@16: goal_edge[e] = !outer_face_edge[e] && Chris@16: (source(e,g) == z || target(e,g) == z); Chris@16: forbidden_edge[e] = outer_face_edge[e]; Chris@16: } Chris@16: Chris@16: kuratowski_walkup(v, Chris@16: forbidden_edge, Chris@16: goal_edge, Chris@16: is_embedded, Chris@16: z_v_path Chris@16: ); Chris@16: Chris@16: if (chosen_case == detail::BM_CASE_E) Chris@16: { Chris@16: Chris@16: for(boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) Chris@16: { Chris@16: forbidden_edge[*ei] = outer_face_edge[*ei]; Chris@16: goal_edge[*ei] = !outer_face_edge[*ei] && Chris@16: (source(*ei,g) == w || target(*ei,g) == w); Chris@16: } Chris@16: Chris@16: for(boost::tie(oei, oei_end) = out_edges(w,g); oei != oei_end; ++oei) Chris@16: { Chris@16: if (!outer_face_edge[*oei]) Chris@16: goal_edge[*oei] = true; Chris@16: } Chris@16: Chris@16: typename std::vector::iterator pi, pi_end; Chris@16: pi_end = z_v_path.end(); Chris@16: for(pi = z_v_path.begin(); pi != pi_end; ++pi) Chris@16: { Chris@16: goal_edge[*pi] = true; Chris@16: } Chris@16: Chris@16: w_ancestor = v; Chris@16: vertex_t w_endpoint = graph_traits::null_vertex(); Chris@16: Chris@16: while(w_endpoint == graph_traits::null_vertex()) Chris@16: { Chris@16: w_ancestor = dfs_parent[w_ancestor]; Chris@16: w_endpoint = kuratowski_walkup(w_ancestor, Chris@16: forbidden_edge, Chris@16: goal_edge, Chris@16: is_embedded, Chris@16: w_path Chris@16: ); Chris@16: Chris@16: } Chris@16: Chris@16: } Chris@16: Chris@16: Chris@16: } Chris@16: Chris@16: Chris@16: //We're done isolating the Kuratowski subgraph at this point - Chris@16: //but there's still some cleaning up to do. Chris@16: Chris@16: //Update is_in_subgraph with the paths we just found Chris@16: Chris@16: xi_end = x_external_path.end(); Chris@16: for(xi = x_external_path.begin(); xi != xi_end; ++xi) Chris@16: is_in_subgraph[*xi] = true; Chris@16: Chris@16: xi_end = y_external_path.end(); Chris@16: for(xi = y_external_path.begin(); xi != xi_end; ++xi) Chris@16: is_in_subgraph[*xi] = true; Chris@16: Chris@16: xi_end = z_v_path.end(); Chris@16: for(xi = z_v_path.begin(); xi != xi_end; ++xi) Chris@16: is_in_subgraph[*xi] = true; Chris@16: Chris@16: xi_end = case_d_edges.end(); Chris@16: for(xi = case_d_edges.begin(); xi != xi_end; ++xi) Chris@16: is_in_subgraph[*xi] = true; Chris@16: Chris@16: xi_end = w_path.end(); Chris@16: for(xi = w_path.begin(); xi != xi_end; ++xi) Chris@16: is_in_subgraph[*xi] = true; Chris@16: Chris@16: child = bicomp_root; Chris@16: parent = dfs_parent[child]; Chris@16: while(child != parent) Chris@16: { Chris@16: is_in_subgraph[dfs_parent_edge[child]] = true; Chris@16: boost::tie(parent, child) = std::make_pair( dfs_parent[parent], parent ); Chris@16: } Chris@16: Chris@16: Chris@16: Chris@16: Chris@16: // At this point, we've already isolated the Kuratowski subgraph and Chris@16: // collected all of the edges that compose it in the is_in_subgraph Chris@16: // property map. But we want the verification of such a subgraph to be Chris@16: // a deterministic process, and we can simplify the function Chris@16: // is_kuratowski_subgraph by cleaning up some edges here. Chris@16: Chris@16: if (chosen_case == detail::BM_CASE_B) Chris@16: { Chris@16: is_in_subgraph[dfs_parent_edge[v]] = false; Chris@16: } Chris@16: else if (chosen_case == detail::BM_CASE_C) Chris@16: { Chris@16: // In a case C subgraph, at least one of the x-y path endpoints Chris@16: // (call it alpha) is above either x or y on the outer face. The Chris@16: // other endpoint may be attached at x or y OR above OR below. In Chris@16: // any of these three cases, we can form a K_3_3 by removing the Chris@16: // edge attached to v on the outer face that is NOT on the path to Chris@16: // alpha. Chris@16: Chris@16: typename face_vertex_iterator::type Chris@16: face_itr, face_end; Chris@16: if (face_handles[v_dfchild_handle.first_vertex()].first_edge() == Chris@16: v_dfchild_handle.first_edge() Chris@16: ) Chris@16: { Chris@16: face_itr = typename face_vertex_iterator Chris@16: ::type Chris@16: (v_dfchild_handle.first_vertex(), face_handles, second_side()); Chris@16: } Chris@16: else Chris@16: { Chris@16: face_itr = typename face_vertex_iterator Chris@16: ::type Chris@16: (v_dfchild_handle.first_vertex(), face_handles, first_side()); Chris@16: } Chris@16: Chris@16: for(; true; ++face_itr) Chris@16: { Chris@16: vertex_t current_vertex(*face_itr); Chris@16: if (current_vertex == x || current_vertex == y) Chris@16: { Chris@16: is_in_subgraph[v_dfchild_handle.first_edge()] = false; Chris@16: break; Chris@16: } Chris@16: else if (current_vertex == first_x_y_path_endpoint || Chris@16: current_vertex == second_x_y_path_endpoint) Chris@16: { Chris@16: is_in_subgraph[v_dfchild_handle.second_edge()] = false; Chris@16: break; Chris@16: } Chris@16: } Chris@16: Chris@16: } Chris@16: else if (chosen_case == detail::BM_CASE_D) Chris@16: { Chris@16: // Need to remove both of the edges adjacent to v on the outer face. Chris@16: // remove the connecting edges from v to bicomp, then Chris@16: // is_kuratowski_subgraph will shrink vertices of degree 1 Chris@16: // automatically... Chris@16: Chris@16: is_in_subgraph[v_dfchild_handle.first_edge()] = false; Chris@16: is_in_subgraph[v_dfchild_handle.second_edge()] = false; Chris@16: Chris@16: } Chris@16: else if (chosen_case == detail::BM_CASE_E) Chris@16: { Chris@16: // Similarly to case C, if the endpoints of the x-y path are both Chris@16: // below x and y, we should remove an edge to allow the subgraph to Chris@16: // contract to a K_3_3. Chris@16: Chris@16: Chris@16: if ((first_x_y_path_endpoint != x && first_x_y_path_endpoint != y) || Chris@16: (second_x_y_path_endpoint != x && second_x_y_path_endpoint != y) Chris@16: ) Chris@16: { Chris@16: is_in_subgraph[dfs_parent_edge[v]] = false; Chris@16: Chris@16: vertex_t deletion_endpoint, other_endpoint; Chris@16: if (lower_face_vertex[first_x_y_path_endpoint]) Chris@16: { Chris@16: deletion_endpoint = second_x_y_path_endpoint; Chris@16: other_endpoint = first_x_y_path_endpoint; Chris@16: } Chris@16: else Chris@16: { Chris@16: deletion_endpoint = first_x_y_path_endpoint; Chris@16: other_endpoint = second_x_y_path_endpoint; Chris@16: } Chris@16: Chris@16: typename face_edge_iterator<>::type face_itr, face_end; Chris@16: Chris@16: bool found_other_endpoint = false; Chris@16: for(face_itr = typename face_edge_iterator<>::type Chris@16: (deletion_endpoint, face_handles, first_side()); Chris@16: face_itr != face_end; ++face_itr Chris@16: ) Chris@16: { Chris@16: edge_t e(*face_itr); Chris@16: if (source(e,g) == other_endpoint || Chris@16: target(e,g) == other_endpoint Chris@16: ) Chris@16: { Chris@16: found_other_endpoint = true; Chris@16: break; Chris@16: } Chris@16: } Chris@16: Chris@16: if (found_other_endpoint) Chris@16: { Chris@16: is_in_subgraph[face_handles[deletion_endpoint].first_edge()] Chris@16: = false; Chris@16: } Chris@16: else Chris@16: { Chris@16: is_in_subgraph[face_handles[deletion_endpoint].second_edge()] Chris@16: = false; Chris@16: } Chris@16: } Chris@16: Chris@16: } Chris@16: Chris@16: Chris@16: for(boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) Chris@16: if (is_in_subgraph[*ei]) Chris@16: *o_itr = *ei; Chris@16: Chris@16: } Chris@16: Chris@16: Chris@16: Chris@16: template Chris@16: void make_edge_permutation(EdgePermutation perm) Chris@16: { Chris@16: vertex_iterator_t vi, vi_end; Chris@16: for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi) Chris@16: { Chris@16: vertex_t v(*vi); Chris@16: perm[v].clear(); Chris@16: face_handles[v].get_list(std::back_inserter(perm[v])); Chris@16: } Chris@16: } Chris@16: Chris@16: Chris@16: private: Chris@16: Chris@16: const Graph& g; Chris@16: VertexIndexMap vm; Chris@16: Chris@16: vertex_t kuratowski_v; Chris@16: vertex_t kuratowski_x; Chris@16: vertex_t kuratowski_y; Chris@16: Chris@16: vertex_list_t garbage; // we delete items from linked lists by Chris@16: // splicing them into garbage Chris@16: Chris@16: //only need these two for kuratowski subgraph isolation Chris@16: std::vector current_merge_points; Chris@16: std::vector embedded_edges; Chris@16: Chris@16: //property map storage Chris@16: std::vector low_point_vector; Chris@16: std::vector dfs_parent_vector; Chris@16: std::vector dfs_number_vector; Chris@16: std::vector least_ancestor_vector; Chris@16: std::vector pertinent_roots_vector; Chris@16: std::vector backedge_flag_vector; Chris@16: std::vector visited_vector; Chris@16: std::vector< face_handle_t > face_handles_vector; Chris@16: std::vector< face_handle_t > dfs_child_handles_vector; Chris@16: std::vector< vertex_list_ptr_t > separated_dfs_child_list_vector; Chris@16: std::vector< typename vertex_list_t::iterator > Chris@16: separated_node_in_parent_list_vector; Chris@16: std::vector canonical_dfs_child_vector; Chris@16: std::vector flipped_vector; Chris@16: std::vector backedges_vector; Chris@16: edge_vector_t self_loops; Chris@16: std::vector dfs_parent_edge_vector; Chris@16: vertex_vector_t vertices_by_dfs_num; Chris@16: Chris@16: //property maps Chris@16: vertex_to_v_size_map_t low_point; Chris@16: vertex_to_vertex_map_t dfs_parent; Chris@16: vertex_to_v_size_map_t dfs_number; Chris@16: vertex_to_v_size_map_t least_ancestor; Chris@16: vertex_to_face_handle_list_ptr_map_t pertinent_roots; Chris@16: vertex_to_v_size_map_t backedge_flag; Chris@16: vertex_to_v_size_map_t visited; Chris@16: vertex_to_face_handle_map_t face_handles; Chris@16: vertex_to_face_handle_map_t dfs_child_handles; Chris@16: vertex_to_vertex_list_ptr_map_t separated_dfs_child_list; Chris@16: vertex_to_separated_node_map_t separated_node_in_parent_list; Chris@16: vertex_to_vertex_map_t canonical_dfs_child; Chris@16: vertex_to_bool_map_t flipped; Chris@16: vertex_to_edge_vector_map_t backedges; Chris@16: vertex_to_edge_map_t dfs_parent_edge; //only need for kuratowski Chris@16: Chris@16: merge_stack_t merge_stack; Chris@16: Chris@16: }; Chris@16: Chris@16: Chris@16: } //namespace boost Chris@16: Chris@16: #endif //__BOYER_MYRVOLD_IMPL_HPP__