How to delete edge and vertices from directed graph-CodePudding

Given u and v I want to delete the u vertex and u,v edge from an adjacency list graph. The approach I followed is to delete the vertex from root and from the other sets of other roots.

exemple :

I want to delete the vertex u

u -> a b c d
x -> u   // u should be deleted

here s a brief description of my class :

template <class T>
class Digraph
{
public:
    Digraph();
    ~Digraph();

void delete_vertex(T u);
void delete_edge(T u, T v);


private:
    std::map<T, std::set<T>> graph;
}

What I tried :

template <class T>
void Digraph<T>::delete_vertex(T u)
{
    graphe.erase(u);

    for (auto const &pair : graphe)
    {
        for (auto const &elem : pair.second)
        {
            if(elem == u){
                pair->second.erase(u);
            }
        }
    }
}

template <class T>
void Digraph<T>::delete_edge(T u, T v)
{
    std::set<T> s = graphe[u];
    s.erase(v);
}

I wonder if what I'm doing in the delete_vertex function is right, because it doesn't work, maybe I forgot something, can someone help me with that?

CodePudding user response：

Both functions are bugged. The problem with delete_edge is that you are copying the set of edges, and you then erase from the copy not the original. This is the common beginner mistake of treating C objects as if they are references when they aren't. Here's version that really uses a reference

template <class T>
void Digraph<T>::delete_edge(T u, T v)
{
    std::set<T>& s = graphe[u]; // s is a reference
    s.erase(v);
}

but just eliminating the variable is even simpler (IMHO)

template <class T>
void Digraph<T>::delete_edge(T u, T v)
{
    graphe[u].erase(v);
}

The problem with delete_vertex is as Some Programmer Dude says, you cannot erase from a container if you are iterating through it. Here's an iterator based solution

template <class T>
void Digraph<T>::delete_vertex(T u)
{
    graphe.erase(u);
    for (auto const &pair : graphe)
    {
        auto i = pair.second.begin();
        while (i != pair.second.end())
        {
            if (*i == u)
                i = pair.second.erase(i);
            else
                  i;
        }
    }
}

It's even illegal to use on an iterator to an erased element, which is why erase returns an iterator to the next element.

Untested code, so apologies for any mistakes.