graph_sfdp.cc 9.29 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-2015 Tiago de Paula Peixoto <tiago@skewed.de>
Tiago Peixoto's avatar
Tiago Peixoto committed
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//
// 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/>.

#include "graph_filtering.hh"
#include "graph.hh"
#include "graph_properties.hh"
#include "graph_exceptions.hh"

#include <boost/lambda/bind.hpp>

#include "graph_sfdp.hh"
26
#include "random.hh"
Tiago Peixoto's avatar
Tiago Peixoto committed
27
28
29
30
31
32
33
34
35

using namespace std;
using namespace boost;
using namespace graph_tool;

void sfdp_layout(GraphInterface& g, boost::any pos, boost::any vweight,
                 boost::any eweight, boost::any pin, python::object spring_parms,
                 double theta, double init_step, double step_schedule,
                 size_t max_level, double epsilon, size_t max_iter,
36
                 bool adaptive, bool verbose, rng_t& rng)
Tiago Peixoto's avatar
Tiago Peixoto committed
37
38
39
40
41
42
43
44
{
    typedef ConstantPropertyMap<int32_t,GraphInterface::vertex_t> vweight_map_t;
    typedef ConstantPropertyMap<int32_t,GraphInterface::edge_t> eweight_map_t;
    typedef mpl::push_back<vertex_scalar_properties, vweight_map_t>::type
        vertex_props_t;
    typedef mpl::push_back<edge_scalar_properties, eweight_map_t>::type
        edge_props_t;

45
46
    typedef property_map_type::apply<int32_t,
                                     GraphInterface::vertex_index_map_t>::type
47
48
        group_map_t;

Tiago Peixoto's avatar
Tiago Peixoto committed
49
50
51
    double C = python::extract<double>(spring_parms[0]);
    double K = python::extract<double>(spring_parms[1]);
    double p = python::extract<double>(spring_parms[2]);
52
    double gamma = python::extract<double>(spring_parms[3]);
53
54
    double mu = python::extract<double>(spring_parms[4]);
    double mu_p = python::extract<double>(spring_parms[5]);
55
    group_map_t groups =
56
        any_cast<group_map_t>(python::extract<any>(spring_parms[6]));
Tiago Peixoto's avatar
Tiago Peixoto committed
57
58
59
60
61
62

    if(vweight.empty())
        vweight = vweight_map_t(1);
    if(eweight.empty())
        eweight = eweight_map_t(1);

63
64
65
66
    typedef property_map_type::apply<uint8_t,
                                     GraphInterface::vertex_index_map_t>::type
        pin_map_t;
    pin_map_t pin_map = any_cast<pin_map_t>(pin);
67

Tiago Peixoto's avatar
Tiago Peixoto committed
68
69
    run_action<graph_tool::detail::never_directed>()
        (g,
Tiago Peixoto's avatar
Tiago Peixoto committed
70
         std::bind(get_sfdp_layout(C, K, p, theta, gamma, mu, mu_p, init_step,
71
                                   step_schedule, max_level, epsilon,
Tiago Peixoto's avatar
Tiago Peixoto committed
72
73
74
                                   max_iter, adaptive),
                   placeholders::_1, g.GetVertexIndex(), placeholders::_2,
                   placeholders::_3, placeholders::_4,
75
76
77
                   pin_map.get_unchecked(num_vertices(g.GetGraph())),
                   groups.get_unchecked(num_vertices(g.GetGraph())), verbose,
                   std::ref(rng)),
78
79
         vertex_floating_vector_properties(), vertex_props_t(), edge_props_t())
        (pos, vweight, eweight);
Tiago Peixoto's avatar
Tiago Peixoto committed
80
81
82
83
84
85
}

