What should be the return value of a custom function addEdge in a new class based on BGL?

Question

I try to implement a graph class based on https://stackoverflow.com/a/950173/7558038. When adding an edge I return the edge descriptor of the added edge, but if the edge already exists, it shouldn't be added. What shall I return then? Unfortunately, null_edge() does not exist (unlike null_vertex()). It could be an std::pair<e_it_t,bool> with an appropriate edge iterator type e_it_t, but how can I get an iterator to the new edge?

Answer 1

Don't use that class that is almost 10 years old. It is obsolete.

Bundled properties have come to BGL as long as I know, which is... probably since at least 2010. Nothing there is fundamentally easier than straight boost.

Another weird property is that somehow only complementary edges can be inserted in that graph. This might be what you want, but it doesn't warrant having the complete class, IMO.

In fact, having the custom type removes ADL, which makes things more tedious unless you go and add each other operation (like, you know, out_edges or in_edges, which presumably is what you wanted a bidirectional graph for in the first place; maybe you actually wish to have iterable ranges instead of pair<iterator, iterator> which requires you to write old-fashioned for loops).

Now that I've warmed up a bit, lets demonstrate:

Using The Obsolete Wrapper class

The linked wrapper affords usage like this:

struct VertexProperties { int i; };
struct EdgeProperties { double weight; }; 

int main() {
    using MyGraph = Graph<VertexProperties, EdgeProperties>;

    MyGraph g;

    VertexProperties vp;
    vp.i = 42;

    MyGraph::Vertex v1 = g.AddVertex(vp);

    g.properties(v1).i = 23;


    MyGraph::Vertex v2 = g.AddVertex(vp);
    g.properties(v2).i = 67;

    g.AddEdge(v1, v2, EdgeProperties{1.0}, EdgeProperties{0.0});

    for (auto vr = g.getVertices(); vr.first!=vr.second; ++vr.first) {
        auto& vp = g.properties(*vr.first);
        std::cout << "Vertex " << vp.i << "\n";

        for (auto er = g.getAdjacentVertices(*vr.first); er.first!=er.second; ++er.first) {
            auto  s  = *vr.first;
            auto  t = *er.first;
            // erm how to get edge properties now?

            std::cout << "Edge " << g.properties(s).i << " -> " << g.properties(t).i << " (weight?!?)\n";
        }
    }
}

Which prints:

Vertex 23
Edge 23 -> 67 (weight?!?)
Vertex 67
Edge 67 -> 23 (weight?!?)

Note I didn't exactly bother to solve the problem of getting the edge-weight (we don't readily get edge descriptors from the interface at all). The for loops throw us back in time at least 6 years. And that's not nearly the worst problem. Presumably, you need your graph for something. Let's assume you want minimum cut, or a shortest path. This means you want to invoke an algorithm that requires the edge weight. This would look like so:

// let's find a shortest path:
// build the vertex index map
boost::property_map<MyGraph::GraphContainer, vertex_properties_t>::const_type vpmap =
    boost::get(vertex_properties, g.getGraph());
// oops we need the id from it. No problem, it takes only rocket science:
struct GetId {
    int operator()(VertexProperties const& vp) const {
        return vp.i;
    }
};
GetId get_id;
boost::transform_value_property_map<GetId,
    boost::property_map<MyGraph::GraphContainer, vertex_properties_t>::const_type,
    int> id_map 
        = boost::make_transform_value_property_map<int>(get_id, vpmap);

// build the weight map
boost::property_map<MyGraph::GraphContainer, edge_properties_t>::const_type epmap =
    boost::get(edge_properties, g.getGraph());
// oops we need the weight from it. No problem, it takes only rocket science:
struct GetWeight {
    double operator()(EdgeProperties const& ep) const {
        return ep.weight;
    }
};
GetWeight get_weight;
boost::transform_value_property_map<GetWeight, 
    boost::property_map<MyGraph::GraphContainer, edge_properties_t>::const_type,
    double> weight_map 
        = boost::make_transform_value_property_map<double>(get_weight, epmap);

