CODEWITHSUNDEEP
c++boosthashcodeblocksunordered-set
user3101913
user3101913

Reputation: 65

hash problems with c++ and boost library

I'm writing a code for graph mining. Here is the full source code:http://pastebin.com/BpjZPcEi

I'm trying to use std unordered_set but I got problems on this part :

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;
}

When I run the program on code blocks I got this message:

/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>&)’|

what's that mean and how can I solve this problem?

Upvotes: 2

Views: 1208

Answers (1)

sehe
sehe

Reputation: 392833

After reading the code, the hash function of an unordered set doesn't take two arguments (let alone a Graph by value ☹).

You'll need at least something like this (make it readable!!!)

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;
};

This uses divide an conquer to hash the bundled properties. So you define those separately:

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;
    }
};
}

That compiles and works.

Now you have similar issues with the unordered_set<Graph>. I'm pretty sure you're looking at this from the wrong end. Can you compare transitive condensations? Can you use filtered graphs?

Here's a partial demo, using edge_descriptor instead of edge_iterator (because, why 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));
    }
}

Upvotes: 1

Related Questions