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@raspberrypi5:~ $ g++ ug_demo.cpp pi@raspberrypi5:~ $ ./a.out 0 <--> 1 <--> 2 2 <--> 1 foobar foobar2 0 <--> 1 <--> 2 <--> 1 pi@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.