graph_filtering.hh 11.9 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) 2007  Tiago de Paula Peixoto <tiago@forked.de>
Tiago Peixoto's avatar
Tiago Peixoto committed
4
5
6
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
Tiago Peixoto's avatar
Tiago Peixoto committed
7
// as published by the Free Software Foundation; either version 3
Tiago Peixoto's avatar
Tiago Peixoto committed
8
9
10
11
12
13
14
15
// 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
// along with this program. If not, see <http://www.gnu.org/licenses/>.
Tiago Peixoto's avatar
Tiago Peixoto committed
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

#ifndef FILTERING_HH
#define FILTERING_HH

#include <boost/graph/graph_traits.hpp>
#include <boost/graph/filtered_graph.hpp>
#include <boost/graph/reverse_graph.hpp>
#include <boost/mpl/vector.hpp>
#include <boost/mpl/map.hpp>
#include <boost/mpl/for_each.hpp>
#include <boost/mpl/at.hpp>
#include <boost/mpl/or.hpp>
#include <boost/mpl/if.hpp>
#include <boost/mpl/logical.hpp>
#include <boost/python/object.hpp>
#include <boost/python/dict.hpp>
#include <boost/python/extract.hpp>

#include "graph_adaptor.hh"
#include "graph_selectors.hh"
37

38
// some additional functions for filtered graphs...
39
40
41
42
43
namespace boost
{
//==============================================================================
// vertex(i, filtered_graph<G>)
//==============================================================================
44
template <class Graph, class EdgePredicate, class VertexPredicate>
45
46
47
48
inline
typename graph_traits<filtered_graph<Graph,
                                     EdgePredicate,
                                     VertexPredicate> >::vertex_descriptor
49
50
51
52
53
54
55
56
57
58
59
60
vertex(size_t i, const filtered_graph<Graph,EdgePredicate,VertexPredicate>& g)
{
    typename graph_traits<Graph>::vertex_descriptor v = vertex(i, g.m_g);
    if (g.m_vertex_pred(v))
        return v;
    else
        return graph_traits<Graph>::null_vertex();
}

//==============================================================================
// vertex(i, reverse_graph<G>)
//==============================================================================
61
template <class Graph>
62
inline
63
64
65
66
67
68
typename graph_traits<reverse_graph<Graph> >::vertex_descriptor
vertex(size_t i, const reverse_graph<Graph>& g)
{
    return vertex(i, g.m_g);
}

Tiago Peixoto's avatar
   
Tiago Peixoto committed
69
70
71
72

//==============================================================================
// add_edge(u, v, filtered_graph<G>)
//==============================================================================
73
template <class Graph, class EdgePredicate, class VertexPredicate>
74
75
76
77
78
79
inline
std::pair<typename graph_traits
              <filtered_graph<Graph,EdgePredicate,
                              VertexPredicate> >::edge_descriptor, bool>
add_edge(typename graph_traits
              <filtered_graph<Graph,EdgePredicate,
80
                              VertexPredicate> >::vertex_descriptor u,
81
82
83
         typename graph_traits
              <filtered_graph<Graph,EdgePredicate,
                              VertexPredicate> >::vertex_descriptor v,
Tiago Peixoto's avatar
   
Tiago Peixoto committed
84
85
86
87
88
89
90
91
         filtered_graph<Graph,EdgePredicate,VertexPredicate>& g)
{
    return add_edge(u,v, const_cast<Graph&>(g.m_g));
}

//==============================================================================
//remove_edge(e, filtered_graph<G>)
//==============================================================================
92
template <class Graph, class EdgePredicate, class VertexPredicate>
93
94
95
inline
void remove_edge(typename graph_traits
                     <filtered_graph<Graph,EdgePredicate,
96
                                     VertexPredicate> >::edge_descriptor e,
Tiago Peixoto's avatar
   
Tiago Peixoto committed
97
98
99
100
101
102
                 filtered_graph<Graph,EdgePredicate,VertexPredicate>& g)
{
    return remove_edge(e,const_cast<Graph&>(g.m_g));
}


103
104
105
} // namespace boost


