What is needed to use BGL algorithms on existing data structures ( edges and vertices as vector<Object *>)?

Question

I have custom data structures like this :

vector<myVertex *> my_vertices;
vector<myEdge *> my_edges;

My class myEdge has source() and target() methods, returning myVertex*, so it should be quite ready as is, right?

What external adaptation do I need to do to use a BGL graph with my containers? I am aware of the adaptor examples in the doc, yet some help would be much appreciated!

I am interested is the sheer adjacency_list basic-graph type, not sure about the graph traversal concepts I need yet.

What I understood so far about the adjacency_list parameters :

adjacency_list<OutEdgeListS, VertexListS, DirectedS,
             VertexProperty, EdgeProperty, GraphProperty, EdgeListS>

• OutEdgeListS and VertexListS are selectors for the containers used to represent the (1) edge-list for each of the vertices, and (2) the vertex list. These containers hold as elements vertex_descriptor and edge_descriptor respectively. My container type is the simple std::vector, so I guess I do not need to create a new container type as in example/container_gen.cpp. I must need to simply precise, probably with graph_traits, that the type of my container elements is pointer-to-object.
• VertexProperty and EdgeProperty are intended to be used as internal bulk storage for additional information, for example color tags, edge weights... and offer since a few years the bundled-property feature.

I would like the vertex and edge descriptors to not default to integers, but to be pointers to my objects. BGL documentation explicitly states that this is feasible in the 2002-version of the book, 12.1.2 :

An object-oriented graph implementation might use pointers to heap allocated vertex objects. With the graph traits class, these differences are hidden by the vertex descriptor associated type.

Although it seems to have disapeared from the current 1.70 online doc.

I would ideally like to initialize like this :

MyGraph g(const& my_edges,const& my_vertices,
  undirected_tag, some_color, someweights, allow_parallel_edges_tag);

P.S. I am not interested in stuffing object pointers in the property_map. I am willing to not use 'default vecS', a std::vector where the descriptor is an integer. I am willing to use a 'custom vecS' as a std::vector of object pointers ; for both OutEdgeList and VertexList.

Edit : this is the same exact question as the "1." of this one. Except that it never got answered... and the proposed solution was for "2.", with property_map and expensive double mapping :). It looks, after having digged hundreds of SO topics for hours, that most people recommend using property_maps rather than working with custom containers. People tend to use property_maps to store the actual nodes and edges - their object pointers, and let the vertex&edge_descriptors hold sheer default integer indexes. Yet, from what I read here, there is "below" vertex_descriptor a real-index layer internal to boost.

As context : I plan to use dijkstra/johnson_all_pairs_shortest_paths (with predecessor map and a visitor?), and further optimal-dreyfus-wagner for steiner trees with http://paal.mimuw.edu.pl/, a library on top of the bgl. To make a sql join-solver for the dbms-erd tool pgmodeler https://github.com/pgmodeler/pgmodeler/pull/1232.

20/05/19 : Replying to sehe's answer

Awesome piece of information, that glues all pieces together and made me catch up on some core points such as graph concepts. I came asking how to use adjacency list with custom data structures, and you went to explain how to define an entirely custom graph.

I am about to study tradeoffs between approaches :

1. keep my data structures as is, and your solution of a custom graph. I will be spending quite to no time initializing, but probably a lot more time finding out-edges. Low space complexity, but high time complexity.
2. Same approach, but refactor my library, add dedicated storage, with a vector of incident edges per vertex (as a class attribute of myVertex?). Constant-time out-edge lookup rather than O(log(n)) with (1) std::equal_range ? Probably the best option.
3. Use an adjacency_list but and have the bgl time-complexity guarantees.
   • Instantiate a default adjacency list, setup dual-way mapping with my library containers / use bundled/internal properties. High space complexity ; low time complexity but for the bgl algos only, initialization will be long.
   • Do you care to also elaborate if having a proper OutEdgeList and VertexList makes using the adjacency-list class with custom containers an option ? Keeping references to those lasts ? I suspect at this point that the implementation of adjacency_list might not be that flexible.

Lindquist

Care to narrow this down to a specific minimal reproducible example using #include <boost/graph/????_graph.hpp>? I can take a stab at it. I know the general principles. Wait ... that link you said never got answered has an accepted answer with upvotes. – Desertion

