What Is Needed to Use Bgl Algorithms on Existing Data Structures ( Edges and Vertices as Vector<Object *>)

  • Home
  • Languages
  • C++
  • What Is Needed to Use Bgl Algorithms on Existing Data Structures ( Edges and Vertices as Vector<Object *>)

What is needed to use BGL algorithms on existing data structures ( edges and vertices as vectorObject *)?

The documentation for the Graph concepts is conveniently here: https://www.boost.org/doc/libs/1_70_0/libs/graph/doc/graph_concepts.html

So - you never told us what algorithms you intend to use.

So let me pick an examples: BFS. The docs say it requires:

A directed or undirected graph. The graph type must be a model of Vertex List Graph and Incidence Graph.

Looking at your pre-existing data structures, it looks like you only cover the Vertex List use case easily.

The edges are implemented more as an Edge List. It's not possible to emulate Incidence Graph from Edge List without runtime or storage overhead (that's mathematics, nothing to do with library or code quality).

In reality, it's pretty likely that you omitted parts of your pre-existing data-structures that are relevant to the problem, as most algorithms will be highly sub-optimal on just Vertex+Edge lists.

In practice I suppose you Edge list might be organized like a classical adjacency list (e.g. ordering by source vertex, so you CAN have a O(log(n)) lookup by source vertex).

For the example below I'm assuming this is the case. Keep in mind we're only approaching the complexity guarantees from Incidence Graph Concept:

Complexity guarantees


The source(), target(), and out_edges() functions must all be constant time. The out_degree() function must be linear in the number of out-edges.


To actually meet these requirements, you will need to have dedicated storage of out-edges per vertex

So, let'st have a go:

Mocking YourLibrary

namespace YourLibrary {
    struct myVertex {
    };

    struct myEdge {
        myVertex* _s = nullptr;
        myVertex* _t = nullptr;

        myVertex* source() const { return _s; }
        myVertex* target() const { return _t; }
    };

    using Vertices = std::vector<myVertex *>;
    using Edges = std::vector<myEdge *>;
}

Fulfilling the Graph Concepts

You wanted to keep references to the pre-existing data structures:

namespace Glue {

    struct MyGraph {
        struct EdgeOrder {
            template <typename A, typename B>
                bool operator()(A const* a, B const* b) const { return source(a) < source(b); }
            private:
            static auto source(YourLibrary::myVertex const* v) { return v; }
            static auto source(YourLibrary::myEdge const* e) { return e->source(); }
        };

        using Vertices = YourLibrary::Vertices;
        using Edges = YourLibrary::Edges;

        Vertices& _vertices;
        Edges& _edges;

        MyGraph(Vertices& vv, Edges& ee) : _vertices(vv), _edges(ee)  { }
    };
}

Now, I'll just run down the list of required trait types per concept:

namespace boost {

    template <> struct graph_traits<Glue::MyGraph> {
        // Due to Graph concept
        using vertex_descriptor      = YourLibrary::myVertex*;
        using edge_descriptor        = YourLibrary::myEdge*;
        using directed_category      = directed_tag;
        using edge_parallel_category = allow_parallel_edge_tag;
        static vertex_descriptor null_vertex() { return nullptr; }

        // Due to Vertex List concept
        struct traversal_category : vertex_list_graph_tag, incidence_graph_tag { };
        using vertex_iterator        = Glue::MyGraph::Vertices::const_iterator;
        using vertices_size_type     = std::size_t;

        // Due to Incidence Graph concept
        using out_edge_iterator = Glue::MyGraph::Edges::const_iterator;
        using degree_size_type = std::size_t;
    };

}

And finally re-open the namespace so ADL can find these functions that are required to satisfy the "valid expressions" criteria:

namespace Glue {
    // Due to Vertex List concept
    auto vertices(MyGraph const& g) {
        return std::make_pair(g._vertices.begin(), g._vertices.end());
    }

    std::size_t num_vertices(MyGraph const& g) {
        return g._vertices.size();
    }

