c++ - boost graph equality and subgraph -
i'm writing code graph mining using boost library , want know how test:
if 2 graphs equal using isomorphism (return true if graphs have same structure , same labels)
if graph subgraph of another?
this graphs file: 3test.txt
and here parts of source code have make:
#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 = 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 = 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 file , return 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 @ point in time, call munmap(...) return addr; } //==========split string 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 string starting pos============ string getpos(int const& pos, string const& yy) { size_t = pos; string str; (; ((yy[i] != ' ') && (i < yy.length())); i++) {str += yy[i];} return str; } //==================read string vector , return graphs vector=================== std::vector<graph> creategraphs(std::vector<string> const& fichlines) { (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 terminate program if argument turns out 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 terminate program if argument turns out 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()); (size_t = 0; < num_vertices(datag.back()); ++i) // size_t vertice number in 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 n p r o g r m ======================================= int main() { size_t length; std::vector<graph> datag =creategraphs(splitstringtolines(readfromfile("3test.txt", length))); cout<<"***ps***\n datag[0] subgraph of datag[1]\n datag[2] same datag[0]\n datag[3] same datag[0] other labels.\n"<<endl; my_callback<graph, graph> my_callback(datag[0], datag[3]); cout<<"equal(datag[0], datag[3],my_callback)="<<vf2_graph_iso(datag[0], datag[3],my_callback)<<endl; mcgregor_common_subgraphs(datag[0], datag[3], true, my_callback); } unfortunately when run got these errors:
/usr/include/boost/graph/mcgregor_common_subgraphs.hpp||in instantiation of ‘bool boost::detail::mcgregor_common_subgraphs_internal(const graphfirst&, const graphsecond&, const vertexindexmapfirst&, const vertexindexmapsecond&, correspondencemapfirsttosecond, correspondencemapsecondtofirst, vertexstackfirst&, edgeequivalencepredicate, vertexequivalencepredicate, bool, subgraphinternalcallback) [with graphfirst = boost::adjacency_list<boost::vecs, boost::vecs, boost::undirecteds, vertexproperties, edgeproperties, graphproperties>; graphsecond = boost::adjacency_list<boost::vecs, boost::vecs, boost::undirecteds, vertexproperties, edgeproperties, graphproperties>; vertexindexmapfirst = boost::vec_adj_list_vertex_id_map<vertexproperties, unsigned int>; vertexindexmapsecond = boost::vec_adj_list_vertex_id_map<vertexproperties, unsigned int>; correspondencemapfirsttosecond = boost::shared_array_property_map<unsigned int, boost::vec_adj_list_vertex_id_map<vertexproperties, unsigned int> >; correspondencemapsecondtofirst = boost::shared_array_property_map<unsigned int, boost::vec_adj_list_vertex_id_map<vertexproperties, unsigned int> >; vertexstackfirst = std::stack<unsigned int, std::deque<unsigned int, std::allocator<unsigned int> > >; edgeequivalencepredicate = boost::always_equivalent; vertexequivalencepredicate = boost::always_equivalent; subgraphinternalcallback = my_callback<boost::adjacency_list<boost::vecs, boost::vecs, boost::undirecteds, vertexproperties, edgeproperties, graphproperties>, boost::adjacency_list<boost::vecs, boost::vecs, boost::undirecteds, vertexproperties, edgeproperties, graphproperties> >]’:| /usr/include/boost/graph/mcgregor_common_subgraphs.hpp|433|required ‘void boost::detail::mcgregor_common_subgraphs_internal_init(const graphfirst&, const graphsecond&, vertexindexmapfirst, vertexindexmapsecond, edgeequivalencepredicate, vertexequivalencepredicate, bool, subgraphinternalcallback) [with graphfirst = boost::adjacency_list<boost::vecs, boost::vecs, boost::undirecteds, vertexproperties, edgeproperties, graphproperties>; graphsecond = boost::adjacency_list<boost::vecs, boost::vecs, boost::undirecteds, vertexproperties, edgeproperties, graphproperties>; vertexindexmapfirst = boost::vec_adj_list_vertex_id_map<vertexproperties, unsigned int>; vertexindexmapsecond = boost::vec_adj_list_vertex_id_map<vertexproperties, unsigned int>; edgeequivalencepredicate = boost::always_equivalent; vertexequivalencepredicate = boost::always_equivalent; subgraphinternalcallback = my_callback<boost::adjacency_list<boost::vecs, boost::vecs, boost::undirecteds, vertexproperties, edgeproperties, graphproperties>, boost::adjacency_list<boost::vecs, boost::vecs, boost::undirecteds, vertexproperties, edgeproperties, graphproperties> >]’| /usr/include/boost/graph/mcgregor_common_subgraphs.hpp|484|required ‘void boost::mcgregor_common_subgraphs(const graphfirst&, const graphsecond&, bool, subgraphcallback) [with graphfirst = boost::adjacency_list<boost::vecs, boost::vecs, boost::undirecteds, vertexproperties, edgeproperties, graphproperties>; graphsecond = boost::adjacency_list<boost::vecs, boost::vecs, boost::undirecteds, vertexproperties, edgeproperties, graphproperties>; subgraphcallback = my_callback<boost::adjacency_list<boost::vecs, boost::vecs, boost::undirecteds, vertexproperties, edgeproperties, graphproperties>, boost::adjacency_list<boost::vecs, boost::vecs, boost::undirecteds, vertexproperties, edgeproperties, graphproperties> >]’| /home/mohsenuss91/bureau/nouvelleapprocheboost/stackoverflow.cpp|211|required here| /usr/include/boost/graph/mcgregor_common_subgraphs.hpp|337|error: no match call ‘(my_callback<boost::adjacency_list<boost::vecs, boost::vecs, boost::undirecteds, vertexproperties, edgeproperties, graphproperties>, boost::adjacency_list<boost::vecs, boost::vecs, boost::undirecteds, vertexproperties, edgeproperties, graphproperties> >) (boost::shared_array_property_map<unsigned int, boost::vec_adj_list_vertex_id_map<vertexproperties, unsigned int> >&, boost::shared_array_property_map<unsigned int, boost::vec_adj_list_vertex_id_map<vertexproperties, unsigned int> >&, vertexsizefirst&)’| /home/mohsenuss91/bureau/nouvelleapprocheboost/stackoverflow.cpp|69|note: candidate is:| /home/mohsenuss91/bureau/nouvelleapprocheboost/stackoverflow.cpp|76|note: template<class correspondencemap1to2, class correspondencemap2to1> bool my_callback<graph1, graph2>::operator()(correspondencemap1to2, correspondencemap2to1) const [with correspondencemap1to2 = correspondencemap1to2; correspondencemap2to1 = correspondencemap2to1; graph1 = boost::adjacency_list<boost::vecs, boost::vecs, boost::undirecteds, vertexproperties, edgeproperties, graphproperties>; graph2 = boost::adjacency_list<boost::vecs, boost::vecs, boost::undirecteds, vertexproperties, edgeproperties, graphproperties>]| /home/mohsenuss91/bureau/nouvelleapprocheboost/stackoverflow.cpp|76|note: template argument deduction/substitution failed:| /usr/include/boost/graph/mcgregor_common_subgraphs.hpp|337|note: candidate expects 2 arguments, 3 provided| ||=== build failed: 1 error(s), 4 warning(s) (0 minute(s), 6 second(s)) ===|
docs:
out:
subgraphcallbackuser_callbacka function object invoked when subgraph has been discovered.
operator()must have following form:template <typename correspondencemapfirsttosecond, typename correspondencemapsecondtofirst> bool operator()( correspondencemapfirsttosecond correspondence_map_1_to_2, correspondencemapsecondtofirst correspondence_map_2_to_1, typename graph_traits<graphfirst>::vertices_size_type subgraph_size );
so @ least make functor take argument:
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 { // vf2_graph_iso return true; } template <typename correspondencemap1to2, typename correspondencemap2to1, typename x> bool operator()(correspondencemap1to2 f, correspondencemap2to1, x) const { // mcgregor_common_subgraphs return true; } private: const graph1 &graph1_; const graph2 &graph2_; }; of course, /just/ fixes compilation error. doesn't callbacks useful work.
output:
***ps*** datag[0] subgraph of datag[1] datag[2] same datag[0] datag[3] same datag[0] other labels. equal(datag[0], datag[3],my_callback)=1 working sample:
#include <boost/graph/adjacency_list.hpp> #include <boost/graph/vf2_sub_graph_iso.hpp> #include <boost/graph/mcgregor_common_subgraphs.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> // 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 = 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 = 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 { // vf2_graph_iso return true; } template <typename correspondencemap1to2, typename correspondencemap2to1, typename x> bool operator()(correspondencemap1to2 f, correspondencemap2to1, x) const { // mcgregor_common_subgraphs return true; } private: const graph1 &graph1_; const graph2 &graph2_; }; //==========handle_error========== void handle_error(const char *msg) { perror(msg); exit(255); } //============read file , return 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 @ point in time, call munmap(...) return addr; } //==========split string 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 string starting pos============ string getpos(int const &pos, string const &yy) { size_t = pos; string str; (; ((yy[i] != ' ') && (i < yy.length())); i++) { str += yy[i]; } return str; } //==================read string vector , return graphs vector=================== std::vector<graph> creategraphs(std::vector<string> const &fichlines) { (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 terminate program if argument turns out 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 terminate program if argument turns out 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()); (size_t = 0; < num_vertices(datag.back()); ++i) // size_t vertice number in 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 n p r o g r m ======================================= int main() { size_t length; std::vector<graph> datag = creategraphs(splitstringtolines(readfromfile("3test.txt", length))); cout << "***ps***\n datag[0] subgraph of datag[1]\n datag[2] same datag[0]\n datag[3] same " "as datag[0] other labels.\n" << endl; my_callback<graph, graph> my_callback(datag[0], datag[3]); cout << "equal(datag[0], datag[3],my_callback)=" << vf2_graph_iso(datag[0], datag[3], my_callback) << endl; mcgregor_common_subgraphs(datag[0], datag[3], true, my_callback); }
Comments
Post a Comment