// and now we "simply" use Dijkstra:
MyGraph::vertex_range_t vertices = g.getVertices();
//size_t n_vertices = g.getVertexCount();
MyGraph::Vertex source = *vertices.first;

std::map<MyGraph::Vertex, MyGraph::Vertex> predecessors;
std::map<MyGraph::Vertex, double> distance;

boost::dijkstra_shortest_paths(g.getGraph(), source, 
        boost::predecessor_map(boost::make_assoc_property_map(predecessors))
        .distance_map(boost::make_assoc_property_map(distance))
        .weight_map(weight_map)
        .vertex_index_map(id_map));

This is not my idea of usability. Just to show it all compiles and runs:

Live On Coliru

Replace The Wrapper In 2 Lines Of C++11

Let's replace the whole Graph class template in modern BGL style:

template <typename VertexProperties, typename EdgeProperties>
using Graph = adjacency_list<setS, listS, bidirectionalS, VertexProperties, EdgeProperties>;

Really. That is a solid replacement, I'll demonstrate it right away.

In fact, let's not do using namespace boost; because it pollutes our namespace with all manner of names we might find really useful (like, you know source or num_vertices) and invites ambiguous symbols:

template <typename VertexProperties, typename EdgeProperties>
using Graph = boost::adjacency_list<boost::setS, boost::listS, boost::bidirectionalS, VertexProperties, EdgeProperties>;

The Same Use-Cases - creation and dijkstra

They are still as simple, or in fact simpler. The full code goes down from 249 lines of code to just 57:

Live On Coliru

#include <boost/graph/adjacency_list.hpp>

namespace MyLib {
    template <typename VertexProperties, typename EdgeProperties>
    using Graph = boost::adjacency_list<boost::setS, boost::listS, boost::bidirectionalS, VertexProperties, EdgeProperties>;
}

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

struct VertexProperties { int i; };
struct EdgeProperties { double weight; };

int main() {
    using boost::make_iterator_range;
    using MyGraph = MyLib::Graph<VertexProperties, EdgeProperties>;

    MyGraph g;

    auto v1 = add_vertex({42}, g);
    auto v2 = add_vertex({42}, g);
    g[v1].i = 23;
    g[v2].i = 67;

    add_edge(v1, v2, EdgeProperties{ 1.0 }, g);
    add_edge(v2, v1, EdgeProperties{ 0.0 }, g);

    for (auto v : make_iterator_range(vertices(g))) {
        std::cout << "Vertex " << g[v].i << "\n";
    }

    for (auto e : make_iterator_range(boost::edges(g))) {
        auto s = source(e, g);
        auto t = target(e, g);

        std::cout << "Edge " << g[s].i << " -> " << g[t].i << " (weight = " << g[e].weight << ")\n";
    }

    // let's find a shortest path:
    auto id_map = get(&VertexProperties::i, g);
    auto weight_map = get(&EdgeProperties::weight, g);

    auto source = *vertices(g).first;

    using Vertex = MyGraph::vertex_descriptor;
    std::map<Vertex, Vertex> predecessors;
    std::map<Vertex, double> distance;
    std::map<Vertex, boost::default_color_type> colors;

    boost::dijkstra_shortest_paths(
            g, source,
            boost::vertex_color_map(boost::make_assoc_property_map(colors))
            .predecessor_map(boost::make_assoc_property_map(predecessors))
            .distance_map(boost::make_assoc_property_map(distance))
            .weight_map(weight_map)
            .vertex_index_map(id_map));
}

I'd say

• that is superior.
• it's just as elegant despite not relying on using namespace boost (ADL is the key here)
• and we actually printed the edge weight!

And It Can Be Cleaner Still

If you switch to a vertex container selector that has implicit vertex index (like vecS):

Live On Coliru

#include <boost/graph/adjacency_list.hpp>

namespace MyLib {
    template <typename VertexProperties, typename EdgeProperties>
    using Graph = boost::adjacency_list<boost::setS, boost::vecS, boost::bidirectionalS, VertexProperties, EdgeProperties>;
}

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

