I have a graph, produced using the igraph library.
Now, I would like to serialize this graph.
While igraph provides some methods to convert the graph to a file, they all lack either support for attributes, or require some specific problem background of the graph, which are all not given in my case. Additionally, this graph in the problem I am actually trying to solve is a member of a much larger class, which I serialize using the Cereal library.
With my implementation found below, AddressSanitizer reports a allocation-size-too-big issue, implying that either my implementation is incorrect, or I have misunderstood the internals of Cereal.
My attempt to have a consistent implementation looks like this:
namespace cereal {
////////////////////////////////////////////////////////////////
// serialization of igraph objects
template <class Archive>
inline void CEREAL_SAVE_FUNCTION_NAME(Archive &ar, igraph_t const &graph) {
size_t numVertices = igraph_vcount(&graph);
size_t numEdges = igraph_ecount(&graph);
igraph_vector_int_t allEdges;
igraph_vector_int_init(&allEdges, numEdges);
if (igraph_edges(&graph, igraph_ess_all(IGRAPH_EDGEORDER_ID), &allEdges)) {
throw std::runtime_error("Failed to get all edges");
}
std::vector<long int> edges;
utils::igraphVectorTToStdVector(&allEdges, edges);
igraph_vector_int_destroy(&allEdges);
ar(numVertices);
ar(numEdges);
ar(edges);
// after storing the edges, must also store the attributes
// query them first
igraph_strvector_t gnames;
igraph_strvector_init(&gnames, 1);
igraph_vector_int_t gtypes;
igraph_vector_int_init(>ypes, 1);
igraph_strvector_t vnames;
igraph_strvector_init(&vnames, 1);
igraph_vector_int_t vtypes;
igraph_vector_int_init(&vtypes, 1);
igraph_strvector_t enames;
igraph_strvector_init(&enames, 1);
igraph_vector_int_t etypes;
igraph_vector_int_init(&etypes, 1);
igraph_cattribute_list(&graph, &gnames, >ypes, &vnames, &vtypes, &enames,
&etypes);
if (igraph_strvector_size(&gnames) != 0) {
throw std::runtime_error(
"Graph attributes serialization not supported yet.");
}
// serizalize vertex attributes
size_t numVertexAttributes = igraph_strvector_size(&vnames);
ar(make_size_tag(numVertexAttributes));
for (size_t i = 0; i < numVertexAttributes; i++) {
const char *name = igraph_strvector_get(&vnames, i);
ar(std::string(name));
ar(igraph_vector_int_get(&vtypes, i));
switch (igraph_vector_int_get(&vtypes, i)) {
// case IGRAPH_ATTRIBUTE_DEFAULT:
case IGRAPH_ATTRIBUTE_NUMERIC: {
igraph_vector_t results;
igraph_vector_init(&results, numVertices);
igraph_cattribute_VANV(&graph, igraph_strvector_get(&vnames, i),
igraph_vss_all(), &results);
std::vector<double> attributes;
utils::igraphVectorTToStdVector(&results, attributes);
ar(attributes);
igraph_vector_destroy(&results);
} break;
case IGRAPH_ATTRIBUTE_STRING: {
igraph_strvector_t strresults;
igraph_strvector_init(&strresults, numVertices);
igraph_cattribute_VASV(&graph, igraph_strvector_get(&vnames, i),
igraph_vss_all(), &strresults);
std::vector<std::string> strattributes;
utils::igraphVectorTToStdVector(&strresults, strattributes);
ar(strattributes);
igraph_strvector_destroy(&strresults);
} break;
default:
throw std::runtime_error(
"This attribute type (" +
std::to_string(igraph_vector_int_get(&vtypes, i)) +
") is not supported");
}
}
// serizalize edge attributes
size_t numEdgeAttributes = igraph_strvector_size(&enames);
ar(make_size_tag(numEdgeAttributes));
for (size_t i = 0; i < numEdgeAttributes; i++) {
const char *name = igraph_strvector_get(&enames, i);
ar(std::string(name));
ar(igraph_vector_int_get(&etypes, i));
switch (igraph_vector_int_get(&etypes, i)) {
// case IGRAPH_ATTRIBUTE_DEFAULT:
case IGRAPH_ATTRIBUTE_NUMERIC: {
igraph_vector_t results;
igraph_vector_init(&results, numEdges);
igraph_cattribute_EANV(&graph, igraph_strvector_get(&enames, i),
igraph_ess_all(IGRAPH_EDGEORDER_ID), &results);
std::vector<double> attributes;
utils::igraphVectorTToStdVector(&results, attributes);
ar(attributes);
igraph_vector_destroy(&results);
} break;
case IGRAPH_ATTRIBUTE_STRING: {
igraph_strvector_t strresults;
igraph_strvector_init(&strresults, numEdges);
igraph_cattribute_EASV(&graph, igraph_strvector_get(&enames, i),
igraph_ess_all(IGRAPH_EDGEORDER_ID), &strresults);
std::vector<std::string> strattributes;
utils::igraphVectorTToStdVector(&strresults, strattributes);
ar(strattributes);
igraph_strvector_destroy(&strresults);
} break;
default:
throw std::runtime_error(
"This attribute type (" +
std::to_string(igraph_vector_int_get(&etypes, i)) +
") is not supported");
}
}
igraph_strvector_destroy(&gnames);
igraph_strvector_destroy(&enames);
igraph_strvector_destroy(&vnames);
igraph_vector_int_destroy(>ypes);
igraph_vector_int_destroy(&etypes);
igraph_vector_int_destroy(&vtypes);
}
template <class Archive>
inline void CEREAL_LOAD_FUNCTION_NAME(Archive &ar, igraph_t &graph) {
size_t numVertices;
size_t numEdges;
ar(numVertices);
ar(numEdges);
std::vector<long int> edges;
ar(edges);
igraph_vector_int_t allEdges;
igraph_vector_int_init(&allEdges, numEdges);
utils::StdVectorToIgraphVectorT(edges, &allEdges);
igraph_add_vertices(&graph, numVertices, nullptr);
igraph_add_edges(&graph, &allEdges, nullptr);
// deserialize vertex attributes
size_type numVertexAttributes;
ar(make_size_tag(numVertexAttributes));
for (size_t i = 0; i < numVertexAttributes; ++i) {
std::string attributeName;
ar(attributeName);
int attributeType;
ar(attributeType);
switch (attributeType) {
// case IGRAPH_ATTRIBUTE_DEFAULT:
case IGRAPH_ATTRIBUTE_NUMERIC: {
std::vector<double> attributes;
ar(attributes);
igraph_vector_t results;
igraph_vector_init(&results, attributes.size());
utils::StdVectorToIgraphVectorT(attributes, &results);
igraph_cattribute_VAN_setv(&graph, attributeName.c_str(), &results);
igraph_vector_destroy(&results);
}; break;
case IGRAPH_ATTRIBUTE_STRING: {
std::vector<std::string> strattributes;
ar(strattributes);
igraph_strvector_t strresults;
igraph_strvector_init(&strresults, strattributes.size());
utils::StdVectorToIgraphVectorT(strattributes, &strresults);
igraph_cattribute_VAS_setv(&graph, attributeName.c_str(), &strresults);
igraph_strvector_destroy(&strresults);
}; break;
default:
throw std::runtime_error("This attribute type (" +
std::to_string(attributeType) +
") is not supported");
}
}
// and same for edge attributes
size_type numEdgeAttributes;
ar(make_size_tag(numEdgeAttributes));
for (size_t i = 0; i < numEdgeAttributes; ++i) {
std::string attributeName;
ar(attributeName);
int attributeType;
ar(attributeType);
switch (attributeType) {
// case IGRAPH_ATTRIBUTE_DEFAULT:
case IGRAPH_ATTRIBUTE_NUMERIC: {
std::vector<double> attributes;
ar(attributes);
igraph_vector_t results;
igraph_vector_init(&results, 1);
utils::StdVectorToIgraphVectorT(attributes, &results);
igraph_cattribute_EAN_setv(&graph, attributeName.c_str(), &results);
igraph_vector_destroy(&results);
} break;
case IGRAPH_ATTRIBUTE_STRING: {
std::vector<std::string> strattributes;
ar(strattributes);
igraph_strvector_t strresults;
igraph_strvector_init(&strresults, 1);
utils::StdVectorToIgraphVectorT(strattributes, &strresults);
igraph_cattribute_EAS_setv(&graph, attributeName.c_str(), &strresults);
igraph_strvector_destroy(&strresults);
} break;
default:
throw std::runtime_error("This attribute type (" +
std::to_string(attributeType) +
") is not supported");
}
}
}
} // namespace cereal
An implementation to get up and running can be found here: https://github.com/GenieTim/igraph-cereal-serialisation
The issue with this implementation, is, as written above, that AddressSanitizer reports allocation-size-too-big when deserializing, reportedly from Cereal internals where it allocates for deserializing the attributes std::vector. Is my implementation incorrect, or is Cereal supposed to allocate so much memory, and I should simply disable the AddressSanitizer?
Here is the stack trace I get:
=================================================================
==86488==ERROR: AddressSanitizer: requested allocation size 0x4e2000000000 (0x4e2000001000 after adjustments for alignment, red zones etc.) exceeds maximum supported size of 0x10000000000 (thread T0)
#0 0x10f7f5fcd in _Znwm+0x7d (libclang_rt.asan_osx_dynamic.dylib:x86_64h+0xf0fcd)
#1 0x10ea32684 in void* std::__1::__libcpp_operator_new[abi:ue170004]<unsigned long>(unsigned long) new:268
#2 0x10ea3262c in std::__1::__libcpp_allocate[abi:ue170004](unsigned long, unsigned long) new:294
#3 0x10ea35287 in std::__1::allocator<double>::allocate[abi:ue170004](unsigned long) allocator.h:114
#4 0x10ea3517c in std::__1::__allocation_result<std::__1::allocator_traits<std::__1::allocator<double>>::pointer> std::__1::__allocate_at_least[abi:ue170004]<std::__1::allocator<double>>(std::__1::allocator<double>&, unsigned long) allocate_at_least.h:55
#5 0x10ea350c8 in std::__1::__split_buffer<double, std::__1::allocator<double>&>::__split_buffer(unsigned long, unsigned long, std::__1::allocator<double>&) __split_buffer:379
#6 0x10ea34e9c in std::__1::__split_buffer<double, std::__1::allocator<double>&>::__split_buffer(unsigned long, unsigned long, std::__1::allocator<double>&) __split_buffer:375
#7 0x10ea3a8f8 in std::__1::vector<double, std::__1::allocator<double>>::__append(unsigned long) vector:1162
#8 0x10ea3a79f in std::__1::vector<double, std::__1::allocator<double>>::resize(unsigned long) vector:1981
#9 0x10ea3a71e in std::__1::enable_if<traits::is_input_serializable<cereal::BinaryData<double>, cereal::BinaryInputArchive>::value && std::is_arithmetic<double>::value && !std::is_same<double, bool>::value, void>::type cereal::load<cereal::BinaryInputArchive, double, std::__1::allocator<double>>(cereal::BinaryInputArchive&, std::__1::vector<double, std::__1::allocator<double>>&) vector.hpp:57
#10 0x10ea3a6b4 in cereal::BinaryInputArchive& cereal::InputArchive<cereal::BinaryInputArchive, 1u>::processImpl<std::__1::vector<double, std::__1::allocator<double>>, (cereal::traits::detail::sfinae)0>(std::__1::vector<double, std::__1::allocator<double>>&) cereal.hpp:941
#11 0x10ea3a665 in void cereal::InputArchive<cereal::BinaryInputArchive, 1u>::process<std::__1::vector<double, std::__1::allocator<double>>&>(std::__1::vector<double, std::__1::allocator<double>>&) cereal.hpp:853
#12 0x10ea39410 in cereal::BinaryInputArchive& cereal::InputArchive<cereal::BinaryInputArchive, 1u>::operator()<std::__1::vector<double, std::__1::allocator<double>>&>(std::__1::vector<double, std::__1::allocator<double>>&) cereal.hpp:730
#13 0x10ea38b37 in void cereal::load<cereal::BinaryInputArchive>(cereal::BinaryInputArchive&, igraph_s&) main.cpp:228
#14 0x10ea38964 in cereal::BinaryInputArchive& cereal::InputArchive<cereal::BinaryInputArchive, 1u>::processImpl<igraph_s, (cereal::traits::detail::sfinae)0>(igraph_s&) cereal.hpp:941
#15 0x10ea38915 in void cereal::InputArchive<cereal::BinaryInputArchive, 1u>::process<igraph_s&>(igraph_s&) cereal.hpp:853
#16 0x10ea25250 in cereal::BinaryInputArchive& cereal::InputArchive<cereal::BinaryInputArchive, 1u>::operator()<igraph_s&>(igraph_s&) cereal.hpp:730
#17 0x10ea24baa in main main.cpp:333
#18 0x7ff8141fe3a5 in start+0x795 (dyld:x86_64+0xfffffffffff5c3a5)
==86488==HINT: if you don't care about these errors you may set allocator_may_return_null=1
SUMMARY: AddressSanitizer: allocation-size-too-big (libclang_rt.asan_osx_dynamic.dylib:x86_64h+0xf0fcd) in _Znwm+0x7d
==86488==ABORTING
./bin/compileAndRun.sh: line 10: 86488 Abort trap: 6 MallocNanoZone=0 ASAN_OPTIONS=detect_leaks=1 ./main
It turns out, Cereal does not seem to allow this form of hierarchy that I expected. Instead, the make_size_tag has a limited application for some type of arrays (vectors).
In effect, the attributes cannot be serialized in an inner loop as I have tried; one possible working implementation could look like this (with the igraph vectors also being serialized in their own methods, rather than having them be converted to an std::vector first):
namespace cereal {
////////////////////////////////////////////////////////////////
// serialization of igraph objects
// igraph vectors
template <class Archive>
inline void CEREAL_SAVE_FUNCTION_NAME(Archive &ar,
igraph_vector_int_t const &vec) {
size_type n = igraph_vector_int_size(&vec);
ar(make_size_tag(n));
for (size_type i = 0; i < n; ++i) {
ar(igraph_vector_int_get(&vec, i));
}
}
template <class Archive>
inline void CEREAL_LOAD_FUNCTION_NAME(Archive &ar, igraph_vector_int_t &vec) {
size_type n;
ar(make_size_tag(n));
igraph_vector_int_resize(&vec, n);
for (size_type i = 0; i < n; ++i) {
long int val;
ar(val);
igraph_vector_int_set(&vec, i, val);
}
}
template <class Archive>
inline void CEREAL_SAVE_FUNCTION_NAME(Archive &ar, igraph_vector_t const &vec) {
size_type n = igraph_vector_size(&vec);
ar(make_size_tag(n));
for (size_type i = 0; i < n; ++i) {
ar(igraph_vector_get(&vec, i));
}
}
template <class Archive>
inline void CEREAL_LOAD_FUNCTION_NAME(Archive &ar, igraph_vector_t &vec) {
size_type n;
ar(make_size_tag(n));
igraph_vector_resize(&vec, n);
for (size_type i = 0; i < n; ++i) {
double val;
ar(val);
igraph_vector_set(&vec, i, val);
}
}
template <class Archive>
inline void CEREAL_SAVE_FUNCTION_NAME(Archive &ar,
igraph_strvector_t const &vec) {
size_type n = igraph_strvector_size(&vec);
ar(make_size_tag(n));
for (size_type i = 0; i < n; ++i) {
std::string val = igraph_strvector_get(&vec, i);
ar(val);
}
}
template <class Archive>
inline void CEREAL_LOAD_FUNCTION_NAME(Archive &ar, igraph_strvector_t &vec) {
size_type n;
ar(make_size_tag(n));
igraph_strvector_resize(&vec, n);
std::string val;
val.reserve(50);
for (size_type i = 0; i < n; ++i) {
val.clear();
ar(val);
igraph_strvector_set(&vec, i, val.c_str());
}
}
// the graph
template <class Archive>
inline void CEREAL_SAVE_FUNCTION_NAME(Archive &ar, igraph_t const &graph) {
size_t numVertices = igraph_vcount(&graph);
ar(make_nvp("num_vertices", numVertices));
size_t numEdges = igraph_ecount(&graph);
ar(make_nvp("num_edges", numEdges));
igraph_vector_int_t allEdges;
igraph_vector_int_init(&allEdges, numEdges);
if (igraph_edges(&graph, igraph_ess_all(IGRAPH_EDGEORDER_ID), &allEdges)) {
throw std::runtime_error("Failed to get all edges");
}
ar(make_nvp("edges", allEdges));
igraph_vector_int_destroy(&allEdges);
// after storing the edges, must also store the attributes
// query them first
igraph_strvector_t gnames;
igraph_strvector_init(&gnames, 1);
igraph_vector_int_t gtypes;
igraph_vector_int_init(>ypes, 1);
igraph_strvector_t vnames;
igraph_strvector_init(&vnames, 1);
igraph_vector_int_t vtypes;
igraph_vector_int_init(&vtypes, 1);
igraph_strvector_t enames;
igraph_strvector_init(&enames, 1);
igraph_vector_int_t etypes;
igraph_vector_int_init(&etypes, 1);
igraph_cattribute_list(&graph, &gnames, >ypes, &vnames, &vtypes, &enames,
&etypes);
if (igraph_strvector_size(&gnames) != 0) {
throw std::runtime_error(
"Graph attributes serialization not supported yet.");
}
// serizalize vertex attributes
size_type numVertexAttributes = igraph_strvector_size(&vnames);
assert(igraph_strvector_size(&vnames) == igraph_vector_int_size(&vtypes));
ar(make_nvp("vertex_attr_names", vnames));
ar(make_nvp("vertex_attr_types", vtypes));
// ar(make_size_tag(numVertexAttributes));
for (size_t i = 0; i < numVertexAttributes; i++) {
const char *name = igraph_strvector_get(&vnames, i);
std::string namestr = std::string(name);
switch (igraph_vector_int_get(&vtypes, i)) {
// case IGRAPH_ATTRIBUTE_DEFAULT:
case IGRAPH_ATTRIBUTE_NUMERIC: {
igraph_vector_t results;
igraph_vector_init(&results, numVertices);
igraph_cattribute_VANV(&graph, igraph_strvector_get(&vnames, i),
igraph_vss_all(), &results);
ar(make_nvp("vertex_attr_" + namestr, results));
igraph_vector_destroy(&results);
} break;
case IGRAPH_ATTRIBUTE_STRING: {
igraph_strvector_t strresults;
igraph_strvector_init(&strresults, numVertices);
igraph_cattribute_VASV(&graph, igraph_strvector_get(&vnames, i),
igraph_vss_all(), &strresults);
ar(make_nvp("vertex_attr_" + namestr, strresults));
igraph_strvector_destroy(&strresults);
} break;
default:
throw std::runtime_error(
"This attribute type (" +
std::to_string(igraph_vector_int_get(&vtypes, i)) +
") is not supported");
}
}
// serizalize edge attributes
size_type numEdgeAttributes = igraph_strvector_size(&enames);
assert(igraph_strvector_size(&enames) == igraph_vector_int_size(&etypes));
ar(make_nvp("edge_attr_names", enames));
ar(make_nvp("edge_attr_types", etypes));
// ar(make_size_tag(numEdgeAttributes * 3));
for (size_t i = 0; i < numEdgeAttributes; i++) {
const char *name = igraph_strvector_get(&enames, i);
std::string namestr = std::string(name);
switch (igraph_vector_int_get(&etypes, i)) {
// case IGRAPH_ATTRIBUTE_DEFAULT:
case IGRAPH_ATTRIBUTE_NUMERIC: {
igraph_vector_t results;
igraph_vector_init(&results, numEdges);
igraph_cattribute_EANV(&graph, igraph_strvector_get(&enames, i),
igraph_ess_all(IGRAPH_EDGEORDER_ID), &results);
ar(make_nvp("edge_attr_" + namestr, results));
igraph_vector_destroy(&results);
} break;
case IGRAPH_ATTRIBUTE_STRING: {
igraph_strvector_t strresults;
igraph_strvector_init(&strresults, numEdges);
igraph_cattribute_EASV(&graph, igraph_strvector_get(&enames, i),
igraph_ess_all(IGRAPH_EDGEORDER_ID), &strresults);
ar(make_nvp("edge_attr_" + namestr, strresults));
igraph_strvector_destroy(&strresults);
} break;
default:
throw std::runtime_error(
"This attribute type (" +
std::to_string(igraph_vector_int_get(&etypes, i)) +
") is not supported");
}
}
igraph_strvector_destroy(&gnames);
igraph_strvector_destroy(&enames);
igraph_strvector_destroy(&vnames);
igraph_vector_int_destroy(>ypes);
igraph_vector_int_destroy(&etypes);
igraph_vector_int_destroy(&vtypes);
}
template <class Archive>
inline void CEREAL_LOAD_FUNCTION_NAME(Archive &ar, igraph_t &graph) {
size_t numVertices;
ar(make_nvp("num_vertices", numVertices));
size_t numEdges;
ar(make_nvp("num_edges", numEdges));
igraph_vector_int_t allEdges;
igraph_vector_int_init(&allEdges, numEdges);
ar(make_nvp("edges", allEdges));
igraph_add_vertices(&graph, numVertices, nullptr);
igraph_add_edges(&graph, &allEdges, nullptr);
igraph_vector_int_destroy(&allEdges);
// deserialize vertex attributes
igraph_strvector_t vnames;
igraph_strvector_init(&vnames, 1);
ar(make_nvp("vertex_attr_names", vnames));
igraph_vector_int_t vtypes;
igraph_vector_int_init(&vtypes, 1);
ar(make_nvp("vertex_attr_types", vtypes));
size_type numVertexAttributes = igraph_vector_int_size(&vtypes);
for (size_t i = 0; i < numVertexAttributes; ++i) {
std::string attributeName = std::string(igraph_strvector_get(&vnames, i));
int attributeType = igraph_vector_int_get(&vtypes, i);
switch (attributeType) {
// case IGRAPH_ATTRIBUTE_DEFAULT:
case IGRAPH_ATTRIBUTE_NUMERIC: {
igraph_vector_t results;
igraph_vector_init(&results, numVertices);
ar(make_nvp("vertex_attr_" + attributeName, results));
igraph_cattribute_VAN_setv(&graph, attributeName.c_str(), &results);
igraph_vector_destroy(&results);
}; break;
case IGRAPH_ATTRIBUTE_STRING: {
igraph_strvector_t strresults;
igraph_strvector_init(&strresults, numVertices);
ar(make_nvp("vertex_attr_" + attributeName, strresults));
igraph_cattribute_VAS_setv(&graph, attributeName.c_str(), &strresults);
igraph_strvector_destroy(&strresults);
}; break;
default:
throw std::runtime_error("This attribute type (" +
std::to_string(attributeType) +
") is not supported");
}
}
igraph_vector_int_destroy(&vtypes);
igraph_strvector_destroy(&vnames);
// and same for edge attributes
igraph_strvector_t enames;
igraph_strvector_init(&enames, 1);
ar(make_nvp("edge_attr_names", enames));
igraph_vector_int_t etypes;
igraph_vector_int_init(&etypes, 1);
ar(make_nvp("edge_attr_types", etypes));
size_t numEdgeAttributes = igraph_vector_int_size(&etypes);
for (size_t i = 0; i < numEdgeAttributes; ++i) {
std::string attributeName = std::string(igraph_strvector_get(&enames, i));
int attributeType = igraph_vector_int_get(&etypes, i);
switch (attributeType) {
// case IGRAPH_ATTRIBUTE_DEFAULT:
case IGRAPH_ATTRIBUTE_NUMERIC: {
igraph_vector_t results;
igraph_vector_init(&results, 1);
ar(make_nvp("edge_attr_" + attributeName, results));
igraph_cattribute_EAN_setv(&graph, attributeName.c_str(), &results);
igraph_vector_destroy(&results);
} break;
case IGRAPH_ATTRIBUTE_STRING: {
igraph_strvector_t strresults;
igraph_strvector_init(&strresults, 1);
ar(make_nvp("edge_attr_" + attributeName, strresults));
igraph_cattribute_EAS_setv(&graph, attributeName.c_str(), &strresults);
igraph_strvector_destroy(&strresults);
} break;
default:
throw std::runtime_error("This attribute type (" +
std::to_string(attributeType) +
") is not supported");
}
}
igraph_vector_int_destroy(&etypes);
igraph_strvector_destroy(&enames);
}
} // namespace cereal