graph_neighbour_sampler.hh 4.82 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// graph-tool -- a general graph modification and manipulation thingy
//
// Copyright (C) 2006-2016 Tiago de Paula Peixoto <tiago@skewed.de>
//
// 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_NEIGHBOUR_SAMPLER_HH
#define GRAPH_NEIGHBOUR_SAMPLER_HH

#include "config.h"

#include "graph_tool.hh"

// Sample neighbours efficiently
// =============================

namespace graph_tool
{

31
32
template <class Graph, class Weighted, class Dynamic>
class NeighbourSampler
33
34
35
36
37
{
public:
    typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_t;

    template <class Eprop>
38
39
40
41
    NeighbourSampler(Graph& g, Eprop& eweight, bool self_loops=false)
        : _sampler(get(vertex_index_t(), g), num_vertices(g)),
          _sampler_pos(get(vertex_index_t(), g), num_vertices(g)),
          _eindex(get(edge_index_t(), g))
42
    {
43
        for (auto e : edges_range(g))
44
        {
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
            auto u = source(e, g);
            auto v = target(e, g);

            if (!self_loops && u == v)
                continue;

            auto w = eweight[e];

            if (w == 0)
                continue;

            if (u == v)
            {
                insert(v, u, w, e);
            }
            else
61
            {
62
63
                insert(v, u, w, e);
                insert(u, v, w, e);
64
65
66
67
68
69
70
            }
        }
    }

    template <class RNG>
    vertex_t sample(vertex_t v, RNG& rng)
    {
71
72
73
        auto& sampler = _sampler[v];
        auto& item = sample_item(sampler, rng);
        return item.first;
74
75
76
77
78
79
80
    }

    bool empty(vertex_t v)
    {
        return _sampler[v].empty();
    }

81
82
    template <class Edge>
    void remove(vertex_t v, vertex_t u, Edge&& e)
83
84
85
86
    {
        auto& sampler = _sampler[v];
        auto& sampler_pos = _sampler_pos[v];

87
88
        auto k = std::make_pair(u, _eindex[e]);
        remove_item(k, sampler, sampler_pos);
89
90
    }

91
92
    template <class Weight, class Edge>
    void insert(vertex_t v, vertex_t u, Weight w, Edge&& e)
93
94
95
    {
        auto& sampler = _sampler[v];
        auto& sampler_pos = _sampler_pos[v];
96
97
        auto k = std::make_pair(u, _eindex[e]);
        insert_item(k, w, sampler, sampler_pos);
98
99
100
    }

private:
101
102
    typedef std::pair<vertex_t, size_t> item_t;
    typedef gt_hash_map<item_t, size_t> pos_map_t;
103

104
105
    template <class RNG>
    const item_t& sample_item(std::vector<item_t>& sampler, RNG& rng)
106
    {
107
        return uniform_sample(sampler, rng);
108
109
    }

110
111
    template <class Sampler, class RNG>
    const item_t& sample_item(Sampler& sampler, RNG& rng)
112
    {
113
        return sampler.sample(rng);
114
115
    }

116
117
    void remove_item(item_t& u, std::vector<item_t>& sampler,
                     pos_map_t& sampler_pos)
118
    {
119
120
121
122
123
124
        auto& back = sampler.back();
        size_t pos = sampler_pos[u];
        sampler_pos[back] = pos;
        sampler[pos] = back;
        sampler.pop_back();
        sampler_pos.erase(u);
125
126
    }

127
128
129
    template <class Sampler>
    void remove_item(item_t& u, Sampler& sampler,
                     pos_map_t& sampler_pos)
130
    {
131
132
133
134
        size_t pos = sampler_pos[u];
        sampler.remove(pos);
        sampler_pos.erase(u);
    }
135
136


137
138
139
140
141
142
    template <class Weight>
    void insert_item(item_t& u, Weight, std::vector<item_t>& sampler,
                     pos_map_t& sampler_pos)
    {
        sampler_pos[u] = sampler.size();
        sampler.push_back(u);
143
144
    }

145
146
147
    template <class Sampler, class Weight>
    void insert_item(item_t& u, Weight w, Sampler& sampler,
                     pos_map_t& sampler_pos)
148
    {
149
150
        assert(sampler_pos.find(u) == sampler_pos.end());
        sampler_pos[u] = sampler.insert(u, w);
151
152
    }

153
154
155
156
157
158
159
160
161
    typedef typename std::conditional<Weighted::value,
                                      typename std::conditional<Dynamic::value,
                                                                DynamicSampler<item_t>,
                                                                Sampler<item_t>>::type,
                                      vector<item_t>>::type
        sampler_t;

    typedef typename vprop_map_t<sampler_t>::type vsampler_t;
    typename vsampler_t::unchecked_t _sampler;
162

163
    typedef typename vprop_map_t<pos_map_t>::type sampler_pos_t;
164
    typename sampler_pos_t::unchecked_t _sampler_pos;
165
166

    typename property_map<Graph, edge_index_t>::type _eindex;
167
168
169
170
171
};

}

#endif // GRAPH_NEIGHBOUR_SAMPLER_HH