Modifying Vertex Properties in a Boost::Graph

Time complexity/performance of edge and vertex properties in Boost Graph

is it guaranteed that access to the name of a vertex and weight of an edge are efficient and fast under random access like so:

Yes. The properties are actually stored inline with the vertex/edge node. A descriptor is effectively a type erased pointer to that node. name_map[*vi] ends up inlining to something like get<N>(*static_cast<storage_node*>(vi)) if you imagine the property storage as a kind of tuple with a get<> accessor¹.

Part of my confusion comes from general std::map characteristic that it too does not support random access

Property maps are not like std::map; They may be consecutive, they may be node-based, ordered, unordered, or even calculated. In fact Boost Property Map maybe closer to the concept of a Lense in some functional programming languages. It is a set of functions that can be used to model (mutable) projections for a given key type.

Curiosity Wins... Code Gen

Let's see what code gets generated:

Live On Compiler Explorer

#include <boost/graph/adjacency_list.hpp>
#include <fmt/format.h>

using G =
    boost::adjacency_list<boost::listS, // out edges stored as list
                        boost::listS, // vertices stored as list
                        boost::directedS,
                        boost::property<boost::vertex_name_t, std::string>,
                        boost::property<boost::edge_weight_t, double>>;

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

void test(V v, E e, G const& g) {
    auto name   = get(boost::vertex_name, g);
    auto weight = get(boost::edge_weight, g);

    fmt::print("{} {}\n", name[v], weight[e]);
}

int main()
{
    G g;
    E e = add_edge(add_vertex({"foo"}, g), add_vertex({"bar"}, g), {42}, g).first;

    test(vertex(0, g), e, g);
}

Prints

foo 42

But more interestingly, the codegen:

test(void*, boost::detail::edge_desc_impl<boost::directed_tag, void*>, boost::adjacency_list<boost::listS, boost::listS, boost::directedS, boost::property<boost::vertex_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property>, boost::property<boost::edge_weight_t, double, boost::no_property>, boost::no_property, boost::listS> const&): # @test(void*, boost::detail::edge_desc_impl<boost::directed_tag, void*>, boost::adjacency_list<boost::listS, boost::listS, boost::directedS, boost::property<boost::vertex_name_t, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, boost::no_property>, boost::property<boost::edge_weight_t, double, boost::no_property>, boost::no_property, boost::listS> const&)
  sub rsp, 40
  mov rax, qword ptr [rsp + 64]
  movups xmm0, xmmword ptr [rdi + 24]
  mov rax, qword ptr [rax]
  movaps xmmword ptr [rsp], xmm0
  mov qword ptr [rsp + 16], rax
  mov rcx, rsp
  mov edi, offset .L.str
  mov esi, 6
  mov edx, 173
  call fmt::v7::vprint(fmt::v7::basic_string_view<char>, fmt::v7::format_args)
  add rsp, 40
  ret

You see, no algorithmic overhead, just dereferences.

¹ In reality, the properties are stored in a kind of Lisp-like list type that end up behaving similarly to a tuple. Boost Graph predates tuples by considerable time margin. I suppose if you want one can compare it closely to Boost Fusion's map type (which also has a type key).

How to modify properties while proceeding BFS in Boost Graph Library?

You could make the fields mutable

class Node
{
    void AssignPlane(Plane& p) const;
    Plane* mutable dp;
    double mutable errors;
}

void Node::AssignPlane(Plane& p) const
{
    dp=&p;
    errors=p.a+p.b+p.c;// simplified
}

Otherwise, consider holding a non-const "reference" to the graph inside the visitor:

struct NVisitor: default_bfs_visitor
{
    NGraph* gref_;
    NVisitor(NGraph& g) : gref_(&g) {}

    void discover_vertex(VertexDesc u, const NGraph& g) const
    {
        Plane* p = /*get it somewhere*/;
        (*gref_)[u].AssignPlane(p);
    }
}

