1

I'm learning about BGL and pieced together a program (from various related StackOverflow answers) to build a graph that should be able to deal with polymorphic vertices and edges. The graph should be able to handle parallel edges (of the same type or not). I'd like to get dijkstra_shortest_paths from a starting vertex_descriptor to : 1. all Park's; 2. all Park's and City's; 3. all City's via Railway only. Is that even possible ? Thank you.

#include <iostream>
#include <deque>

#include "boost/graph/adjacency_list.hpp"
#include "boost/graph/topological_sort.hpp"
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/variant.hpp>


#include <boost/graph/adj_list_serialize.hpp>
#include <boost/property_map/function_property_map.hpp>
#include <boost/property_map/transform_value_property_map.hpp>

using namespace boost;

struct Highway {
  std::string name;
  int miles;
  int speed_limit;
  int lanes;
  bool divided;
};

struct Railway { 
  std::string name; 
  int km;
};

struct City {
  std::string name;
  int population;
  std::vector<int> zipcodes;
};

struct Park {
  std::string name;
  int population;
  std::vector<int> zipcodes;
};


struct Country {
  std::string name;
  bool use_right;   // Drive on the left or right
  bool use_metric;  // mph or km/h
};

int main(int argc, char *argv[]) {

  typedef boost::adjacency_list<
    boost::listS, boost::vecS, boost::bidirectionalS,
    boost::variant<City, Park>, boost::variant<Highway, Railway>, Country>
      Map;

  City c1 = {"San Jose", 1200000, {95126, 95128}};
  City c2 = {"San Francisco", 500000, {95008, 95009}};
  City c3 = {"Santa Cruz", 300000, {94001, 94002}};
  City c4 = {"Oakland", 800000, {93001, 93002}};
  City c5 = {"San Diego", 2800000, {92001, 92002}};

  Map map; // load the map
  Map::vertex_descriptor c1d = boost::add_vertex(c1, map),
    c2d = boost::add_vertex(c2, map),
    c3d = boost::add_vertex(c3, map),
    c4d = boost::add_vertex(c4, map), 
    c5d = boost::add_vertex(c5, map); 
  add_edge(c1d, c2d, Highway{"101", 42, 65, 3, true}, map);
  add_edge(c2d, c3d, Highway{"280", 52, 60, 1, true}, map);
  add_edge(c2d, c3d, Highway{"92", 13, 60, 1, true}, map);
  //add_edge(c2, c3, map);
  //add_edge(c1, c3, map);

  map[graph_bundle].name = "United States";
  map[graph_bundle].use_right = true;
  map[graph_bundle].use_metric = false;

  using vertex_descriptor = boost::graph_traits<Map>::vertex_descriptor;

  Map::vertex_descriptor from = *vertices(map).first;
  std::vector<int> distances(num_vertices(map));
  auto v_index = get(boost::vertex_index, map);
  auto v_bundle = get(boost::vertex_bundle, map);
  dijkstra_shortest_paths(map, from,
      weight_map(get(get(&Highway::miles, map))
      .distance_map(make_iterator_property_map(distances.begin(),
      get(vertex_index, map))));
  std::cout << "distances and parents:" << std::endl;
  graph_traits <Map>::vertex_iterator vi, vend;
  for (boost::tie(vi, vend) = vertices(map); vi != vend; ++vi) {
    std::cout << "distance(" << get<City>(&City::name, map[*vi]) << ") = " << distances[*vi] << ", " << "\n";
  }
  std::cout << std::endl;

  return 0;
}
ihi
  • 107
  • 1
  • 9
  • " get dijkstra_shortest_paths from a starting vertex_descriptor" This is certainly possible! So, what is your problem? What is stopping you in this case? – ravenspoint Jan 29 '22 at 13:03
  • Have a look at subgraph adaptors. They may be more what you're after. Or filtered-graphs, where you would get concrete variant elements *after* filtering. – sehe Jan 29 '22 at 17:06

1 Answers1

2

So, in short, you want to access a property from a variant element type. You could make your own property map, facilitate your own set of get/put accessors or use a property map adaptor.

The latter being least work:

auto highway_miles = boost::make_transform_value_property_map(
    [](Interconnect const& conn) {
        if (auto* c = boost::get<Highway>(&conn)) {
            return c->miles;
        } else {
            return std::numeric_limits<Distance>::max();
        }
    },
    get(boost::edge_bundle, map));

dijkstra_shortest_paths(
    map, from,
    weight_map(highway_miles)
        .distance_map(make_iterator_property_map(
            distances.begin(), v_index)));

In fact with vecS chosen vertex container selector, you could write it more succinctly:

dijkstra_shortest_paths(
    map, from, weight_map(highway_miles).distance_map(distances.data()));

Live Demo

Live on Compiler Explorer

#include <deque>
#include <iostream>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/topological_sort.hpp>
#include <boost/property_map/function_property_map.hpp>
#include <boost/property_map/transform_value_property_map.hpp>
#include <boost/variant.hpp>

using Distance = int;

struct Highway {
    std::string name;
    Distance    miles;
    unsigned    speed_limit, lanes;
    bool        divided;
};

struct Railway {
    std::string name;
    Distance    km;
};

struct City {
    std::string           name;
    unsigned              population;
    std::vector<unsigned> zipcodes;
};

struct Park {
    std::string           name;
    unsigned              population;
    std::vector<unsigned> zipcodes;
};

using Interconnect = boost::variant<Highway, Railway>;
using Area = boost::variant<City, Park>;

enum class RoadOrientation { right, left };
enum class UnitSystem { metric, imperial };

struct Country {
    std::string     name;
    RoadOrientation driving;
    UnitSystem      measure;
};

using Map = boost::adjacency_list<                    //
    boost::listS, boost::vecS, boost::bidirectionalS, //
    Area, Interconnect, Country>;

int main()
{
    Map map;
    map[boost::graph_bundle] = {
        "United States",
        RoadOrientation::right,
        UnitSystem::imperial,
    };

    auto c1d = add_vertex(City{"San Jose",      1200000, {95126, 95128}}, map);
    auto c2d = add_vertex(City{"San Francisco", 500000,  {95008, 95009}}, map);
    auto c3d = add_vertex(City{"Santa Cruz",    300000,  {94001, 94002}}, map);
               add_vertex(City{"Oakland",       800000,  {93001, 93002}}, map);
               add_vertex(City{"San Diego",     2800000, {92001, 92002}}, map);

    add_edge(c1d, c2d, Highway{"101", 42, 65, 3, true}, map);
    add_edge(c2d, c3d, Highway{"280", 52, 60, 1, true}, map);
    add_edge(c2d, c3d, Highway{"92",  13, 60, 1, true}, map);

    using V = Map::vertex_descriptor;

    V                from = vertex(0, map);
    std::vector<int> distances(num_vertices(map));

    auto v_index       = get(boost::vertex_index, map);
    auto highway_miles = boost::make_transform_value_property_map(
        [](Interconnect const& conn) {
            if (auto* c = boost::get<Highway>(&conn)) {
                return c->miles;
            } else {
                return std::numeric_limits<Distance>::max();
            }
        },
        get(boost::edge_bundle, map));

    dijkstra_shortest_paths(
        map, from,
        weight_map(highway_miles)
            .distance_map(make_iterator_property_map(
                distances.begin(), v_index)));

    // dijkstra_shortest_paths(
    //     map, from, weight_map(highway_miles).distance_map(distances.data()));

    std::cout << "distances and parents:" << std::endl;

    auto name_of = [](auto const& area) {
        return boost::apply_visitor(
            [](auto const& c_or_p) { return c_or_p.name; }, area);
    };

    for (auto v : boost::make_iterator_range(vertices(map)))
        std::cout << "distance(" << name_of(map[v]) << ") = " << distances[v] << "\n";
}

Prints

distances and parents:
distance(San Jose) = 0
distance(San Francisco) = 42
distance(Santa Cruz) = 55
distance(Oakland) = 2147483647
distance(San Diego) = 2147483647

More Ideas

I've provided recommendations/alternatives in the past:

UPDATE: Filtering Graph

In response to

I'd like to get dijkstra_shortest_paths from a starting vertex_descriptor to : 1. all Park's; 2. all Park's and City's; 3. all City's via Railway only. Is that even possible ? Thank you.

Here's how you might write that using filtered graphs:

using V = Map::vertex_descriptor;
using E = Map::edge_descriptor;

using VertexFilter = std::function<bool(V)>;
using EdgeFilter   = std::function<bool(E)>;
using FMap         = boost::filtered_graph<Map, EdgeFilter, VertexFilter>;

EdgeFilter any_interconnect = boost::keep_all{};
EdgeFilter railway_only     = [&map](E e) -> bool { return get<Railway>(&map[e]); };
VertexFilter parks          = [&map](V v) -> bool { return get<Park>(&map[v]); };
VertexFilter cities         = [&map](V v) -> bool { return get<City>(&map[v]); };
VertexFilter parks_cities   = boost::keep_all{};

struct {
    FMap             fmap;
    std::string_view caption;
} cases[] = {
    {FMap(map, any_interconnect, parks),        "All parks"},
    {FMap(map, any_interconnect, parks_cities), "All parks and cities"},
    {FMap(map, railway_only,     cities),       "Cities by railway"},
};

for (auto const& [fmap, caption] : cases) {
    std::cout << " ---- " << caption << "\n";

    if (auto [vb, ve] = vertices(fmap); vb != ve) {
        std::vector<Distance> distances(num_vertices(
            fmap)); // or map, since descriptors are same domain

        auto weight = make_transform_value_property_map(
            distance_km, get(boost::edge_bundle, fmap));

        dijkstra_shortest_paths(
            fmap, *vb,
            weight_map(weight).distance_map(distances.data()));

        for (auto v : boost::make_iterator_range(vertices(fmap)))
            std::cout << "distance(" << name_of(fmap[v])
                      << ") = " << distances[v] << "km\n";
    }
}

Here's a live demo:

Live On Compiler Explorer

#include <iostream>
#include <iomanip>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/adjacency_list_io.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/topological_sort.hpp>
#include <boost/graph/filtered_graph.hpp>
#include <boost/property_map/transform_value_property_map.hpp>
#include <boost/variant.hpp>

using Distance = double;

struct Highway {
    std::string name;
    Distance    miles;
    unsigned    speed_limit, lanes;
    bool        divided;
};

struct Railway {
    std::string name;
    Distance    km;
};

struct City {
    std::string           name;
    unsigned              population;
    std::vector<unsigned> zipcodes;
};

struct Park {
    std::string           name;
    unsigned              population;
    std::vector<unsigned> zipcodes;
};

using Interconnect = boost::variant<Highway, Railway>;
using Area = boost::variant<City, Park>;

enum class RoadOrientation { right, left };
enum class UnitSystem { metric, imperial };

struct {
    Distance operator()(Highway const& hw) const { return 1.60934 * hw.miles; }
    Distance operator()(Railway const& rw) const { return rw.km; }
    Distance operator()(auto const& variant) const {
        return boost::apply_visitor(
            [this](auto const& obj) { return (*this)(obj); }, variant);
    }
} static const inline distance_km;

struct {
    std::string_view operator()(auto const& variant) const {
        return boost::apply_visitor(
            [](auto const& obj) -> std::string_view { return obj.name; },
            variant);
    }
} static const inline name_of;

struct Country {
    std::string     name;
    RoadOrientation driving;
    UnitSystem      measure;
};

// for debug output
static inline std::ostream& operator<<(std::ostream& os, City const& c) { return os << "City{" << std::quoted(c.name) << ", pop:" << c.population << "}"; }
static inline std::ostream& operator<<(std::ostream& os, Park const& p) { return os << "Park{" << std::quoted(p.name) << ", pop:" << p.population << "}"; }
static inline std::ostream& operator<<(std::ostream& os, Highway const& hw) { return os << "Highway{" << std::quoted(hw.name) << ", " << distance_km(hw) << "km}"; }
static inline std::ostream& operator<<(std::ostream& os, Railway const& rw) { return os << "Railway{" << std::quoted(rw.name) << ", " << distance_km(rw) << "km}"; }

using Map = boost::adjacency_list<                    //
    boost::listS, boost::vecS, boost::bidirectionalS, //
    Area, Interconnect, Country>;

int main()
{
    Map map;
    map[boost::graph_bundle] = {
        "United States",
        RoadOrientation::right,
        UnitSystem::imperial,
    };

    auto c1d = add_vertex(City{"San Jose",      1200000, {95126, 95128}}, map);
    auto c2d = add_vertex(City{"San Francisco", 500000,  {95008, 95009}}, map);
    auto c3d = add_vertex(City{"Santa Cruz",    300000,  {94001, 94002}}, map);
    auto c4d = add_vertex(City{"Oakland",       800000,  {93001, 93002}}, map);
               add_vertex(City{"San Diego",     2800000, {92001, 92002}}, map);

    auto p1d = add_vertex(Park{"Alum Rock Park",     0, {}}, map);
    auto p2d = add_vertex(Park{"Calero County Park", 0, {}}, map);
    auto p3d = add_vertex(Park{"Reinhardt Redwood",  0, {}}, map);
    auto p4d = add_vertex(Park{"Knowland Park",      0, {}}, map);

    add_edge(c1d, c2d, Highway{"101", 42, 65, 3, true}, map);
    add_edge(c2d, c3d, Highway{"280", 52, 60, 1, true}, map);
    add_edge(c2d, c3d, Highway{"92",  13, 60, 1, true}, map);

    add_edge(c1d, p1d, Highway{"102", 27, 65, 2, false}, map);
    add_edge(c1d, p2d, Railway{"N1", 36}, map);
    add_edge(c4d, p3d, Highway{"703", 53, 65, 2, false}, map);
    add_edge(c4d, p4d, Railway{"N2", 70}, map);

    std::cout << " ---- map\n" << boost::write(map) << "\n";

    using V = Map::vertex_descriptor;
    using E = Map::edge_descriptor;

    using VertexFilter = std::function<bool(V)>;
    using EdgeFilter   = std::function<bool(E)>;
    using FMap         = boost::filtered_graph<Map, EdgeFilter, VertexFilter>;

    EdgeFilter any_interconnect = boost::keep_all{};
    EdgeFilter railway_only     = [&map](E e) -> bool { return get<Railway>(&map[e]); };
    VertexFilter parks          = [&map](V v) -> bool { return get<Park>(&map[v]); };
    VertexFilter cities         = [&map](V v) -> bool { return get<City>(&map[v]); };
    VertexFilter parks_cities   = boost::keep_all{};

    struct {
        FMap             fmap;
        std::string_view caption;
    } cases[] = {
        {FMap(map, any_interconnect, parks),        "All parks"},
        {FMap(map, any_interconnect, parks_cities), "All parks and cities"},
        {FMap(map, railway_only,     cities),       "Cities by railway"},
    };

    for (auto const& [fmap, caption] : cases) {
        std::cout << " ---- " << caption << "\n";

        if (auto [vb, ve] = vertices(fmap); vb != ve) {
            std::vector<Distance> distances(num_vertices(
                fmap)); // or map, since descriptors are same domain

            auto weight = make_transform_value_property_map(
                distance_km, get(boost::edge_bundle, fmap));

            dijkstra_shortest_paths(
                fmap, *vb,
                weight_map(weight).distance_map(distances.data()));

            for (auto v : boost::make_iterator_range(vertices(fmap)))
                std::cout << "distance(" << name_of(fmap[v])
                          << ") = " << distances[v] << "km\n";
        }
    }
}

Prints

 ---- map
v
City{"San Jose", pop:1200000} 
City{"San Francisco", pop:500000} 
City{"Santa Cruz", pop:300000} 
City{"Oakland", pop:800000} 
City{"San Diego", pop:2800000} 
Park{"Alum Rock Park", pop:0} 
Park{"Calero County Park", pop:0} 
Park{"Reinhardt Redwood", pop:0} 
Park{"Knowland Park", pop:0} 
e
0 1  Highway{"101", 67.5923km} 
1 2  Highway{"280", 83.6857km} 
1 2  Highway{"92", 20.9214km} 
0 5  Highway{"102", 43.4522km} 
0 6  Railway{"N1", 36km} 
3 7  Highway{"703", 85.295km} 
3 8  Railway{"N2", 70km} 


 ---- All parks
distance(Alum Rock Park) = 0km
distance(Calero County Park) = 1.79769e+308km
distance(Reinhardt Redwood) = 1.79769e+308km
distance(Knowland Park) = 1.79769e+308km
 ---- All parks and cities
distance(San Jose) = 0km
distance(San Francisco) = 67.5923km
distance(Santa Cruz) = 88.5137km
distance(Oakland) = 1.79769e+308km
distance(San Diego) = 1.79769e+308km
distance(Alum Rock Park) = 43.4522km
distance(Calero County Park) = 36km
distance(Reinhardt Redwood) = 1.79769e+308km
distance(Knowland Park) = 1.79769e+308km
 ---- Cities by railway
distance(San Jose) = 0km
distance(San Francisco) = 1.79769e+308km
distance(Santa Cruz) = 1.79769e+308km
distance(Oakland) = 1.79769e+308km
distance(San Diego) = 1.79769e+308km

I made up some extra data to even have parks or railways.

sehe
  • 374,641
  • 47
  • 450
  • 633
  • Added a demo using filtering_graphs to show "All parks", "All parks and cities" and "Cities by railway" cases https://godbolt.org/z/hz1deMa4s – sehe Jan 29 '22 at 18:11
  • 1
    I was hoping @sehe would answer my question - the testcase I put together was with fragments from your other answers. Thank you very much, especially for using San Francisco Bay Area parks and cities - I would've been lost otherwise :) - this is the answer, 3 different ways, will have to make a bigger graph to test for speed. Thanks again, more questions to follow soon. P.S. In one of your other answers, you said you're using "The Boost Graph Library: User Guide and Reference Manual" - it's from 2001, is it still relevant ? – ihi Jan 31 '22 at 19:43
  • I think it is. I suppose the big revolution since then has mainly been PBGL, aside from a handful new algorithms. I readily admit I don't know the first thing about PBGL though. Also, the book is just the site docs, as far as I remember. – sehe Jan 31 '22 at 21:09