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

From: hermann_at_[hidden]
Date: 2024-08-07 15:42:38

On 2024-08-05 22:37, Hermann Stamm-Wilbrandt via Boost wrote:
> 
> Fore remove_edge() there is no O(1) option listed.
> 
> On the other hand in Boost graph code I see this O(1) remove_edge()
> in boost/graph/detail/adjacency_list.hpp:
> 
> template < class Config > struct directed_edges_helper
> {
> ...
>     // O(1)
>     inline void remove_edge(typename Config::out_edge_iterator iter)
>     {  std::cerr << "foobar" << std::endl;
>         typedef typename Config::graph_type graph_type;
>         graph_type& g = static_cast< graph_type& >(*this);
>         typename Config::edge_descriptor e = *iter;
>         typename Config::OutEdgeList& el = g.out_edge_list(source(e, 
> g));
>         el.erase(iter.base());
>     }
> };
> 
> So my questions is for which graph and how I can make use of that O(1)
> function to remove an edge. It seems to be for directed graph only.
> While I need it for undirected graph, being able to use that O(1)
> function for directed graph would be a first step.
> 
I went a step further, transferred the directed O(1) concept to 
undirected graph.

Given an out_edge_iterator it can be removed in O(1), and that is true 
for
undirected graph as well. This small demo code piece:

...
     out_edge_iterator it = out_edges(v1, g).first;
     g.remove_edge(it);
...

between two print_graph() statements shows that the concept works.
The (only) edge gets removed from out edge list of v1 only:

pi_at_raspberrypi5:~ $ g++ ug_demo.cpp
pi_at_raspberrypi5:~ $ ./a.out
0 <-->
1 <--> 2
2 <--> 1
foobar
foobar2

0 <-->
1 <-->
2 <--> 1
pi_at_raspberrypi5:~ $

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);
      }
  };

An undirected edge needs to know its out_edge_iterators for
both of its vertices. I plan to use an edge map of std::pair of
out_edge_iterators and initialize for each edge correctly.
Then I will be able to do a sequence of edge removals taking
O(1) time for each edge removal ...

Regards,

Hermann.