Be careful not to break the invariants for BFS (like, don't edit edges while traversing).

Dynamic allocation usign Boost Graph vertex properties

Ok, depht_first_visit must work on constant graphs. However, obviously constant graphs cannot be modified.

So, you want to tell your visitor a non-constant reference to your graph so you can modify through that.

I'd propose the following minimal change:

Live On Coliru

#include <iostream>
#include <fstream>
#include <boost/graph/graphml.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>

//#include "cgfnode.h"
enum S{standby};
enum M{normal};

struct custom_node{
    custom_node(std::string, int, S, M){}
};
void usage(){}

using namespace boost;

struct VertexProperties {
    std::string vertex_name;
    bool node_logic;
    std::unique_ptr<custom_node> node;
};

typedef adjacency_list<vecS, vecS, directedS, VertexProperties> DirectedGraph;
typedef graph_traits<DirectedGraph>::vertex_descriptor custom_vertex;
typedef graph_traits<DirectedGraph>::edge_descriptor custom_edge;

struct custom_dfs_visitor : default_dfs_visitor {
    custom_dfs_visitor(DirectedGraph& g) : _mutable_graph(&g) {}

    void discover_vertex(custom_vertex v, DirectedGraph const& g) const {
        assert(&g == _mutable_graph);
        return discover_vertex(v, *_mutable_graph);
    }
    void discover_vertex(custom_vertex v, DirectedGraph& g) const
    {
        // Looking for adjacent vertices
        DirectedGraph::adjacency_iterator neighbourIt, neighbourEnd;

        if(g[v].node_logic) {
            g[v].node.reset(new custom_node(g[v].vertex_name, 0, standby, normal));
        }

        std::cout << g[v].vertex_name << " is connected with ";

        tie(neighbourIt, neighbourEnd) = adjacent_vertices(v, g);
        for (; neighbourIt != neighbourEnd; ++neighbourIt) {
            std::cout << g[*neighbourIt].vertex_name << " ";
        }
        std::cout << "\n";
    }

    void examine_edge(custom_edge e, const DirectedGraph& g) const {
        std::cout << "Examining edges : " << g[e.m_source].vertex_name << " >> " << g[e.m_target].vertex_name << "\n";
    }

  private:
    DirectedGraph* _mutable_graph;
};

int main() {
    DirectedGraph g;

    {
        dynamic_properties dp(ignore_other_properties);
        dp.property("node_name",  boost::get(&VertexProperties::vertex_name, g));
        dp.property("node_logic", boost::get(&VertexProperties::node_logic, g));

        std::ifstream infile("input.xml");
        boost::read_graphml(infile, g, dp);
    }

    custom_dfs_visitor vis (g);
    depth_first_search(g, boost::visitor(vis));
}

Adding custom properties to vertex of a grid in Boost Graph Library

Here's a simple example I can come up with (which also uses the properties in the output):

Live On Coliru

#include <boost/graph/grid_graph.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/graphviz.hpp>
#include <iostream>

struct sampleVertex {
    int row;
    int col;
    bool occupied;
    friend std::ostream& operator<<(std::ostream& os, sampleVertex& sv) {
        return os << "{" << sv.row << "," << sv.col << "," << sv.occupied << "}";
    }
    friend std::istream& operator>>(std::istream& is, sampleVertex& sv) {
        return is >> sv.row >> sv.col >> sv.occupied;
    }
};

int main() {
    boost::array<int, 2> lengths = { { 3, 2 } };
    using Graph  = boost::grid_graph<2, int>;
    using Traits = boost::graph_traits<Graph>;
    using IdMap  = boost::property_map<Graph, boost::vertex_index_t>::const_type;

    Graph gridD(lengths);
    IdMap indexMap(get(boost::vertex_index, gridD));
    // properties
    boost::vector_property_map<sampleVertex, IdMap> props(num_vertices(gridD), indexMap);

    // initialize
    for (int i = 0; i < 3; ++i)
        for (int j = 0; j < 2; ++j)
            put(props, Traits::vertex_descriptor {{i, j}}, sampleVertex{i,j,false});

    // print a property
    boost::dynamic_properties dp;
    dp.property("node_id", props);
    boost::write_graphviz_dp(std::cout, gridD, dp);
}

Output:

digraph G {
"{0,0,0}";
"{1,0,0}";
"{2,0,0}";
"{0,1,0}";
"{1,1,0}";
"{2,1,0}";
"{0,0,0}"->"{1,0,0}" ;
"{1,0,0}"->"{2,0,0}" ;
"{0,1,0}"->"{1,1,0}" ;
"{1,1,0}"->"{2,1,0}" ;
"{1,0,0}"->"{0,0,0}" ;
"{2,0,0}"->"{1,0,0}" ;
"{1,1,0}"->"{0,1,0}" ;
"{2,1,0}"->"{1,1,0}" ;
"{0,0,0}"->"{0,1,0}" ;
"{1,0,0}"->"{1,1,0}" ;
"{2,0,0}"->"{2,1,0}" ;
"{0,1,0}"->"{0,0,0}" ;
"{1,1,0}"->"{1,0,0}" ;
"{2,1,0}"->"{2,0,0}" ;
}

How to use vertex dentifiers in Boost graph of size int64_t

Using vecS the vertex index is implicit. They correspond to the index in the vertex storage container, which is vector.

This means that using vertex index 1810014749 on g would be Undefined Behaviour if you have fewer than 1810014750 vertices. "Luckily" (?) for you add_edge is smart enough to detect this and resize the vector in the case of vecS container selector, so it tries to allocate enough storage for the highest vertex id mentioned before adding the edge, which fails because your program doesn't have access to that much memory:

    at /usr/include/c++/10/ext/new_allocator.h:115
115             return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp)));

