Boost圖形邊緣比較不起作用

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) 

我做了邊緣下面的代碼。

​​3210

的問題是，提升圖形的邊緣有「m_eproperty」我真的不知道爲什麼會出現，它包含像0x125d0c0值。然後，我根據邊的源和目標創建一對，然後按照上面的方式（使用模板）評估。

Answer 2

挖掘到Boost的edge_descriptor實現（boost/graph/detail/edge.hpp，我們發現，每邊描述符存儲源和目標vertex_descriptor S，而且一個指向邊緣屬性。這個指針是兩個邊，其vertex_descriptor s爲其他相同的不同。

這意味着你需要定義自己的edge_descriptor比較，你用你std::set S並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