summaryrefslogtreecommitdiff
path: root/boost/graph/depth_first_search.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'boost/graph/depth_first_search.hpp')
-rw-r--r--boost/graph/depth_first_search.hpp66
1 files changed, 47 insertions, 19 deletions
diff --git a/boost/graph/depth_first_search.hpp b/boost/graph/depth_first_search.hpp
index 34d73a2fdd..b002d3674a 100644
--- a/boost/graph/depth_first_search.hpp
+++ b/boost/graph/depth_first_search.hpp
@@ -21,8 +21,10 @@
#include <boost/graph/named_function_params.hpp>
#include <boost/ref.hpp>
#include <boost/implicit_cast.hpp>
+#include <boost/optional.hpp>
#include <boost/parameter.hpp>
#include <boost/concept/assert.hpp>
+#include <boost/tti/has_member_function.hpp>
#include <vector>
#include <utility>
@@ -41,6 +43,7 @@ namespace boost {
vis.tree_edge(e, g);
vis.back_edge(e, g);
vis.forward_or_cross_edge(e, g);
+ // vis.finish_edge(e, g); // Optional for user
vis.finish_vertex(u, g);
}
private:
@@ -57,6 +60,25 @@ namespace boost {
bool operator()(const T&, const T2&) const { return false; }
};
+ BOOST_TTI_HAS_MEMBER_FUNCTION(finish_edge)
+
+ template <bool IsCallable> struct do_call_finish_edge {
+ template <typename E, typename G, typename Vis>
+ static void call_finish_edge(Vis& vis, const E& e, const G& g) {
+ vis.finish_edge(e, g);
+ }
+ };
+
+ template <> struct do_call_finish_edge<false> {
+ template <typename E, typename G, typename Vis>
+ static void call_finish_edge(Vis&, const E&, const G&) {}
+ };
+
+ template <typename E, typename G, typename Vis>
+ void call_finish_edge(Vis& vis, const E& e, const G& g) { // Only call if method exists
+ do_call_finish_edge<has_member_function_finish_edge<Vis, void>::value>::call_finish_edge(vis, e, g);
+ }
+
// Define BOOST_RECURSIVE_DFS to use older, recursive version.
// It is retained for a while in order to perform performance
@@ -85,36 +107,35 @@ namespace boost {
BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<IncidenceGraph> ));
BOOST_CONCEPT_ASSERT(( DFSVisitorConcept<DFSVisitor, IncidenceGraph> ));
typedef typename graph_traits<IncidenceGraph>::vertex_descriptor Vertex;
+ typedef typename graph_traits<IncidenceGraph>::edge_descriptor Edge;
BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<ColorMap, Vertex> ));
typedef typename property_traits<ColorMap>::value_type ColorValue;
BOOST_CONCEPT_ASSERT(( ColorValueConcept<ColorValue> ));
typedef color_traits<ColorValue> Color;
typedef typename graph_traits<IncidenceGraph>::out_edge_iterator Iter;
- typedef std::pair<Vertex, std::pair<Iter, Iter> > VertexInfo;
+ typedef std::pair<Vertex, std::pair<boost::optional<Edge>, std::pair<Iter, Iter> > > VertexInfo;
+ boost::optional<Edge> src_e;
Iter ei, ei_end;
std::vector<VertexInfo> stack;
// Possible optimization for vector
//stack.reserve(num_vertices(g));
- typedef typename unwrap_reference<TerminatorFunc>::type TF;
-
put(color, u, Color::gray());
vis.discover_vertex(u, g);
boost::tie(ei, ei_end) = out_edges(u, g);
- // Variable is needed to workaround a borland bug.
- TF& fn = static_cast<TF&>(func);
- if (fn(u, g)) {
+ if (func(u, g)) {
// If this vertex terminates the search, we push empty range
- stack.push_back(std::make_pair(u, std::make_pair(ei_end, ei_end)));
+ stack.push_back(std::make_pair(u, std::make_pair(boost::optional<Edge>(), std::make_pair(ei_end, ei_end))));
} else {
- stack.push_back(std::make_pair(u, std::make_pair(ei, ei_end)));
+ stack.push_back(std::make_pair(u, std::make_pair(boost::optional<Edge>(), std::make_pair(ei, ei_end))));
}
while (!stack.empty()) {
VertexInfo& back = stack.back();
u = back.first;
- boost::tie(ei, ei_end) = back.second;
+ src_e = back.second.first;
+ boost::tie(ei, ei_end) = back.second.second;
stack.pop_back();
while (ei != ei_end) {
Vertex v = target(*ei, g);
@@ -122,24 +143,28 @@ namespace boost {
ColorValue v_color = get(color, v);
if (v_color == Color::white()) {
vis.tree_edge(*ei, g);
- stack.push_back(std::make_pair(u, std::make_pair(++ei, ei_end)));
+ src_e = *ei;
+ stack.push_back(std::make_pair(u, std::make_pair(src_e, std::make_pair(++ei, ei_end))));
u = v;
put(color, u, Color::gray());
vis.discover_vertex(u, g);
boost::tie(ei, ei_end) = out_edges(u, g);
- if (fn(u, g)) {
+ if (func(u, g)) {
ei = ei_end;
}
- } else if (v_color == Color::gray()) {
- vis.back_edge(*ei, g);
- ++ei;
} else {
- vis.forward_or_cross_edge(*ei, g);
+ if (v_color == Color::gray()) {
+ vis.back_edge(*ei, g);
+ } else {
+ vis.forward_or_cross_edge(*ei, g);
+ }
+ call_finish_edge(vis, *ei, g);
++ei;
}
}
put(color, u, Color::black());
vis.finish_vertex(u, g);
+ if (src_e) call_finish_edge(vis, src_e.get(), g);
}
}
@@ -164,10 +189,7 @@ namespace boost {
put(color, u, Color::gray()); vis.discover_vertex(u, g);
- typedef typename unwrap_reference<TerminatorFunc>::type TF;
- // Variable is needed to workaround a borland bug.
- TF& fn = static_cast<TF&>(func);
- if (!fn(u, g))
+ if (!func(u, g))
for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) {
Vertex v = target(*ei, g); vis.examine_edge(*ei, g);
ColorValue v_color = get(color, v);
@@ -175,6 +197,7 @@ namespace boost {
depth_first_visit_impl(g, v, vis, color, func);
} else if (v_color == Color::gray()) vis.back_edge(*ei, g);
else vis.forward_or_cross_edge(*ei, g);
+ call_finish_edge(vis, *ei, g);
}
put(color, u, Color::black()); vis.finish_vertex(u, g);
}
@@ -259,6 +282,10 @@ namespace boost {
void forward_or_cross_edge(Edge u, const Graph& g) {
invoke_visitors(m_vis, u, g, ::boost::on_forward_or_cross_edge());
}
+ template <class Edge, class Graph>
+ void finish_edge(Edge u, const Graph& g) {
+ invoke_visitors(m_vis, u, g, ::boost::on_finish_edge());
+ }
template <class Vertex, class Graph>
void finish_vertex(Vertex u, const Graph& g) {
invoke_visitors(m_vis, u, g, ::boost::on_finish_vertex());
@@ -271,6 +298,7 @@ namespace boost {
BOOST_GRAPH_EVENT_STUB(on_tree_edge,dfs)
BOOST_GRAPH_EVENT_STUB(on_back_edge,dfs)
BOOST_GRAPH_EVENT_STUB(on_forward_or_cross_edge,dfs)
+ BOOST_GRAPH_EVENT_STUB(on_finish_edge,dfs)
BOOST_GRAPH_EVENT_STUB(on_finish_vertex,dfs)
protected:
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-24 11:05:14 +0000