Here, 1810014750 * sizeof(_Tp) is 14,48 GB.

Other than that, 64 bits is no problem, since the vertex descriptor would already be 64 (albeit unsigned):

using V = UndirectedOSMIdGraph::vertex_descriptor;

static_assert(not std::is_same_v<osm_id_t, V>);
static_assert(std::is_same_v<std::make_unsigned_t<osm_id_t>, V>);
static_assert(sizeof(osm_id_t) == sizeof(V));

So as long as you don't actually use negative osm_id_t there was no technical barrier to using osm_id_t as the index.

"Sparse" vertex index

If your vertex index isn't dense then vecS might be less suited for your storage. Consider using something else:

Live On Compiler Exlorer

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>

using osm_id_t = int64_t;

using UndirectedOSMIdGraph = boost::adjacency_list<
    boost::vecS, boost::listS, boost::undirectedS,
    boost::property<
        boost::vertex_index_t, osm_id_t,
        boost::property<boost::vertex_color_t, boost::default_color_type>>,
    boost::no_property>;

using V = UndirectedOSMIdGraph::vertex_descriptor;

static_assert(not std::is_same_v<std::make_unsigned_t<osm_id_t>, V>);

int main() {
    UndirectedOSMIdGraph g;

    osm_id_t large{1810014749};
    auto     v2 = add_vertex(2, g);
    add_edge(add_vertex(large, g), v2, g);
    add_edge(v2, add_vertex(3, g), g);

    print_graph(g);
}

Prints

2 <--> 1810014749 3 
1810014749 <--> 2 
3 <--> 2

adding custom vertices to a boost graph

I don't understand what you want to do exactly. Do you want to associate some data to vertices? Then use bundled properties.

//Define a class that has the data you want to associate to every vertex and edge
struct Vertex{ int foo;}
struct Edge{std::string blah;}

//Define the graph using those classes
typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS, Vertex, Edge > Graph;
//Some typedefs for simplicity
typedef boost::graph_traits<Graph>::vertex_descriptor vertex_t;
typedef boost::graph_traits<Graph>::edge_descriptor edge_t;

//Instanciate a graph
Graph g;

// Create two vertices in that graph
vertex_t u = boost::add_vertex(g);
vertex_t v = boost::add_vertex(g);

// Create an edge conecting those two vertices
edge_t e; bool b;
boost::tie(e,b) = boost::add_edge(u,v,g);

// Set the properties of a vertex and the edge
g[u].foo = 42;
g[e].blah = "Hello world";

The are other ways to set the properties, but there you a have an example to bootstrap.

I hope I didn't misunderstand the question.