    // Due to Incidence Graph concept
    auto source(YourLibrary::myEdge const* e, MyGraph const& g) {
        return e->source();
    }
    auto target(YourLibrary::myEdge const* e, MyGraph const& g) {
        return e->target();
    }

    auto out_edges(YourLibrary::myVertex const* v, MyGraph const& g) {
        return std::equal_range(g._edges.begin(), g._edges.end(), v, MyGraph::EdgeOrder{});;
    }
    std::size_t out_degree(YourLibrary::myVertex const* v, MyGraph const& g) {
        auto oee = std::equal_range(g._edges.begin(), g._edges.end(), v, MyGraph::EdgeOrder{});
        return std::distance(oee.first, oee.second);
    }
}

This would be roughly functionally equivalent to an adjacency_list with a setS for the vertex container.

See it Live On Coliru

Running BFS

All that's required in addition is for the arguments of the algorithm. You'd need both the color map and the vertex index map. This is completely normal and would also be required if you had e.g. adjacency_list<vecS, listS, directedS>.

I'll hide the index map inside the MyGraph wrapper and expose the color map so you can pick your preference:

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/container/flat_map.hpp>
#include <algorithm>

namespace YourLibrary {
    struct myVertex {
    };

    struct myEdge {
        myVertex* _s = nullptr;
        myVertex* _t = nullptr;

        myVertex* source() const { return _s; }
        myVertex* target() const { return _t; }
    };

    using Vertices = std::vector<myVertex *>;
    using Edges = std::vector<myEdge *>;
}

namespace Glue {

    struct MyGraph {
        struct EdgeOrder {
            template <typename A, typename B>
                bool operator()(A const* a, B const* b) const { return source(a) < source(b); }
            private:
            static auto source(YourLibrary::myVertex const* v) { return v; }
            static auto source(YourLibrary::myEdge const* e) { return e->source(); }
        };

        using Vertices = YourLibrary::Vertices;
        using Edges = YourLibrary::Edges;

        using Index = boost::container::flat_map<Vertices::value_type, std::size_t>;

        Vertices& _vertices;
        Edges& _edges;
        Index _index;

        MyGraph(Vertices& vv, Edges& ee) : _vertices(vv), _edges(ee)  {
            _index.reserve(vv.size());
            std::size_t i = 0;
            for(auto v : vv) { _index[v] = i++; }
        }
    };
}

namespace boost {

    template <> struct graph_traits<Glue::MyGraph> {
        // Due to Graph concept
        using vertex_descriptor      = YourLibrary::myVertex*;
        using edge_descriptor        = YourLibrary::myEdge*;
        using directed_category      = directed_tag;
        using edge_parallel_category = allow_parallel_edge_tag;
        static vertex_descriptor null_vertex() { return nullptr; }

        // Due to Vertex List concept
        struct traversal_category : vertex_list_graph_tag, incidence_graph_tag { };
        using vertex_iterator        = Glue::MyGraph::Vertices::const_iterator;
        using vertices_size_type     = std::size_t;

        // Due to Incidence Graph concept
        using out_edge_iterator = Glue::MyGraph::Edges::const_iterator;
        using degree_size_type = std::size_t;
    };

}

namespace Glue {
    // Due to Vertex List concept
    auto vertices(MyGraph const& g) {
        return std::make_pair(g._vertices.begin(), g._vertices.end());
    }

    std::size_t num_vertices(MyGraph const& g) {
        return g._vertices.size();
    }

    // Due to Incidence Graph concept
    auto source(YourLibrary::myEdge const* e, MyGraph const& g) {
        return e->source();
    }
    auto target(YourLibrary::myEdge const* e, MyGraph const& g) {
        return e->target();
    }

    auto out_edges(YourLibrary::myVertex const* v, MyGraph const& g) {
        return std::equal_range(g._edges.begin(), g._edges.end(), v, MyGraph::EdgeOrder{});;
    }
    std::size_t out_degree(YourLibrary::myVertex const* v, MyGraph const& g) {
        auto oee = std::equal_range(g._edges.begin(), g._edges.end(), v, MyGraph::EdgeOrder{});
        return std::distance(oee.first, oee.second);
    }

