1 #ifndef DEPTHFIRSTSEARCH_H 2 #define DEPTHFIRSTSEARCH_H 1 3 4 #include "Graph/ContigGraphAlgorithms.h" // for contiguous_in 5 #include <boost/graph/depth_first_search.hpp> 6 7 using boost::graph_traits; 8 9 /** 10 * Perform a depth-first search starting first with vertices with 11 * deg-(u) = 0 and then visiting any remaining vertices. 12 */ 13 template <class Graph, class Visitor, class ColorMap> 14 void depthFirstSearch(const Graph& g, Visitor vis, ColorMap color, bool ss = false) 15 { 16 using boost::color_traits; 17 using boost::property_traits; 18 using boost::tie; 19 20 typedef graph_traits<Graph> GTraits; 21 typedef typename GTraits::vertex_descriptor V; 22 typedef typename GTraits::vertex_iterator Vit; 23 typedef typename property_traits<ColorMap>::value_type ColorValue; 24 const ColorValue white = color_traits<ColorValue>::white(); 25 26 // Initialize the vertices. 27 Vit uit, ulast; 28 for (tie(uit, ulast) = vertices(g); uit != ulast; ++uit) { 29 V u = *uit; 30 put(color, u, white); 31 vis.initialize_vertex(u, g); 32 } 33 34 // Visit vertices with deg-(u) = 0. 35 for (tie(uit, ulast) = vertices(g); uit != ulast; ++uit) { 36 V u = *uit; 37 if (get(color, u) == white && in_degree(u, g) == 0) { 38 vis.start_vertex(u, g); 39 boost::detail::depth_first_visit_impl(g, u, vis, color, 40 boost::detail::nontruth2()); 41 } 42 if (ss) { 43 ++uit; 44 assert(uit != ulast); 45 } 46 } 47 48 // Visit vertices where discontiguous-(u). 49 for (tie(uit, ulast) = vertices(g); uit != ulast; ++uit) { 50 V u = *uit; 51 if (get(color, u) == white && !contiguous_in(g, u)) { 52 vis.start_vertex(u, g); 53 boost::detail::depth_first_visit_impl(g, u, vis, color, 54 boost::detail::nontruth2()); 55 } 56 if (ss) { 57 ++uit; 58 assert(uit != ulast); 59 } 60 } 61 62 // Visit the remaining vertices. 63 for (tie(uit, ulast) = vertices(g); uit != ulast; ++uit) { 64 V u = *uit; 65 if (get(color, u) == white) { 66 vis.start_vertex(u, g); 67 boost::detail::depth_first_visit_impl(g, u, vis, color, 68 boost::detail::nontruth2()); 69 } 70 } 71 } 72 73 #endif 74