Re: How to use the O(1) remove_edge(typename Config::out_edge_iterator iter)

From: hermann_at_[hidden]
Date: 2024-08-08 15:47:30

On 2024-08-07 17:42, Hermann Stamm-Wilbrandt via Boost wrote:
> 
> I had to add "void remove_edge(out_edge_iterator i)" to
> graph/undirected_graph.h ...
> 
>      void remove_edge(edge_iterator i) { remove_edge(*i); }
> 
> +    void remove_edge(out_edge_iterator i) {
> +       std::cerr << "foobar" << std::endl;
> +        boost::remove_edge(i, m_graph);
> +    }
> +
>      void remove_edge(edge_descriptor e)
> 
> 
> ... and modify (only for proof of concept) in
> graph/detail/adjacency_list.hpp:
> 
>      // O(E/V)
>      inline void remove_edge(typename Config::out_edge_iterator iter)
>      {
> -        this->remove_edge(*iter);
> +        std::cerr << "foobar2" << std::endl;
> +        typedef typename Config::graph_type graph_type;
> +        graph_type& g = static_cast< graph_type& >(*this);
> +        typename Config::edge_descriptor e = *iter;
> +        auto el = g.out_edge_list(source(e, g));
> +        el.erase(iter.base());
> +
> +//        this->remove_edge(*iter);
>      }
>  };
> 
I just comitted
https://github.com/Hermann-SW/graph/commit/fca0056ea64a1637d7602aaddbb7cad4c207daf1

implementation of O(1) "remove_edge(out_edge_iterator, 
out_edge_iterator)".

I followed the steps needed seen for "remove_edge(edge_descriptor e)"
implementation in undirected_graph.hpp, up to and including the
dispatcher stuff in detail/adjacency_list.hpp.

Short demo and description can be found here:
https://github.com/Hermann-SW/graph?tab=readme-ov-file#fork-mission-statement

Later I added assertions guaranteeing being correctly called:

             typename Config::edge_descriptor e = *iter1;
             typename Config::edge_descriptor f = *iter2;
             BOOST_ASSERT(source(e, g) == target(f, g));
             BOOST_ASSERT(source(f, g) == target(e, g));

Next steps:
- create edge_map with std::pair<edout_edge_iterator, out_edge_iterator>
- use that to build 5-compaction of planar graph utilizing O(1) edge 
removal
- implement "planar_vertex_six_coloring(const VertexListGraph& g, 
ColorMap color)"
- add testcases and doc

Regards,

Hermann.