    // Due to BFD requiring the index_map
    auto get(boost::vertex_index_t, MyGraph const& g) {
        return boost::make_assoc_property_map(g._index);
    }
}

int main() {
    // I hate manual memory management, so let's own some objects
    auto a = std::make_unique<YourLibrary::myVertex>();
    auto b = std::make_unique<YourLibrary::myVertex>();
    auto c = std::make_unique<YourLibrary::myVertex>();
    auto ab = std::make_unique<YourLibrary::myEdge>(YourLibrary::myEdge{a.get(), b.get()});
    auto bc = std::make_unique<YourLibrary::myEdge>(YourLibrary::myEdge{b.get(), c.get()});

    // These were given in your question:
    YourLibrary::Vertices vv { a.get(), b.get(), c.get() };
    YourLibrary::Edges ee { ab.get(), bc.get() };

    // this is the glue required to fulfill the BGL concepts:
    Glue::MyGraph g(vv, ee);

    // this is showing that you can now BFS on it
    using V = boost::graph_traits<Glue::MyGraph>::vertex_descriptor;
    V start_vertex = a.get();
    std::map<V, boost::default_color_type> color_data;

    boost::breadth_first_search(g, start_vertex,
            boost::visitor(boost::default_bfs_visitor{})
            .color_map(boost::make_assoc_property_map(color_data)));
}

Conclusion

Algorithms have requirements, and as long as you satisfy them, you can use whatever data structure you want.

In this case you MIGHT want to be really sure about the assumptions made and add this to the MyGraph constructor:

assert(std::is_sorted(_edges.begin(), _edges.end(), EdgeOrder{}));

On Converting Existing Graphs to BGL

In other words, which are precisely the property maps as outlined here that guarantee me that I could run all the algorithms from the Boost Graph Library?

That's asking the wrong question.
One of the key design choices of the BGL (much like the STL) is separation of data structures and algorithms. The set of properties required by algorithm varies by algorithm (and even by usage of the same algorithm), and can be satisfied in many ways generically.

Which property map(s) are required is documented with the algorithm. This, by the way, in addition to which concept the graph model must satisfy.

I do know that the documentation can be slightly out of date¹ and more specifically, life with c++14+ can be significantly easier than in the documentation examples.

In case it helps, here are "modern" examples on adapting your own datastructures for use with BGL:

  • What is needed to use BGL algorithms on existing data structures ( edges and vertices as vector<Object *>)?
  • Interestingly, someone later ran into precisely your question about additional requirements for a specific algorithm. In this answer: What is required for a custom BGL graph to work with topological sort? I show not only how to figure out what requirements have to be satisfied but also how to achieve that.

I invite you to read these, and apply them to your particular situation. If you get stuck on something along the way you'll have a new (better) question well-suited to ask on StackOverflow.

¹ like with Boost Geometry, which has a similar design philosophy as BGL, but where this is much bigger problem than with BGL

What is required for a custom BGL graph to work with topological sort?

As you correctly surmised, the error novel is telling you that there is no index map. That is required for the default color map:

UTIL/OUT: color_map(ColorMap color) This is used by the algorithm to
keep track of its progress through the graph. The type ColorMap must
be a model of Read/Write Property Map and its key type must be the
graph's vertex descriptor type and the value type of the color map
must model ColorValue.

Default: an iterator_property_map created from
a std::vector of default_color_type of size num_vertices(g) and using
the i_map for the index map.

Indeed, the index map isn't even required if you fulfill the color map requirement yourself: Live On Coliru

std::map<V, boost::default_color_type> vertex_colors;
boost::topological_sort(
        g,
        back_inserter(rev_topo),
        boost::color_map(boost::make_assoc_property_map(vertex_colors))
    );

More Musings: Teaching BGL Vertex Indices

Now, many algorithms require an index-map, and many get much more convenient, just like above, when your graph model does have a vertex index map.

