12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012 |
- //=======================================================================
- // 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/next_prior.hpp>
- #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&)
- {
- 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(boost::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(boost::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
- = graph_traits<Graph>::null_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();
- boost::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();
- boost::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;
- vertex_t merge_point = chosen;
- while(!merge_stack.empty())
- {
- bottom_path_follows_first = next_bottom_follows_first;
- boost::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, 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, 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(boost::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(boost::tie(oi,oi_end) = out_edges(v,g); oi != oi_end; ++oi)
- forbidden_edge[*oi] = true;
- for(boost::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(boost::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 = graph_traits<Graph>::null_vertex();
- 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(boost::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(boost::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(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
- if (lower_face_vertex[*vi])
- for(boost::tie(oei,oei_end) = out_edges(*vi,g); oei != oei_end; ++oei)
- if(!outer_face_edge[*oei])
- goal_edge[*oei] = true;
- for(boost::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(boost::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(boost::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(boost::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(boost::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(boost::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(boost::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;
- boost::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(boost::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(boost::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__
|