This uses bundled properties, it works but I am forced to copy vertices and edges one at a time, when the data structures are already here ready to go framabin.org/p/?38454294b9eecc09#fONu/B/xaGhaXk6Dlf/3/ehs/…. This tries to use custom containers, and I am very far from getting it right : framabin.org/p/…. The accepted answer throws the leda file as RTFM, and runs away toward the "bundle workaround". – Lindquist

Good run-down with the responses. 1. The time complexity cost might not be too bad. It depends on scale and distribution (log(N) is pretty swift IF your edges are indeed ordered. It would not be hard to add a little lookup cache on the Glue wrapper constructor (MyGraph). – Army

I agree 2. is probably optimal and conceptually cleanest (it does require BGL specific code but it would be unintrusive so the tight coupling is avoided). – Army

3. [ad 1st bullet] simplist if you don't have to modify the graph often and keep the mappings around seems the least code/catering to BGL magic. You'll be most able to leverage e.g. existing body of work on StackOverflow – Army

3. [ad 2nd bullet] I agree it's not gonna be flexible enough. I think regardless of how you spin it, adjacency_list will assume it can construct the out-edge-list container (so references are out) and even if you get it to use a "fake container wrapper" to actually refer to your vertex list that would probably violate some assumptions in the library. I think by definition Graph Models have value semantics in BGL). Not worth it? – Army

Answer 1

The documentation for the Graph concepts is conveniently here: https://www.boost.org/doc/libs/1_70_0/libs/graph/doc/graph_concepts.html

So - you never told us what algorithms you intend to use.

So let me pick an examples: BFS. The docs say it requires:

A directed or undirected graph. The graph type must be a model of Vertex List Graph and Incidence Graph.

Looking at your pre-existing data structures, it looks like you only cover the Vertex List use case easily.

The edges are implemented more as an Edge List. It's not possible to emulate Incidence Graph from Edge List without runtime or storage overhead (that's mathematics, nothing to do with library or code quality).

In reality, it's pretty likely that you omitted parts of your pre-existing data-structures that are relevant to the problem, as most algorithms will be highly sub-optimal on just Vertex+Edge lists.

In practice I suppose you Edge list might be organized like a classical adjacency list (e.g. ordering by source vertex, so you CAN have a O(log(n)) lookup by source vertex).

For the example below I'm assuming this is the case. Keep in mind we're only approaching the complexity guarantees from Incidence Graph Concept:

Complexity guarantees

The source(), target(), and out_edges() functions must all be constant time. The out_degree() function must be linear in the number of out-edges.

To actually meet these requirements, you will need to have dedicated storage of out-edges per vertex

So, let'st have a go:

Mocking YourLibrary

namespace YourLibrary {
    struct myVertex {
    };

    struct myEdge {
        myVertex* _s = nullptr;
        myVertex* _t = nullptr;

        myVertex* source() const { return _s; }
        myVertex* target() const { return _t; }
    };

    using Vertices = std::vector<myVertex *>;
    using Edges = std::vector<myEdge *>;
}

Fulfilling the Graph Concepts

You wanted to keep references to the pre-existing data structures:

namespace Glue {

    struct MyGraph {
        struct EdgeOrder {
            template <typename A, typename B>
                bool operator()(A const* a, B const* b) const { return source(a) < source(b); }
            private:
            static auto source(YourLibrary::myVertex const* v) { return v; }
            static auto source(YourLibrary::myEdge const* e) { return e->source(); }
        };

        using Vertices = YourLibrary::Vertices;
        using Edges = YourLibrary::Edges;

        Vertices& _vertices;
        Edges& _edges;

        MyGraph(Vertices& vv, Edges& ee) : _vertices(vv), _edges(ee)  { }
    };
}

Now, I'll just run down the list of required trait types per concept:

namespace boost {

