I'm writing code for graph mining using boost library and I want to use the vf2_sub_graph_iso function, in general vf2_subgraph_iso returns true if a graph-subgraph isomorphism exists and false otherwise, but in my case I want to make it return true only if the graphs are exactly the same (structure and labels), as mentioned in the official documentation: EdgeEquivalencePredicate and VertexEquivalencePredicate predicates are used to test whether edges and vertices are equivalent.
This is the graphs file: 3test.txt and here is some part of my code:
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/vf2_sub_graph_iso.hpp>
#include <boost/algorithm/string/split.hpp>
#include <boost/algorithm/string/classification.hpp>
#include <boost/config.hpp>
#include <boost/graph/isomorphism.hpp>
#include <boost/graph/graph_utility.hpp>
#include <fstream>
#include <iostream>
#include <vector>
//for mmap:
#include <sys/mman.h>
#include <sys/stat.h>
#include <fcntl.h>
using namespace std;
using namespace boost;
//==========STRUCTURES==========
// vertex
struct VertexProperties {
int id;
int label;
VertexProperties(unsigned i = 0, unsigned l = 0) : id(i), label(l) {}
};
// edge
struct EdgeProperties {
unsigned label;
EdgeProperties(unsigned l = 0) :label(l) {}
};
// Graph
struct GraphProperties {
unsigned id;
unsigned label;
GraphProperties(unsigned i = 0, unsigned l = 0) : id(i), label(l) {}
};
// adjency list
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, VertexProperties, EdgeProperties,
GraphProperties> Graph;
// descriptors
typedef boost::graph_traits<Graph>::vertex_descriptor vertex_t;
typedef std::pair<boost::graph_traits<Graph>::edge_descriptor, bool> edge_t;
// iterators
typedef graph_traits<Graph>::vertex_iterator vertex_iter;
typedef graph_traits<Graph>::edge_iterator edge_iter;
typedef std::pair<edge_iter, edge_iter> edge_pair;
//*********global variables*************
vector<Graph> dataG;
//=================callback used fro subgraph_iso=================================================================
// Default print_callback
template <typename Graph1,typename Graph2>
struct my_callback {
my_callback(const Graph1& graph1, const Graph2& graph2)
: graph1_(graph1), graph2_(graph2) {}
template <typename CorrespondenceMap1To2,
typename CorrespondenceMap2To1>
bool operator()(CorrespondenceMap1To2 f, CorrespondenceMap2To1) const {
return true;
}
private:
const Graph1& graph1_;
const Graph2& graph2_;
};
//==========handle_error==========
void handle_error(const char *msg) {
perror(msg);
exit(255);
}
//============READ ALL THE FILE AND RETURN A STRING===================
const char *readfromfile(const char *fname, size_t &length) {
int fd = open(fname, O_RDONLY);
if (fd == -1)
handle_error("open");
// obtain file size
struct stat sb;
if (fstat(fd, &sb) == -1)
handle_error("fstat");
length = sb.st_size;
const char *addr = static_cast<const char *>(mmap(NULL, length, PROT_READ, MAP_PRIVATE, fd, 0u));
if (addr == MAP_FAILED)
handle_error("mmap");
// TODO close fd at some point in time, call munmap(...)
return addr;
}
//==========SPLIT THE STRING BY NEWLINE (\n) ==========
vector<string> splitstringtolines(string const& str) {
std::vector<string> split_vector;
split(split_vector, str, is_any_of("\n"));
return split_vector;
}
//============Get a string starting from pos============
string getpos(int const& pos, string const& yy) {
size_t i = pos;
string str;
for (; ((yy[i] != ' ') && (i < yy.length())); i++) {str += yy[i];}
return str;
}
//==================read string vector and return graphs vector===================
std::vector<Graph> creategraphs(std::vector<string> const& fichlines) {
for (string yy : fichlines) {
switch (yy[0]) {
case 't': {
string str2 = getpos(4, yy);
unsigned gid = atoi(str2.c_str());
dataG.emplace_back(GraphProperties(gid, gid));
} break;
case 'v': {
assert(!dataG.empty()); // assert will terminate the program if its argument turns out to be false
// cout<<yy<<endl;
int vId, vLabel;
string vvv = getpos(2, yy);
vId = atoi(vvv.c_str());
string vvvv = getpos((int)vvv.length() + 3, yy);
// cout<<vvvv<<endl;
vLabel = atoi(vvvv.c_str());
boost::add_vertex(VertexProperties(vId, vLabel), dataG.back());
}
break;
case 'e': { // cout<<yy<<endl;
assert(!dataG.empty()); // assert will terminate the program if its argument turns out to be false
int fromId, toId, eLabel;
string eee = getpos(2, yy);
// cout<<eee<<endl;
fromId = atoi(eee.c_str());
string eee2 = getpos((int)eee.length() + 3, yy);
// cout<<eee2<<endl;
toId = atoi(eee2.c_str());
int c = (int)eee.length() + (int)eee2.length() + 4;
// cout<<c<<endl;
string eee3 = getpos(c, yy);
// cout<<eee3<<endl;
eLabel = atoi(eee3.c_str());
for (size_t i = 0; i < num_vertices(dataG.back()); ++i) // size_t vertice number in the graph
{
if(dataG.back()[i].id==fromId) fromId=i;
else if(dataG.back()[i].id==toId) toId=i;
}
boost::add_edge(fromId, toId, EdgeProperties(eLabel), dataG.back());
} break;
}
}
return dataG;
}
//==============================M A I N P R O G R A M =======================================
int main()
{
size_t length;
std::vector<Graph> dataG =creategraphs(splitstringtolines(readfromfile("3test.txt", length)));
my_callback<Graph, Graph> my_callback(dataG[0], dataG[3]);
cout<<"equal(dataG[0], dataG[3],my_callback)="<<vf2_sub_graph_iso(dataG[0], dataG[3],my_callback)<<endl;
}
How to use property maps for equivalence in my_callback function for my case?
This is a simple graph file that countain only 2 graphs:
t # 0
v 0 35
v 1 47
v 2 15
v 3 14
v 4 86
e 0 1 10
e 1 2 77
e 1 3 17
e 4 2 43
t # 1
v 0 35
v 1 47
v 2 15
v 3 14
v 4 86
e 0 1 10
e 1 2 7
e 1 3 17
e 4 2 4
The graphs are have same structure but not the same labels, so this code must return false and not true:
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/vf2_sub_graph_iso.hpp>
#include <boost/algorithm/string/split.hpp>
#include <boost/algorithm/string/classification.hpp>
#include <boost/config.hpp>
#include <boost/graph/isomorphism.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/tuple/tuple_comparison.hpp>
#include <fstream>
#include <iostream>
#include <vector>
//for mmap:
#include <sys/mman.h>
#include <sys/stat.h>
#include <fcntl.h>
using namespace boost;
//==========STRUCTURES==========
// vertex
struct VertexProperties {
int id;
int label;
VertexProperties(unsigned i = 0, unsigned l = 0) : id(i), label(l) {}
bool operator==(VertexProperties const& other) const {
return tie(id, label) == tie(other.id, other.label);
}
};
// edge
struct EdgeProperties {
unsigned label;
EdgeProperties(unsigned l = 0) :label(l) {}
bool operator==(EdgeProperties const& other) const {
return tie(label) == tie(other.label);
}
};
// Graph
struct GraphProperties {
unsigned id;
unsigned label;
GraphProperties(unsigned i = 0, unsigned l = 0) : id(i), label(l) {}
};
// adjency list
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, VertexProperties, EdgeProperties,
GraphProperties> Graph;
// descriptors
typedef boost::graph_traits<Graph>::vertex_descriptor vertex_t;
typedef std::pair<boost::graph_traits<Graph>::edge_descriptor, bool> edge_t;
// iterators
typedef graph_traits<Graph>::vertex_iterator vertex_iter;
typedef graph_traits<Graph>::edge_iterator edge_iter;
typedef std::pair<edge_iter, edge_iter> edge_pair;
//*********global variables*************
std::vector<Graph> dataG;
//=================callback used fro subgraph_iso=================================================================
// Default print_callback
template <typename Graph1,typename Graph2>
struct my_callback {
my_callback(const Graph1& graph1, const Graph2& graph2)
: graph1_(graph1), graph2_(graph2) {}
template <typename CorrespondenceMap1To2,
typename CorrespondenceMap2To1>
bool operator()(CorrespondenceMap1To2 /*f*/, CorrespondenceMap2To1) const {
return true;
}
private:
const Graph1& graph1_;
const Graph2& graph2_;
};
//==========handle_error==========
void handle_error(const char *msg) {
perror(msg);
exit(255);
}
//============READ ALL THE FILE AND RETURN A STRING===================
const char *readfromfile(const char *fname, size_t &length) {
int fd = open(fname, O_RDONLY);
if (fd == -1)
handle_error("open");
// obtain file size
struct stat sb;
if (fstat(fd, &sb) == -1)
handle_error("fstat");
length = sb.st_size;
const char *addr = static_cast<const char *>(mmap(NULL, length, PROT_READ, MAP_PRIVATE, fd, 0u));
if (addr == MAP_FAILED)
handle_error("mmap");
// TODO close fd at some point in time, call munmap(...)
return addr;
}
//==========SPLIT THE STRING BY NEWLINE (\n) ==========
std::vector<std::string> splitstringtolines(std::string const& str) {
std::vector<std::string> split_vector;
split(split_vector, str, is_any_of("\n"));
return split_vector;
}
//============Get a string starting from pos============
std::string getpos(int const& pos, std::string const& yy) {
size_t i = pos;
std::string str;
for (; ((yy[i] != ' ') && (i < yy.length())); i++) {str += yy[i];}
return str;
}
//==================read string vector and return graphs vector===================
std::vector<Graph> creategraphs(std::vector<std::string> const& fichlines) {
for (std::string yy : fichlines) {
switch (yy[0]) {
case 't': {
std::string str2 = getpos(4, yy);
unsigned gid = atoi(str2.c_str());
dataG.emplace_back(GraphProperties(gid, gid));
} break;
case 'v': {
assert(!dataG.empty()); // assert will terminate the program if its argument turns out to be false
// std::cout<<yy<<std::endl;
int vId, vLabel;
std::string vvv = getpos(2, yy);
vId = atoi(vvv.c_str());
std::string vvvv = getpos((int)vvv.length() + 3, yy);
// std::cout<<vvvv<<std::endl;
vLabel = atoi(vvvv.c_str());
boost::add_vertex(VertexProperties(vId, vLabel), dataG.back());
}
break;
case 'e': { // std::cout<<yy<<std::endl;
assert(!dataG.empty()); // assert will terminate the program if its argument turns out to be false
int fromId, toId, eLabel;
std::string eee = getpos(2, yy);
// std::cout<<eee<<std::endl;
fromId = atoi(eee.c_str());
std::string eee2 = getpos((int)eee.length() + 3, yy);
// std::cout<<eee2<<std::endl;
toId = atoi(eee2.c_str());
int c = (int)eee.length() + (int)eee2.length() + 4;
// std::cout<<c<<std::endl;
std::string eee3 = getpos(c, yy);
// std::cout<<eee3<<std::endl;
eLabel = atoi(eee3.c_str());
for (size_t i = 0; i < num_vertices(dataG.back()); ++i) // size_t vertice number in the graph
{
if(dataG.back()[i].id==fromId) fromId=i;
else if(dataG.back()[i].id==toId) toId=i;
}
boost::add_edge(fromId, toId, EdgeProperties(eLabel), dataG.back());
} break;
}
}
return dataG;
}
template <typename Graph1, typename Graph2>
bool my_bundled_graph_iso(Graph1 const& graph_small, Graph2 const& graph_large) {
auto const vos = boost::copy_range<std::vector<Graph::vertex_descriptor> >(vertices(graph_small));
return vf2_subgraph_iso(graph_small, graph_large, my_callback<Graph, Graph>(graph_small, graph_large), vos,
edges_equivalent (make_property_map_equivalent(boost::get(edge_bundle, graph_small), boost::get(edge_bundle, graph_large))).
vertices_equivalent(make_property_map_equivalent(boost::get(vertex_bundle, graph_small), boost::get(vertex_bundle, graph_large)))
);
}
//==============================M A I N P R O G R A M =======================================
int main() {
size_t length;
std::vector<Graph> dataG = creategraphs(splitstringtolines(readfromfile("2.txt", length)));
std::cout << std::boolalpha << my_bundled_graph_iso(dataG[0], dataG[1]) << std::endl;
}
I didn't mentionned in the question and the little precedent example that vertices can be the same even if there id's are not (in different graphs).
Ok, let's dissect the documentation.
In order to pass non-default implementations for EdgeEquivalencePredicate and VertexEquivalencePredicate you need the second overload:
bool vf2_subgraph_iso(const GraphSmall& graph_small,
const GraphLarge& graph_large,
SubGraphIsoMapCallback user_callback,
const VertexOrderSmall& vertex_order_small,
const bgl_named_params<Param, Tag, Rest>& params)
This means you need at least a parameter to match vertex_order_small and params. Let's do the minimum amount of work and supply only vertex_order_small first:
The ordered vertices of the smaller (first) graph graph_small. During the matching process the vertices are examined in the order given by
vertex_order_small. TypeVertexOrderSmallmust be a model ofContainerConceptwith value typegraph_traits<GraphSmall>::vertex_descriptor.Default The vertices are ordered by multiplicity of in/out degrees.
Let's pass a vector of vertex descriptors in default order:
auto const& graph_small = dataG[0];
auto const& graph_large = dataG[3];
auto vos = boost::copy_range<std::vector<Graph::vertex_descriptor> >(vertices(graph_small));
bool iso = vf2_graph_iso(graph_small, graph_large, my_callback, vos, no_named_parameters());
Next step, you add the named parameters, e.g.: [¹]
bool iso = vf2_graph_iso(graph_small, graph_large, my_callback, vos,
edges_equivalent ([&graph_small, &graph_large](Graph::edge_descriptor small_ed, Graph::edge_descriptor large_ed) {
return graph_small[small_ed] == graph_large[large_ed];
}).
vertices_equivalent([&graph_small, &graph_large](Graph::vertex_descriptor small_vd, Graph::vertex_descriptor large_vd) {
return graph_small[small_vd] == graph_large[large_vd];
})
);
As the final topping use make_property_map_equivalent documented here:
bool iso = vf2_graph_iso(graph_small, graph_large, my_callback, vos,
edges_equivalent (make_property_map_equivalent(boost::get(edge_bundle, graph_small), boost::get(edge_bundle, graph_large))).
vertices_equivalent(make_property_map_equivalent(boost::get(vertex_bundle, graph_small), boost::get(vertex_bundle, graph_large)))
);
See all three steps Live On Coliru
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/vf2_sub_graph_iso.hpp>
#include <boost/algorithm/string/split.hpp>
#include <boost/algorithm/string/classification.hpp>
#include <boost/config.hpp>
#include <boost/graph/isomorphism.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/tuple/tuple_comparison.hpp>
#include <fstream>
#include <iostream>
#include <vector>
//for mmap:
#include <sys/mman.h>
#include <sys/stat.h>
#include <fcntl.h>
using namespace boost;
//==========STRUCTURES==========
// vertex
struct VertexProperties {
int id;
int label;
VertexProperties(unsigned i = 0, unsigned l = 0) : id(i), label(l) {}
bool operator==(VertexProperties const& other) const {
return tie(id, label) == tie(other.id, other.label);
}
};
// edge
struct EdgeProperties {
unsigned label;
EdgeProperties(unsigned l = 0) :label(l) {}
bool operator==(EdgeProperties const& other) const {
return tie(label) == tie(other.label);
}
};
// Graph
struct GraphProperties {
unsigned id;
unsigned label;
GraphProperties(unsigned i = 0, unsigned l = 0) : id(i), label(l) {}
};
// adjency list
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, VertexProperties, EdgeProperties,
GraphProperties> Graph;
// descriptors
typedef boost::graph_traits<Graph>::vertex_descriptor vertex_t;
typedef std::pair<boost::graph_traits<Graph>::edge_descriptor, bool> edge_t;
// iterators
typedef graph_traits<Graph>::vertex_iterator vertex_iter;
typedef graph_traits<Graph>::edge_iterator edge_iter;
typedef std::pair<edge_iter, edge_iter> edge_pair;
//*********global variables*************
std::vector<Graph> dataG;
//=================callback used fro subgraph_iso=================================================================
// Default print_callback
template <typename Graph1,typename Graph2>
struct my_callback {
my_callback(const Graph1& graph1, const Graph2& graph2)
: graph1_(graph1), graph2_(graph2) {}
template <typename CorrespondenceMap1To2,
typename CorrespondenceMap2To1>
bool operator()(CorrespondenceMap1To2 /*f*/, CorrespondenceMap2To1) const {
return true;
}
private:
const Graph1& graph1_;
const Graph2& graph2_;
};
//==========handle_error==========
void handle_error(const char *msg) {
perror(msg);
exit(255);
}
//============READ ALL THE FILE AND RETURN A STRING===================
const char *readfromfile(const char *fname, size_t &length) {
int fd = open(fname, O_RDONLY);
if (fd == -1)
handle_error("open");
// obtain file size
struct stat sb;
if (fstat(fd, &sb) == -1)
handle_error("fstat");
length = sb.st_size;
const char *addr = static_cast<const char *>(mmap(NULL, length, PROT_READ, MAP_PRIVATE, fd, 0u));
if (addr == MAP_FAILED)
handle_error("mmap");
// TODO close fd at some point in time, call munmap(...)
return addr;
}
//==========SPLIT THE STRING BY NEWLINE (\n) ==========
std::vector<std::string> splitstringtolines(std::string const& str) {
std::vector<std::string> split_vector;
split(split_vector, str, is_any_of("\n"));
return split_vector;
}
//============Get a string starting from pos============
std::string getpos(int const& pos, std::string const& yy) {
size_t i = pos;
std::string str;
for (; ((yy[i] != ' ') && (i < yy.length())); i++) {str += yy[i];}
return str;
}
//==================read string vector and return graphs vector===================
std::vector<Graph> creategraphs(std::vector<std::string> const& fichlines) {
for (std::string yy : fichlines) {
switch (yy[0]) {
case 't': {
std::string str2 = getpos(4, yy);
unsigned gid = atoi(str2.c_str());
dataG.emplace_back(GraphProperties(gid, gid));
} break;
case 'v': {
assert(!dataG.empty()); // assert will terminate the program if its argument turns out to be false
// std::cout<<yy<<std::endl;
int vId, vLabel;
std::string vvv = getpos(2, yy);
vId = atoi(vvv.c_str());
std::string vvvv = getpos((int)vvv.length() + 3, yy);
// std::cout<<vvvv<<std::endl;
vLabel = atoi(vvvv.c_str());
boost::add_vertex(VertexProperties(vId, vLabel), dataG.back());
}
break;
case 'e': { // std::cout<<yy<<std::endl;
assert(!dataG.empty()); // assert will terminate the program if its argument turns out to be false
int fromId, toId, eLabel;
std::string eee = getpos(2, yy);
// std::cout<<eee<<std::endl;
fromId = atoi(eee.c_str());
std::string eee2 = getpos((int)eee.length() + 3, yy);
// std::cout<<eee2<<std::endl;
toId = atoi(eee2.c_str());
int c = (int)eee.length() + (int)eee2.length() + 4;
// std::cout<<c<<std::endl;
std::string eee3 = getpos(c, yy);
// std::cout<<eee3<<std::endl;
eLabel = atoi(eee3.c_str());
for (size_t i = 0; i < num_vertices(dataG.back()); ++i) // size_t vertice number in the graph
{
if(dataG.back()[i].id==fromId) fromId=i;
else if(dataG.back()[i].id==toId) toId=i;
}
boost::add_edge(fromId, toId, EdgeProperties(eLabel), dataG.back());
} break;
}
}
return dataG;
}
//==============================M A I N P R O G R A M =======================================
int main() {
size_t length;
std::cout << std::boolalpha;
std::vector<Graph> dataG = creategraphs(splitstringtolines(readfromfile("3test.txt", length)));
auto const& graph_small = dataG[0];
auto const& graph_large = dataG[3];
my_callback<Graph, Graph> my_callback(graph_small, graph_large);
std::cout << "equal(graph_small, graph_large,my_callback)=" << vf2_graph_iso(graph_small, graph_large, my_callback) << std::endl;
// first step
{
auto vos = boost::copy_range<std::vector<Graph::vertex_descriptor> >(vertices(graph_small));
std::cout << "equal(graph_small, graph_large,my_callback)=" << vf2_graph_iso(graph_small, graph_large, my_callback, vos, no_named_parameters()) << std::endl;
}
// second step
{
auto vos = boost::copy_range<std::vector<Graph::vertex_descriptor> >(vertices(graph_small));
bool iso = vf2_graph_iso(graph_small, graph_large, my_callback, vos,
edges_equivalent ([&graph_small, &graph_large](Graph::edge_descriptor small_ed, Graph::edge_descriptor large_ed) {
return graph_small[small_ed] == graph_large[large_ed];
}).
vertices_equivalent([&graph_small, &graph_large](Graph::vertex_descriptor small_vd, Graph::vertex_descriptor large_vd) {
return graph_small[small_vd] == graph_large[large_vd];
})
);
std::cout << "equal(graph_small, graph_large,my_callback)=" << iso << std::endl;
}
// third step
{
auto vos = boost::copy_range<std::vector<Graph::vertex_descriptor> >(vertices(graph_small));
bool iso = vf2_graph_iso(graph_small, graph_large, my_callback, vos,
edges_equivalent (make_property_map_equivalent(boost::get(edge_bundle, graph_small), boost::get(edge_bundle, graph_large))).
vertices_equivalent(make_property_map_equivalent(boost::get(vertex_bundle, graph_small), boost::get(vertex_bundle, graph_large)))
);
std::cout << "equal(graph_small, graph_large,my_callback)=" << iso << std::endl;
}
}
Prints output:
equal(graph_small, graph_large,my_callback)=true
equal(graph_small, graph_large,my_callback)=true
equal(graph_small, graph_large,my_callback)=false
equal(graph_small, graph_large,my_callback)=false
[¹] Of course assuming you implement operator== for your edge and vertex property types (see full listing)