Невозможно сопоставить сравнение графа графа

Question

Я пытаюсь сделать некоторую статистику с графиками (сравнивая 2 графика). Но у меня проблема, когда я сравниваю ребра.

Итак, я создаю два графика с некоторыми ребрами, а затем некоторые шаблоны для операций с вершинами и ребрами. Для вершин он работает неплохо, но для краев он работает неправильно.

#include <boost/graph/adjacency_list.hpp> 
#include <boost/graph/reverse_graph.hpp> 
#include <boost/graph/iteration_macros.hpp> 
#include <boost/graph/graph_utility.hpp> 
typedef boost::adjacency_list < boost::vecS, boost::vecS, 
          boost::undirectedS > Graph; 

template <typename T> std::set<T> operator-(const std::set<T>& a, 
              const std::set<T>& b) 
{ 
    std::set<T> r; 
    std::set_difference(
         a.begin(), a.end(), 
         b.begin(), b.end(), 
         std::inserter(r, r.end())); 

    return r; 
} 

template <typename T> std::set<T> operator/(const std::set<T>& a, 
              const std::set<T>& b) 
{ 
    std::set<T> r; 
    std::set_intersection(
          a.begin(), a.end(), 
          b.begin(), b.end(), 
          std::inserter(r, r.end())); 

    return r; 
} 



void compare(const Graph& a, const Graph& b) 
{ 
    std::set<Graph::vertex_descriptor > av, bv, samev, extrav, missingv; 
    std::set<Graph::edge_descriptor> ae, be, re, samee, extrae, missinge; 

    BGL_FORALL_VERTICES_T(v, a, Graph) av.insert(v); 
    BGL_FORALL_VERTICES_T(v, b, Graph) bv.insert(v); 
    samev = (av/bv); 
    extrav = (bv - av); 
    missingv = (av - bv); 


    BGL_FORALL_EDGES_T(e, a, Graph) ae.insert(e); 
    BGL_FORALL_EDGES_T(e, b, Graph) be.insert(e); 

    samee = (ae/be); 
    extrae = (be - ae); 
    missinge = (ae - be); 

    // TODO(silgon): reverse_graph 
    // boost::reverse_graph<Graph> r(b); 
    // BGL_FORALL_EDGES_T(e, r, Graph) re.insert(e); 
    std::cout << "---- Vertices ----\n" 
       << "same: " << samev.size() << std::endl 
       << "extra: " << extrav.size() << std::endl 
       << "missing: " << missingv.size() << std::endl; 

    std::cout << "---- Edges ----\n" 
       << "same: " << samee.size() << std::endl 
       << "extra: " << extrae.size() << std::endl 
       << "missing: " << missinge.size() << std::endl; 
} 

int main() 
{ 
    Graph a; 
    { 
     boost::graph_traits<Graph>::vertex_descriptor v, u, y; 
     u = boost::vertex(1, a); 
     v = boost::vertex(2, a); 
     y = boost::vertex(3, a); 
     boost::add_edge(u, v, a); 
    } 
    Graph b; 
    { 
     boost::graph_traits<Graph>::vertex_descriptor v, u, y; 
     u = vertex(1, b); 
     v = vertex(2, b); 
     y = vertex(3, b); 
     boost::add_edge(u, v, b); 
     boost::add_edge(y, v, b); 
    } 

    const char* name = "123456"; 
    std::cout << "---Graph1---" << "\n"; 
    boost::print_graph(a); 
    std::cout << "Edges: "; 
    boost::print_edges(a,name); 
    std::cout << "---Graph2---" << "\n"; 
    boost::print_graph(b); 
    std::cout << "Edges: "; 
    boost::print_edges(b,name); 

    compare(a,b); 
} 

Что касается результата программы это следующее:

---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: 0 
extra: 2 
missing: 1 

Вы можете видеть, что один из краев такой же (2,3), но при выполнении операции он не принимает это учитывается, поэтому в результатах он говорит то же самое: 0, и либо лишние, либо отсутствующие результаты не работают.

Answer 1

В качестве временного решения моей проблемы, вместо того, чтобы:

std::set<Graph::edge_descriptor> ae 
BGL_FORALL_EDGES_T(e, a, Graph) ae.insert(e) 

Я сделал следующий код для ребер.

std::set<std::pair<unsigned long, unsigned long> > ae; 
BGL_FORALL_EDGES_T(e, ga, Graph) gae.insert(std::make_pair(e.m_source, 
                  e.m_target)); 

Проблема заключается в том, что края повышающего графа имеют «m_eproperty», который я не знаю, почему там, и она содержит значение, как 0x125d0c0. Затем я создал пару на основе источника и цели ребра, а затем я оценил то же самое, что и выше (с помощью шаблонов).

Answer 2

Порывшись в edge_descriptor реализации Boost (в boost/graph/detail/edge.hpp, мы видим, что каждое ребро Дескриптор хранит источник и цель vertex_descriptor с, но и указатель на собственность края. Этот указатель отличается для двух ребер, vertex_descriptor s в остальном идентичны .

Это означает, что вам нужно определить свой собственный edge_descriptor компаратор, который вы используете для std::set с и для set_intersection/set_difference операций, например, как это:

struct edge_cmp 
{ 
    bool operator() (const Graph::edge_descriptor& a, const Graph::edge_descriptor& b) const 
    { 
    if (a.m_source < b.m_source) { return true; } 
    if (a.m_source > b.m_source) { return false; } 
    return (a.m_target < b.m_target); 
    } 
}; 

Объект-компаратор этого типа должен быть передан всем конструкциям, которые вы создаете, и к вызовам пересечения/разницы.

I've forked your code on ideone и соответствующим образом изменил его. Выход:

---- Vertices ---- 
same: 3 
extra: 1 
missing: 0 
---- Edges ---- 
same: 1 
extra: 1 
missing: 0