overlay/graph/graph_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_GRAPH_UTIL_HPP
0010 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GRAPH_UTIL_HPP
0011
0012 #include <boost/graph/biconnected_components.hpp>
0013 #include <boost/graph/adjacency_list.hpp>
0014
0015 namespace boost { namespace geometry
0016 {
0017
0018 #ifndef DOXYGEN_NO_DETAIL
0019 namespace detail { namespace overlay
0020 {
0021
0022 struct edge_component
0023 {
0024     using kind = edge_property_tag;
0025 };
0026
0027 // It appears that in an undirected graph, the components for two edges are sometimes different.
0028 // It happens a lot in the unit tests, for example in test case "#case_recursive_boxes_93"
0029 // Fix that. To be found out why this is.
0030 template <typename Graph, typename Components>
0031 void fix_components(Components& components, Graph const& g)
0032 {
0033     typename graph_traits<Graph>::edge_iterator ei, ei_end;
0034     for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
0035     {
0036         auto& component = components[*ei];
0037
0038         auto const source_vertex = source(*ei, g);
0039         auto const target_vertex = target(*ei, g);
0040
0041         // Get the reverse edge and its component
0042         auto const reverse_edge_pair = edge(target_vertex, source_vertex, g);
0043         if (! reverse_edge_pair.second)
0044         {
0045             continue;
0046         }
0047
0048         auto& reverse_component = components[reverse_edge_pair.first];
0049
0050         if (component != reverse_component)
0051         {
0052             component = reverse_component;
0053         }
0054     }
0055 }
0056
0057 }} // namespace detail::overlay
0058 #endif // DOXYGEN_NO_DETAIL
0059
0060 }} // namespace boost::geometry
0061
0062 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GRAPH_UTIL_HPP