fork download
copy 
  1. #include <boost/graph/adjacency_list.hpp>
  2. #include <boost/graph/reverse_graph.hpp>
  3. #include <boost/graph/iteration_macros.hpp>
  4. #include <boost/graph/graph_utility.hpp>
  5.  
  6. // using namespace boost;
  7. typedef boost::adjacency_list < boost::vecS, boost::vecS, boost::undirectedS > Graph;
  8.  
  9. struct edge_cmp
  10. {
  11.   bool operator () (const Graph::edge_descriptor& a, const Graph::edge_descriptor& b) const
  12.   {
  13.     if (a.m_source < b.m_source) { return true; }
  14.     if (a.m_source > b.m_source) { return false; }
  15.     return (a.m_target < b.m_target);
  16.   }
  17. };
  18.  
  19. template <typename T, typename Compare> std::set<T,Compare> operator-(const std::set<T,Compare>& a, const std::set<T,Compare>& b)
  20. {
  21.   std::set<T,Compare> r;
  22.   std::set_difference(a.begin(), a.end(),
  23.                       b.begin(), b.end(),
  24.                       std::inserter(r, r.end()));
  25.  
  26.   return r;
  27. }
  28.  
  29. template <typename T,typename Compare> std::set<T,Compare> operator/(const std::set<T,Compare>& a, const std::set<T,Compare>& b)
  30. {
  31.   std::set<T,Compare> r;
  32.   std::set_intersection(
  33.     a.begin(), a.end(),
  34.     b.begin(), b.end(),
  35.     std::inserter(r, r.end()));
  36.  
  37.   return r;
  38. }
  39.  
  40. // Overload operator for our specific set type.
  41. template <> std::set<Graph::edge_descriptor,edge_cmp> operator-(const std::set<Graph::edge_descriptor,edge_cmp>& a,
  42.                                                                 const std::set<Graph::edge_descriptor,edge_cmp>& b)
  43. {
  44.   std::set<Graph::edge_descriptor,edge_cmp> r;
  45.   std::set_difference(a.begin(), a.end(),
  46.                       b.begin(), b.end(),
  47.                       std::inserter(r, r.end()), edge_cmp());
  48.   return r;
  49. }
  50.  
  51. template <> std::set<Graph::edge_descriptor,edge_cmp> operator/(const std::set<Graph::edge_descriptor,edge_cmp>& a,
  52.                                                                 const std::set<Graph::edge_descriptor,edge_cmp>& b)
  53. {
  54.   std::set<Graph::edge_descriptor,edge_cmp> r;
  55.   std::set_intersection(
  56.     a.begin(), a.end(),
  57.     b.begin(), b.end(),
  58.     std::inserter(r, r.end()), edge_cmp());
  59.  
  60.   return r;
  61. }
  62.  
  63. void compare(const Graph& a, const Graph& b)
  64. {
  65.   std::set<Graph::vertex_descriptor > av, bv, samev, extrav, missingv;
  66.   // Use our comparator here.
  67.   edge_cmp comp;
  68.   std::set<Graph::edge_descriptor, edge_cmp> ae(comp), be(comp), re(comp), samee(comp), extrae(comp), missinge(comp);
  69.  
  70.   BGL_FORALL_VERTICES_T(v, a, Graph) av.insert(v);
  71.   BGL_FORALL_VERTICES_T(v, b, Graph) bv.insert(v);
  72.   samev    = (av / bv);
  73.   extrav   = (bv - av);
  74.   missingv = (av - bv);
  75.  
  76.  
  77.   BGL_FORALL_EDGES_T(e, a, Graph) ae.insert(e);
  78.   BGL_FORALL_EDGES_T(e, b, Graph) be.insert(e);
  79.  
  80.   samee    = (ae / be);
  81.   extrae   = (be - ae);
  82.   missinge = (ae - be);
  83.  
  84.   // TODO(silgon): reverse_graph
  85.   // boost::reverse_graph<Graph> r(b);
  86.   // BGL_FORALL_EDGES_T(e, r, Graph) re.insert(e);
  87.   std::cout << "---- Vertices ----\n"
  88.             << "same: " << samev.size() << std::endl
  89.             << "extra: " << extrav.size() << std::endl
  90.             << "missing: " << missingv.size() << std::endl;
  91.  
  92.   std::cout << "---- Edges ----\n"
  93.             << "same: " << samee.size() << std::endl
  94.             << "extra: " << extrae.size() << std::endl
  95.             << "missing: " << missinge.size() << std::endl;
  96. }
  97.  
  98. int main()
  99. {
  100.   Graph a;
  101.   {
  102.     boost::graph_traits<Graph>::vertex_descriptor v, u, y;
  103.     u = boost::vertex(1, a);
  104.     v = boost::vertex(2, a);
  105.     y = boost::vertex(3, a);
  106.     boost::add_edge(u, v, a);
  107.   }
  108.   Graph b;
  109.   {
  110.     boost::graph_traits<Graph>::vertex_descriptor v, u, y;
  111.     u = vertex(1, b);
  112.     v = vertex(2, b);
  113.     y = vertex(3, b);
  114.     boost::add_edge(u, v, b);
  115.     boost::add_edge(y, v, b);
  116.   }
  117.  
  118.   const char* name = "123456";
  119.   std::cout << "---Graph1---" << "\n";
  120.   boost::print_graph(a);
  121.   std::cout << "Edges: ";
  122.   boost::print_edges(a,name);
  123.   std::cout << "---Graph2---" << "\n";
  124.   boost::print_graph(b);
  125.   std::cout << "Edges: ";
  126.   boost::print_edges(b,name);
  127.  
  128.   compare(a,b);
  129. }
  130.  
Success #stdin #stdout 0s 3424KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
---Graph1---
0 <--> 
1 <--> 2 
2 <--> 1 
Edges: (2,3) 
---Graph2---
0 <--> 
1 <--> 2 
2 <--> 1 3 
3 <--> 2 
Edges: (2,3) (4,3) 
---- Vertices ----
same: 3
extra: 1
missing: 0
---- Edges ----
same: 1
extra: 1
missing: 0
https://ideone.com/yxwiGz
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!