A vertex index should map the vertex descriptors to integral numbers [0, n) (where n is the total number of vertices). In the case of the example graph model, a trivial index would be the element index into the vector of vertices.

So, you could also express the index map as:

auto idmap = boost::make_function_property_map<V>([&](V v) {
    auto match = std::find(begin(vv), end(vv), v);
    assert(match != end(vv));
    return std::distance(begin(vv), match);
});

Now you can call the algorithm relying on their default color map: Coliru

boost::topological_sort(
        g,
        back_inserter(rev_topo),
        boost::vertex_index_map(idmap)
    );

That's not a big win, since now we still need optional named params, and even need the idmap contraption which seems more complicated than the vertex_colors map before?

Simplifying / Integrating Into The Model

We can make it better by teaching the BGL how to get our property maps from the Glue::MyGraph model.

Property Maps will be found by BGL using

  • the type trait boost::property_map<Graph, Tag> which tells BGL about the type of the propertymap.

    Here, Tag would be e.g. boost::vertex_index_t for the vertex index map.

  • the accessor functions

    • get(tag, graph)

      Returning a copy of the property-map of that type

    • get(tag_type, graph, descriptor)

    For writable property maps there's also the corresponding put accessor, but I'll leave it for brevity. See the documentation for Boost PropertyMap Library for more information on the features of that library.

Let's do that. We start by moving the idmap generator to our MyGraph model, so we don't need to know about the implementation details anymore:

    auto idmap() const {
        using V = YourLibrary::myVertex const*;
        return boost::make_function_property_map<V>([this](V v) {
            auto match = std::find(begin(_vertices), end(_vertices), v);
            assert(match != end(_vertices));
            return std::distance(begin(_vertices), match);
        });
    }

That means you could simply call g.idmap() to get the same propery map. However, we wanted the library to "magically" know. So, first we specialize the trait:

namespace boost {
    template <> struct property_map<Glue::MyGraph, boost::vertex_index_t> {
        using const_type = decltype(std::declval<Glue::MyGraph>().idmap());
    };
}

It's a delight of c++14 that we can deduce all these types. Only remaining step: the accessor functions, which are again ADL-enabled customization points, so we put them into our Glue namespace:

    auto get(boost::vertex_index_t, MyGraph const& g) {
        return g.idmap();
    }
    auto get(boost::vertex_index_t, MyGraph const& g, YourLibrary::myVertex const* v) {
        return g.idmap()[v];
    }
}  // namespace Glue

Proof Of The Pudding

Now, since the library "just understands" vertex indices for our model, we can enjoy the algorithms that need one without any additional help:

std::list<V> order;
boost::topological_sort(g, back_inserter(order));

And we can exercise the other accessor for fun:

std::cout << "Topo order:\n";
order.reverse(); // output is reversed
for (auto v : order)
    std::cout << "Vertex index:" << get(boost::vertex_index, g, v)
              << " name:" << v->name << "\n";

In your own (non-generic, library) code you would probably write

auto idmap = g.idmap(); // or
auto idmap = get(boost::vertex_index, g, v);

And use idmap[v] to get values instead.

Live Demo

Live On Coliru

#include <algorithm>
#include <boost/container/flat_map.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/topological_sort.hpp>
#include <boost/property_map/function_property_map.hpp>
#include <iostream>
#include <utility>

namespace YourLibrary {
    struct myVertex {
        myVertex(std::string n) : name(std::move(n)) {}
        std::string name;
    };

    struct myEdge {
        myVertex* _s = nullptr;
        myVertex* _t = nullptr;

        [[nodiscard]] myVertex* source() const { return _s; }
        [[nodiscard]] myVertex* target() const { return _t; }
    };

    using Vertices = std::vector<myVertex *>;
    using Edges = std::vector<myEdge *>;
}  // namespace YourLibrary

namespace Glue {

    struct MyGraph {
        struct EdgeOrder {
            template <typename A, typename B>
                bool operator()(A const* a, B const* b) const { return source(a) < source(b); }
            private:
            static auto source(YourLibrary::myVertex const* v) { return v; }
            static auto source(YourLibrary::myEdge const* e) { return e->source(); }
        };

