OKlibrary  0.2.1.6
SimpleBacktracking.cpp
Go to the documentation of this file.
00001 // Oliver Kullmann, 26.11.2007 (Swansea)
00002 /* Copyright 2007 Oliver Kullmann
00003 This file is part of the OKlibrary. OKlibrary is free software; you can redistribute
00004 it and/or modify it under the terms of the GNU General Public License as published by
00005 the Free Software Foundation and included in this library; either version 3 of the
00006 License, or any later version. */
00007 
00016 #include <iostream>
00017 #include <cstdlib>
00018 #include <string>
00019 #include <fstream>
00020 #include <vector>
00021 #include <utility>
00022 
00023 #include <boost/graph/adjacency_list.hpp>
00024 #include <boost/graph/graphviz.hpp>
00025 #include <boost/property_map/dynamic_property_map.hpp>
00026 #include <boost/graph/isomorphism.hpp>
00027 
00028 int main(const int argc, const char* const argv[]) {
00029 
00030   if (argc != 3) {
00031     std::cerr << "ERROR[SimpleBacktracking]: Exactly two parameters are needed, the filenames for the two graphs.\n";
00032     return EXIT_FAILURE;
00033   }
00034 
00035   typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, boost::property<boost::vertex_name_t, std::string> > UndirectedGraph;
00036   typedef boost::graph_traits<UndirectedGraph>::vertex_descriptor vertex_type;
00037   typedef boost::graph_traits<UndirectedGraph>::vertices_size_type vertices_size_type;
00038   typedef boost::graph_traits<UndirectedGraph>::edges_size_type edges_size_type;
00039 
00040   UndirectedGraph ga, gb;
00041   vertices_size_type n;
00042 
00043   { // Reading
00044     const std::string grapha_s(argv[1]);
00045     const std::string graphb_s(argv[2]);
00046     { // ga
00047       std::ifstream grapha_f(grapha_s.c_str());
00048       if (not grapha_f) {
00049         std::cerr << "ERROR[SimpleBacktracking]: Can't read from first file \"" << grapha_s << "\".\n";
00050         return EXIT_FAILURE;
00051       }
00052       {
00053         boost::dynamic_properties p;
00054         p.property("node_id", get(boost::vertex_name, ga));
00055         boost::read_graphviz(grapha_f, ga, p);
00056       }
00057       if (not grapha_f) {
00058         std::cerr << "ERROR[SimpleBacktracking]: Error while reading from first file \"" << grapha_s << "\".\n";
00059         return EXIT_FAILURE;
00060       }
00061     }
00062     { // gb
00063       std::ifstream graphb_f(graphb_s.c_str());
00064       if (not graphb_f) {
00065         std::cerr << "ERROR[SimpleBacktracking]: Can't read from second file \"" << graphb_s << "\".\n";
00066         return EXIT_FAILURE;
00067       }
00068       {
00069         boost::dynamic_properties p;
00070         p.property("node_id", get(boost::vertex_name, gb));
00071         boost::read_graphviz(graphb_f, gb, p);
00072       }
00073       if (not graphb_f) {
00074         std::cerr << "ERROR[SimpleBacktracking]: Error while reading from second file \"" << graphb_s << "\".\n";
00075         return EXIT_FAILURE;
00076       }
00077     }
00078     n = num_vertices(ga);
00079     std::cout << "First graph (\"" << grapha_s << "\"):\n " << num_vertices(ga) << " vertices, " << num_edges(ga) << " edges.\n";
00080     std::cout << "Second graph (\"" << graphb_s << "\"):\n " << num_vertices(gb) << " vertices, " << num_edges(gb) << " edges.\n";
00081   }
00082  
00083   if (n != num_vertices(gb)) {
00084     std::cout << "Graphs non-isomorphic due to different number of vertices.\n";
00085     return 0;
00086   }
00087   std::cout << "Isomorphism testing started." << std::endl;
00088   typedef std::vector<boost::graph_traits<UndirectedGraph>::vertex_descriptor> map_type;
00089   map_type f(n);
00090   const bool result = boost::isomorphism(ga, gb, boost::isomorphism_map(boost::make_iterator_property_map(f.begin(), get(boost::vertex_index, ga), f[0])));
00091   std::cout << "Result = " << result << ".\n";
00092   if (result) {
00093     typedef boost::graph_traits<UndirectedGraph>::vertex_iterator vertex_iterator;
00094     typedef std::pair<vertex_iterator, vertex_iterator> vertex_range;
00095     const vertex_range& r(vertices(ga));
00096     const vertex_iterator& end(r.second);
00097     for (vertex_iterator i = r.first; i != end; ++i)
00098       std::cout << get(boost::vertex_name, ga, *i) << " -> " << get(boost::vertex_name, gb, f[get(boost::vertex_index, ga, *i)]) << "\n";
00099   }
00100 }
00101