1

The BGL aims to be as generic as possible. Therefore I have written for an interface for another piece of software that also aims to be as generic as possible. However, I get problems, when the vertex_descriptor is not valid.

Here is a minimal example that describes the problem:

template <class Graph>
class Wrapper {
  public:
    T& get_property_obj(const typename Graph::vertex_descriptor& v) {
        // This should be inserted:
        // if (invalid_descriptor(v)) {
        //    throw something;
        // }
        return g[v];
    }
  private:
    Graph& g;
};

The problem is that when Graph is a boost::adjacency_list with vecT as vertex storage type the Graph::operator[ does not seem to check if v is valid and can deliver invalid memory.

Can I somehow do a simple check in the wrapper class that v is valid?

Obviously the simplest solution is to iterate over all vertices and check for equality but for the given example a check of vertex_descriptor and num_vertices() would be sufficient (but of course not generic).

gerion
  • 345
  • 2
  • 9

1 Answers1

2

There is no way to tell whether a vertex descriptor is valid.

You can only check

  • the range (in case of integral vertex descriptors, like with vecS)
  • by looking it up for node-based vertex storage descriptors.

However, both scenarios risk giving you the wrong results, for the same reason that standard library containers do:

 std::vector<int> is{1,2,3};
 auto i1 = is.begin();

 is.push_back(4);

 std::cout << "Undefined Behaviour: " << *i1;

The point is, the iterator (or descriptor as the case may be) has been invalidated. There's no way to detect this happened¹, you'll always have to deal with it yourself.

The iterator/descriptor invalidation guarantees follow the guarantees of the underlying containers though. This means that for node-based containers, you can actually rely on descriptors (and references) being stable across insertion and even deletion (except for the element that was deleted, obviously).

See e.g. Iterator invalidation rules

So for integral descriptors, you'd write:

bool descriptor_looks_valid(vertex_descriptor v) const {
    return v>=0 && v < num_vertices(g);
}

As you know, it'll be horribly inefficient for most other container selectors:

bool descriptor_looks_valid(vertex_descriptor v) const {
    auto vds = vertices(g);
    return std::count(vds.first, vds.second, v);
}

Or generically (assuming c++17):

bool descriptor_looks_valid(vertex_descriptor v) const {
    if constexpr(std::is_integral_v<vertex_descriptor>) {
        return v>=0 && v < num_vertices(g);
    } else {
        auto vds = vertices(g);
        return std::count(vds.first, vds.second, v);
    }
}

Demonstration Of The Perils

This tiny demo shows the perils of mistaking "range check pass" for "valid". This program repeats this:

template <typename vertexS> void doTest() {
    using Graph = boost::adjacency_list<
        boost::vecS,
        vertexS,
        boost::directedS,
        PropertyObj>;

    Graph g;
    auto v1 = add_vertex({"one"}, g);
    auto v2 = add_vertex({"two"}, g);
    auto v3 = add_vertex({"three"}, g);
    auto v4 = add_vertex({"four"}, g);
    auto v5 = add_vertex({"five"}, g);

    Wrapper w = g;
    std::cout << w.get_property_obj(v3).something << std::endl;

    // but this is confounding, and only accidentally "works" for vecS:
    remove_vertex(v1, g);
    std::cout << w.get_property_obj(v3).something << std::endl;

    try {
        // this looks "valid" with vecS, but should throw for listS
        //
        // of course, like with v3 the descriptor was already invalidated both cases
        std::cout << w.get_property_obj(v1).something << std::endl;
    } catch(std::range_error const& re) {
        std::cout << "(range_error cautgh: " << re.what() << "\n";
    }
}

For vertexS equal to vecS, listS or setS. Typical output is Live On Coliru:

Testing with vecS:
three
four
two

Testing with listS:
three
three
(range_error caught: get_property_obj

Testing with setS:
three
three
(range_error caught: get_property_obj

Conclusion

The reason validity checks aren't implemented is because the underlying containers do not support them.

Also, although you can "approximate" a validation this will only prevent against crashes, not against unspecified behavior.

In fact, depending on what semantics are expected you might trigger Undefined Behavior just the same (e.g. if you assume that get_property_obj(v3) yields the same value each time, you will have broken code with vecS).

Can I somehow do a simple check in the wrapper class that v is valid?

In short, no.Descriptor validity is a function of the usage patterns and the caller will have to account for it.

Full Listing

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <iostream>

struct PropertyObj {
    std::string something;
};

template <class Graph, class T = PropertyObj>
class Wrapper {
  public:
    using vertex_descriptor = typename Graph::vertex_descriptor;
    T& get_property_obj(vertex_descriptor v) {
        if (!descriptor_looks_valid(v)) 
            throw std::range_error("get_property_obj");
        return g[v];
    }
    Wrapper(Graph& g) : g(g){}
  private:
    bool descriptor_looks_valid(vertex_descriptor v) const {
        if constexpr(std::is_integral_v<vertex_descriptor>) {
            return v>=0 && v < num_vertices(g);
        } else {
            auto vds = vertices(g);
            return std::count(vds.first, vds.second, v);
        }
    }

    Graph& g;
};

template <typename vertexS> void doTest() {
    using Graph = boost::adjacency_list<
        boost::vecS,
        vertexS,
        boost::directedS,
        PropertyObj>;

    Graph g;
    auto v1 = add_vertex({"one"}, g);
    auto v2 = add_vertex({"two"}, g);
    auto v3 = add_vertex({"three"}, g);
    auto v4 = add_vertex({"four"}, g);
    auto v5 = add_vertex({"five"}, g);

    boost::ignore_unused_variable_warning(v1);
    boost::ignore_unused_variable_warning(v2);
    boost::ignore_unused_variable_warning(v3);
    boost::ignore_unused_variable_warning(v4);
    boost::ignore_unused_variable_warning(v5);

    Wrapper w = g;
    std::cout << w.get_property_obj(v3).something << std::endl;

    // but this is confounding, and only accidentally "works" for vecS:
    remove_vertex(v1, g);
    std::cout << w.get_property_obj(v3).something << std::endl;

    try {
        // this looks "valid" with vecS, but should throw for listS
        //
        // of course, like with v3 the descriptor was already invalidated both cases
        std::cout << w.get_property_obj(v1).something << std::endl;
    } catch(std::range_error const& re) {
        std::cout << "(range_error caught: " << re.what() << "\n";
    }
}

int main() {
    std::cout << "Testing with vecS:\n";
    doTest<boost::vecS>();

    std::cout << "\nTesting with listS:\n";
    doTest<boost::listS>();

    std::cout << "\nTesting with setS:\n";
    doTest<boost::setS>();
}

¹ although some library implementations have extensions that allow you to detect it some of the time - like https://learn.microsoft.com/en-us/cpp/standard-library/debug-iterator-support?view=vs-2019

sehe
  • 374,641
  • 47
  • 450
  • 633