1

I'm using BGL to build a graph storing bundled vertices where one type of vertex stores a reference to the other vertex type. Both types are handled using std::variant:

struct simple_node_t {
    size_t enabled;
};

struct complex_node_t {
    bool foo1;
    size_t foo2;
    simple_node_t& control;
};

using vertex_t = std::variant<simple_node_t, complex_node_t>;

using netListGraph_t = boost::adjacency_list<
    boost::vecS,
    boost::vecS,
    boost::undirectedS,
    vertex_t>;

Vertices of type complex_node_t are created and stored like this:

// Create node
complex_node_t cpx = {
    true,
    0xDEADBEEF,
    std::get<simple_node_t>(mGraph[desc_to_simple_vertex])
};

// Add complex_node_t to graph
vertex_t vtx(cpx);
auto vertex = boost::add_vertex(vtx, mGraph);

Now the problem:

auto pVal = std::get_if<complex_node_t>(&mGraph[vertex]);

assert(pVal->foo1 == true); //OK
assert(pVal->foo2 == 0xDEADBEEF); //OK

But accessing the reference fails (invalid object)!

**pVal->control.enabled -> GARBAGE**

Storing the data by value works - but storing by reference does not.

What am I doing wrong?

PS: My example is very reduced of course... that means the vertices I want to store via reference are much bigger.

EDIT

I now changed my code:

struct complex_node_t {
    bool foo1;
    size_t foo2;
    std::reference_wrapper<simple_node_t> control;
};

and try to access elements:

if (pVal->control.get().enabled) -> **STILL GARBAGE**
fhw72
  • 1,066
  • 1
  • 11
  • 19

1 Answers1

1

If you store a reference inside a class, it is no longer assignable nor default-constructible.

BGL Has the concept of a descriptor here, it's an abstraction of something like an array index, but independent of the graph representation. So you could use those.

Beware of invalidation rules though: depending on the graph model[1]. See

PS. if you know your graph has reference stability for vertices you could do what you want replacing the reference with raw pointers or std::reference_Wrapper<>


[1] in the case of adjacency_list<> it depends on the vertex/edge container selector template arguments

Demo Code

This code demonstrates

  • the mechanics of defining the graph (with self-referential descriptor types)
  • how NOT to populate (see // BUG)
  • how to safely populate/use the attributes instead.

Live On Coliru

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

using base_traits = boost::graph_traits<boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS> >;

struct simple_node_t {
    size_t enabled = 0;
};

struct complex_node_t {
    bool foo1 = false;
    size_t foo2 = 0;
    base_traits::vertex_descriptor control {};
};

using vertex_t = std::variant<simple_node_t, complex_node_t>;

using netListGraph_t = boost::adjacency_list<
    boost::vecS,
    boost::vecS,
    boost::undirectedS,
    vertex_t>;

int main() {
    {
        netListGraph_t g;
        auto control = add_vertex(simple_node_t{12}, g);
        // BUG HERE:
        add_vertex(complex_node_t{ true, 42, control }, g); // whoops, might invalidate `control`
    }

    {
        netListGraph_t g(10);
        auto control = vertex(6, g);
        g[control] = simple_node_t{12};

        auto other   = vertex(4, g);
        g[other] = complex_node_t{ true, 42, control }; // fine

        // also fine:
        std::get<complex_node_t>(g[other]).control = control;
    }
}
sehe
  • 374,641
  • 47
  • 450
  • 633
  • Thanks! once the graph is fully built it will be stable. So I think that using std::reference_wrapper<> would be the route to go!? Do you have a short example or some hints how I should do it in this case? – fhw72 May 03 '19 at 12:59
  • I edited the question to show how I tried to solve it. But it's not working... unfortunately. Any idea? – fhw72 May 03 '19 at 14:31
  • Be aware that you need to be setting the reference _after_ the graph became stable then. Added sample to my answer – sehe May 03 '19 at 15:18
  • Thanks again! Short question: Am I right you're now storing a vertex descriptor instead of reference or did I miss something? What I tried to achieve is storing a reference to an underlying object in a variant. – fhw72 May 03 '19 at 18:31
  • Indeed, since you said "once the graph is fully built it will be stable" I would go that way. Of course you _can_ use a raw pointer (reference wrappers only work if they're never uninitialized) – sehe May 03 '19 at 23:53
  • I wanted to avoid that additional indirection and store a reference. However this is where I fail. Don't know how to do that. – fhw72 May 04 '19 at 11:41
  • 1
    Got it: I missed the point the vecS get invalidated in my case. – fhw72 May 04 '19 at 12:04