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