graph_similarity.hh 6.96 KB
Newer Older
Tiago Peixoto's avatar
Tiago Peixoto committed
1
2
// graph-tool -- a general graph modification and manipulation thingy
//
Tiago Peixoto's avatar
Tiago Peixoto committed
3
// Copyright (C) 2006-2018 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

21
#include "hash_map_wrap.hh"
22
#include "idx_map.hh"
23

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

29
30
template <bool normed, class Keys, class Set1, class Set2>
auto set_difference(Keys& ks, Set1& s1, Set2& s2, double norm, bool asym)
31
{
32
    typename Set1::value_type::second_type s = 0;
33
34
35
36
37
38
39
40
41
    auto ndispatch = [&](auto x){ return normed ? std::pow(x, norm) : x; };
    auto get_map =
        [&](auto& m, auto&& k)
        {
            auto iter = m.find(k);
            if (iter == m.end())
                return decltype(iter->second)(0);
            return iter->second;
        };
42
    for (auto& k : ks)
43
    {
44
45
46
        auto x1 = get_map(s1, k);
        auto x2 = get_map(s2, k);
        if (x1 > x2)
47
            s += ndispatch(x1 - x2);
48
        else if (!asym)
49
            s += ndispatch(x2 - x1);
50
51
52
53
    }
    return s;
}

54
55
template <class Vertex, class WeightMap, class LabelMap,
          class Graph1, class Graph2, class Keys, class Adj>
56
57
auto vertex_difference(Vertex v1, Vertex v2, WeightMap& ew1, WeightMap& ew2,
                       LabelMap& l1, LabelMap& l2, const Graph1& g1,
58
                       const Graph2& g2, bool asym, Keys& keys, Adj& adj1,
59
                       Adj& adj2, double norm)
60
{
61
62
63
64
65
66
67
68
69
70
    if (v1 != graph_traits<Graph1>::null_vertex())
    {
        for (auto e : out_edges_range(v1, g1))
        {
            auto w = ew1[e];
            auto k = get(l1, target(e, g1));
            adj1[k] += w;
            keys.insert(k);
        }
    }
71

72
73
74
    if (v2 != graph_traits<Graph2>::null_vertex())
    {
        for (auto e : out_edges_range(v2, g2))
75
        {
76
77
78
79
            auto w = ew2[e];
            auto k = get(l2, target(e, g2));
            adj2[k] += w;
            keys.insert(k);
80
81
82
        }
    }

83
84
85
86
    if (norm == 1)
        return set_difference<false>(keys, adj1, adj2, 1, asym);
    else
        return set_difference<true>(keys, adj1, adj2, norm, asym);
87
88
89
90
}

template <class Graph1, class Graph2, class WeightMap, class LabelMap>
auto get_similarity(const Graph1& g1, const Graph2& g2, WeightMap ew1,
91
92
                    WeightMap ew2, LabelMap l1, LabelMap l2, double norm,
                    bool asym)
93
{
94
95
96
97
98
99
100
101
102
103
104
105
106
107
    typedef typename property_traits<LabelMap>::value_type label_t;
    typedef typename property_traits<WeightMap>::value_type val_t;

    typedef typename graph_traits<Graph1>::vertex_descriptor vertex_t;
    std::unordered_map<label_t, vertex_t> lmap1;
    std::unordered_map<label_t, vertex_t> lmap2;

    for (auto v : vertices_range(g1))
        lmap1[get(l1, v)] = v;
    for (auto v : vertices_range(g2))
        lmap2[get(l2, v)] = v;

    val_t s = 0;
    for (auto& lv1 : lmap1)
108
    {
109
110
        vertex_t v1 = lv1.second;
        vertex_t v2;
111

112
113
114
115
116
        auto li2 = lmap2.find(lv1.first);
        if (li2 == lmap2.end())
            v2 = graph_traits<Graph2>::null_vertex();
        else
            v2 = li2->second;
117

118
119
120
121
        std::unordered_set<label_t> keys;
        std::unordered_map<label_t, val_t> adj1, adj2;

        s += vertex_difference(v1, v2, ew1, ew2, l1, l2, g1, g2, asym, keys,
122
                               adj1, adj2, norm);
123
    }
124

125
    if (!asym)
126
    {
127
128
129
130
        for (auto& lv2 : lmap2)
        {
            vertex_t v2 = lv2.second;
            vertex_t v1;
131

132
133
134
135
136
            auto li1 = lmap1.find(lv2.first);
            if (li1 == lmap1.end())
                v1 = graph_traits<Graph2>::null_vertex();
            else
                continue;
137

138
139
140
141
            std::unordered_set<label_t> keys;
            std::unordered_map<label_t, val_t> adj1, adj2;

            s += vertex_difference(v1, v2, ew1, ew2, l1, l2, g1, g2, false,
142
                                   keys, adj1, adj2, norm);
143
        }
144
    }
145
146
147
148
149
    return s;
}

template <class Graph1, class Graph2, class WeightMap, class LabelMap>
auto get_similarity_fast(const Graph1& g1, const Graph2& g2, WeightMap ew1,
150
151
                         WeightMap ew2, LabelMap l1, LabelMap l2, double norm,
                         bool asym)
152
153
154
{
    typedef typename property_traits<WeightMap>::value_type val_t;
    typedef typename graph_traits<Graph1>::vertex_descriptor vertex_t;
155
    typedef typename property_traits<LabelMap>::value_type label_t;
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178

    vector<vertex_t> lmap1, lmap2;

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

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

    size_t N = std::max(lmap1.size(), lmap2.size());
    lmap1.resize(N, graph_traits<Graph1>::null_vertex());
    lmap2.resize(N, graph_traits<Graph2>::null_vertex());

179
180
181
    idx_set<label_t> keys;
    idx_map<label_t, val_t> adj1, adj2;

182
183
    val_t s = 0;
    #pragma omp parallel if (num_vertices(g1) > OPENMP_MIN_THRESH) \
184
        reduction(+:s) firstprivate(keys, adj1, adj2)
185
186
187
188
189
190
    parallel_loop_no_spawn
        (lmap1,
         [&](size_t i, auto v1)
         {
             auto v2 = lmap2[i];
             if (v1 == graph_traits<Graph1>::null_vertex() &&
191
                 v2 == graph_traits<Graph2>::null_vertex())
192
                 return;
193
194
195
196
             keys.clear();
             adj1.clear();
             adj2.clear();
             s += vertex_difference(v1, v2, ew1, ew2, l1, l2, g1, g2, asym,
197
                                    keys, adj1, adj2, norm);
198
199
         });

200
201
202
    if (!asym)
    {
        #pragma omp parallel if (num_vertices(g2) > OPENMP_MIN_THRESH)  \
203
            reduction(+:s) firstprivate(keys, adj1, adj2)
204
205
206
207
208
209
210
211
        parallel_loop_no_spawn
            (lmap2,
             [&](size_t i, auto v2)
             {
                 auto v1 = lmap1[i];
                 if (v1 != graph_traits<Graph1>::null_vertex() ||
                     v2 == graph_traits<Graph2>::null_vertex())
                     return;
212
213
214
215
                 keys.clear();
                 adj1.clear();
                 adj2.clear();
                 s += vertex_difference(v1, v2, ew1, ew2, l1, l2, g1, g2, false,
216
                                        keys, adj1, adj2, norm);
217
218
             });
    }
219
220
221

    return s;
}
222
223
224
225

} // graph_tool namespace

#endif // GRAPH_SIMILARITY_HH