    template <> struct graph_traits<Glue::MyGraph> {
        // Due to Graph concept
        using vertex_descriptor      = YourLibrary::myVertex*;
        using edge_descriptor        = YourLibrary::myEdge*;
        using directed_category      = directed_tag;
        using edge_parallel_category = allow_parallel_edge_tag;
        static vertex_descriptor null_vertex() { return nullptr; }

        // Due to Vertex List concept
        struct traversal_category : vertex_list_graph_tag, incidence_graph_tag { };
        using vertex_iterator        = Glue::MyGraph::Vertices::const_iterator;
        using vertices_size_type     = std::size_t;

        // Due to Incidence Graph concept
        using out_edge_iterator = Glue::MyGraph::Edges::const_iterator;
        using degree_size_type = std::size_t;
    };

}

And finally re-open the namespace so ADL can find these functions that are required to satisfy the "valid expressions" criteria:

namespace Glue {
    // Due to Vertex List concept
    auto vertices(MyGraph const& g) {
        return std::make_pair(g._vertices.begin(), g._vertices.end());
    }

    std::size_t num_vertices(MyGraph const& g) {
        return g._vertices.size();
    }

    // Due to Incidence Graph concept
    auto source(YourLibrary::myEdge const* e, MyGraph const& g) {
        return e->source();
    }
    auto target(YourLibrary::myEdge const* e, MyGraph const& g) {
        return e->target();
    }

    auto out_edges(YourLibrary::myVertex const* v, MyGraph const& g) {
        return std::equal_range(g._edges.begin(), g._edges.end(), v, MyGraph::EdgeOrder{});;
    }
    std::size_t out_degree(YourLibrary::myVertex const* v, MyGraph const& g) {
        auto oee = std::equal_range(g._edges.begin(), g._edges.end(), v, MyGraph::EdgeOrder{});
        return std::distance(oee.first, oee.second);
    }
}

This would be roughly functionally equivalent to an adjacency_list with a setS for the vertex container.

See it Live On Coliru

Running BFS

All that's required in addition is for the arguments of the algorithm. You'd need both the color map and the vertex index map. This is completely normal and would also be required if you had e.g. adjacency_list<vecS, listS, directedS>.

I'll hide the index map inside the MyGraph wrapper and expose the color map so you can pick your preference:

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/container/flat_map.hpp>
#include <algorithm>

namespace YourLibrary {
    struct myVertex {
    };

    struct myEdge {
        myVertex* _s = nullptr;
        myVertex* _t = nullptr;

        myVertex* source() const { return _s; }
        myVertex* target() const { return _t; }
    };

    using Vertices = std::vector<myVertex *>;
    using Edges = std::vector<myEdge *>;
}

namespace Glue {

    struct MyGraph {
        struct EdgeOrder {
            template <typename A, typename B>
                bool operator()(A const* a, B const* b) const { return source(a) < source(b); }
            private:
            static auto source(YourLibrary::myVertex const* v) { return v; }
            static auto source(YourLibrary::myEdge const* e) { return e->source(); }
        };

        using Vertices = YourLibrary::Vertices;
        using Edges = YourLibrary::Edges;

        using Index = boost::container::flat_map<Vertices::value_type, std::size_t>;

        Vertices& _vertices;
        Edges& _edges;
        Index _index;

        MyGraph(Vertices& vv, Edges& ee) : _vertices(vv), _edges(ee)  {
            _index.reserve(vv.size());
            std::size_t i = 0;
            for(auto v : vv) { _index[v] = i++; }
        }
    };
}

namespace boost {

    template <> struct graph_traits<Glue::MyGraph> {
        // Due to Graph concept
        using vertex_descriptor      = YourLibrary::myVertex*;
        using edge_descriptor        = YourLibrary::myEdge*;
        using directed_category      = directed_tag;
        using edge_parallel_category = allow_parallel_edge_tag;
        static vertex_descriptor null_vertex() { return nullptr; }

        // Due to Vertex List concept
        struct traversal_category : vertex_list_graph_tag, incidence_graph_tag { };
        using vertex_iterator        = Glue::MyGraph::Vertices::const_iterator;
        using vertices_size_type     = std::size_t;

        // Due to Incidence Graph concept
        using out_edge_iterator = Glue::MyGraph::Edges::const_iterator;
        using degree_size_type = std::size_t;
    };

}

namespace Glue {
    // Due to Vertex List concept
    auto vertices(MyGraph const& g) {
        return std::make_pair(g._vertices.begin(), g._vertices.end());
    }

