EIC code displayed by LXR master/​include/​boost/​geometry/​algorithms/​detail/​overlay/​graph/​detect_biconnected_components.hpp	Source navigation Diff markup Identifier search General search
	Version: master test Revert   Change

File indexing completed on 2026-08-21 08:45:50

 // Boost.Geometry
 
 // Copyright (c) 2025 Barend Gehrels, Amsterdam, the Netherlands.
 
 // Use, modification and distribution is subject to 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 BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_DETECT_ARTICULATION_POINTS_HPP
 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_DETECT_ARTICULATION_POINTS_HPP
 
 #include <map>
 #include <set>
 
 #include <boost/geometry/algorithms/detail/signed_size_type.hpp>
 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
 #include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp>
 #include <boost/geometry/algorithms/detail/overlay/graph/node_util.hpp>
 #include <boost/geometry/algorithms/detail/overlay/graph/graph_util.hpp>
 
 #include <boost/geometry/algorithms/detail/overlay/graph/debug_graph.hpp>
 
 #include <boost/graph/biconnected_components.hpp>
 #include <boost/graph/adjacency_list.hpp>
 
 #if ! defined(BOOST_GEOMETRY_OVERLAY_NO_THROW)
 #include <boost/geometry/core/exception.hpp>
 #include <boost/throw_exception.hpp>
 #endif
 
 #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSE_GRAPH)
 #include <fstream>
 #endif
 
 namespace boost { namespace geometry
 {
 
 #ifndef DOXYGEN_NO_DETAIL
 namespace detail { namespace overlay
 {
 
 struct vertex_info
 {
     signed_size_type node_id{0};
 
     set_of_size_t target_vertex_indices;
 
     bool is_extra{false};
 
     // For extra nodes, also store the original node
     signed_size_type original_node_id{0};
 };
 
 struct state_type
 {
     // Using a flatmap changes behavior and cause errors.
     // Using an ordered map gives a just a tiny bit of performance improvement, sometimes.
     // Maps from vertex to vertex info
     std::map<std::size_t, vertex_info> vertex_map;
 
     // Reverse mapping. Every node (turn or cluster) has only ONE vertex,
     // but there might be so called "extra" vertices, not associated with a node.
     std::map<signed_size_type, std::size_t> node_to_vertex_index;
 
     // For each edge, store the segment identifier
     std::map<std::pair<std::size_t, std::size_t>, segment_identifier> edge_to_seg_id;
 
     // Keeps track of vertex index, which must, for Boost.Graph, be consecutive.
     // The turn index is not consecutive (because of discarded, and of clusters).
     std::size_t vertex_index{0};
 
     // For round-trips extra nodes are inserted.
     // Round-trips are operations returning to itself, for example in some uu cases.
     // They are numbered from turn.size() and up, such that they have a unique positive id.
     std::size_t extra_node_id{0};
 };
 
 inline void add_edge(signed_size_type source_node_id, signed_size_type target_node_id,
         segment_identifier const& seg_id, state_type& state)
 {
     // Insert the source and target node (turn or cluster)
     auto it_source = state.node_to_vertex_index.find(source_node_id);
     if (it_source == state.node_to_vertex_index.end())
     {
         it_source = state.node_to_vertex_index.insert({source_node_id, state.vertex_index++}).first;
     }
 
     auto it_target = state.node_to_vertex_index.find(target_node_id);
     if (it_target == state.node_to_vertex_index.end())
     {
         it_target = state.node_to_vertex_index.insert({target_node_id, state.vertex_index++}).first;
 
         // Get the accompanying vertex info (might be a new record)
         auto& target_vertex_info = state.vertex_map[it_target->second];
         target_vertex_info.node_id = target_node_id;
     }
 
     // Get the accompanying vertex info (might be a new record)
     // and store node and the segment id for this edge
     auto& vertex_info = state.vertex_map[it_source->second];
     vertex_info.node_id = source_node_id;
     state.edge_to_seg_id[{it_source->second, it_target->second}] = seg_id;
 
     if (target_node_id != source_node_id)
     {
         // The normal case, Not a round trip
         vertex_info.target_vertex_indices.insert(it_target->second);
         return;
     }
 
     // For a round trip, add an extra vertex.
     // It is not necessary to add them to the node_to_vertex_index,
     // because they won't be looked up further.
     std::size_t const extra_node_id = state.extra_node_id++;
     std::size_t const extra_vertex_index = state.vertex_index++;
 
     // Store the segment id in both of these edges
     auto& extra_vertex_info = state.vertex_map[extra_vertex_index];
     extra_vertex_info.node_id = extra_node_id;
     state.edge_to_seg_id[{it_source->second, extra_vertex_index}] = seg_id;
     state.edge_to_seg_id[{extra_vertex_index, it_target->second}] = seg_id;
 
     extra_vertex_info.is_extra = true;
     extra_vertex_info.original_node_id = source_node_id;
     extra_vertex_info.target_vertex_indices.insert(it_target->second);
 
     vertex_info.target_vertex_indices.insert(extra_vertex_index);
 }
 
 template <operation_type TargetOperation, typename Turns, typename Clusters>
 void fill_vertex_map(Turns const& turns, Clusters const& clusters, state_type& state)
 {
     std::set<edge_info> edges;
     for (auto const& key_value : clusters)
     {
         // The node id is negative for clusters
         auto const cluster_node_id = -key_value.first;
         auto const& cluster = key_value.second;
         for (std::size_t turn_index : cluster.turn_indices)
         {
             auto const& turn = turns[turn_index];
             get_target_operations<TargetOperation>(turns, turn, turn_index, cluster_node_id, edges);
         }
     }
     for (std::size_t i = 0; i < turns.size(); i++)
     {
         auto const& turn = turns[i];
         if (turn.discarded || turn.is_clustered())
         {
             continue;
         }
         get_target_operations<TargetOperation>(turns, turn, i, i, edges);
     }
     for (auto const& edge : edges)
     {
         add_edge(edge.source_node_id, edge.target_node_id, edge.seg_id, state);
     }
 }
 
 // Assigns biconnected components to turns
 template <typename Turns, typename Clusters, typename Graph, typename Components>
 void assign_biconnected_component_ids(Turns& turns, Clusters const& clusters, bool allow_closed,
     Graph const& graph, Components const& component, state_type const& state)
 {
     auto node_id_from_it = [](auto const& it)
     {
         return it->second.is_extra
             ? it->second.original_node_id
             : it->second.node_id;
     };
 
     typename graph_traits<Graph>::edge_iterator ei, ei_end;
     for (boost::tie(ei, ei_end) = edges(graph); ei != ei_end; ++ei)
     {
         auto it_source = state.vertex_map.find(source(*ei, graph));
         auto it_target = state.vertex_map.find(target(*ei, graph));
         if (it_source == state.vertex_map.end() || it_target == state.vertex_map.end())
         {
 #if ! defined(BOOST_GEOMETRY_OVERLAY_NO_THROW)
             BOOST_THROW_EXCEPTION(logic_exception("Edge not found in vertex map"));
 #endif
             continue;
         }
 
         auto const source_node_id = node_id_from_it(it_source);
         auto const target_node_id = node_id_from_it(it_target);
         auto const edge_seg_id = state.edge_to_seg_id.at({source(*ei, graph), target(*ei, graph)});
 
         auto const turn_indices = get_turn_indices_by_node_id(turns, clusters, source_node_id,
             allow_closed);
 
         // Assign the component to all the operations
         // going from the source node to the target node.
         for (auto const& turn_index : turn_indices)
         {
             auto& turn = turns[turn_index];
             for (std::size_t j = 0; j < 2; j++)
             {
                 auto& op = turn.operations[j];
                 if (op.enriched.travels_to_ip_index < 0)
                 {
                     continue;
                 }
 
                 auto const travels_to_node_id = get_node_id(turns, op.enriched.travels_to_ip_index);
                 if (travels_to_node_id == target_node_id && op.seg_id == edge_seg_id)
                 {
                     op.enriched.component_id = static_cast<int>(component[*ei]);
                     if (turn.both(operation_continue))
                     {
                         // For cc, always set both operations (only one of them is returned by get_node_id)
                         auto& other_op = turn.operations[1 - j];
                         other_op.enriched.component_id = op.enriched.component_id;
                     }
                 }
             }
         }
     }
 }
 
 template <operation_type TargetOperation, typename Turns, typename Clusters>
 void detect_biconnected_components(Turns& turns, Clusters const& clusters)
 {
     using graph_t = boost::adjacency_list
         <
             boost::vecS,
             boost::vecS,
             boost::undirectedS,
             boost::no_property,
             boost::property<edge_component, std::size_t>
         >;
 
     // Mapping to add turns to vertices, count them, and then build the graph.
     // (It is convenient if the vertex index is the same as the turn index.
     // Therefore the default mapping is made like that, extra vertices
     // are added later)
 
     state_type state;
     state.extra_node_id = static_cast<std::size_t>(turns.size());
 
     fill_vertex_map<TargetOperation>(turns, clusters, state);
 
     // Build the graph from the vertices
     graph_t graph(state.vertex_map.size());
     for (auto const& key_value : state.vertex_map)
     {
         auto const vertex_index = key_value.first;
         for (auto const target_vertex_index : key_value.second.target_vertex_indices)
         {
             boost::add_edge(vertex_index, target_vertex_index, graph);
         }
     }
 
     edge_component ec;
     auto component = boost::get(ec, graph);
     biconnected_components(graph, component);
     fix_components(component, graph);
 
     assign_biconnected_component_ids(turns, clusters,
         TargetOperation == operation_intersection,
         graph, component, state);
 
 #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSE_GRAPH)
     {
         std::ofstream out("/tmp/graph_viz.dot");
         write_graph_viz(out, turns, clusters, graph, component, state.vertex_map);
     }
 #endif
 }
 
 }} // namespace detail::overlay
 #endif // DOXYGEN_NO_DETAIL
 
 }} // namespace boost::geometry
 
 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_DETECT_ARTICULATION_POINTS_HPP

This page was automatically generated by the 2.3.7 LXR engine. The LXR team