        using Vertices = YourLibrary::Vertices;
        using Edges = YourLibrary::Edges;

        Vertices& _vertices;
        Edges& _edges;

        auto idmap() const {
            using V = YourLibrary::myVertex const*;
            return boost::make_function_property_map<V>([this](V v) {
                auto match = std::find(begin(_vertices), end(_vertices), v);
                assert(match != end(_vertices));
                return std::distance(begin(_vertices), match);
            });
        }

        MyGraph(Vertices& vv, Edges& ee) : _vertices(vv), _edges(ee)  { 
            assert(std::is_sorted(_edges.begin(), _edges.end(), EdgeOrder{}));
        }
    };
}  // namespace Glue

namespace boost {

    template <> struct graph_traits<Glue::MyGraph> {
        // Due to Graph concept
        using vertex_descriptor      = YourLibrary::myVertex*;
        using edge_descriptor        = YourLibrary::myEdge*;
        using directed_category      = directed_tag;
        using edge_parallel_category = allow_parallel_edge_tag;
        static vertex_descriptor null_vertex() { return nullptr; }

        // Due to Vertex List concept
        struct traversal_category : vertex_list_graph_tag, incidence_graph_tag { };
        using vertex_iterator        = Glue::MyGraph::Vertices::const_iterator;
        using vertices_size_type     = std::size_t;

        // Due to Incidence Graph concept
        using out_edge_iterator = Glue::MyGraph::Edges::const_iterator;
        using degree_size_type = std::size_t;
    };

}  // namespace boost

namespace Glue {
    // Due to Vertex List concept
    auto vertices(MyGraph const& g) {
        return std::make_pair(g._vertices.begin(), g._vertices.end());
    }

    std::size_t num_vertices(MyGraph const& g) {
        return g._vertices.size();
    }

    // Due to Incidence Graph concept
    auto source(YourLibrary::myEdge const* e, MyGraph const& /*g*/) {
        return e->source();
    }
    auto target(YourLibrary::myEdge const* e, MyGraph const& /*g*/) {
        return e->target();
    }

    auto out_edges(YourLibrary::myVertex const* v, MyGraph const& g) {
        return std::equal_range(g._edges.begin(), g._edges.end(), v, MyGraph::EdgeOrder{});;
    }
    std::size_t out_degree(YourLibrary::myVertex const* v, MyGraph const& g) {
        auto oee = std::equal_range(g._edges.begin(), g._edges.end(), v, MyGraph::EdgeOrder{});
        return std::distance(oee.first, oee.second);
    }

    auto get(boost::vertex_index_t, MyGraph const& g) {
        return g.idmap();
    }
    auto get(boost::vertex_index_t, MyGraph const& g, YourLibrary::myVertex const* v) {
        return g.idmap()[v];
    }
}  // namespace Glue

namespace boost {
    template <> struct property_map<Glue::MyGraph, boost::vertex_index_t> {
        using const_type = decltype(std::declval<Glue::MyGraph>().idmap());
    };
}