Tiago Peixoto's avatar
Tiago Peixoto committed
106
107
108
109
namespace graph_tool
{
using namespace boost;

110
// this will count "by hand" the number of vertices on a graph
Tiago Peixoto's avatar
Tiago Peixoto committed
111
112
113
114
115
struct HardNumVertices
{
    template <class Graph>
    size_t operator()(const Graph &g) const
    {
116
117
118
119
120
121
        size_t n = 0;
        typename graph_traits<Graph>::vertex_iterator v_iter, v_begin, v_end;
        tie(v_begin, v_end) = vertices(g);
        for (v_iter = v_begin; v_iter != v_end; ++v_iter)
            n++;
        return n;
Tiago Peixoto's avatar
Tiago Peixoto committed
122
123
124
    }
};

125
// this will return the number of vertices on a graph, as given by num_vertices
Tiago Peixoto's avatar
Tiago Peixoto committed
126
127
128
129
130
131
struct SoftNumVertices
{
    template <class Graph>
    size_t operator()(const Graph &g) const { return num_vertices(g); }
};

132
// this will count "by hand" the number of edges on a graph
Tiago Peixoto's avatar
Tiago Peixoto committed
133
134
135
136
137
struct HardNumEdges
{
    template <class Graph>
    size_t operator()(const Graph &g) const
    {
138
139
140
141
142
143
        size_t n = 0;
        typename graph_traits<Graph>::edge_iterator e_iter, e_begin, e_end;
        tie(e_begin, e_end) = edges(g);
        for (e_iter = e_begin; e_iter != e_end; ++e_iter)
            n++;
        return n;
Tiago Peixoto's avatar
Tiago Peixoto committed
144
145
146
    }
};

147
// this will return the number of edges on a graph, as given by num_edges
Tiago Peixoto's avatar
Tiago Peixoto committed
148
149
struct SoftNumEdges
{
150
    template <class Graph>
Tiago Peixoto's avatar
Tiago Peixoto committed
151
152
153
    size_t operator()(const Graph &g) const { return num_edges(g); }
};

154
155
156
157
// The following filter predicate will filter out edges or vertices which lay
// outside a given range of values of a specific property. The range is
// specified as a pair of 'double' values

Tiago Peixoto's avatar
Tiago Peixoto committed
158
159
160
161
162
template <class FilteredPropertyMap>
class RangeFilter
{
public:
    RangeFilter(){}
163
164
165
166
167
    RangeFilter(const FilteredPropertyMap& filtered_property,
                const std::pair<double, double>& range,
                const std::pair<bool, bool>& include, const bool& invert)
        : _filtered_property(&filtered_property), _range(&range),
          _include(&include), _invert(&invert) {}
168

Tiago Peixoto's avatar
Tiago Peixoto committed
169
    template <class VertexOrEdge>
170
    bool operator() (VertexOrEdge e) const
Tiago Peixoto's avatar
Tiago Peixoto committed
171
    {
172
        bool retval;
173
174
        map_visitor<VertexOrEdge> visitor(e, *_range, *_include, *_invert, retval);
        apply_visitor(visitor, *_filtered_property);
175
        return retval;
Tiago Peixoto's avatar
Tiago Peixoto committed
176
    }
177

Tiago Peixoto's avatar
Tiago Peixoto committed
178
private:
179
180
181
182
    template <class VertexOrEdge>
    class map_visitor: public static_visitor<void>
    {
    public:
183
184
185
        map_visitor(const VertexOrEdge& descriptor,
                    const std::pair<double, double>& range,
                    const std::pair<bool, bool>& include, bool invert,
186
                    bool& retval)
187
            : _descriptor(descriptor), _range(range), _include(include),
188
              _invert(invert), _retval(retval) {}
189
190
191
192
        template <class MapType>
        void operator()(MapType& filter_prop)
        {
            // ignore if outside allowed range
193
194
195
196
197

            // TODO: This is a critical section. It will be called for every
            //       vertex or edge in the graph, every time they're iterated
            //       through. Therefore, it must be guaranteed this is as
            //       optimized as possible.
198

199
            double val = double(get(filter_prop, _descriptor));
Tiago Peixoto's avatar
   
Tiago Peixoto committed
200
201
            bool lower;
            if (_include.first)
202
                lower = val < _range.first;
Tiago Peixoto's avatar
   
Tiago Peixoto committed
203
            else
204
                lower = val <= _range.first;
Tiago Peixoto's avatar
   
Tiago Peixoto committed
205
206
            bool upper;
            if (_include.second)
207
                upper = val > _range.second;
Tiago Peixoto's avatar
   
Tiago Peixoto committed
208
            else
209
                upper = val >= _range.second;
Tiago Peixoto's avatar
   
Tiago Peixoto committed
210
211
212
            _retval = !(lower || upper);
            if (_invert)
                _retval = !_retval;
213
        }
214

215
    private:
216
217
        const VertexOrEdge& _descriptor;
        const std::pair<double, double>& _range;
Tiago Peixoto's avatar
   
Tiago Peixoto committed
218
219
        const std::pair<bool, bool>& _include;
        bool _invert;
220
        bool& _retval;
221
222
    };

223
224
225
226
    const FilteredPropertyMap* _filtered_property;
    const std::pair<double, double>* _range;
    const std::pair<bool, bool>* _include;
    const bool* _invert;
Tiago Peixoto's avatar
Tiago Peixoto committed
227
228
};

229
230
231
232
233

// below are some functions which will run a specific algorithm on a properly
// filtered graph, i.e., reversed, undirected and/or range filtered, or a
// combination of these

Tiago Peixoto's avatar
Tiago Peixoto committed
234
235
236
237
238
239
240
typedef mpl::vector<mpl::bool_<true>, mpl::bool_<false> > reverse_check;
typedef mpl::vector<mpl::bool_<false> > never_reversed;
typedef mpl::vector<mpl::bool_<true> > always_reversed;
typedef mpl::vector<mpl::bool_<true>, mpl::bool_<false> > directed_check;
typedef mpl::vector<mpl::bool_<true> > always_directed;
typedef mpl::vector<mpl::bool_<false> > always_undirected;

241
242
243
// this will check whether a graph is reversed and run the proper version of the
// algorithm

Tiago Peixoto's avatar
Tiago Peixoto committed
244
245
246
template <class Graph, class Action>
struct check_reverse
{
247
248
249
    check_reverse(const Graph &g, Action a, bool reverse, bool& found,
                  bool run_all)
        : _g(g), _a(a), _reverse(reverse), _found(found), _run_all(run_all) {}
Tiago Peixoto's avatar
Tiago Peixoto committed
250
251
252
253