struct VertexProperties { int i; };
struct EdgeProperties { double weight; };

int main() {
    using boost::make_iterator_range;
    using MyGraph = MyLib::Graph<VertexProperties, EdgeProperties>;

    MyGraph g;

    add_vertex({23}, g);
    add_vertex({67}, g);

    add_edge(0, 1, EdgeProperties{ 1.0 }, g);
    add_edge(1, 0, EdgeProperties{ 0.0 }, g);

    for (auto v : make_iterator_range(vertices(g))) {
        std::cout << "Vertex " << g[v].i << "\n";
    }

    for (auto e : make_iterator_range(boost::edges(g))) {
        auto s = source(e, g);
        auto t = target(e, g);

        std::cout << "Edge " << g[s].i << " -> " << g[t].i << " (weight = " << g[e].weight << ")\n";
    }

    // let's find a shortest path:
    std::vector<size_t> predecessors(num_vertices(g));
    std::vector<double> distance(num_vertices(g));

    boost::dijkstra_shortest_paths(g, *vertices(g).first,
            boost::predecessor_map(predecessors.data()).distance_map(distance.data())
            .weight_map(get(&EdgeProperties::weight, g)));
}

Output:

Vertex 23
Vertex 67
Edge 23 -> 67 (weight = 1)
Edge 67 -> 23 (weight = 0)

WAIT - Don't Forget About The Question!

I won't! I think the above shows the problem was an X/Y problem.

If you hadn't had the handicap of custom class wrapping, detecting duplicate edges was a given (see if add_vertex in BGL checks for the existence of the vertex for background):

struct { size_t from, to; double weight; } edge_data[] = {
    {0, 1, 1.0}, 
    {1, 0, 0.0}, 
    {0, 1, 99.999} // oops, a duplicate
};
for(auto request : edge_data) {
    auto addition = add_edge(request.from, request.to, { request.weight }, g);
    if (!addition.second) {
        auto& weight = g[addition.first].weight;
        std::cout << "Edge already existed, changing weight from " << weight << " to " << request.weight << "\n";
        weight = request.weight;
    }
}

This will print Live On Coliru:

Edge already existed, changing weight from 1 to 99.999

If you prefer you can of course write things more expressively:

Graph::edge_descriptor e;
bool inserted;
boost::tie(e, inserted) = add_edge(request.from, request.to, { request.weight }, g);

Or, with some c++17 flair:

auto [e, inserted] = add_edge(request.from, request.to, { request.weight }, g);

More From Here

Also, in all likelihood you need to do uniqueness checks on the vertices too, so you end up with graph creation code like you can see in this answer: Boost BGL BFS Find all unique paths from Source to Target

Graph read_graph() {
    std::istringstream iss(R"(
        0 1 0.001
        0 2 0.1
        0 3 0.001
        1 5 0.001
        2 3 0.001
        3 4 0.1
        1 482 0.1
        482 635 0.001
        4 705 0.1
        705 5 0.1
        1 1491 0.01
        1 1727 0.01
        1 1765 0.01)");

    Graph g;
    std::map<int,Vertex> idx; // temporary lookup of existing vertices

    auto vertex = [&](int id) mutable {
        auto it = idx.find(id);
        if (it != idx.end())
            return it->second;
        return idx.emplace(id, add_vertex(id, g)).first->second;
    };

    for (std::string line; getline(iss, line);) {
        std::istringstream ls(line);
        int s,t; double w;
        if (ls >> s >> t >> w) {
            add_edge(vertex(s), vertex(t), w, g);
        } else {
            std::cerr << "Skipped invalid line '" << line << "'\n";
        }
    }

    return g;
}

Other examples show how you can insert both a -> b and b -> a while maintaining a mapping between the forward and back edges: Accessing specific edges in boost::graph with integer index

Summary

Coming full circle, I recommend getting acquainted with the newer, more elegant Boost Graph features. In the end, it's perfectly normal to encapsulate your graph, and you might end up with an even more polished interface.