graph_similarity.hh 4.58 KB
Newer Older
Tiago Peixoto's avatar
Tiago Peixoto committed
1 2 3
// graph-tool -- a general graph modification and manipulation thingy
//
// Copyright (C) 2006-2015 Tiago de Paula Peixoto <tiago@skewed.de>
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 3
// of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program. If not, see <http://www.gnu.org/licenses/>.

#ifndef GRAPH_SIMILARITY_HH
#define GRAPH_SIMILARITY_HH

Tiago Peixoto's avatar
Tiago Peixoto committed
21
#include <unordered_set>
22

23

24 25 26 27 28 29
namespace graph_tool
{
using namespace std;
using namespace boost;


30 31
template <class Keys, class Set1, class Set2>
size_t intersection_size(Keys& ks, Set1& s1, Set2& s2)
32 33
{
    size_t s = 0;
34
    for (auto k : ks)
35
    {
36 37
        int c1 = s1.count(k);
        int c2 = s2.count(k);
38 39 40 41 42 43 44 45 46 47
        s += max(c1, c2) - abs(c1 - c2);
    }
    return s;
}


struct get_similarity
{
    template <class Graph1, class Graph2, class LabelMap>
    void operator()(const Graph1& g1, const Graph2* g2p, LabelMap l1,
48
                    boost::any al2, size_t& s) const
49 50 51
    {
        const Graph2& g2 = *g2p;

52 53
        LabelMap l2 = boost::any_cast<typename LabelMap::checked_t>(al2).get_unchecked(num_vertices(g2));

54
        typedef typename property_traits<LabelMap>::value_type label_t;
Tiago Peixoto's avatar
Tiago Peixoto committed
55

56
        std::unordered_map<label_t, typename graph_traits<Graph1>::vertex_descriptor>
57
            lmap1;
58
        std::unordered_map<label_t, typename graph_traits<Graph2>::vertex_descriptor>
59 60
            lmap2;

61 62 63 64
        for (auto v : vertices_range(g1))
            lmap1[get(l1, v)] = v;
        for (auto v : vertices_range(g2))
            lmap2[get(l2, v)] = v;
65 66

        s = 0;
67
        for (auto& lv1 : lmap1)
68
        {
69
            auto v1 = lv1.second;
70

71
            auto li2 = lmap2.find(lv1.first);
72 73
            if (li2 == lmap2.end())
                continue;
74 75
            auto v2 = li2->second;

76 77 78
            std::unordered_set<label_t> keys;
            std::unordered_multiset<label_t> adj1;
            std::unordered_multiset<label_t> adj2;
79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127

            for (auto a1 : adjacent_vertices_range(v1, g1))
            {
                adj1.insert(get(l1, a1));
                keys.insert(get(l1, a1));
            }

            for (auto a2 : adjacent_vertices_range(v2, g2))
            {
                adj2.insert(get(l2, a2));
                keys.insert(get(l2, a2));
            }

            s += intersection_size(keys, adj1, adj2);
        }
    }
};

struct get_similarity_fast
{
    template <class Graph1, class Graph2, class LabelMap>
    void operator()(const Graph1& g1, const Graph2* g2p, LabelMap l1,
                    boost::any al2, size_t& s) const
    {
        const Graph2& g2 = *g2p;

        LabelMap l2 = boost::any_cast<LabelMap>(al2);

        typedef typename property_traits<LabelMap>::value_type label_t;

        vector<typename graph_traits<Graph1>::vertex_descriptor> lmap1;
        vector<typename graph_traits<Graph1>::vertex_descriptor> lmap2;

        for (auto v : vertices_range(g1))
        {
            size_t i = get(l1, v);
            if (lmap1.size() <= i)
                lmap1.resize(i + 1);
            lmap1[i] = v;
        }

        for (auto v : vertices_range(g2))
        {
            size_t i = get(l2, v);
            if (lmap2.size() <= i)
                lmap2.resize(i + 1);
            lmap2[i] = v;
        }

128
        size_t ss = 0;
129

130
        int64_t i, N = std::min(lmap1.size(), lmap2.size());
Tiago Peixoto's avatar
Tiago Peixoto committed
131
        #pragma omp parallel for default(shared) private(i) schedule(runtime) \
132
            reduction(+:ss) if (N > 100)
133 134 135 136
        for (i = 0; i < N; ++i)
        {
            auto v1 = lmap1[i];
            auto v2 = lmap2[i];
137

Tiago Peixoto's avatar
Tiago Peixoto committed
138 139 140
            std::unordered_set<label_t> keys;
            std::unordered_multiset<label_t> adj1;
            std::unordered_multiset<label_t> adj2;
141

142
            for (auto a1 : adjacent_vertices_range(v1, g1))
143
            {
144 145
                adj1.insert(get(l1, a1));
                keys.insert(get(l1, a1));
146
            }
Tiago Peixoto's avatar
Tiago Peixoto committed
147

148
            for (auto a2 : adjacent_vertices_range(v2, g2))
149
            {
150 151
                adj2.insert(get(l2, a2));
                keys.insert(get(l2, a2));
152 153
            }

154
            ss += intersection_size(keys, adj1, adj2);
155
        }
156 157

        s = ss;
158 159 160 161 162 163
    }
};

} // graph_tool namespace

#endif // GRAPH_SIMILARITY_HH