struct do_propagate_pos
{
    template <class Graph, class CoarseGraph, class VertexMap, class PosMap,
              class RNG>
Tiago Peixoto's avatar
Tiago Peixoto committed
86
    void operator()(Graph& g, CoarseGraph* cg, VertexMap vmap,
Tiago Peixoto's avatar
Tiago Peixoto committed
87
88
89
90
91
92
93
94
95
                    boost::any acvmap, PosMap pos, boost::any acpos,
                    double delta, RNG& rng) const
    {
        typename PosMap::checked_t cpos =
            any_cast<typename PosMap::checked_t>(acpos);
        typename VertexMap::checked_t cvmap =
            any_cast<typename VertexMap::checked_t>(acvmap);
        typedef typename property_traits<VertexMap>::value_type c_t;
        typedef typename property_traits<PosMap>::value_type pos_t;
96
        typedef typename pos_t::value_type val_t;
Tiago Peixoto's avatar
Tiago Peixoto committed
97

Tiago Peixoto's avatar
Tiago Peixoto committed
98
        uniform_real_distribution<val_t> noise(-delta, delta);
99
        unordered_map<c_t, pos_t> cmap(num_vertices(*cg));
100
101

        for (auto v : vertices_range(*cg))
Tiago Peixoto's avatar
Tiago Peixoto committed
102
103
            cmap[cvmap[v]] = cpos[v];

104
        for (auto v : vertices_range(g))
Tiago Peixoto's avatar
Tiago Peixoto committed
105
106
        {
            pos[v] = cmap[vmap[v]];
Tiago Peixoto's avatar
Tiago Peixoto committed
107
108

            if (delta > 0)
Tiago Peixoto's avatar
Tiago Peixoto committed
109
            {
110
                pos[v].resize(2, 0);
Tiago Peixoto's avatar
Tiago Peixoto committed
111
112
                for (size_t j = 0; j < pos[v].size(); ++j)
                    pos[v][j] += noise(rng);
Tiago Peixoto's avatar
Tiago Peixoto committed
113
114
115
116
117
118
119
120
121
122
123
            }
        }
    }
};

struct get_pointers
{
    template <class List>
    struct apply
    {
        typedef typename mpl::transform<List,
Tiago Peixoto's avatar
Tiago Peixoto committed
124
                                        mpl::quote1<std::add_pointer> >::type type;
Tiago Peixoto's avatar
Tiago Peixoto committed
125
126
127
128
129
    };
};

void propagate_pos(GraphInterface& gi, GraphInterface& cgi, boost::any vmap,
                   boost::any cvmap, boost::any pos, boost::any cpos,
130
                   double delta, rng_t& rng)
Tiago Peixoto's avatar
Tiago Peixoto committed
131
{
132
    typedef mpl::vector<property_map_type::apply
Tiago Peixoto's avatar
Tiago Peixoto committed
133
134
135
136
137
138
                            <int32_t,
                             GraphInterface::vertex_index_map_t>::type>::type
        vmaps_t;


    run_action<>()
Tiago Peixoto's avatar
Tiago Peixoto committed
139
140
141
        (gi, std::bind(do_propagate_pos(),
                       placeholders::_1, placeholders::_2, placeholders::_3,
                       cvmap, placeholders::_4, cpos, delta, std::ref(rng)),
Tiago Peixoto's avatar
Tiago Peixoto committed
142
143
144
145
146
147
148
149
150
151
152
153
         get_pointers::apply<graph_tool::detail::all_graph_views>::type(),
         vmaps_t(), vertex_floating_vector_properties())
        (cgi.GetGraphView(), vmap, pos);
}

struct do_propagate_pos_mivs
{
    template <class Graph, class MIVSMap, class PosMap,
              class RNG>
    void operator()(Graph& g, MIVSMap mivs, PosMap pos, double delta, RNG& rng) const
    {
        typedef typename property_traits<PosMap>::value_type pos_t;
154
        typedef typename pos_t::value_type val_t;
Tiago Peixoto's avatar
Tiago Peixoto committed
155

Tiago Peixoto's avatar
Tiago Peixoto committed
156
        uniform_real_distribution<val_t> noise(-delta, delta);
Tiago Peixoto's avatar
Tiago Peixoto committed
157

158
        for (auto v : vertices_range(g))
Tiago Peixoto's avatar
Tiago Peixoto committed
159
160
161
162
163
164
        {
            if (mivs[v])
                continue;
            pos[v].resize(2);
            pos[v][0] = pos[v][1] = 0;
            size_t count = 0;
165
166

            for (auto a : adjacent_vertices_range(v, g))
Tiago Peixoto's avatar
Tiago Peixoto committed
167
            {
168
                if (!mivs[a])
Tiago Peixoto's avatar
Tiago Peixoto committed
169
                    continue;
170
                pos[a].resize(2, 0);
Tiago Peixoto's avatar
Tiago Peixoto committed
171
                for (size_t j = 0; j < pos[v].size(); ++j)
172
                    pos[v][j] += pos[a][j];
Tiago Peixoto's avatar
Tiago Peixoto committed
173
174
175
176
177
178
179
180
181
                ++count;
            }

            if (count == 0)
                throw ValueException("invalid MIVS! Vertex has no neighbours "
                                     "belonging to the set!");

            if (count == 1)
            {
182
183
184
                if (delta > 0)
                {
                    for (size_t j = 0; j < pos[v].size(); ++j)
Tiago Peixoto's avatar
Tiago Peixoto committed
185
                        pos[v][j] += noise(rng);
186
                }
Tiago Peixoto's avatar
Tiago Peixoto committed
187
188
189
190
191
192
193
194
195
196
197
198
            }
            else
            {
                for (size_t j = 0; j < pos[v].size(); ++j)
                    pos[v][j] /= count;
            }
        }
    }
};


