graph_layout.cc 11.2 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// graph-tool -- a general graph modification and manipulation thingy
//
// Copyright (C) 2007  Tiago de Paula Peixoto <tiago@forked.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
16
17
// along with this program. If not, see <http://www.gnu.org/licenses/>.

18
19
20
#include "graph_filtering.hh"
#include "graph.hh"
#include "graph_properties.hh"
21
22
23
24
25
26

#include <boost/graph/gursoy_atun_layout.hpp>
#include <boost/graph/kamada_kawai_spring_layout.hpp>
#include <boost/graph/fruchterman_reingold.hpp>
#include <boost/graph/random_layout.hpp>
#include <boost/random.hpp>
27
#include <boost/lambda/lambda.hpp>
28
29
30
31
32
33
34
35
36

using namespace std;
using namespace boost;
using namespace boost::lambda;
using namespace graph_tool;

struct compute_gursoy
{
    template <class Graph, class PosMap, class WeightMap, class IndexMap>
37
    void operator()(const Graph* gp, size_t iter, size_t seed, PosMap pos,
38
                    WeightMap weight, string topology, IndexMap index_map) const
39
    {
40
        const Graph& g = *gp;
41
        mt19937 rng(static_cast<mt19937::result_type>(seed));
42
43
44
        size_t n = HardNumVertices()(&g);

        typename get_weight_map<WeightMap>::type weight_map(weight);
45

46
47
48
49
50
        if (iter == 0)
            iter = n;
        if (topology == "square")
        {
            square_topology<mt19937> top(rng, sqrt(n));
51
52
            gursoy_atun_layout(g, top,  pos, iter, sqrt(double(n)),
                               1.0, 0.8, 0.2, index_map, weight_map);
53
54
55
56
        }
        else if (topology == "circle")
        {
            circle_topology<mt19937> top(rng, n/2);
57
58
            gursoy_atun_layout(g, top,  pos, iter, sqrt(double(n)),
                               1.0, 0.8, 0.2, index_map, weight_map);
59
60
61
62
        }
        else if (topology == "heart")
        {
            heart_topology<mt19937> top(rng);
63
64
65
66
67
68
            vector_property_map<heart_topology<mt19937>::point_type,
                                IndexMap> pos_map (index_map);
            gursoy_atun_layout(g, top, pos_map, iter, sqrt(double(n)),
                              1.0, 0.8, 0.2, index_map, weight_map);
            typename graph_traits<Graph>::vertex_iterator v, v_end;
            for (tie(v, v_end) = vertices(g); v != v_end; ++v)
69
            {
70
71
                pos[*v][0] = pos_map[*v][0];
                pos[*v][1] = pos_map[*v][1];
72
73
74
75
            }
        }
        else
        {
76
77
            throw GraphException("invalid topology for graph layout: " +
                                 topology);
78
        }
79
    }
80

81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
    template <class PropertyMap>
    struct get_weight_map
    {
        typedef typename property_traits<PropertyMap>::value_type
            value_type;
        typedef typename mpl::if_<
            typename mpl::or_<is_floating_point<value_type>,
                              is_same<PropertyMap,dummy_property_map> >::type,
            PropertyMap,
            ConvertedPropertyMap<PropertyMap,double> >::type type;
    };
};

struct copy_points
{
    template <class Graph, class VectorProperty, class PointsMap>
    void operator()(const Graph* g, VectorProperty vec_prop, PointsMap pos_map)
        const
    {
        typename graph_traits<Graph>::vertex_iterator v, v_end;
        for (tie(v, v_end) = vertices(*g); v != v_end; ++v)
102
        {
103
104
105
            vec_prop[*v].resize(2);
            vec_prop[*v][0] = pos_map[*v][0];
            vec_prop[*v][1] = pos_map[*v][1];
106
107
108
109
        }
    }
};

110
struct copy_weights
111
{
112
113
114
115
116
117
    template <class Graph, class WeightSrcMap, class WeightTgtMap>
    void operator()(const Graph* g, WeightSrcMap src_map, WeightTgtMap tgt_map)
        const
    {
        do_copy(g, src_map, tgt_map, is_same<WeightSrcMap, WeightTgtMap>());
    }
118

119
120
121
    template <class Graph, class WeightSrcMap, class WeightTgtMap>
    void do_copy(const Graph* g, WeightSrcMap src_map, WeightTgtMap tgt_map,
                 true_type) const
122
    {
123
        tgt_map = src_map;
124
    }
125
126
127
128

    template <class Graph, class WeightSrcMap, class WeightTgtMap>
    void do_copy(const Graph* g, WeightSrcMap src_map, WeightTgtMap tgt_map,
                 false_type) const
129
    {
130
131
        typename graph_traits<Graph>::edge_iterator e, e_end;
        for (tie(e, e_end) = edges(*g); e != e_end; ++e)
132
        {
133
            tgt_map[*e] = src_map[*e];
134
135
        }
    }
136
};
137
138
139
140
141


