title: boost graph equality and subgraph
body: <p>I'm writing code for graph mining using boost library and I want to know how to test: </p>
  
  <ul>
  <li><p>if two graphs are equal using isomorphism (return true only if graphs have the same structure and same labels) </p></li>
  <li><p>if a graph is a subgraph of another? </p></li>
  </ul>
  
  <p>This is the graphs file: <a href="http://pastebin.com/JYtyYTQd" rel="nofollow">3test.txt</a></p>
  
  <p>and Here is some parts of the source code that I have make:</p>
  
  <pre><code>#include &lt;boost/graph/adjacency_list.hpp&gt;
  #include &lt;boost/graph/vf2_sub_graph_iso.hpp&gt;
  #include &lt;boost/algorithm/string/split.hpp&gt;
  #include &lt;boost/algorithm/string/classification.hpp&gt;
  #include &lt;boost/config.hpp&gt;
  #include &lt;boost/graph/isomorphism.hpp&gt;
  #include &lt;boost/graph/graph_utility.hpp&gt;
  
  #include &lt;fstream&gt;
  #include &lt;iostream&gt;
  #include &lt;vector&gt;
  
  
  //for mmap:
  #include &lt;sys/mman.h&gt;
  #include &lt;sys/stat.h&gt;
  #include &lt;fcntl.h&gt;
  
  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&lt;boost::vecS, boost::vecS, boost::undirectedS, VertexProperties, EdgeProperties,
  GraphProperties&gt; Graph;
  
  // descriptors
  
  typedef boost::graph_traits&lt;Graph&gt;::vertex_descriptor vertex_t;
  typedef std::pair&lt;boost::graph_traits&lt;Graph&gt;::edge_descriptor, bool&gt; edge_t;
  // iterators
  typedef graph_traits&lt;Graph&gt;::vertex_iterator vertex_iter;
  typedef graph_traits&lt;Graph&gt;::edge_iterator edge_iter;
  typedef std::pair&lt;edge_iter, edge_iter&gt; edge_pair;
  
  
  //*********global variables*************
  
  
  vector&lt;Graph&gt; dataG;
  
  
  
  //=================callback used fro subgraph_iso=================================================================
  // Default print_callback
  template &lt;typename Graph1,typename Graph2&gt;
  
    struct my_callback {
  
      my_callback(const Graph1&amp; graph1, const Graph2&amp; graph2)
        : graph1_(graph1), graph2_(graph2) {}
  
      template &lt;typename CorrespondenceMap1To2,
                typename CorrespondenceMap2To1&gt;
      bool operator()(CorrespondenceMap1To2 f, CorrespondenceMap2To1) const {
  
        return true;
      }
  
    private:
      const Graph1&amp; graph1_;
      const Graph2&amp; 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 &amp;length) {
      int fd = open(fname, O_RDONLY);
      if (fd == -1)
          handle_error("open");
  
      // obtain file size
      struct stat sb;
      if (fstat(fd, &amp;sb) == -1)
          handle_error("fstat");
  
      length = sb.st_size;
  
      const char *addr = static_cast&lt;const char *&gt;(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&lt;string&gt; splitstringtolines(string const&amp; str) {
  
      std::vector&lt;string&gt; split_vector;
      split(split_vector, str, is_any_of("\n"));
  
      return split_vector;
  }
  
  //============Get a string starting from pos============
  string getpos(int const&amp; pos, string const&amp; yy) {
      size_t i = pos;
      string str;
      for (; ((yy[i] != ' ') &amp;&amp; (i &lt; yy.length())); i++) {str += yy[i];}
      return str;
  }
  //==================read string vector and return graphs vector===================
  std::vector&lt;Graph&gt; creategraphs(std::vector&lt;string&gt; const&amp; 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&lt;&lt;yy&lt;&lt;endl;
                  int vId, vLabel;
                  string vvv = getpos(2, yy);
                  vId = atoi(vvv.c_str());
                  string vvvv = getpos((int)vvv.length() + 3, yy);
                  // cout&lt;&lt;vvvv&lt;&lt;endl;
                  vLabel = atoi(vvvv.c_str());
                  boost::add_vertex(VertexProperties(vId, vLabel), dataG.back());
              }
  
                  break;
  
              case 'e': { // cout&lt;&lt;yy&lt;&lt;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&lt;&lt;eee&lt;&lt;endl;
                  fromId = atoi(eee.c_str());
                  string eee2 = getpos((int)eee.length() + 3, yy);
                  // cout&lt;&lt;eee2&lt;&lt;endl;
                  toId = atoi(eee2.c_str());
                  int c = (int)eee.length() + (int)eee2.length() + 4;
                  //    cout&lt;&lt;c&lt;&lt;endl;
                  string eee3 = getpos(c, yy);
                  //  cout&lt;&lt;eee3&lt;&lt;endl;
                  eLabel = atoi(eee3.c_str());
                  for (size_t i = 0; i &lt; 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&lt;Graph&gt; dataG =creategraphs(splitstringtolines(readfromfile("3test.txt", length)));
  
      cout&lt;&lt;"***PS***\n dataG[0] is a subgraph of dataG[1]\n dataG[2] is the same as dataG[0]\n dataG[3] is the same as dataG[0] but with other labels.\n"&lt;&lt;endl;
  
  
      my_callback&lt;Graph, Graph&gt; my_callback(dataG[0], dataG[3]);
    cout&lt;&lt;"equal(dataG[0], dataG[3],my_callback)="&lt;&lt;vf2_graph_iso(dataG[0], dataG[3],my_callback)&lt;&lt;endl;
   mcgregor_common_subgraphs(dataG[0], dataG[3], true, my_callback);
  
  
  }
  </code></pre>
  
  <p>Unfortunately when I run it I got these errors:</p>
  
  <pre><code>/usr/include/boost/graph/mcgregor_common_subgraphs.hpp||In instantiation of ‘bool boost::detail::mcgregor_common_subgraphs_internal(const GraphFirst&amp;, const GraphSecond&amp;, const VertexIndexMapFirst&amp;, const VertexIndexMapSecond&amp;, CorrespondenceMapFirstToSecond, CorrespondenceMapSecondToFirst, VertexStackFirst&amp;, EdgeEquivalencePredicate, VertexEquivalencePredicate, bool, SubGraphInternalCallback) [with GraphFirst = boost::adjacency_list&lt;boost::vecS, boost::vecS, boost::undirectedS, VertexProperties, EdgeProperties, GraphProperties&gt;; GraphSecond = boost::adjacency_list&lt;boost::vecS, boost::vecS, boost::undirectedS, VertexProperties, EdgeProperties, GraphProperties&gt;; VertexIndexMapFirst = boost::vec_adj_list_vertex_id_map&lt;VertexProperties, unsigned int&gt;; VertexIndexMapSecond = boost::vec_adj_list_vertex_id_map&lt;VertexProperties, unsigned int&gt;; CorrespondenceMapFirstToSecond = boost::shared_array_property_map&lt;unsigned int, boost::vec_adj_list_vertex_id_map&lt;VertexProperties, unsigned int&gt; &gt;; CorrespondenceMapSecondToFirst = boost::shared_array_property_map&lt;unsigned int, boost::vec_adj_list_vertex_id_map&lt;VertexProperties, unsigned int&gt; &gt;; VertexStackFirst = std::stack&lt;unsigned int, std::deque&lt;unsigned int, std::allocator&lt;unsigned int&gt; &gt; &gt;; EdgeEquivalencePredicate = boost::always_equivalent; VertexEquivalencePredicate = boost::always_equivalent; SubGraphInternalCallback = my_callback&lt;boost::adjacency_list&lt;boost::vecS, boost::vecS, boost::undirectedS, VertexProperties, EdgeProperties, GraphProperties&gt;, boost::adjacency_list&lt;boost::vecS, boost::vecS, boost::undirectedS, VertexProperties, EdgeProperties, GraphProperties&gt; &gt;]’:|
  /usr/include/boost/graph/mcgregor_common_subgraphs.hpp|433|required from ‘void boost::detail::mcgregor_common_subgraphs_internal_init(const GraphFirst&amp;, const GraphSecond&amp;, VertexIndexMapFirst, VertexIndexMapSecond, EdgeEquivalencePredicate, VertexEquivalencePredicate, bool, SubGraphInternalCallback) [with GraphFirst = boost::adjacency_list&lt;boost::vecS, boost::vecS, boost::undirectedS, VertexProperties, EdgeProperties, GraphProperties&gt;; GraphSecond = boost::adjacency_list&lt;boost::vecS, boost::vecS, boost::undirectedS, VertexProperties, EdgeProperties, GraphProperties&gt;; VertexIndexMapFirst = boost::vec_adj_list_vertex_id_map&lt;VertexProperties, unsigned int&gt;; VertexIndexMapSecond = boost::vec_adj_list_vertex_id_map&lt;VertexProperties, unsigned int&gt;; EdgeEquivalencePredicate = boost::always_equivalent; VertexEquivalencePredicate = boost::always_equivalent; SubGraphInternalCallback = my_callback&lt;boost::adjacency_list&lt;boost::vecS, boost::vecS, boost::undirectedS, VertexProperties, EdgeProperties, GraphProperties&gt;, boost::adjacency_list&lt;boost::vecS, boost::vecS, boost::undirectedS, VertexProperties, EdgeProperties, GraphProperties&gt; &gt;]’|
  /usr/include/boost/graph/mcgregor_common_subgraphs.hpp|484|required from ‘void boost::mcgregor_common_subgraphs(const GraphFirst&amp;, const GraphSecond&amp;, bool, SubGraphCallback) [with GraphFirst = boost::adjacency_list&lt;boost::vecS, boost::vecS, boost::undirectedS, VertexProperties, EdgeProperties, GraphProperties&gt;; GraphSecond = boost::adjacency_list&lt;boost::vecS, boost::vecS, boost::undirectedS, VertexProperties, EdgeProperties, GraphProperties&gt;; SubGraphCallback = my_callback&lt;boost::adjacency_list&lt;boost::vecS, boost::vecS, boost::undirectedS, VertexProperties, EdgeProperties, GraphProperties&gt;, boost::adjacency_list&lt;boost::vecS, boost::vecS, boost::undirectedS, VertexProperties, EdgeProperties, GraphProperties&gt; &gt;]’|
  /home/mohsenuss91/Bureau/NouvelleApprocheBOOST/stackoverflow.cpp|211|required from here|
  /usr/include/boost/graph/mcgregor_common_subgraphs.hpp|337|error: no match for call to ‘(my_callback&lt;boost::adjacency_list&lt;boost::vecS, boost::vecS, boost::undirectedS, VertexProperties, EdgeProperties, GraphProperties&gt;, boost::adjacency_list&lt;boost::vecS, boost::vecS, boost::undirectedS, VertexProperties, EdgeProperties, GraphProperties&gt; &gt;) (boost::shared_array_property_map&lt;unsigned int, boost::vec_adj_list_vertex_id_map&lt;VertexProperties, unsigned int&gt; &gt;&amp;, boost::shared_array_property_map&lt;unsigned int, boost::vec_adj_list_vertex_id_map&lt;VertexProperties, unsigned int&gt; &gt;&amp;, VertexSizeFirst&amp;)’|
  /home/mohsenuss91/Bureau/NouvelleApprocheBOOST/stackoverflow.cpp|69|note: candidate is:|
  /home/mohsenuss91/Bureau/NouvelleApprocheBOOST/stackoverflow.cpp|76|note: template&lt;class CorrespondenceMap1To2, class CorrespondenceMap2To1&gt; bool my_callback&lt;Graph1, Graph2&gt;::operator()(CorrespondenceMap1To2, CorrespondenceMap2To1) const [with CorrespondenceMap1To2 = CorrespondenceMap1To2; CorrespondenceMap2To1 = CorrespondenceMap2To1; Graph1 = boost::adjacency_list&lt;boost::vecS, boost::vecS, boost::undirectedS, VertexProperties, EdgeProperties, GraphProperties&gt;; Graph2 = boost::adjacency_list&lt;boost::vecS, boost::vecS, boost::undirectedS, VertexProperties, EdgeProperties, GraphProperties&gt;]|
  /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)) ===|
  </code></pre>