/
usr
/
include
/
boost
/
graph
/
/usr/include/boost/graph
mkdir
upload
Name
Size
Mode
Actions
detail/
-
0755
rm
distributed/
-
0755
rm
parallel/
-
0755
rm
planar_detail/
-
0755
rm
property_maps/
-
0755
rm
accounting.hpp
876
0644
edit
dl
rm
adjacency_iterator.hpp
2899
0644
edit
dl
rm
adjacency_list.hpp
13692
0644
edit
dl
rm
adjacency_list_io.hpp
11849
0644
edit
dl
rm
adjacency_matrix.hpp
45743
0644
edit
dl
rm
adj_list_serialize.hpp
4523
0644
edit
dl
rm
astar_search.hpp
26736
0644
edit
dl
rm
bandwidth.hpp
2992
0644
edit
dl
rm
bc_clustering.hpp
5937
0644
edit
dl
rm
bellman_ford_shortest_paths.hpp
8229
0644
edit
dl
rm
betweenness_centrality.hpp
26290
0644
edit
dl
rm
biconnected_components.hpp
16701
0644
edit
dl
rm
bipartite.hpp
13492
0644
edit
dl
rm
boyer_myrvold_planar_test.hpp
9849
0644
edit
dl
rm
boykov_kolmogorov_max_flow.hpp
47342
0644
edit
dl
rm
breadth_first_search.hpp
14751
0644
edit
dl
rm
bron_kerbosch_all_cliques.hpp
11736
0644
edit
dl
rm
buffer_concepts.hpp
2429
0644
edit
dl
rm
chrobak_payne_drawing.hpp
8641
0644
edit
dl
rm
circle_layout.hpp
1924
0644
edit
dl
rm
closeness_centrality.hpp
6057
0644
edit
dl
rm
clustering_coefficient.hpp
5726
0644
edit
dl
rm
compressed_sparse_row_graph.hpp
69887
0644
edit
dl
rm
connected_components.hpp
4134
0644
edit
dl
rm
copy.hpp
21225
0644
edit
dl
rm
core_numbers.hpp
13663
0644
edit
dl
rm
create_condensation_graph.hpp
3159
0644
edit
dl
rm
cuthill_mckee_ordering.hpp
5992
0644
edit
dl
rm
cycle_canceling.hpp
6645
0644
edit
dl
rm
dag_shortest_paths.hpp
6064
0644
edit
dl
rm
degree_centrality.hpp
4236
0644
edit
dl
rm
depth_first_search.hpp
15430
0644
edit
dl
rm
dijkstra_shortest_paths.hpp
23687
0644
edit
dl
rm
dijkstra_shortest_paths_no_color_map.hpp
9620
0644
edit
dl
rm
dimacs.hpp
10448
0644
edit
dl
rm
directed_graph.hpp
24214
0644
edit
dl
rm
dll_import_export.hpp
892
0644
edit
dl
rm
dominator_tree.hpp
17553
0644
edit
dl
rm
eccentricity.hpp
4611
0644
edit
dl
rm
edge_coloring.hpp
6809
0644
edit
dl
rm
edge_connectivity.hpp
6796
0644
edit
dl
rm
edge_list.hpp
9948
0644
edit
dl
rm
edmonds_karp_max_flow.hpp
10177
0644
edit
dl
rm
edmunds_karp_max_flow.hpp
982
0644
edit
dl
rm
erdos_renyi_generator.hpp
7257
0644
edit
dl
rm
exception.hpp
1466
0644
edit
dl
rm
exterior_property.hpp
4289
0644
edit
dl
rm
filtered_graph.hpp
20098
0644
edit
dl
rm
find_flow_cost.hpp
1859
0644
edit
dl
rm
floyd_warshall_shortest.hpp
8510
0644
edit
dl
rm
fruchterman_reingold.hpp
17325
0644
edit
dl
rm
geodesic_distance.hpp
8015
0644
edit
dl
rm
graphml.hpp
13460
0644
edit
dl
rm
graphviz.hpp
33503
0644
edit
dl
rm
graph_archetypes.hpp
11008
0644
edit
dl
rm
graph_as_tree.hpp
4532
0644
edit
dl
rm
graph_concepts.hpp
19785
0644
edit
dl
rm
graph_mutability_traits.hpp
4995
0644
edit
dl
rm
graph_selectors.hpp
1274
0644
edit
dl
rm
graph_stats.hpp
4394
0644
edit
dl
rm
graph_traits.hpp
13065
0644
edit
dl
rm
graph_utility.hpp
16182
0644
edit
dl
rm
grid_graph.hpp
33830
0644
edit
dl
rm
gursoy_atun_layout.hpp
13248
0644
edit
dl
rm
hawick_circuits.hpp
14593
0644
edit
dl
rm
howard_cycle_ratio.hpp
23107
0644
edit
dl
rm
incremental_components.hpp
8224
0644
edit
dl
rm
isomorphism.hpp
26308
0644
edit
dl
rm
is_kuratowski_subgraph.hpp
10260
0644
edit
dl
rm
is_straight_line_drawing.hpp
7230
0644
edit
dl
rm
iteration_macros.hpp
11659
0644
edit
dl
rm
iteration_macros_undef.hpp
673
0644
edit
dl
rm
johnson_all_pairs_shortest.hpp
7646
0644
edit
dl
rm
kamada_kawai_spring_layout.hpp
28048
0644
edit
dl
rm
king_ordering.hpp
12101
0644
edit
dl
rm
kruskal_min_spanning_tree.hpp
5743
0644
edit
dl
rm
labeled_graph.hpp
30914
0644
edit
dl
rm
leda_graph.hpp
28789
0644
edit
dl
rm
lookup_edge.hpp
1894
0644
edit
dl
rm
loop_erased_random_walk.hpp
4436
0644
edit
dl
rm
make_biconnected_planar.hpp
3513
0644
edit
dl
rm
make_connected.hpp
2645
0644
edit
dl
rm
make_maximal_planar.hpp
7578
0644
edit
dl
rm
matrix_as_graph.hpp
7227
0644
edit
dl
rm
maximum_adjacency_search.hpp
15125
0644
edit
dl
rm
maximum_weighted_matching.hpp
49722
0644
edit
dl
rm
max_cardinality_matching.hpp
31000
0644
edit
dl
rm
mcgregor_common_subgraphs.hpp
43470
0644
edit
dl
rm
mesh_graph_generator.hpp
5616
0644
edit
dl
rm
metis.hpp
10982
0644
edit
dl
rm
metric_tsp_approx.hpp
10809
0644
edit
dl
rm
minimum_degree_ordering.hpp
27087
0644
edit
dl
rm
named_function_params.hpp
39639
0644
edit
dl
rm
named_graph.hpp
20614
0644
edit
dl
rm
neighbor_bfs.hpp
11763
0644
edit
dl
rm
numeric_values.hpp
1814
0644
edit
dl
rm
one_bit_color_map.hpp
3277
0644
edit
dl
rm
overloading.hpp
1584
0644
edit
dl
rm
page_rank.hpp
6164
0644
edit
dl
rm
planar_canonical_ordering.hpp
7203
0644
edit
dl
rm
planar_face_traversal.hpp
6020
0644
edit
dl
rm
plod_generator.hpp
7708
0644
edit
dl
rm
point_traits.hpp
782
0644
edit
dl
rm
prim_minimum_spanning_tree.hpp
2960
0644
edit
dl
rm
profile.hpp
1327
0644
edit
dl
rm
properties.hpp
12417
0644
edit
dl
rm
property_iter_range.hpp
4345
0644
edit
dl
rm
push_relabel_max_flow.hpp
34737
0644
edit
dl
rm
random.hpp
9672
0644
edit
dl
rm
random_layout.hpp
988
0644
edit
dl
rm
random_spanning_tree.hpp
5775
0644
edit
dl
rm
read_dimacs.hpp
12080
0644
edit
dl
rm
relax.hpp
4400
0644
edit
dl
rm
reverse_graph.hpp
22402
0644
edit
dl
rm
rmat_graph_generator.hpp
19291
0644
edit
dl
rm
r_c_shortest_paths.hpp
30673
0644
edit
dl
rm
sequential_vertex_coloring.hpp
4562
0644
edit
dl
rm
simple_point.hpp
628
0644
edit
dl
rm
sloan_ordering.hpp
15540
0644
edit
dl
rm
smallest_last_ordering.hpp
5458
0644
edit
dl
rm
small_world_generator.hpp
3670
0644
edit
dl
rm
ssca_graph_generator.hpp
6564
0644
edit
dl
rm
stanford_graph.hpp
20126
0644
edit
dl
rm
stoer_wagner_min_cut.hpp
12415
0644
edit
dl
rm
strong_components.hpp
13009
0644
edit
dl
rm
st_connected.hpp
2852
0644
edit
dl
rm
subgraph.hpp
39996
0644
edit
dl
rm
successive_shortest_path_nonnegative_weights.hpp
10413
0644
edit
dl
rm
tiernan_all_cycles.hpp
12547
0644
edit
dl
rm
topological_sort.hpp
2611
0644
edit
dl
rm
topology.hpp
20389
0644
edit
dl
rm
transitive_closure.hpp
14260
0644
edit
dl
rm
transitive_reduction.hpp
5326
0644
edit
dl
rm
transpose_graph.hpp
1198
0644
edit
dl
rm
tree_traits.hpp
1338
0644
edit
dl
rm
two_bit_color_map.hpp
3510
0644
edit
dl
rm
two_graphs_common_spanning_trees.hpp
34996
0644
edit
dl
rm
undirected_dfs.hpp
10672
0644
edit
dl
rm
undirected_graph.hpp
25276
0644
edit
dl
rm
use_mpi.hpp
437
0644
edit
dl
rm
vector_as_graph.hpp
10474
0644
edit
dl
rm
vertex_and_edge_range.hpp
5528
0644
edit
dl
rm
vf2_sub_graph_iso.hpp
48585
0644
edit
dl
rm
visitors.hpp
11318
0644
edit
dl
rm
wavefront.hpp
3932
0644
edit
dl
rm
write_dimacs.hpp
2889
0644
edit
dl
rm
Edit:
/usr/include/boost/graph/depth_first_search.hpp
(15430B)
//======================================================================= // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. // Copyright 2003 Bruce Barr // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek // // 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) //======================================================================= // Nonrecursive implementation of depth_first_visit_impl submitted by // Bruce Barr, schmoost <at> yahoo.com, May/June 2003. #ifndef BOOST_GRAPH_RECURSIVE_DFS_HPP #define BOOST_GRAPH_RECURSIVE_DFS_HPP #include <boost/config.hpp> #include <boost/graph/graph_traits.hpp> #include <boost/graph/graph_concepts.hpp> #include <boost/graph/properties.hpp> #include <boost/graph/visitors.hpp> #include <boost/graph/named_function_params.hpp> #include <boost/graph/detail/mpi_include.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> namespace boost { template < class Visitor, class Graph > class DFSVisitorConcept { public: void constraints() { BOOST_CONCEPT_ASSERT((CopyConstructibleConcept< Visitor >)); vis.initialize_vertex(u, g); vis.start_vertex(u, g); vis.discover_vertex(u, g); vis.examine_edge(e, g); 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: Visitor vis; Graph g; typename graph_traits< Graph >::vertex_descriptor u; typename graph_traits< Graph >::edge_descriptor e; }; namespace detail { struct nontruth2 { template < class T, class T2 > 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, 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&, E, const G&) { } }; template < typename E, typename G, typename Vis > void call_finish_edge(Vis& vis, E e, const G& g) { // Only call if method exists #if ((defined(__GNUC__) && (__GNUC__ > 4) \ || ((__GNUC__ == 4) && (__GNUC_MINOR__ >= 9))) \ || defined(__clang__) \ || (defined(__INTEL_COMPILER) && (__INTEL_COMPILER >= 1200))) do_call_finish_edge< has_member_function_finish_edge< Vis, void, boost::mpl::vector< E, const G& > >::value >::call_finish_edge(vis, e, g); #else do_call_finish_edge< has_member_function_finish_edge< Vis, void >::value >::call_finish_edge(vis, e, g); #endif } // Define BOOST_RECURSIVE_DFS to use older, recursive version. // It is retained for a while in order to perform performance // comparison. #ifndef BOOST_RECURSIVE_DFS // If the vertex u and the iterators ei and ei_end are thought of as the // context of the algorithm, each push and pop from the stack could // be thought of as a context shift. // Each pass through "while (ei != ei_end)" may refer to the out-edges of // an entirely different vertex, because the context of the algorithm // shifts every time a white adjacent vertex is discovered. // The corresponding context shift back from the adjacent vertex occurs // after all of its out-edges have been examined. // // See https://lists.boost.org/Archives/boost/2003/06/49265.php for FAQ. template < class IncidenceGraph, class DFSVisitor, class ColorMap, class TerminatorFunc > void depth_first_visit_impl(const IncidenceGraph& g, typename graph_traits< IncidenceGraph >::vertex_descriptor u, DFSVisitor& vis, ColorMap color, TerminatorFunc func = TerminatorFunc()) { 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< 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)); put(color, u, Color::gray()); vis.discover_vertex(u, g); boost::tie(ei, ei_end) = out_edges(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(boost::optional< Edge >(), std::make_pair(ei_end, ei_end)))); } else { 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; src_e = back.second.first; boost::tie(ei, ei_end) = back.second.second; stack.pop_back(); // finish_edge has to be called here, not after the // loop. Think of the pop as the return from a recursive call. if (src_e) { call_finish_edge(vis, src_e.get(), g); } while (ei != ei_end) { Vertex v = target(*ei, g); vis.examine_edge(*ei, g); ColorValue v_color = get(color, v); if (v_color == Color::white()) { vis.tree_edge(*ei, g); 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 (func(u, g)) { ei = ei_end; } } 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); ++ei; } } put(color, u, Color::black()); vis.finish_vertex(u, g); } } #else // BOOST_RECURSIVE_DFS is defined template < class IncidenceGraph, class DFSVisitor, class ColorMap, class TerminatorFunc > void depth_first_visit_impl(const IncidenceGraph& g, typename graph_traits< IncidenceGraph >::vertex_descriptor u, DFSVisitor& vis, // pass-by-reference here, important! ColorMap color, TerminatorFunc func) { BOOST_CONCEPT_ASSERT((IncidenceGraphConcept< IncidenceGraph >)); BOOST_CONCEPT_ASSERT((DFSVisitorConcept< DFSVisitor, IncidenceGraph >)); typedef typename graph_traits< IncidenceGraph >::vertex_descriptor Vertex; BOOST_CONCEPT_ASSERT((ReadWritePropertyMapConcept< ColorMap, Vertex >)); typedef typename property_traits< ColorMap >::value_type ColorValue; BOOST_CONCEPT_ASSERT((ColorValueConcept< ColorValue >)); typedef color_traits< ColorValue > Color; typename graph_traits< IncidenceGraph >::out_edge_iterator ei, ei_end; put(color, u, Color::gray()); vis.discover_vertex(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); if (v_color == Color::white()) { vis.tree_edge(*ei, g); 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); } #endif } // namespace detail template < class VertexListGraph, class DFSVisitor, class ColorMap > void depth_first_search(const VertexListGraph& g, DFSVisitor vis, ColorMap color, typename graph_traits< VertexListGraph >::vertex_descriptor start_vertex) { typedef typename graph_traits< VertexListGraph >::vertex_descriptor Vertex; BOOST_CONCEPT_ASSERT((DFSVisitorConcept< DFSVisitor, VertexListGraph >)); typedef typename property_traits< ColorMap >::value_type ColorValue; typedef color_traits< ColorValue > Color; typename graph_traits< VertexListGraph >::vertex_iterator ui, ui_end; for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) { Vertex u = implicit_cast< Vertex >(*ui); put(color, u, Color::white()); vis.initialize_vertex(u, g); } if (start_vertex != detail::get_default_starting_vertex(g)) { vis.start_vertex(start_vertex, g); detail::depth_first_visit_impl( g, start_vertex, vis, color, detail::nontruth2()); } for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) { Vertex u = implicit_cast< Vertex >(*ui); ColorValue u_color = get(color, u); if (u_color == Color::white()) { vis.start_vertex(u, g); detail::depth_first_visit_impl( g, u, vis, color, detail::nontruth2()); } } } template < class VertexListGraph, class DFSVisitor, class ColorMap > void depth_first_search( const VertexListGraph& g, DFSVisitor vis, ColorMap color) { typedef typename boost::graph_traits< VertexListGraph >::vertex_iterator vi; std::pair< vi, vi > verts = vertices(g); if (verts.first == verts.second) return; depth_first_search(g, vis, color, detail::get_default_starting_vertex(g)); } template < class Visitors = null_visitor > class dfs_visitor { public: dfs_visitor() {} dfs_visitor(Visitors vis) : m_vis(vis) {} template < class Vertex, class Graph > void initialize_vertex(Vertex u, const Graph& g) { invoke_visitors(m_vis, u, g, ::boost::on_initialize_vertex()); } template < class Vertex, class Graph > void start_vertex(Vertex u, const Graph& g) { invoke_visitors(m_vis, u, g, ::boost::on_start_vertex()); } template < class Vertex, class Graph > void discover_vertex(Vertex u, const Graph& g) { invoke_visitors(m_vis, u, g, ::boost::on_discover_vertex()); } template < class Edge, class Graph > void examine_edge(Edge u, const Graph& g) { invoke_visitors(m_vis, u, g, ::boost::on_examine_edge()); } template < class Edge, class Graph > void tree_edge(Edge u, const Graph& g) { invoke_visitors(m_vis, u, g, ::boost::on_tree_edge()); } template < class Edge, class Graph > void back_edge(Edge u, const Graph& g) { invoke_visitors(m_vis, u, g, ::boost::on_back_edge()); } template < class Edge, class Graph > 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()); } BOOST_GRAPH_EVENT_STUB(on_initialize_vertex, dfs) BOOST_GRAPH_EVENT_STUB(on_start_vertex, dfs) BOOST_GRAPH_EVENT_STUB(on_discover_vertex, dfs) BOOST_GRAPH_EVENT_STUB(on_examine_edge, dfs) 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: Visitors m_vis; }; template < class Visitors > dfs_visitor< Visitors > make_dfs_visitor(Visitors vis) { return dfs_visitor< Visitors >(vis); } typedef dfs_visitor<> default_dfs_visitor; // Boost.Parameter named parameter variant namespace graph { namespace detail { template < typename Graph > struct depth_first_search_impl { typedef void result_type; template < typename ArgPack > void operator()(const Graph& g, const ArgPack& arg_pack) const { using namespace boost::graph::keywords; boost::depth_first_search(g, arg_pack[_visitor | make_dfs_visitor(null_visitor())], boost::detail::make_color_map_from_arg_pack(g, arg_pack), arg_pack[_root_vertex || boost::detail::get_default_starting_vertex_t< Graph >(g)]); } }; } BOOST_GRAPH_MAKE_FORWARDING_FUNCTION(depth_first_search, 1, 4) } BOOST_GRAPH_MAKE_OLD_STYLE_PARAMETER_FUNCTION(depth_first_search, 1) template < class IncidenceGraph, class DFSVisitor, class ColorMap > void depth_first_visit(const IncidenceGraph& g, typename graph_traits< IncidenceGraph >::vertex_descriptor u, DFSVisitor vis, ColorMap color) { vis.start_vertex(u, g); detail::depth_first_visit_impl(g, u, vis, color, detail::nontruth2()); } template < class IncidenceGraph, class DFSVisitor, class ColorMap, class TerminatorFunc > void depth_first_visit(const IncidenceGraph& g, typename graph_traits< IncidenceGraph >::vertex_descriptor u, DFSVisitor vis, ColorMap color, TerminatorFunc func = TerminatorFunc()) { vis.start_vertex(u, g); detail::depth_first_visit_impl(g, u, vis, color, func); } } // namespace boost #include BOOST_GRAPH_MPI_INCLUDE(<boost/graph/distributed/depth_first_search.hpp>) #endif
Save
cmd:
run