I am trying to get Predecessor and Successor of a vertex from a directed graph implemented with adjacency list.

here s a brief description of my class :

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

void predecessor(T u);
void successor(T u, T v);


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

Here is what I tried :

template <class T>
const std::set<T> Digraph<T>::predecessor(T u) const
{
    std::set<T> p;

    int index = 0;
    for (auto it = graphe.begin(); it != graphe.end();   it, index  )
    {
        for(T el : *it) //I got the error here
        {
            if (el == u)
                p.insert(index);
        }
    }
    return p;
}

template <class T>
const std::set<T> Digraph<T>::successor(T u) const
{
    return graphe.at(u);
}

I get the error in the inner loop. Does anyone have an idea for an implementation? or can help me by telling me what i forgot.

CodePudding user response：

Searching through the entire graph to find predecessors is a possibly costly operation. You would make your life much easier if you just stored all back-edges in a separate, identical structure:

std::map<T, std::set<T>> inverted;

Then, your member functions would be quite trivial:

template <typename T>
std::set<T> const& Digraph<T>::successor(T const& v) const {
    return graph.at(v);
}
template <typename T>
std::set<T> const& Digraph<T>::predecessor(T const& u) const {
    return inverted.at(u);
}

Note that the return type is an std::set<T> const& instead of an std::set<T>. This means that you don't copy the entire set.

For insertion the code becomes:

graph[v].insert(u);
inverted[u].insert(v); // new line

However, if you really want to keep your expensive lookup, maybe because it happens really seldom you can do it like this:

template <class T>
std::set<T> Digraph<T>::predecessor(T const& u) const {
    std::set<T> p;

    for (auto const& [v, set]: graph)
        for(auto const& w : set)
            if (u == w) {
                p.insert(v);
                break;
            }

    return p;
}

Please note however, that this will create copies of the values stored in your graph. If you only have integers, that's no issue. But if you have class-objects in there, copying might not be what you want.