I am currently working with the C++ Boost Graph Library and have the following typedef:
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS> Graph;
An algorithm from an external library I need to call expects the following input:
void external_library(int num_nodes, int *xadj, int *adjncy)
Is there a way I can somehow extract the pointers to the raw arrays/vectors of the adjacency list of the Graph object?
I'm going to assume the external library expects the sparse graph representation like the one seen in GKLib also used in Metis library: https://github.com/KarypisLab/GKlib/blob/master/gk_struct.h#L94-L105
/*-------------------------------------------------------------
* The following data structure stores a sparse graph
*-------------------------------------------------------------*/
typedef struct gk_graph_t {
int32_t nvtxs; /*!< The number of vertices in the graph */
ssize_t *xadj; /*!< The ptr-structure of the adjncy list */
int32_t *adjncy; /*!< The adjacency list of the graph */
// ...
} gk_graph_t;
Boost Graph wasn't really designed for this purpose. Instead, you can probably better adapt the GK/Metis format to satisfy BGL requirements.
If you insist, the best you can do is to convert your BGL graph to the required representation. E.g.:
void wrap_external_library(Graph const& g) {
std::vector<ssize_t> xadj(num_vertices(g) + 1);
std::vector<int> adjncy(num_edges(g) * 2);
auto out = xadj.data();
size_t idx = 0;
for (*out++ = idx; auto v : boost::make_iterator_range(vertices(g))) {
for (auto u : boost::make_iterator_range(adjacent_vertices(v, g)))
adjncy.at(idx++) = u;
*out++ = idx;
}
::external_library(num_vertices(g), xadj.data(), adjncy.data());
}
I've reverse engineered the semantics using GKlib's gk_graph_Read for the GK_GRAPH_FMT_METIS format.
Here is a sample program that first uses gk_read_Graph to read a sample graph from a text file, and then creates the SAME graph using BGL adjacency_list and sees that wrap_external_library causes ::external_library to be invoked with identical data:
#include <fmt/ranges.h>
#include <fstream>
#include <ranges>
#include <span>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
#include <GKlib.h> // this pollutes the global namespace so keep last
using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>;
void external_library(int nvtxs, ssize_t* xadj, int* adjncy) {
fmt::print("\nexternal_library nvtxs: {}, nedges: {}\n", nvtxs, xadj[nvtxs]);
auto index = std::span(xadj, nvtxs + 1) | std::views::pairwise;
fmt::print("xadj: {}\n", index);
fmt::print("adjncy: {}\n", std::span(adjncy, xadj[nvtxs]));
for (int v = 0; auto [f, l] : index)
fmt::print(" vertex {} has {} neighbours: {}\n", v++, l - f, std::span(adjncy + f, l - f));
}
void wrap_external_library(Graph const& g) {
std::vector<ssize_t> xadj(num_vertices(g) + 1);
std::vector<int> adjncy(num_edges(g) * 2);
auto out = xadj.data();
size_t idx = 0;
for (*out++ = idx; auto v : boost::make_iterator_range(vertices(g))) {
for (auto u : boost::make_iterator_range(adjacent_vertices(v, g)))
adjncy.at(idx++) = u;
*out++ = idx;
}
::external_library(num_vertices(g), xadj.data(), adjncy.data());
}
int main() {
{
char fname[] = "graph.metis";
std::ofstream(fname) << R"(% METIS graph example
% reverse engineered from gk_graph_Read
4 4
2 3
1 3
2 1 4
3)";
struct gk_graph_t* gk = ::gk_graph_Read(fname, GK_GRAPH_FMT_METIS, 0, 0, 0, 0, 0);
::external_library(gk->nvtxs, gk->xadj, gk->adjncy);
::gk_graph_Free(&gk);
}
{
Graph g;
add_edge(0, 1, g);
add_edge(1, 2, g);
add_edge(2, 0, g);
add_edge(2, 3, g);
print_graph(g, std::cout << "\nUsing Boost.Graph print_graph:\n");
wrap_external_library(g);
}
}
Printing:
external_library nvtxs: 4, nedges: 8
xadj: [(0, 2), (2, 4), (4, 7), (7, 8)]
adjncy: [1, 2, 0, 2, 1, 0, 3, 2]
vertex 0 has 2 neighbours: [1, 2]
vertex 1 has 2 neighbours: [0, 2]
vertex 2 has 3 neighbours: [1, 0, 3]
vertex 3 has 1 neighbours: [2]
Using Boost.Graph print_graph:
0 <--> 1 2
1 <--> 0 2
2 <--> 1 0 3
3 <--> 2
external_library nvtxs: 4, nedges: 8
xadj: [(0, 2), (2, 4), (4, 7), (7, 8)]
adjncy: [1, 2, 0, 2, 1, 0, 3, 2]
vertex 0 has 2 neighbours: [1, 2]
vertex 1 has 2 neighbours: [0, 2]
vertex 2 has 3 neighbours: [1, 0, 3]
vertex 3 has 1 neighbours: [2]
To compile the above I installed GKlib according to https://github.com/KarypisLab/GKlib instructions and used this CMakeLists.txt:
cmake_minimum_required(VERSION 3.19)
project(sotest)
set(CMAKE_CXX_STANDARD 23)
set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -Wall -Wextra -pedantic")
set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -fsanitize=address -fsanitize=leak -fsanitize=undefined")
include_directories(/home/sehe/local/include)
link_directories(/home/sehe/local/lib)
find_package(Boost CONFIG 1.64.0 COMPONENTS headers)
link_libraries(Boost::headers)
add_executable(sotest test.cpp)
target_link_libraries(sotest metis GKlib)
add_subdirectory(deps/fmt)
target_link_libraries(sotest fmt::fmt)