/
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/biconnected_components.hpp
(16701B)
// Copyright (c) Jeremy Siek 2001 // Copyright (c) Douglas Gregor 2004 // // 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) // NOTE: this final is generated by libs/graph/doc/biconnected_components.w #ifndef BOOST_GRAPH_BICONNECTED_COMPONENTS_HPP #define BOOST_GRAPH_BICONNECTED_COMPONENTS_HPP #include <stack> #include <vector> #include <algorithm> // for std::min and std::max #include <boost/config.hpp> #include <boost/limits.hpp> #include <boost/graph/graph_traits.hpp> #include <boost/graph/graph_concepts.hpp> #include <boost/property_map/property_map.hpp> #include <boost/graph/depth_first_search.hpp> #include <boost/graph/graph_utility.hpp> #include <boost/concept/assert.hpp> #include <boost/assert.hpp> namespace boost { namespace detail { template < typename ComponentMap, typename DiscoverTimeMap, typename LowPointMap, typename PredecessorMap, typename OutputIterator, typename Stack, typename ArticulationVector, typename IndexMap, typename DFSVisitor > struct biconnected_components_visitor : public dfs_visitor<> { biconnected_components_visitor(ComponentMap comp, std::size_t& c, std::size_t& children_of_root, DiscoverTimeMap dtm, std::size_t& dfs_time, LowPointMap lowpt, PredecessorMap pred, OutputIterator out, Stack& S, ArticulationVector& is_articulation_point, IndexMap index_map, DFSVisitor vis) : comp(comp) , c(c) , children_of_root(children_of_root) , dtm(dtm) , dfs_time(dfs_time) , lowpt(lowpt) , pred(pred) , out(out) , S(S) , is_articulation_point(is_articulation_point) , index_map(index_map) , vis(vis) { } template < typename Vertex, typename Graph > void initialize_vertex(const Vertex& u, Graph& g) { put(pred, u, u); vis.initialize_vertex(u, g); } template < typename Vertex, typename Graph > void start_vertex(const Vertex& u, Graph& g) { children_of_root = 0; vis.start_vertex(u, g); } template < typename Vertex, typename Graph > void discover_vertex(const Vertex& u, Graph& g) { put(dtm, u, ++dfs_time); put(lowpt, u, get(dtm, u)); vis.discover_vertex(u, g); } template < typename Edge, typename Graph > void examine_edge(const Edge& e, Graph& g) { vis.examine_edge(e, g); } template < typename Edge, typename Graph > void tree_edge(const Edge& e, Graph& g) { typename boost::graph_traits< Graph >::vertex_descriptor src = source(e, g); typename boost::graph_traits< Graph >::vertex_descriptor tgt = target(e, g); S.push(e); put(pred, tgt, src); if (get(pred, src) == src) { ++children_of_root; } vis.tree_edge(e, g); } template < typename Edge, typename Graph > void back_edge(const Edge& e, Graph& g) { BOOST_USING_STD_MIN(); typename boost::graph_traits< Graph >::vertex_descriptor src = source(e, g); typename boost::graph_traits< Graph >::vertex_descriptor tgt = target(e, g); if (tgt != get(pred, src)) { S.push(e); put(lowpt, src, min BOOST_PREVENT_MACRO_SUBSTITUTION( get(lowpt, src), get(dtm, tgt))); } vis.back_edge(e, g); } template < typename Edge, typename Graph > void forward_or_cross_edge(const Edge& e, Graph& g) { vis.forward_or_cross_edge(e, g); } template < typename Vertex, typename Graph > void finish_vertex(const Vertex& u, Graph& g) { BOOST_USING_STD_MIN(); Vertex parent = get(pred, u); if (parent == u) { // Root of tree is special is_articulation_point[get(index_map, u)] = (children_of_root > 1); } else { put(lowpt, parent, min BOOST_PREVENT_MACRO_SUBSTITUTION( get(lowpt, parent), get(lowpt, u))); if (get(lowpt, u) >= get(dtm, parent)) { is_articulation_point[get(index_map, parent)] = true; while (get(dtm, source(S.top(), g)) >= get(dtm, u)) { put(comp, S.top(), c); S.pop(); } BOOST_ASSERT(source(S.top(), g) == parent); BOOST_ASSERT(target(S.top(), g) == u); put(comp, S.top(), c); S.pop(); ++c; } } if (is_articulation_point[get(index_map, u)]) { *out++ = u; } vis.finish_vertex(u, g); } ComponentMap comp; std::size_t& c; std::size_t& children_of_root; DiscoverTimeMap dtm; std::size_t& dfs_time; LowPointMap lowpt; PredecessorMap pred; OutputIterator out; Stack& S; ArticulationVector& is_articulation_point; IndexMap index_map; DFSVisitor vis; }; template < typename Graph, typename ComponentMap, typename OutputIterator, typename VertexIndexMap, typename DiscoverTimeMap, typename LowPointMap, typename PredecessorMap, typename DFSVisitor > std::pair< std::size_t, OutputIterator > biconnected_components_impl( const Graph& g, ComponentMap comp, OutputIterator out, VertexIndexMap index_map, DiscoverTimeMap dtm, LowPointMap lowpt, PredecessorMap pred, DFSVisitor dfs_vis) { typedef typename graph_traits< Graph >::vertex_descriptor vertex_t; typedef typename graph_traits< Graph >::edge_descriptor edge_t; BOOST_CONCEPT_ASSERT((VertexListGraphConcept< Graph >)); BOOST_CONCEPT_ASSERT((IncidenceGraphConcept< Graph >)); BOOST_CONCEPT_ASSERT( (WritablePropertyMapConcept< ComponentMap, edge_t >)); BOOST_CONCEPT_ASSERT( (ReadWritePropertyMapConcept< DiscoverTimeMap, vertex_t >)); BOOST_CONCEPT_ASSERT( (ReadWritePropertyMapConcept< LowPointMap, vertex_t >)); BOOST_CONCEPT_ASSERT( (ReadWritePropertyMapConcept< PredecessorMap, vertex_t >)); std::size_t num_components = 0; std::size_t children_of_root; std::size_t dfs_time = 0; std::stack< edge_t > S; std::vector< char > is_articulation_point(num_vertices(g)); biconnected_components_visitor< ComponentMap, DiscoverTimeMap, LowPointMap, PredecessorMap, OutputIterator, std::stack< edge_t >, std::vector< char >, VertexIndexMap, DFSVisitor > vis(comp, num_components, children_of_root, dtm, dfs_time, lowpt, pred, out, S, is_articulation_point, index_map, dfs_vis); depth_first_search(g, visitor(vis).vertex_index_map(index_map)); return std::pair< std::size_t, OutputIterator >( num_components, vis.out); } template < typename PredecessorMap > struct bicomp_dispatch3 { template < typename Graph, typename ComponentMap, typename OutputIterator, typename VertexIndexMap, typename DiscoverTimeMap, typename LowPointMap, class P, class T, class R > static std::pair< std::size_t, OutputIterator > apply(const Graph& g, ComponentMap comp, OutputIterator out, VertexIndexMap index_map, DiscoverTimeMap dtm, LowPointMap lowpt, const bgl_named_params< P, T, R >& params, PredecessorMap pred) { return biconnected_components_impl(g, comp, out, index_map, dtm, lowpt, pred, choose_param(get_param(params, graph_visitor), make_dfs_visitor(null_visitor()))); } }; template <> struct bicomp_dispatch3< param_not_found > { template < typename Graph, typename ComponentMap, typename OutputIterator, typename VertexIndexMap, typename DiscoverTimeMap, typename LowPointMap, class P, class T, class R > static std::pair< std::size_t, OutputIterator > apply(const Graph& g, ComponentMap comp, OutputIterator out, VertexIndexMap index_map, DiscoverTimeMap dtm, LowPointMap lowpt, const bgl_named_params< P, T, R >& params, param_not_found) { typedef typename graph_traits< Graph >::vertex_descriptor vertex_t; std::vector< vertex_t > pred(num_vertices(g)); vertex_t vert = graph_traits< Graph >::null_vertex(); return biconnected_components_impl(g, comp, out, index_map, dtm, lowpt, make_iterator_property_map(pred.begin(), index_map, vert), choose_param(get_param(params, graph_visitor), make_dfs_visitor(null_visitor()))); } }; template < typename LowPointMap > struct bicomp_dispatch2 { template < typename Graph, typename ComponentMap, typename OutputIterator, typename VertexIndexMap, typename DiscoverTimeMap, typename P, typename T, typename R > static std::pair< std::size_t, OutputIterator > apply(const Graph& g, ComponentMap comp, OutputIterator out, VertexIndexMap index_map, DiscoverTimeMap dtm, const bgl_named_params< P, T, R >& params, LowPointMap lowpt) { typedef typename get_param_type< vertex_predecessor_t, bgl_named_params< P, T, R > >::type dispatch_type; return bicomp_dispatch3< dispatch_type >::apply(g, comp, out, index_map, dtm, lowpt, params, get_param(params, vertex_predecessor)); } }; template <> struct bicomp_dispatch2< param_not_found > { template < typename Graph, typename ComponentMap, typename OutputIterator, typename VertexIndexMap, typename DiscoverTimeMap, typename P, typename T, typename R > static std::pair< std::size_t, OutputIterator > apply(const Graph& g, ComponentMap comp, OutputIterator out, VertexIndexMap index_map, DiscoverTimeMap dtm, const bgl_named_params< P, T, R >& params, param_not_found) { typedef typename graph_traits< Graph >::vertices_size_type vertices_size_type; std::vector< vertices_size_type > lowpt(num_vertices(g)); vertices_size_type vst(0); typedef typename get_param_type< vertex_predecessor_t, bgl_named_params< P, T, R > >::type dispatch_type; return bicomp_dispatch3< dispatch_type >::apply(g, comp, out, index_map, dtm, make_iterator_property_map(lowpt.begin(), index_map, vst), params, get_param(params, vertex_predecessor)); } }; template < typename DiscoverTimeMap > struct bicomp_dispatch1 { template < typename Graph, typename ComponentMap, typename OutputIterator, typename VertexIndexMap, class P, class T, class R > static std::pair< std::size_t, OutputIterator > apply(const Graph& g, ComponentMap comp, OutputIterator out, VertexIndexMap index_map, const bgl_named_params< P, T, R >& params, DiscoverTimeMap dtm) { typedef typename get_param_type< vertex_lowpoint_t, bgl_named_params< P, T, R > >::type dispatch_type; return bicomp_dispatch2< dispatch_type >::apply(g, comp, out, index_map, dtm, params, get_param(params, vertex_lowpoint)); } }; template <> struct bicomp_dispatch1< param_not_found > { template < typename Graph, typename ComponentMap, typename OutputIterator, typename VertexIndexMap, class P, class T, class R > static std::pair< std::size_t, OutputIterator > apply(const Graph& g, ComponentMap comp, OutputIterator out, VertexIndexMap index_map, const bgl_named_params< P, T, R >& params, param_not_found) { typedef typename graph_traits< Graph >::vertices_size_type vertices_size_type; std::vector< vertices_size_type > discover_time(num_vertices(g)); vertices_size_type vst(0); typedef typename get_param_type< vertex_lowpoint_t, bgl_named_params< P, T, R > >::type dispatch_type; return bicomp_dispatch2< dispatch_type >::apply(g, comp, out, index_map, make_iterator_property_map( discover_time.begin(), index_map, vst), params, get_param(params, vertex_lowpoint)); } }; } template < typename Graph, typename ComponentMap, typename OutputIterator, typename DiscoverTimeMap, typename LowPointMap > std::pair< std::size_t, OutputIterator > biconnected_components(const Graph& g, ComponentMap comp, OutputIterator out, DiscoverTimeMap dtm, LowPointMap lowpt) { typedef param_not_found dispatch_type; return detail::bicomp_dispatch3< dispatch_type >::apply(g, comp, out, get(vertex_index, g), dtm, lowpt, bgl_named_params< int, buffer_param_t >(0), param_not_found()); } template < typename Graph, typename ComponentMap, typename OutputIterator, typename P, typename T, typename R > std::pair< std::size_t, OutputIterator > biconnected_components(const Graph& g, ComponentMap comp, OutputIterator out, const bgl_named_params< P, T, R >& params) { typedef typename get_param_type< vertex_discover_time_t, bgl_named_params< P, T, R > >::type dispatch_type; return detail::bicomp_dispatch1< dispatch_type >::apply(g, comp, out, choose_const_pmap(get_param(params, vertex_index), g, vertex_index), params, get_param(params, vertex_discover_time)); } template < typename Graph, typename ComponentMap, typename OutputIterator > std::pair< std::size_t, OutputIterator > biconnected_components( const Graph& g, ComponentMap comp, OutputIterator out) { return biconnected_components( g, comp, out, bgl_named_params< int, buffer_param_t >(0)); } namespace graph_detail { struct dummy_output_iterator { typedef std::output_iterator_tag iterator_category; typedef void value_type; typedef void pointer; typedef void difference_type; struct reference { template < typename T > reference& operator=(const T&) { return *this; } }; reference operator*() const { return reference(); } dummy_output_iterator& operator++() { return *this; } dummy_output_iterator operator++(int) { return *this; } }; } // end namespace graph_detail template < typename Graph, typename ComponentMap, typename P, typename T, typename R > std::size_t biconnected_components(const Graph& g, ComponentMap comp, const bgl_named_params< P, T, R >& params) { return biconnected_components( g, comp, graph_detail::dummy_output_iterator(), params) .first; } template < typename Graph, typename ComponentMap > std::size_t biconnected_components(const Graph& g, ComponentMap comp) { return biconnected_components( g, comp, graph_detail::dummy_output_iterator()) .first; } template < typename Graph, typename OutputIterator, typename P, typename T, typename R > OutputIterator articulation_points(const Graph& g, OutputIterator out, const bgl_named_params< P, T, R >& params) { return biconnected_components(g, dummy_property_map(), out, params).second; } template < typename Graph, typename OutputIterator > OutputIterator articulation_points(const Graph& g, OutputIterator out) { return biconnected_components(g, dummy_property_map(), out, bgl_named_params< int, buffer_param_t >(0)) .second; } } // namespace boost #endif /* BOOST_GRAPH_BICONNECTED_COMPONENTS_HPP */
Save
cmd:
run