graph_similarity.hh 6.64 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
31
32
33
34
35
36
37
38
template <class Map, class K>
typename Map::value_type::second_type get_map(Map& m, K&& k)
{
    auto iter = m.find(k);
    if (iter == m.end())
        return typename Map::value_type::second_type(0);
    return iter->second;
}


39
template <class Keys, class Set1, class Set2>
40
auto set_difference(Keys& ks, Set1& s1, Set2& s2, bool asym)
41
{
42
43
    typename Set1::value_type::second_type s = 0;
    for (auto& k : ks)
44
    {
45
46
47
48
49
50
        auto x1 = get_map(s1, k);
        auto x2 = get_map(s2, k);
        if (x1 > x2)
            s += x1 - x2;
        else if (!asym)
            s += x2 - x1;
51
52
53
54
    }
    return s;
}

55
56
template <class Vertex, class WeightMap, class LabelMap,
          class Graph1, class Graph2, class Keys, class Adj>
57
58
auto vertex_difference(Vertex v1, Vertex v2, WeightMap& ew1, WeightMap& ew2,
                       LabelMap& l1, LabelMap& l2, const Graph1& g1,
59
60
                       const Graph2& g2, bool asym, Keys& keys, Adj& adj1,
                       Adj& adj2)
61
{
62
63
64
65
66
67
68
69
70
71
    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);
        }
    }
72

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

84
    return set_difference(keys, adj1, adj2, asym);
85
86
87
88
}

template <class Graph1, class Graph2, class WeightMap, class LabelMap>
auto get_similarity(const Graph1& g1, const Graph2& g2, WeightMap ew1,
89
                    WeightMap ew2, LabelMap l1, LabelMap l2, bool asym)
90
{
91
92
93
94
95
96
97
98
99
100
101
102
103
104
    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)
105
    {
106
107
        vertex_t v1 = lv1.second;
        vertex_t v2;
108

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

115
116
117
118
119
        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,
                               adj1, adj2);
120
    }
121

122
    if (!asym)
123
    {
124
125
126
127
        for (auto& lv2 : lmap2)
        {
            vertex_t v2 = lv2.second;
            vertex_t v1;
128

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

135
136
137
138
139
            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,
                                   keys, adj1, adj2);
140
        }
141
    }
142
143
144
145
146
    return s;
}

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

    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());

175
176
177
    idx_set<label_t> keys;
    idx_map<label_t, val_t> adj1, adj2;

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

196
197
198
    if (!asym)
    {
        #pragma omp parallel if (num_vertices(g2) > OPENMP_MIN_THRESH)  \
199
            reduction(+:s) firstprivate(keys, adj1, adj2)
200
201
202
203
204
205
206
207
        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;
208
209
210
211
212
                 keys.clear();
                 adj1.clear();
                 adj2.clear();
                 s += vertex_difference(v1, v2, ew1, ew2, l1, l2, g1, g2, false,
                                        keys, adj1, adj2);
213
214
             });
    }
215
216
217

    return s;
}
218
219
220
221

} // graph_tool namespace

#endif // GRAPH_SIMILARITY_HH