int main() {
    // I hate manual memory management, so let's own some objects
    auto a = std::make_unique<YourLibrary::myVertex>("a");
    auto b = std::make_unique<YourLibrary::myVertex>("b");
    auto c = std::make_unique<YourLibrary::myVertex>("c");
    auto ab = std::make_unique<YourLibrary::myEdge>(YourLibrary::myEdge{a.get(), b.get()});
    auto cb = std::make_unique<YourLibrary::myEdge>(YourLibrary::myEdge{c.get(), b.get()});

    // These were given in your question:
    YourLibrary::Vertices vv { a.get(), b.get(), c.get() };
    YourLibrary::Edges ee { ab.get(), cb.get() };

    // this is the glue required to fulfill the BGL concepts:
    using boost::make_iterator_range;

    Glue::MyGraph g(vv, ee);
    for (auto v : make_iterator_range(vertices(g)))
        for (auto e : make_iterator_range(out_edges(v, g)))
            std::cout << "out edge ("
                      << source(e, g)->name << " -> "
                      << target(e, g)->name << ")\n";

    // this is showing that you can now BFS on it
    using V = boost::graph_traits<Glue::MyGraph>::vertex_descriptor;
    V start_vertex = a.get();
    std::map<V, boost::default_color_type> color_data;

    boost::breadth_first_search(g, start_vertex,
        boost::visitor(boost::default_bfs_visitor {})
            .color_map(boost::make_assoc_property_map(color_data)));

    boost::depth_first_search(g, boost::default_dfs_visitor {},
        boost::make_assoc_property_map(color_data), start_vertex);

    // named params
    boost::depth_first_search(g,
        boost::visitor(boost::default_dfs_visitor {})
            .color_map(boost::make_assoc_property_map(color_data))
            .root_vertex(start_vertex));

    std::list<V> order;
    boost::topological_sort(g, back_inserter(order));

    std::cout << "Topo order:\n";
    order.reverse(); // output is reversed

    auto idmap = g.idmap();
    for (auto v : order)
        std::cout << "Vertex index:" << idmap[v] << " name:" << v->name << "\n";
}

Printing

out edge (a -> b)
out edge (c -> b)
Topo order:
Vertex index:2 name:c
Vertex index:0 name:a
Vertex index:1 name:b

Boost::Graph-algorithm does not write data with PropertyMap (kamada_kawai_spring_layout, bundled properties)

The return value of the algorithm:

Returns: true if layout was successful or false if a negative weight cycle was detected or the graph is disconnected.

When you print it, you'll see that it is false. So, your graph doesn't satisfy the requirements.

Raising the edge probability makes for connected graphs:

Live On Compiler Explorer

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/circle_layout.hpp>
#include <boost/graph/erdos_renyi_generator.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/kamada_kawai_spring_layout.hpp>
#include <boost/random/linear_congruential.hpp>
#include <fmt/ranges.h>

using tPoint = boost::convex_topology<2>::point;
struct Graph_Node { tPoint Position{}; };
struct Graph_Edge { /*unsigned int ID;*/ double weight = 100; };

using Graph = boost::adjacency_list<boost::vecS, boost::vecS,
                                    boost::undirectedS, Graph_Node, Graph_Edge>;

static constexpr int    ER_INIT_NODES = 20; // 50
static constexpr double p             = 1;  // 0.05

Graph make_graph() {
    boost::random::minstd_rand rng;
    using Gen = boost::erdos_renyi_iterator<boost::random::minstd_rand, Graph>;
    return {Gen(rng, ER_INIT_NODES, p), Gen(), ER_INIT_NODES};
}

int main()
{
    auto g = make_graph();
    //write_graphviz(std::cout, g);

    auto print_position = [pos = get(&Graph_Node::Position, g)](size_t v) {
        fmt::print("Vertex {:3} Position {:9.4f}, {:9.4f}\n", v, pos[v][0], pos[v][1]);
    };

    auto mid_vertex = vertex(ER_INIT_NODES / 2, g);
    print_position(mid_vertex);
    boost::circle_graph_layout(g, get(&Graph_Node::Position, g), 25.0);

    if (true) { // ball-topology
        print_position(mid_vertex);

        bool ok = kamada_kawai_spring_layout(                    //
            g,                                                   //
            get(&Graph_Node::Position, g),                       //
            get(&Graph_Edge::weight, g),                         //
            boost::ball_topology<2>(1.),                         //
            boost::detail::graph::edge_or_side<true, double>(1.) //
        );
        fmt::print("kamada_kawai_spring_layout ok: {}\n", ok);
    } else {
        print_position(mid_vertex);
        bool ok = kamada_kawai_spring_layout( //
            g,                                //
            get(&Graph_Node::Position, g),    //
            get(&Graph_Edge::weight, g),      //
            boost::square_topology<>(50.0),   //
            boost::side_length(50.0)          //
        );
        fmt::print("kamada_kawai_spring_layout ok: {}\n", ok);
    }

    print_position(mid_vertex);
    fmt::print("----\n");
    for (auto v : boost::make_iterator_range(vertices(g)))
        print_position(v);
}

