CODEWITHSUNDEEP
c++boostgraphboost-graph
AIDoubt
AIDoubt

Reputation: 382

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

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>

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.

Upvotes: 6

Views: 632

Answers (1)

sehe
sehe

Reputation: 393039

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{}));

Upvotes: 7

Related Questions