overlay/graph/node_util.hpp

0001 // Boost.Geometry
0002
0003 // Copyright (c) 2025 Barend Gehrels, Amsterdam, the Netherlands.
0004
0005 // Use, modification and distribution is subject to the Boost Software License,
0006 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0007 // http://www.boost.org/LICENSE_1_0.txt)
0008
0009 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_NODE_UTIL_HPP
0010 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_NODE_UTIL_HPP
0011
0012 #include <boost/geometry/algorithms/detail/signed_size_type.hpp>
0013 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
0014 #include <boost/geometry/algorithms/detail/overlay/graph/is_operation_included.hpp>
0015 #include <boost/geometry/algorithms/detail/overlay/graph/is_target_operation.hpp>
0016 #include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp>
0017 #include <boost/geometry/algorithms/detail/overlay/turn_operation_id.hpp>
0018
0019 #include <set>
0020 #include <tuple>
0021
0022 namespace boost { namespace geometry
0023 {
0024
0025 #ifndef DOXYGEN_NO_DETAIL
0026 namespace detail { namespace overlay
0027 {
0028
0029 using set_of_tois = std::set<turn_operation_id>;
0030 using set_of_size_t = std::set<std::size_t>;
0031
0032 struct edge_info
0033 {
0034     signed_size_type source_node_id{0};
0035     signed_size_type target_node_id{0};
0036     segment_identifier seg_id{};
0037
0038     bool operator<(edge_info const& other) const
0039     {
0040         return std::tie(source_node_id, target_node_id, seg_id)
0041              < std::tie(other.source_node_id, other.target_node_id, other.seg_id);
0042     }
0043 };
0044
0045 template <typename Turns, typename Clusters>
0046 set_of_size_t get_turn_indices_by_cluster_id(Turns const& turns, Clusters const& clusters,
0047         signed_size_type cluster_id, bool allow_closed)
0048 {
0049     set_of_size_t result;
0050     auto it = clusters.find(cluster_id);
0051     if (it == clusters.end())
0052     {
0053         return result;
0054     }
0055     if (! allow_closed && it->second.open_count == 0)
0056     {
0057         return result;
0058     }
0059     for (std::size_t turn_index : it->second.turn_indices)
0060     {
0061         result.insert(turn_index);
0062     }
0063     return result;
0064 }
0065
0066 // Returns the node id of the turn:
0067 // - if it is clustered, the negative cluster_id
0068 // - if it is not clustered, the turn index
0069 // - there can also be extra nodes for the round trip (>= turns.size())
0070 //   but they are not returned by this function.
0071 template <typename Turns>
0072 signed_size_type get_node_id(Turns const& turns, std::size_t turn_index)
0073 {
0074     auto const& turn = turns[turn_index];
0075     return turn.is_clustered() ? -turn.cluster_id : turn_index;
0076 }
0077
0078 template <typename Turns, typename Clusters>
0079 set_of_size_t get_turn_indices_by_node_id(Turns const& turns, Clusters const& clusters,
0080         signed_size_type node_id, bool allow_closed)
0081 {
0082     if (node_id < 0)
0083     {
0084         return get_turn_indices_by_cluster_id(turns, clusters, -node_id, allow_closed);
0085     }
0086     auto const turn_index = static_cast<std::size_t>(node_id);
0087     if (turn_index >= turns.size())
0088     {
0089         // It is 'allowed' to have node_ids larger than the largest turn index (for example extra
0090         // nodes in a graph). But they are not related to turns.
0091         return {};
0092     }
0093
0094     auto const& turn = turns[turn_index];
0095     if (turn.is_clustered())
0096     {
0097         return get_turn_indices_by_cluster_id(turns, clusters, turn.cluster_id, allow_closed);
0098     }
0099     return {turn_index};
0100 }
0101
0102 template <operation_type TargetOperation, typename Turns>
0103 void get_target_operations(Turns const& turns,
0104                       typename Turns::value_type const& turn,
0105                       std::size_t turn_index,
0106                       signed_size_type source_node_id,
0107                       std::set<edge_info>& edges)
0108 {
0109     using is_included = is_operation_included<TargetOperation>;
0110     for (int j = 0; j < 2; j++)
0111     {
0112         auto const& op = turn.operations[j];
0113         if (is_included::apply(op)
0114             && is_target_operation<TargetOperation>(turns, {turn_index, j}))
0115         {
0116             auto const& target_node_id = get_node_id(turns, op.enriched.travels_to_ip_index);
0117             edges.insert({source_node_id, target_node_id, op.seg_id});
0118         }
0119     }
0120 }
0121
0122
0123 // Get the target nodes of a specific component_id only.
0124 template <operation_type TargetOperation, typename Turns, typename Clusters, typename Set>
0125 auto get_target_nodes(Turns const& turns, Clusters const& clusters,
0126                       Set const& turn_indices,
0127                       signed_size_type component_id)
0128 {
0129     using is_included = is_operation_included<TargetOperation>;
0130
0131     std::set<signed_size_type> result;
0132     for (auto turn_index : turn_indices)
0133     {
0134         auto const& turn = turns[turn_index];
0135         if (turn.discarded)
0136         {
0137             continue;
0138         }
0139
0140         for (int j = 0; j < 2; j++)
0141         {
0142             auto const& op = turn.operations[j];
0143             if (op.enriched.component_id == component_id
0144                 && is_included::apply(op)
0145                 && is_target_operation<TargetOperation>(turns, {turn_index, j}))
0146             {
0147                 result.insert(get_node_id(turns, op.enriched.travels_to_ip_index));
0148             }
0149         }
0150     }
0151     return result;
0152 }
0153
0154 }} // namespace detail::overlay
0155 #endif // DOXYGEN_NO_DETAIL
0156
0157 }} // namespace boost::geometry
0158
0159 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_NODE_UTIL_HPP