I have a an adjacency_list graph with randomly connected nodes using Erdos-Renyi edge generation.
The graph uses bundled properties by defining data structures both for the vertices (Graph_Node) and edges (Graph_Edge), which is used to assign the position of the nodes and the weights of the edges.
I'm trying to use force-directed graph drawing to assign good positions for the nodes, using kamada_kawai_spring_layout.
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/erdos_renyi_generator.hpp>
#include <boost/random/linear_congruential.hpp>
#include <boost/graph/kamada_kawai_spring_layout.hpp>
using namespace boost;
struct Graph_Node
{
typedef convex_topology<2>::point tPoint;
tPoint Position;
};
struct Graph_Edge
{
unsigned int ID;
double weight = 100.;
};
typedef adjacency_list<vecS, vecS, undirectedS, Graph_Node, Graph_Edge> Graph;
static random::minstd_rand rng;
typedef erdos_renyi_iterator<random::minstd_rand, Graph> ERGen;
static const int ER_INIT_NODES = 50;
static const double p = 0.05;
static Graph g(ERGen(rng, ER_INIT_NODES, p), ERGen(), ER_INIT_NODES);
int main()
{
ball_topology<2> T(1.);
detail::graph::edge_or_side<1, double> scaling(1.);
kamada_kawai_spring_layout(g, get(&Graph_Node::Position, g), get(&Graph_Edge::weight, g), T, scaling);
Graph::vertex_iterator v, v_end;
for (std::tie(v, v_end) = vertices(g); v != v_end; ++v)
std::cout << g[*v].Position[0] << ", " << g[*v].Position[1] << std::endl;
}
Graph_Node::Position is intended to be assigned using kamada_kawai_spring_layout, but the Position of all the vertices in g are 0,0 after assignment. Why?
The return value of the algorithm:
Returns: true if layout was successful or false if a negative weight cycle was detected or the graph is disconnected.
When you print it, you'll see that it is false. So, your graph doesn't satisfy the requirements.
Raising the edge probability makes for connected graphs:
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/circle_layout.hpp>
#include <boost/graph/erdos_renyi_generator.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/kamada_kawai_spring_layout.hpp>
#include <boost/random/linear_congruential.hpp>
#include <fmt/ranges.h>
using tPoint = boost::convex_topology<2>::point;
struct Graph_Node { tPoint Position{}; };
struct Graph_Edge { /*unsigned int ID;*/ double weight = 100; };
using Graph = boost::adjacency_list<boost::vecS, boost::vecS,
boost::undirectedS, Graph_Node, Graph_Edge>;
static constexpr int ER_INIT_NODES = 20; // 50
static constexpr double p = 1; // 0.05
Graph make_graph() {
boost::random::minstd_rand rng;
using Gen = boost::erdos_renyi_iterator<boost::random::minstd_rand, Graph>;
return {Gen(rng, ER_INIT_NODES, p), Gen(), ER_INIT_NODES};
}
int main()
{
auto g = make_graph();
//write_graphviz(std::cout, g);
auto print_position = [pos = get(&Graph_Node::Position, g)](size_t v) {
fmt::print("Vertex {:3} Position {:9.4f}, {:9.4f}\n", v, pos[v][0], pos[v][1]);
};
auto mid_vertex = vertex(ER_INIT_NODES / 2, g);
print_position(mid_vertex);
boost::circle_graph_layout(g, get(&Graph_Node::Position, g), 25.0);
if (true) { // ball-topology
print_position(mid_vertex);
bool ok = kamada_kawai_spring_layout( //
g, //
get(&Graph_Node::Position, g), //
get(&Graph_Edge::weight, g), //
boost::ball_topology<2>(1.), //
boost::detail::graph::edge_or_side<true, double>(1.) //
);
fmt::print("kamada_kawai_spring_layout ok: {}\n", ok);
} else {
print_position(mid_vertex);
bool ok = kamada_kawai_spring_layout( //
g, //
get(&Graph_Node::Position, g), //
get(&Graph_Edge::weight, g), //
boost::square_topology<>(50.0), //
boost::side_length(50.0) //
);
fmt::print("kamada_kawai_spring_layout ok: {}\n", ok);
}
print_position(mid_vertex);
fmt::print("----\n");
for (auto v : boost::make_iterator_range(vertices(g)))
print_position(v);
}
Prints
Vertex 10 Position 0.0000, 0.0000
Vertex 10 Position -25.0000, 0.0000
kamada_kawai_spring_layout ok: true
Vertex 10 Position 20.3345, -102.5760
----
Vertex 0 Position -35.8645, -19.4454
Vertex 1 Position -72.7690, -130.3436
Vertex 2 Position -8.5828, -138.2843
Vertex 3 Position -44.7830, -52.9697
Vertex 4 Position -43.0101, 30.9041
Vertex 5 Position -69.7531, 38.7188
Vertex 6 Position -0.4328, 43.2208
Vertex 7 Position 31.3758, -30.9816
Vertex 8 Position 47.1809, 12.8283
Vertex 9 Position -76.9535, 9.7684
Vertex 10 Position 20.3345, -102.5760
Vertex 11 Position -19.5602, -103.9834
Vertex 12 Position -68.2476, -78.6953
Vertex 13 Position -95.3881, -46.8710
Vertex 14 Position -131.4928, 7.9270
Vertex 15 Position 24.0966, -4.9534
Vertex 16 Position 59.0794, -86.1642
Vertex 17 Position -102.4687, -148.9986
Vertex 18 Position -10.8986, -52.8234
Vertex 19 Position -131.8706, -60.2588