struct compute_spring_block
{
    template <class Graph, class PosMap, class IndexMap, class WeightMap>
142
143
144
145
    void operator()(const Graph* gp, string type, size_t iter, size_t seed,
                    PosMap pos, bool progressive, WeightMap weight,
                    IndexMap index_map)
        const
146
    {
147
        const Graph& g = *gp;
148
        mt19937 rng(static_cast<mt19937::result_type>(seed));
149
        size_t n = HardNumVertices()(&g);
150
151
152
153
154

        if (iter == 0)
            iter = 100;
        double radius = n;
        if (!progressive)
155
            random_graph_layout(g, pos, -radius/2, radius/2,
156
                                -radius/2, radius/2, rng);
157
158
        if (type == "fg-grid")
        {
159
160
161
162
            fruchterman_reingold_force_directed_layout
                (g, pos, radius, radius,
                 cooling(linear_cooling<double>(iter)).
                 vertex_index_map(index_map));
163
164
165
        }
        else if (type == "fg-all-pairs")
        {
166
167
168
169
            fruchterman_reingold_force_directed_layout
                (g, pos, radius, radius,
                 cooling(linear_cooling<double>(iter)).
                 vertex_index_map(index_map).force_pairs(all_force_pairs()));
170
        }
171
        else if (type == "kw")
172
        {
173
174
            typedef typename graph_traits<Graph>::directed_category
                directed_category;
175
            bool retval;
176
177
178
179
            retval = compute_kamada_kawai(g, iter, n, pos, weight,
                                          typename is_convertible
                                                      <directed_category,
                                                       undirected_tag>::type());
180
            if (!retval)
181
182
                throw GraphException("the Kamada-Kawai layout algorithm only "
                                     "works for connected graphs!");
183
184
185
        }
        else
        {
186
187
            throw GraphException("invalid type of spring-block graph layout: " +
                                 type);
188
189
190
191
        }
    }

    template <class Graph, class PosMap, class WeightMap>
192
193
    bool compute_kamada_kawai(Graph &g, size_t iter, size_t n, PosMap pos,
                              WeightMap weight, boost::true_type) const
194
195
196
197
198
    {
        return kamada_kawai_spring_layout(g, pos, weight, side_length(n));
    }

    template <class Graph, class PosMap, class WeightMap>
199
200
    bool compute_kamada_kawai(Graph &g,  size_t iter, size_t n, PosMap pos,
                              WeightMap weight, boost::false_type) const
201
202
203
204
205
206
    {
        UndirectedAdaptor<Graph> ug(g);
        return kamada_kawai_spring_layout(ug, pos, weight, side_length(n));
    }
};

207
208

struct copy_positions
209
{
210
211
212
    template <class Graph, class VectorProperty, class PosMap>
    void operator()(const Graph* g, VectorProperty vec_prop, PosMap pos_map)
        const
213
    {
214
215
216
217
218
219
220
        typename graph_traits<Graph>::vertex_iterator v, v_end;
        for (tie(v, v_end) = vertices(*g); v != v_end; ++v)
        {
            vec_prop[*v].resize(2);
            vec_prop[*v][0] = pos_map[*v].x;
            vec_prop[*v][1] = pos_map[*v].y;
        }
221
    }
222
};
223

224
225
226
227
228
229
230
void GraphInterface::ComputeGraphLayoutGursoy(string pos_prop, string weight,
                                              string topology, size_t iter,
                                              size_t seed)
{
    typedef vector_property_map<double, edge_index_map_t> temp_weight_t;
    boost::any pos_map, weight_map;
    try
231
    {
232
233
234
235
236
        pos_map = prop(pos_prop, _vertex_index, _properties);
        if (!belongs<vertex_floating_vector_properties>()(pos_map))
            throw GraphException("property " + pos_prop +
                                 "is not of floating point vector type");
        if (weight == "")
237
        {
238
            weight_map = dummy_property_map();
239
        }
240
        else
241
        {
242
243
244
245
246
247
            temp_weight_t temp_weight(_edge_index);
            run_action<>()(*this, bind<void>(copy_weights(), _1, _2,
                                             temp_weight),
                           edge_scalar_properties())
                (prop(weight, _edge_index, _properties));
            weight_map = temp_weight;
248
249
        }
    }
250
251
252
253
    catch (property_not_found& e)
    {
        throw GraphException("error getting property: " + string(e.what()));
    }
254

255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
    vector_property_map<convex_topology<2>::point_type, vertex_index_map_t>
        pos(_vertex_index);
    run_action<>()(*this, bind<void>(compute_gursoy(), _1, iter, seed, pos,
                                     _2, topology, _vertex_index),
                   mpl::vector<temp_weight_t,dummy_property_map>())
        (weight_map);
    run_action<>()(*this, bind<void>(copy_points(), _1, _2, pos),
                   vertex_floating_vector_properties())(pos_map);
}

struct pos_t
{
    double x;
    double y;
};

void GraphInterface::ComputeGraphLayoutSpringBlock(string pos_prop,
                                                   string weight, string type,
                                                   size_t iter,
                                                   bool progressive,
                                                   size_t seed)
{
    typedef vector_property_map<double, edge_index_map_t> temp_weight_t;
    boost::any pos_map, weight_map;
279
    try
280
    {
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
        pos_map = prop(pos_prop, _vertex_index, _properties);
        if (!belongs<vertex_floating_vector_properties>()(pos_map))
            throw GraphException("property " + pos_prop +
                                 "is not of floating point vector type");

        if (weight == "")
        {
            weight_map = ConstantPropertyMap<double,edge_t>(1.0);
        }
        else
        {
            temp_weight_t temp_weight(_edge_index);
            run_action<>()(*this, bind<void>(copy_weights(), _1, _2,
                                             temp_weight),
                           edge_scalar_properties())
                (prop(weight, _edge_index, _properties));
            weight_map = temp_weight;
        }
299
    }
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
    catch (property_not_found& e)
    {
        throw GraphException("error getting property: " + string(e.what()));
    }

    typedef mpl::vector<temp_weight_t, ConstantPropertyMap<double,edge_t> >
        weight_maps;

    vector_property_map<pos_t, vertex_index_map_t> pos(_vertex_index);
    run_action<>()(*this, bind<void>(compute_spring_block(), _1, type, iter,
                                     seed, pos, progressive, _2, _vertex_index),
                   weight_maps())
        (weight_map);
    run_action<>()(*this, bind<void>(copy_positions(), _1, _2, pos),
                   vertex_floating_vector_properties())(pos_map);
315
}