Boost graph non contiguous vertex indices-CodePudding

#include <boost/graph/adjacency_list.hpp>
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS,
                                        boost::no_property,
                                        boost::property<boost::edge_weight_t, double>>
              DiGraph;

typedef boost::graph_traits<DiGraph>::vertex_descriptor vertex_descriptor;

int main () {
std::vector<std::size_t> vertices = { 1, 5, 10};
std::vector<std::pair<std::size_t, std::size_t>> edges = {std::make_pair(1, 5),
                                                                   std::make_pair(5, 10)};
std::vector<double> weights = {2., 2.};

DiGraph di_graph (edges.begin(), edges.end(), weights.begin(), vertices.size());


DiGraph::vertex_descriptor v_start = boost::vertex(1, di_graph);


std::vector<vertex_descriptor> parents(boost::num_vertices(di_graph));

boost::dijkstra_shortest_paths(di_graph, v_start,
      boost::predecessor_map(boost::make_iterator_property_map(parents.begin(), boost::get(boost::vertex_index, di_graph))));

}

This allocates a vector parents of size 11, since boost uses contiguous vertex indices. I want the non-contiguous vertices (1, 5, 10..) but don't want the unnecessary memory space for the vector parents. How can I make a mapping from my vertex indices to the vertex indices 1, 2, 3 and pass it to boost::dijkstra_shortest_paths?

On top of that it would be even more convenient to receive the result of dijkstra in a struct parents and access the predecessor of an element with my index, e.g.

parents[10]

but without a vector of length 11 or just have an easy conversion function f I could use

parents[f(10)]

I did take a look at the documentation of boost graph and thought the IndexMap could make this possible, but I don't understand the concept and can't make it work.

CodePudding user response：

First step: take a look at bundled properties https://www.boost.org/doc/libs/1_79_0/libs/graph/doc/bundles.html

Second:
the non-contiguous vertices (1, 5, 10..) " these should be regarded as properties of the vertex. e.g "1" is a property of vertex 0.

Third: create a vertex class with 1, 5, 10.. as public attributes

Four: Create a boost graph using the your vertex class, setting and getting 1, 5, 10.. as described in the bundled properties page.

CodePudding user response：

With the boost::vecS vertex container selection, the vertex index is implicit, and the call

DiGraph di_graph(
    edges.begin(), edges.end(), weights.begin(), vertices.size());

is a lie: you tell it that there are 3 vertices, but then you index out of bounds (5, 10 are outside [0,1,2]).

Note also that

V v_start = boost::vertex(1, di_graph);

selects the second vertex, not vertex 1.

Internal Names

I'd probably suggest a more recent addition: internal vertex names. If we add a vertex property bundle, like simply int:

using DiGraph = boost::adjacency_list<
    boost::vecS,
    boost::vecS,
    boost::directedS,
    int,
    boost::property<boost::edge_weight_t, double>>;

And then also teach BGL that we can use it as the vertex internal name:

template<> struct boost::graph::internal_vertex_name<int> {
    struct type : std::identity {
        using result_type = int;
    };
};

Now creating the equivalent graph is simply:

DiGraph g;
add_edge(1, 5, 2., g);
add_edge(5, 10, 2., g);

That's all. You can see that it created vertices with implicit indices as the descriptors:

for (auto e : make_iterator_range(edges(g))) {
    std::cout << "edge: " << e << "\n";
}

Prints:

edge: (0,2)
edge: (1,0)

To get the names, use property maps like so:

for (auto v : make_iterator_range(vertices(g))) {
    std::cout << "vertex at index " << v << " named " << g[v] << "\n";
}

Printing

vertex at index 0 named 5
vertex at index 1 named 1
vertex at index 2 named 10

Using internal vertex names, you can query vertices by property bundles:

boost::optional<V> v_start = g.vertex_by_property(1);

Now, all I can suggest is using safe iterator maps:

dijkstra_shortest_paths(
    g,
    v_start.value(),
    boost::predecessor_map(boost::make_safe_iterator_property_map(
        parents.begin(), parents.size(), get(boost::vertex_index, g))));

for (size_t i = 0; i < parents.size();   i) {
    std::cout << "Parent for '" << g[i] << "' is '" << g[parents[i]] << "'\n";
}

Live Demo

Live On Coliru

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

template<> struct boost::graph::internal_vertex_name<int> {
    struct type : std::identity {
        using result_type = int;
    };
};

using DiGraph = boost::adjacency_list<
    boost::vecS,
    boost::vecS,
    boost::directedS,
    int,
    boost::property<boost::edge_weight_t, double>>;

using V = DiGraph::vertex_descriptor;
using boost::make_iterator_range;

int main()
{
    DiGraph g;
    add_edge(1, 5, 2., g);
    add_edge(5, 10, 2., g);

    for(auto e : make_iterator_range(edges(g)))
        std::cout << "edge: " << e << "\n";

    for(auto v : make_iterator_range(vertices(g)))
        std::cout << "vertex at index " << v << " named " << g[v] << "\n";

    boost::optional<V> v_start = g.vertex_by_property(1);

    std::vector<V> parents(num_vertices(g));

    dijkstra_shortest_paths(
        g,
        v_start.value(),
        boost::predecessor_map(boost::make_safe_iterator_property_map(
            parents.begin(), parents.size(), get(boost::vertex_index, g))));

    for (size_t i = 0; i < parents.size();   i) {
        std::cout << "Parent for '" << g[i] << "' is '" << g[parents[i]] << "'\n";
    }
}

Prints

edge: (0,2)
edge: (1,0)
vertex at index 0 named 5
vertex at index 1 named 1
vertex at index 2 named 10
Parent for '5' is '1'
Parent for '1' is '1'
Parent for '10' is '5'