    std::size_t num_vertices(MyGraph const& g) {
        return g._vertices.size();
    }

    // Due to Incidence Graph concept
    auto source(YourLibrary::myEdge const* e, MyGraph const& g) {
        return e->source();
    }
    auto target(YourLibrary::myEdge const* e, MyGraph const& g) {
        return e->target();
    }

    auto out_edges(YourLibrary::myVertex const* v, MyGraph const& g) {
        return std::equal_range(g._edges.begin(), g._edges.end(), v, MyGraph::EdgeOrder{});;
    }
    std::size_t out_degree(YourLibrary::myVertex const* v, MyGraph const& g) {
        auto oee = std::equal_range(g._edges.begin(), g._edges.end(), v, MyGraph::EdgeOrder{});
        return std::distance(oee.first, oee.second);
    }

    // Due to BFD requiring the index_map
    auto get(boost::vertex_index_t, MyGraph const& g) {
        return boost::make_assoc_property_map(g._index);
    }
}

int main() {
    // I hate manual memory management, so let's own some objects
    auto a = std::make_unique<YourLibrary::myVertex>();
    auto b = std::make_unique<YourLibrary::myVertex>();
    auto c = std::make_unique<YourLibrary::myVertex>();
    auto ab = std::make_unique<YourLibrary::myEdge>(YourLibrary::myEdge{a.get(), b.get()});
    auto bc = std::make_unique<YourLibrary::myEdge>(YourLibrary::myEdge{b.get(), c.get()});

    // These were given in your question:
    YourLibrary::Vertices vv { a.get(), b.get(), c.get() };
    YourLibrary::Edges ee { ab.get(), bc.get() };

    // this is the glue required to fulfill the BGL concepts:
    Glue::MyGraph g(vv, ee);

    // this is showing that you can now BFS on it
    using V = boost::graph_traits<Glue::MyGraph>::vertex_descriptor;
    V start_vertex = a.get();
    std::map<V, boost::default_color_type> color_data;

    boost::breadth_first_search(g, start_vertex,
            boost::visitor(boost::default_bfs_visitor{})
            .color_map(boost::make_assoc_property_map(color_data)));
}

Conclusion

Algorithms have requirements, and as long as you satisfy them, you can use whatever data structure you want.

In this case you MIGHT want to be really sure about the assumptions made and add this to the MyGraph constructor:

assert(std::is_sorted(_edges.begin(), _edges.end(), EdgeOrder{}));

Army

Sorry, in the dirty history of edits on this post, I added the context at the bottom and a bit late. Thank you for the detailed answer, tackling reading. – Lindquist

As stackoverflow now really discourages forum-style threads... I appended, to my original question, my reaction to your great answer. – Lindquist

Yeah. I think that didn't actually solve it. I went along though and commented bullet-by-bullet. In the future, and in the interest of future visitors looking for answers, you could post a new question. This is /more work/ and harder to pose the question usefully, but at least it makes us think about the bigger picture and the value of the questions to the general public :) Cheers – Army

Thanks for this detailed answer, it was very helpful for my understanding. One thing I'm still trying to understand is why this example doesn't work with functions like boost::out_edges? It seems like it ought to work since Glue::MyGraph models the IncidenceGraph concept, but I get type deduction errors on boost::out_edges(start_vertex, g); -- maybe I'm missing something obvious? – Ransom

@Ransom You need to use ADL: Live On Coliru boost::edges is actually not implemented for our graph type. The concept requirements say that out_edges(v, g) should compile, not boost::out_edges(v, g). – Army

Thank you for pointing that out; this not the first time I've been tripped by by ADL. Another question: depth_first_search works with your example, but topological_sort, which is mostly a call to dfs but with a bgl_named_params visitor, doesn't. Do you know what would be required to adapt this example in this case? I am not at all familiar with named params yet, so I have some reading to do in the meantime. – Ransom

@Ransom Did you make all args named? Like this. BGL does require a very accute attention to detail. Personally, I'm not fond of the named arguments thing (but I guess it has something to do with python-bgl interfacing) – Army

I missed the question on topological sort. I think that merits a separate question on the main site. I think topological sort requires a vertex index (mapping vertices to [0..num_vertices(g))) and that's not in the code right now. – Army

Asked. – Ransom