Add support for ephemeral vertexes (lazy graph)

[anadon]

I'm looking at GraphQL, and they have a legitimate use case where vertices aren't local but are dynamically generated. It would be really powerful to support that use case, though it may need to wait for a whole new implementation. Anyways, an eye should be kept to supporting their use case.

[Becheler]

Thank you @anadon ! This is actually supported (but not well documented) 😄

In BGL, you write algorithms against concepts, not concrete types. It means that you can imagine a graph struct that would take no space, and lazily generate its vertices for a given algorithm (algorithms that need to access the entirety of the vertex space may not work).

For example, let's imagine this math problem: starting from 1, what's the minimum number of "double-it" or "add-one" operations to reach a target like 23? It's a well-known problem with a clear BFS solution (7 operations for 23).

The graph becomes just a rule: out_edges(n, g) must yield (n,2n) and (n, n+1).

With BFS from 1 looking for a target N, we find the minimum number of "double or increment by 1" operations needed to reach N.

With BGL design we must then:

• Specialize boost::graph_traits<LazyMathGraph> with descriptors and a traversal_category of incidence_graph_tag.
• Free functions source(), target(), out_edges(), out_degree().
• Use breadth_first_visit (NOT breadth_first_search) because the latter requires VertexListGraph, which is incompatible with unbounded/lazy vertex set.
• Pass property maps backed by std::map for color/predecessor/distance, since we cannot index by vertex into a vector.

See it on Compiler Explorer: https://godbolt.org/z/zMGYf63ch

#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/pending/queue.hpp>
#include <boost/property_map/property_map.hpp>

#include <cstdint>
#include <iostream>
#include <iterator>
#include <map>
#include <utility>
#include <vector>

struct LazyMathGraph {};

// lazy iterator that yields the 2 out-edges of vertex `src`
class LazyOutEdgeIter 
{
    std::uint64_t src{};
    int idx{};  // 0 = (src, 2*src), 1 = (src, src+1), 2 = end
    
    public:

    using value_type        = std::pair<std::uint64_t, std::uint64_t>;
    using difference_type   = std::ptrdiff_t;
    using pointer           = const value_type*;
    using reference         = value_type;
    using iterator_category = std::input_iterator_tag;

    LazyOutEdgeIter() = default;
    LazyOutEdgeIter(std::uint64_t s, int i) : src(s), idx(i) {}
    value_type operator*() const { return idx == 0 ? value_type{src, src * 2} : value_type{src, src + 1}; }
    LazyOutEdgeIter& operator++() { ++idx; return *this; }
    LazyOutEdgeIter  operator++(int) { auto t = *this; ++idx; return t; }
    bool operator==(LazyOutEdgeIter const& o) const { return src == o.src && idx == o.idx; }
    bool operator!=(LazyOutEdgeIter const& o) const { return !(*this == o); }

};

// Specialize boost::graph_traits<LazyMathGraph> with descriptors
// and a traversal_category of incidence_graph_tag.
namespace boost {
template <>
struct graph_traits<LazyMathGraph> {
    using vertex_descriptor      = std::uint64_t;
    using edge_descriptor        = std::pair<std::uint64_t, std::uint64_t>;
    using directed_category      = directed_tag;
    using edge_parallel_category = allow_parallel_edge_tag;

    struct traversal_category : public incidence_graph_tag {};

    using out_edge_iterator  = LazyOutEdgeIter;
    using degree_size_type   = std::size_t;
    using vertices_size_type = std::uint64_t;
    using edges_size_type    = std::uint64_t;

    static vertex_descriptor null_vertex() { return 0; }
};
}  // namespace boost

// Free-function customization points for IncidenceGraph

inline std::pair<LazyOutEdgeIter, LazyOutEdgeIter>
out_edges(std::uint64_t v, LazyMathGraph const&) { return { LazyOutEdgeIter{v, 0}, LazyOutEdgeIter{v, 2} };}

inline std::uint64_t
source(std::pair<std::uint64_t, std::uint64_t> const& e, LazyMathGraph const&) { return e.first;}

inline std::uint64_t
target(std::pair<std::uint64_t, std::uint64_t> const& e, LazyMathGraph const&) { return e.second;}

inline std::size_t 
out_degree(std::uint64_t, LazyMathGraph const&) { return 2; }

// BFS visitor: record predecessors + distances, stop on target

struct FoundTarget {};

struct LazyBFSVisitor : public boost::default_bfs_visitor {
    std::uint64_t target_v;
    std::map<std::uint64_t, std::uint64_t>* pred;
    std::map<std::uint64_t, std::uint64_t>* dist;

    LazyBFSVisitor(std::uint64_t t,
                   std::map<std::uint64_t, std::uint64_t>& p,
                   std::map<std::uint64_t, std::uint64_t>& d)
        : target_v(t), pred(&p), dist(&d) {}

    template <typename E, typename G>
    void tree_edge(E e, G const&) const {
        (*pred)[e.second] = e.first;
        (*dist)[e.second] = (*dist)[e.first] + 1;
    }

    template <typename V, typename G>
    void discover_vertex(V v, G const&) const {
        if (v == target_v) throw FoundTarget{};
    }
};

int main() {
    // zero bytes of graph state
    LazyMathGraph g;

    // operations needed to reach 23 from 1               
    constexpr std::uint64_t target_v = 23; 

    // Vertices live in maps because we cannot index a vector by an unbounded integer.
    std::map<std::uint64_t, boost::default_color_type> color;
    std::map<std::uint64_t, std::uint64_t>             pred;
    std::map<std::uint64_t, std::uint64_t>             dist;
    dist[1] = 0;

    auto color_pm = boost::make_assoc_property_map(color);
    boost::queue<std::uint64_t> Q;
    LazyBFSVisitor vis(target_v, pred, dist);

    try {
        boost::breadth_first_visit(g, std::uint64_t{1}, Q, vis, color_pm);
        std::cout << "Target " << target_v << " was not reached.\n";
        return 1;
    } catch (FoundTarget const&) {
        // Reconstruct path from target back to 1 via the predecessor map
        std::vector<std::uint64_t> path;
        for (auto v = target_v; v != 1; v = pred[v]) path.push_back(v);
        path.push_back(1);

        std::cout << "Minimum operations from 1 to " << target_v << ": " << dist[target_v] << "\n";
        std::cout << "Path: ";
        for (auto it = path.rbegin(); it != path.rend(); ++it) {
            std::cout << *it;
            if (std::next(it) != path.rend()) std::cout << " -> ";
        }
        std::cout << "\n";
        return 0;
    }
}

Output:

Minimum operations from 1 to 23: 7
Path: 1 -> 2 -> 4 -> 5 -> 10 -> 11 -> 22 -> 23