使用C++和boost庫的哈希問題

Question

我正在爲圖挖掘編寫代碼。 下面是完整的源代碼：http://pastebin.com/BpjZPcEi

我嘗試使用std unordered_set，但我得到了這部分的問題：

bool edgeexist(Graph const& g, int const& fromid, int const& toid, unsigned const& elabel) { 
    int bn = 0; 

     if (num_edges(g) != 0) { 
      edge_pair ep; 
      for (ep = edges(g); ep.first != ep.second; ++ep.first) // ep edge number 
      { 
       vertex_t from = source(*ep.first, g); 
       vertex_t to = target(*ep.first, g); 
       edge_t edg = edge(from, to, g); 

       if ((g[from].id == fromid) && (g[to].id == toid) && (g[edg.first].label == elabel)) { 
        return true; 
       } 

     } 
    } 

    return false; 
} 


std::unordered_set<std::array<int, 3>> edgesdiff(Graph const& g1,Graph const& g2){ 

    std::unordered_set<edge_iter> v1,v2,diff; 
    std::array<int, 3> t; 
    std::unordered_set<std::array<int, 3>> res; 


    for(auto x:edges(g1)){ 

      vertex_t from = source(*x, g1); 
      t[0]=g1[from].id; 

      vertex_t to = target(*x, g1); 
      t[1]=g1[to].id; 

      edge_t edg = edge(from, to, g1); 
      t[2]=g1[edg.first].label; 

     if(!edgeexist(g2,t[0],t[1],t[2])){res.insert(t);} 


    } 

return res; 
} 

當我運行的代碼塊的程序，我得到這個消息：

/usr/include/c++/4.9/bits/hashtable_policy.h|85|error: no match for call to ‘(const hashedge) (const boost::detail::undirected_edge_iter<std::_List_iterator<boost::list_edge<unsigned int, EdgeProperties> >, boost::detail::edge_desc_impl<boost::undirected_tag, unsigned int>, int>&)’| 

這是什麼意思，我該如何解決這個問題？

Answer 1

讀取代碼後，一組無序的散列函數不採取兩個參數（更不用說Graph由值☹）。

你需要至少像這樣（使其可讀！）

struct hashedge { 
    hashedge(Graph const &g) : _g(g) {} 

    size_t operator()(const edge_iter e) const { 
     using namespace boost; 
     size_t seed = 42; 
     hash_combine(seed, _g[source(*e, _g)]); 
     hash_combine(seed, _g[*e].label); 
     hash_combine(seed, _g[target(*e, _g)]); 
     return seed; 
    } 

private: 
    Graph const &_g; 
}; 

它使用一個分治散列捆綁特性。所以你分別定義這些：

namespace boost { 
template <> struct hash<VertexProperties> { 
    size_t operator()(VertexProperties const &v) const { 
     using namespace boost; 
     auto seed = hash_value(v.id); 
     hash_combine(seed, v.label); 
     return seed; 
    } 
}; 
template <> struct hash<EdgeProperties> { 
    size_t operator()(EdgeProperties const &e) const { 
     using namespace boost; 
     auto seed = hash_value(e.id); 
     hash_combine(seed, e.label); 
     return seed; 
    } 
}; 
} 

編譯和工作。

現在你有類似的問題與unordered_set<Graph>。我很肯定你是從錯誤的角度看待這個問題的。你能比較傳遞性凝聚嗎？你可以使用過濾圖嗎？

這裏的一個局部的演示，使用edge_descriptor代替edge_iterator（因爲，爲什麼迭代器）：

Live On Coliru

#include <boost/graph/adjacency_list.hpp> 
#include <iostream> 
#include <unordered_set> 

struct VertexProperties { 
    int id; 
    int label; 
    VertexProperties(unsigned i = 0, unsigned l = 0) : id(i), label(l) {} 
}; 

struct EdgeProperties { 
    unsigned id; 
    unsigned label; 
    EdgeProperties(unsigned i = 0, unsigned l = 0) : id(i), label(l) {} 
}; 

namespace boost { 
template <> struct hash<VertexProperties> { 
    size_t operator()(VertexProperties const &v) const { 
     auto seed = hash_value(v.id); 
     hash_combine(seed, v.label); 
     return seed; 
    } 
}; 
template <> struct hash<EdgeProperties> { 
    size_t operator()(EdgeProperties const &e) const { 
     auto seed = hash_value(e.id); 
     hash_combine(seed, e.label); 
     return seed; 
    } 
}; 
} 

struct GraphProperties { 
    unsigned id; 
    unsigned label; 
    GraphProperties(unsigned i = 0, unsigned l = 0) : id(i), label(l) {} 
}; 

// adjacency_list 
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, VertexProperties, EdgeProperties, GraphProperties> Graph; 
typedef boost::graph_traits<Graph>::edge_descriptor edge_descriptor; 

struct hashedge { 
    hashedge(Graph const &g) : _g(g) {} 

    size_t operator()(const edge_descriptor e) const { 
     using namespace boost; 

     size_t seed = 42; 
     hash_combine(seed, _g[source(e, _g)]); 
     hash_combine(seed, _g[e].label); 
     hash_combine(seed, _g[target(e, _g)]); 
     return seed; 
    } 

    private: 
    Graph const &_g; 
}; 

int main() { 
    std::vector<Graph> dataG; 
    for (auto& g : dataG) { 
     auto es = edges(g); 
     std::unordered_set<edge_descriptor, hashedge> edgehash(es.first, es.second, 0ul, hashedge(g)); 
    } 
}