void propagate_pos_mivs(GraphInterface& gi, boost::any mivs, boost::any pos,
199
                        double delta, rng_t& rng)
Tiago Peixoto's avatar
Tiago Peixoto committed
200
201
{
    run_action<>()
Tiago Peixoto's avatar
Tiago Peixoto committed
202
203
204
        (gi, std::bind(do_propagate_pos_mivs(),
                       placeholders::_1, placeholders::_2, placeholders::_3,
                       delta, std::ref(rng)),
Tiago Peixoto's avatar
Tiago Peixoto committed
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
         vertex_scalar_properties(), vertex_floating_vector_properties())
        (mivs, pos);
}


struct do_avg_dist
{
    template <class Graph, class PosMap>
    void operator()(Graph& g, PosMap pos, double& ad) const
    {
        int i, N = num_vertices(g);
        size_t count = 0;
        double d = 0;
        #pragma omp parallel for default(shared) private(i) \
            reduction(+: d, count)
        for (i = 0; i < N; ++i)
        {
            typename graph_traits<Graph>::vertex_descriptor v =
                vertex(i, g);
            if (v == graph_traits<Graph>::null_vertex())
                continue;
226
            for (auto a : adjacent_vertices_range(v, g))
Tiago Peixoto's avatar
Tiago Peixoto committed
227
            {
228
                d += dist(pos[v], pos[a]);
Tiago Peixoto's avatar
Tiago Peixoto committed
229
230
231
                count++;
            }
        }
232
233
        if (count > 0)
            d /= count;
Tiago Peixoto's avatar
Tiago Peixoto committed
234
235
236
237
238
239
240
241
242
        ad = d;
    }
};


double avg_dist(GraphInterface& gi, boost::any pos)
{
    double d;
    run_action<>()
Tiago Peixoto's avatar
Tiago Peixoto committed
243
244
        (gi, std::bind(do_avg_dist(), placeholders::_1,
                       placeholders::_2, std::ref(d)),
Tiago Peixoto's avatar
Tiago Peixoto committed
245
246
247
248
         vertex_scalar_vector_properties()) (pos);
    return d;
}

249
250
251
252
253
254
255

struct do_sanitize_pos
{
    template <class Graph, class PosMap>
    void operator()(Graph& g, PosMap pos) const
    {
        int i, N = num_vertices(g);
256
        #pragma omp parallel for default(shared) private(i) schedule(runtime) if (N > 100)
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
        for (i = 0; i < N; ++i)
        {
            typename graph_traits<Graph>::vertex_descriptor v =
                vertex(i, g);
            if (v == graph_traits<Graph>::null_vertex())
                continue;
            pos[v].resize(2);
        }
    }
};


void sanitize_pos(GraphInterface& gi, boost::any pos)
{
    run_action<>()
Tiago Peixoto's avatar
Tiago Peixoto committed
272
        (gi, std::bind(do_sanitize_pos(), placeholders::_1, placeholders::_2),
273
274
275
         vertex_scalar_vector_properties()) (pos);
}

Tiago Peixoto's avatar
Tiago Peixoto committed
276
277
278
279
280
281
282
283
#include <boost/python.hpp>

void export_sfdp()
{
    python::def("sfdp_layout", &sfdp_layout);
    python::def("propagate_pos", &propagate_pos);
    python::def("propagate_pos_mivs", &propagate_pos_mivs);
    python::def("avg_dist", &avg_dist);
284
    python::def("sanitize_pos", &sanitize_pos);
Tiago Peixoto's avatar
Tiago Peixoto committed
285
}