C++ Boost kamada_kawai_spring_layout Problem

Question

To achieve a planar embedding with fixed positions for some vertices,

1. I am currently using the force-directed layout method. Is this approach feasible?
2. I am currently facing an issue with compiling the kamada_kawai_spring_layout from the Boost library.

typedef geometry::model::point<double, 2, geometry::cs::cartesian> point ;
typedef boost::adjacency_list<
boost::vecS,
boost::vecS,
boost::undirectedS,
boost::property<boost::vertex_index_t, int>,
boost::property<boost::edge_index_t, int,
boost::property<boost::edge_weight_t, int> >
graph;
graph g(this->HubSet.size());

//Add edge
map<pairs,int>::iterator iter;
for(iter = this->edge.begin() ; iter != this->edge.end() ; iter++)
{
   pairs tmpPair = iter->first;
   add_edge(tmpPair.first, tmpPair.second, 1.0, g);
}

//Position Map
typedef vector<point> PositionMap;
PositionMap position(num_vertices(g));
position[33] = point(250.0, 2000.0);
position[35] = point(8000.0, 2000.0);
auto position_map = boost::make_iterator_property_map(position.begin(), get(boost::vertex_index, g));

//Topology
std::minstd_rand gen;
rectangle_topology<std::minstd_rand> topo(gen, 0.0, 0.0, 9000.0, 9000.0);
random_graph_layout(g, position_map, topo);

//Call Force directed algorithm
boost::kamada_kawai_spring_layout(g,
                                  position_map,
                                  get(edge_weight, g),
                                  topo,
                                  edge_length(100.0) );

I would like to inquire about an issue with my code compilation. Could you please help me identify the modifications needed for successful compilation?

Answer 1

It’s impossible to figure out what error you are getting, because you post incomplete code.

If I make up some of the missing code my best guess is that your position map fails to match the documented criteria:

The type PositionMap must be a model of Writable Property Map, with the graph's vertex descriptor type as its key type and Topology::point_type as its value type.

So, instead use:

using Topology = boost::rectangle_topology<std::minstd_rand>;
using Point    = Topology::point_type;

Then, when we also make the edge weight arithmetically compatible with the coordinate types, this has the potential to compile:

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/kamada_kawai_spring_layout.hpp>
#include <boost/graph/random_layout.hpp>
#include <random>

using Topology = boost::rectangle_topology<std::minstd_rand>;
using Point    = Topology::point_type;
using Graph    = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS,              //
                                    boost::property<boost::vertex_index_t, int>,                  //
                                    boost::property<boost::edge_index_t, int,                     //
                                                    boost::property<boost::edge_weight_t, double> //
                                                    >>;
struct Program {
    std::vector<int> HubSet;
    using pairs = std::pair<size_t, size_t>;
    std::map<pairs, int> edge;

    Program()
        : HubSet(42) // no clue, just made it big enough for position[35] to be a valid index
    {}

    void foo() {
        Graph g(this->HubSet.size());

        // Add edge
        std::map<pairs, int>::iterator iter;
        for (iter = this->edge.begin(); iter != this->edge.end(); iter++) {
            pairs tmpPair = iter->first;
            add_edge(tmpPair.first, tmpPair.second, 1.0, g);
        }

        // Position Map
        using PositionMap = std::vector<Point>;
        PositionMap position(num_vertices(g));

        auto make_point = [](double x, double y) {
            Point p;
            p[0] = x;
            p[1] = y;
            return p;
        };
        position[33] = make_point(250.0, 2000.0);
        position[35] = make_point(8000.0, 2000.0);
        auto position_map = boost::make_iterator_property_map(position.begin(), get(boost::vertex_index, g));

        // Topology
        std::minstd_rand gen;
        Topology         topo(gen, 0.0, 0.0, 9000.0, 9000.0);
        random_graph_layout(g, position_map, topo);

        // Call Force directed algorithm
        boost::kamada_kawai_spring_layout(g, position_map, get(boost::edge_weight, g), topo,
                                          boost::edge_length(100.0));
    }
};

int main() {
    Program p;
    p.foo();
}

BONUS

If you MUST have geometry support down the road, you can adapt the point type:

#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
#include <boost/geometry/geometries/register/point.hpp>

namespace bg = boost::geometry;
using Point  = Topology::point_type;

namespace boost::geometry::traits {
    template<> struct tag<Point>               { using type = point_tag;         };
    template<> struct coordinate_type<Point>   { using type = double;            };
    template<> struct coordinate_system<Point> { using type = bg::cs::cartesian; };
    template<> struct dimension<Point> : std::integral_constant<std::size_t, 2> {};
    template<> struct access<Point, 0> {
        static inline double get(Point const& p) { return p[0]; }
        static inline void   set(Point& p, double const& value) { p[0] = value; }
    };
    template <> struct access<Point, 1> {
        static inline double get(Point const& p) { return p[1]; }
        static inline void   set(Point& p, double const& value) { p[1] = value; }
    };
} // namespace boost::geometry::traits

At that point you can use boost::geometry::make<Point>(x,y) instead of the bespoke lambda.