Using remove_edge () in accelerator library and push_back to vector container

I am just starting to learn the extended graph library and have a basic problem using the remove_edge function in the accelerator library.

I would like to remove an edge in a multigraph. For a graph with two edges, connect vertices 0 and 1, I would like to remove one of them, but keep the other.

According to the user manual, remove_edge (u, v, g) removes all occurrences (u, v). So I have to use remove_edge (e, g). Here e is a valid edge descriptor.

For one graph g, I can perform remove_edge (u, v, g) and remove_edge (e, g) operations without any problem.

However, when I want to generalize the implementation to fit my need by putting the plots in a vector container, I got a segmentation fault for remove_edge (e, graph_list [0]). (The compiler doesn't show any warning messages.) On the other hand, remove_edge (u, v, g) works fine. I'm not sure what the difference between these two syntactic reasons is causing my problem.

I really want remove_edge (e, g) and the vector container to work at the same time. So any suggestion that can help me get around this difficulty is appreciated.

Thank you so much!

Below is my test code.

#include <iostream>
#include <utility>
#include <algorithm>
#include <vector>

#include "boost/graph/graph_traits.hpp"
#include "boost/graph/adjacency_list.
hpp"

using namespace boost;

typedef adjacency_list<vecS, vecS, undirectedS> UndirectedGraph;
typedef boost::graph_traits<UndirectedGraph>::edge_iterator edge_iterator;


int graph_show(UndirectedGraph &g);


int main(int argc, char *argv[])
{
    UndirectedGraph g;

    typedef boost::graph_traits<UndirectedGraph>::edge_descriptor edge_descriptor;
    edge_descriptor ed;

    std::vector<edge_descriptor> edge_list;
    std::vector<std::vector<edge_descriptor> > graph_edge_list;
    std::vector<UndirectedGraph> graph_list;

    int nb=0;
    int Nl=4;

    bool inserted;
    while(nb<Nl)
    {
        tie(ed,inserted)=add_edge(nb,nb+1,g);
        edge_list.push_back(ed);
        tie(ed,inserted)=add_edge(nb,nb+1,g);
        edge_list.push_back(ed);
        graph_edge_list.push_back(edge_list);
        nb=nb+1;
        graph_list.push_back(g);
    }

    std::cout<<"size of the graph vector is: "<<graph_list.size()<<std::endl;

    remove_edge(graph_edge_list[0][0],graph_list[0]);//This is where the problem shows.
                                                                           //I got Segmentation fault (core dumped)
    //remove_edge(0,1,graph_list[0]);
    /*Remove edges by assigning vertices works fine, but that is not what I need.*/

    for (int ig = 0; ig < Nl; ++ig) {
        std::cout<<"graph#"<<ig<<std::endl;
        std::cout<<"Size of edge_list is: "<<graph_edge_list[ig].size()<<std::endl;
        graph_show(graph_list[ig]);
    }
    std::cout<<"Success"<<std::endl;
    return 0;
}

int graph_show(UndirectedGraph &g)
{
    std::cout<<"Number of edges is : "<<boost::num_edges(g)<<std::endl;
    std::cout<<"Number of vertices is : "<<boost::num_vertices(g)<<std::endl;
    std::pair<edge_iterator,edge_iterator> ei=edges(g);

    for (edge_iterator edge_iter = ei.first; edge_iter!=ei.second; ++edge_iter) {
            std::cout<<"("<< boost::source(*edge_iter,g)<<","<<boost::target(*edge_iter,g)<<")"<<std::endl;
    }

    typedef boost::graph_traits<UndirectedGraph>::vertex_iterator iter_v;

    std::cout<<"vertices(g)={ ";
    for (std::pair<iter_v,iter_v> p = vertices(g); p.first != p.second; ++p.first) {
            std::cout<< *p.first;
                std::cout<<" ";
    }
    std::cout<<"}"<<std::endl;

    return 0;
}

      

+3


source to share


1 answer


This is not an answer, but I tried the code and it seems that the problem occurs:

g.m_edges.erase(edge_iter_to_erase);

      

in the adjacency_list.hpp file on line 771.

It looks like a bug. You can check the boost mailing list.

Context:

 template <>
  struct remove_undirected_edge_dispatch<no_property> {
    // O(E/V)
    template <class edge_descriptor, class Config>
    static void
    apply(edge_descriptor e,
          undirected_graph_helper<Config>& g_,
          no_property&)
    {
      typedef typename Config::global_edgelist_selector EdgeListS;
      BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));

      typedef typename Config::graph_type graph_type;
      graph_type& g = static_cast<graph_type&>(g_);
      no_property* p = (no_property*)e.get_property();
      typename Config::OutEdgeList& out_el = g.out_edge_list(source(e, g));
      typename Config::OutEdgeList::iterator out_i = out_el.begin();
      typename Config::EdgeIter edge_iter_to_erase;
      for (; out_i != out_el.end(); ++out_i)
        if (&(*out_i).get_property() == p) {
          edge_iter_to_erase = (*out_i).get_iter();
          out_el.erase(out_i);
          break;
        }
      typename Config::OutEdgeList& in_el = g.out_edge_list(target(e, g));
      typename Config::OutEdgeList::iterator in_i = in_el.begin();
      for (; in_i != in_el.end(); ++in_i)
        if (&(*in_i).get_property() == p) {
          in_el.erase(in_i);
          break;
        }
      g.m_edges.erase(edge_iter_to_erase);
    }
  };

      

When I go to the debugger it shows it edge_iter_to_erase = (*out_i).get_iter();

never gets executed. This causes undefined behavior when the vector erase method is called , since the position is not valid (I assume).



If you only use g

instead graph_list[0]

, it works great.

Look here for a similar issue on the mailing list. They use a different adjacency_list.

If I change the graph:

typedef adjacency_list<vecS, vecS, undirectedS,no_property,no_property,no_property,setS> UndirectedGraph;

      

as in this post. I am getting a read access violation, not a seg fault.

Looks like a bug, but I have no idea why this is done for the vector referenced by the graph and not for the variable g.

0


source







All Articles