    template <class Reverse>
    void operator()(Reverse) const
    {
254
        if (_reverse || _run_all)
255
        {
256
            static reverse_graph<Graph> rg(_g);
257
258
259
            _a(rg);
            _found = true;
        }
Tiago Peixoto's avatar
Tiago Peixoto committed
260
261
262
    }

    void operator()(mpl::bool_<false>) const
263
264
    {
        if (!_reverse || _run_all)
265
266
267
268
        {
            _a(_g);
            _found = true;
        }
Tiago Peixoto's avatar
Tiago Peixoto committed
269
270
271
272
273
274
    }

    const Graph &_g;
    Action _a;
    bool _reverse;
    bool& _found;
275
    bool _run_all;
Tiago Peixoto's avatar
Tiago Peixoto committed
276
277
};

278
279
280
// this will check whether a graph is directed and run the proper version of the
// algorithm

Tiago Peixoto's avatar
Tiago Peixoto committed
281
282
283
template <class Graph, class Action, class ReverseCheck>
struct check_directed
{
284
    check_directed(const Graph &g, Action a, bool reverse, bool directed,
285
286
287
                   bool& found, bool run_all)
        : _g(g), _a(a), _reverse(reverse), _directed(directed), _found(found),
          _run_all(run_all) {}
Tiago Peixoto's avatar
Tiago Peixoto committed
288
289
290
291

    template <class Directed>
    void operator()(Directed)
    {
292
        if (_directed || _run_all)
293
            mpl::for_each<ReverseCheck>
294
295
                (check_reverse<Graph, Action>(_g, _a, _reverse, _found,
                                              _run_all));
Tiago Peixoto's avatar
Tiago Peixoto committed
296
297
298
    }

    void operator()(mpl::bool_<false>)
299
300
    {
        if (!_directed || _run_all)
301
        {
302
            static UndirectedAdaptor<Graph> ug(_g);
303
304
305
            _a(ug);
            _found = true;
        }
Tiago Peixoto's avatar
Tiago Peixoto committed
306
307
308
309
310
311
312
    }

    const Graph &_g;
    Action _a;
    bool _reverse;
    bool _directed;
    bool& _found;
313
    bool _run_all;
Tiago Peixoto's avatar
Tiago Peixoto committed
314
315
};

316
317
318
// this will check whether a graph is range filtered and run the proper version
// of the algorithm

319
320
321
template <class Action, class ReverseCheck, class DirectedCheck>
void check_filter(const GraphInterface &g, Action a, ReverseCheck,
                  DirectedCheck, bool run_all = false)
Tiago Peixoto's avatar
Tiago Peixoto committed
322
{
323
324
    bool found = false;

Tiago Peixoto's avatar
Tiago Peixoto committed
325
326
    typedef RangeFilter<GraphInterface::vertex_filter_map_t> vertex_filter_t;
    typedef RangeFilter<GraphInterface::edge_filter_map_t> edge_filter_t;
327

328
329
330
331
332
333
334
335
336
337
338
339
#ifndef NO_RANGE_FILTERING
    if (g._vertex_filter_property != "" || g._edge_filter_property != "" ||
        run_all)
    {
        typedef filtered_graph<GraphInterface::multigraph_t, edge_filter_t,
            vertex_filter_t> fg_t;
        static fg_t fg(g._mg, edge_filter_t(g._edge_filter_map, g._edge_range,
                                            g._edge_range_include,
                                            g._edge_range_invert),
                       vertex_filter_t(g._vertex_filter_map, g._vertex_range,
                                       g._vertex_range_include,
                                       g._vertex_range_invert));
340
        mpl::for_each<DirectedCheck>
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
            (check_directed<fg_t,Action,ReverseCheck>(fg, a, g._reversed,
                                                      g._directed, found,
                                                      run_all));
    }
    if (!found || run_all)
    {
        mpl::for_each<DirectedCheck>
            (check_directed<GraphInterface::multigraph_t,Action,
             ReverseCheck>
             (g._mg, a, g._reversed, g._directed, found, run_all));
    }
#else
    mpl::for_each<DirectedCheck>
        (check_directed<GraphInterface::multigraph_t,Action,ReverseCheck>
         (g._mg, a, g._reversed, g._directed, found));
356
#endif
Tiago Peixoto's avatar
Tiago Peixoto committed
357
    if (!found)
358
359
        throw GraphException("graph filtering error: filter not found "
                             "(this is a bug in graph-tool)");
Tiago Peixoto's avatar
Tiago Peixoto committed
360
361
}

362
} //graph_tool namespace
363

Tiago Peixoto's avatar
   
Tiago Peixoto committed
364
#endif // FILTERING_HH