Prints

Vertex  10 Position    0.0000,    0.0000
Vertex  10 Position  -25.0000,    0.0000
kamada_kawai_spring_layout ok: true
Vertex  10 Position   20.3345, -102.5760
----
Vertex   0 Position  -35.8645,  -19.4454
Vertex   1 Position  -72.7690, -130.3436
Vertex   2 Position   -8.5828, -138.2843
Vertex   3 Position  -44.7830,  -52.9697
Vertex   4 Position  -43.0101,   30.9041
Vertex   5 Position  -69.7531,   38.7188
Vertex   6 Position   -0.4328,   43.2208
Vertex   7 Position   31.3758,  -30.9816
Vertex   8 Position   47.1809,   12.8283
Vertex   9 Position  -76.9535,    9.7684
Vertex  10 Position   20.3345, -102.5760
Vertex  11 Position  -19.5602, -103.9834
Vertex  12 Position  -68.2476,  -78.6953
Vertex  13 Position  -95.3881,  -46.8710
Vertex  14 Position -131.4928,    7.9270
Vertex  15 Position   24.0966,   -4.9534
Vertex  16 Position   59.0794,  -86.1642
Vertex  17 Position -102.4687, -148.9986
Vertex  18 Position  -10.8986,  -52.8234
Vertex  19 Position -131.8706,  -60.2588

How to configure boost::graph to use my own (stable) index for vertices?

Can this be achieved using boost::graph?

The answer is nearly always "yes" with BGL. It's one of the most profoundly generic library designs in existence.

To my surprise, something new appeared in the type-hierarchy for adjacency_list. Apparently these days there's a named_graph mixin (actually maybe_name_graph) which uses traits on the vertex bundle to detect an "internal name".

This means you can get close. Though the vertex descriptor will not become your id, you can have O(1) lookup. And the interface has some conveniences, so you can write:

add_edge(1111, 2222, g);
add_edge(2222, 1111, g);

Notes:

  • the lookup is amortized O(1) because the name-vertex lookup is based on an unordered (hash) index
  • you run into problems (e.g. ambiguous overloads for add_edge) if you make the id type accidentally the same as the vertex_descriptor type (or if your argument have equally "far" conversions to either).
  • as far as I can tell, the internal name property is not automatically picked up as the vertex_index_t nor vertex_name_t property.

Step #1: The Graph

struct Vertex {
    size_t      id;
    std::string other = "default-constructed";
};

using Graph =
    boost::adjacency_list<boost::vecS, boost::listS, boost::directedS, Vertex>;

So far no surprises. I

  • opted to add a second member other just to show when/how it gets default constructed
  • opted listS because it
    • a. offers reference/descriptor stability (except for removed vertices)
    • b. leads to opaque vertex_descriptor (void*) which does not conflict with the id type (size_t) in overload resolution

Step #2: Name Traits

Next we teach BGL about our Internal Vertex Name.


Related Topics

C++ Global Object

What Is the Meaning of This Star (*) Symbol in C++? - Pointer to Member

C++11 Styled Callbacks

How to Set Pointer to a Memory to Null Using Memset

Sigkill While Allocating Memory in C++

Ace VS Boost VS Poco

Capture _Line_ and _File_ Without #Define

How to Print Out the Size of a C++ Class at Compile-Time

C/C++ Inline Assembler with Instructions in String Variables

What Is This Crazy C++11 Syntax ==> Struct:Bar {} Foo {};

C++: Unresolved External Symbol _Sprintf and _Sscanf in Visual Studio 2015

Why Is Using Exit() Considered Bad

Is Uninitialized Data Behavior Well Specified

What Is Inside .Lib File of Static Library, Statically Linked Dynamic Library and Dynamically Linked Dynamic Library

Function Pointer as Parameter

Why Does an Lvalue Cast Work

Why Is Rand()%6 Biased

How to Use Other C++ Compilers with Cuda on Windows


Leave a reply



Submit