graph_filtering.hh 19.2 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
//
// 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

#ifndef FILTERING_HH
#define FILTERING_HH

21
#include "graph.hh"
22
#include <boost/version.hpp>
Tiago Peixoto's avatar
Tiago Peixoto committed
23
24
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/filtered_graph.hpp>
25
26
27
28
29
#if (BOOST_VERSION / 100 % 1000 >= 48)
    #include <boost/graph/reverse_graph_alt.hpp>
#else
    #include <boost/graph/reverse_graph.hpp>
#endif
Tiago Peixoto's avatar
Tiago Peixoto committed
30
#include <boost/mpl/vector.hpp>
31
32
#include <boost/mpl/erase.hpp>
#include <boost/mpl/clear.hpp>
Tiago Peixoto's avatar
Tiago Peixoto committed
33
34
35
36
37
38
#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>
39
40
41
42
43
44
45
46
47
48
#include <boost/mpl/inserter.hpp>
#include <boost/mpl/insert_range.hpp>
#include <boost/mpl/assert.hpp>
#include <boost/mpl/plus.hpp>
#include <boost/mpl/divides.hpp>
#include <boost/mpl/arithmetic.hpp>
#include <boost/mpl/greater_equal.hpp>
#include <boost/mpl/comparison.hpp>
#include <boost/mpl/transform_view.hpp>
#include <boost/mpl/quote.hpp>
49
#include <boost/mpl/range_c.hpp>
50
#include <boost/mpl/print.hpp>
51

Tiago Peixoto's avatar
Tiago Peixoto committed
52
53
#include "graph_adaptor.hh"
#include "graph_selectors.hh"
54
#include "graph_util.hh"
55
#include "mpl_nested_loop.hh"
56

Tiago Peixoto's avatar
Tiago Peixoto committed
57
58
#include <type_traits>

59
namespace graph_tool
Tiago Peixoto's avatar
   
Tiago Peixoto committed
60
{
61

62
63
64
65
66
67
68
69
// Graph filtering
// ---------------
//
// We want to generate versions of a template algorithm for every possible type
// of graph views. The types of graph views are the following:
//
//    - The original directed multigraph
//
70
//    - Filtered graphs, based on MaskFilter below
71
72
73
74
75
76
//
//    - A reversed view of each directed graph (original + filtered)
//
//    - An undirected view of each directed (unreversed) graph (original +
//      filtered)
//
77
// The total number of graph views is then: 1 + 1 + 2 + 2 = 6
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
//
// The specific specialization can be called at run time (and generated at
// compile time) with the run_action() function, which takes as arguments the
// GraphInterface worked on, and the template functor to be specialized, which
// must take as first argument a pointer to a graph type, which itself must be a
// template parameter. Additionally, the function can be called optionally with
// up to 4 extra arguments, which must be MPL sequence instances corresponding
// to the type range of the extra arguments which must be passed to the template
// functor. The run_action() will not run the algorithm itself, but will instead
// return a functor (graph_action) which must be called either with no
// arguments, or with parameters of type boost::any which hold internally the
// type and values of the extra parameters to be passed to the action functor,
// and which will define the specialization to be chosen.
//
// Example:
//
// struct my_algorithm
// {
//     template <class Graph, class ValueType>
97
//     void operator()(Graph& g, ValueType val) const
98
99
100
101
102
103
104
//     {
//         ... do something ...
//     }
// };
//
// ...
//
105
// GraphInterface g;
106
107
// typedef mpl::vector<int, double, string> value_types;
// double foo = 42.0;
108
// run_action(g, my_algorithm(), value_types)(boost::any(foo));
109
110
111
112
//
// The above line will run my_algorithm::operator() with Graph being the
// appropriate graph view type and ValueType being 'double' and val = 42.0.

113
114
115
116
// Whenever no implementation is called, the following exception is thrown
class ActionNotFound: public GraphException
{
public:
117
    ActionNotFound(const std::type_info& action,
118
                   const vector<const std::type_info*>& args);
119
120
    virtual ~ActionNotFound() throw () {}
private:
121
122
    const std::type_info& _action;
    vector<const std::type_info*> _args;
123
};
124
125

namespace detail
126
{
127
128
129
130
131
132

// Implementation
// --------------
//
// The class MaskFilter below is the main filter predicate for the filtered
// graph view, based on descriptor property maps.  It filters out edges or
133
134
// vertices which are masked according to a property map with bool (actually
// uint8_t) value type.
135
136
137

template <class DescriptorProperty>
class MaskFilter
138
{
139
public:
Tiago Peixoto's avatar
Tiago Peixoto committed
140
    typedef typename boost::property_traits<DescriptorProperty>::value_type value_t;
141
    MaskFilter(){}
142
    MaskFilter(DescriptorProperty& filtered_property, bool invert)
143
        : _filtered_property(&filtered_property), _invert(invert) {}
144

145
    template <class Descriptor>
146
    inline bool operator() (Descriptor&& d) const
147
148
    {
        // ignore if masked
Tiago Peixoto's avatar
   
Tiago Peixoto committed
149

150
        return get(*_filtered_property, std::forward<Descriptor>(d)) ^ _invert;
151

152
153
        // This is a critical section. It will be called for every vertex or
        // edge in the graph, every time they're iterated through.
154
    }
155

156
157
158
    DescriptorProperty& get_filter() { return *_filtered_property; }
    bool is_inverted() { return _invert; }

159
private:
160
    DescriptorProperty* _filtered_property;
161
162
163
164
165
166
167
168
169
170
    bool _invert;
};


// Metaprogramming
// ---------------
//
// We need to generate a type sequence with all the filtered graph views, which
// will be called all_graph_views.

171

172
173
174
// metafunction class to get the correct filter predicate
template <class Property>
struct get_predicate
Tiago Peixoto's avatar
Tiago Peixoto committed
175
{
176
177
    typedef MaskFilter<Property> type;
};
Tiago Peixoto's avatar
Tiago Peixoto committed
178

179
template <>
Tiago Peixoto's avatar
Tiago Peixoto committed
180
struct get_predicate<boost::keep_all>
Tiago Peixoto's avatar
Tiago Peixoto committed
181
{
Tiago Peixoto's avatar
Tiago Peixoto committed
182
    typedef boost::keep_all type;
Tiago Peixoto's avatar
Tiago Peixoto committed
183
184
};

185
186
// metafunction to get the filtered graph type
struct graph_filter
Tiago Peixoto's avatar
Tiago Peixoto committed
187
{
188
189
190
    template <class Graph, class EdgeProperty, class VertexProperty>
    struct apply
    {
191

192
193
194
        typedef typename get_predicate<EdgeProperty>::type edge_predicate;
        typedef typename get_predicate<VertexProperty>::type vertex_predicate;

Tiago Peixoto's avatar
Tiago Peixoto committed
195
196
197
        typedef boost::filtered_graph<Graph,
                                      edge_predicate,
                                      vertex_predicate> filtered_graph_t;
198
199
200

        // If both predicates are keep_all, then return the original graph
        // type. Otherwise return the filtered_graph type.
Tiago Peixoto's avatar
Tiago Peixoto committed
201
202
        typedef typename boost::mpl::if_<
            typename boost::mpl::and_<
203
                is_same<edge_predicate,
Tiago Peixoto's avatar
Tiago Peixoto committed
204
                        boost::keep_all>,
205
                is_same<vertex_predicate,
Tiago Peixoto's avatar
Tiago Peixoto committed
206
                        boost::keep_all>
207
208
                >::type,
            Graph,
Tiago Peixoto's avatar
Tiago Peixoto committed
209
            filtered_graph_t>::type type;
210
    };
Tiago Peixoto's avatar
Tiago Peixoto committed
211
212
};

213
214
// metafunction to get the undirected graph type
struct graph_undirect
Tiago Peixoto's avatar
Tiago Peixoto committed
215
216
{
    template <class Graph>
217
    struct apply
Tiago Peixoto's avatar
Tiago Peixoto committed
218
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
219
        typedef boost::UndirectedAdaptor<Graph> type;
220
    };
Tiago Peixoto's avatar
Tiago Peixoto committed
221
222
};

223
224
// metafunction to get the reversed graph type
struct graph_reverse
Tiago Peixoto's avatar
Tiago Peixoto committed
225
{
226
    template <class Graph>
227
228
    struct apply
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
229
        typedef boost::reverse_graph<Graph> type;
230
    };
Tiago Peixoto's avatar
Tiago Peixoto committed
231
232
};

233
234
235
236
237

// metafunction class to get the correct property map type
template <class Scalar, class IndexMap>
struct get_property_map_type
{
238
239
    typedef typename property_map_type::apply<Scalar, IndexMap>
        ::type::unchecked_t type;
240
241
242
};

template <class IndexMap>
Tiago Peixoto's avatar
Tiago Peixoto committed
243
struct get_property_map_type<boost::keep_all, IndexMap>
244
{
Tiago Peixoto's avatar
Tiago Peixoto committed
245
    typedef boost::keep_all type;
246
};
247

248
249
250
251
// this metafunction returns a filtered graph type, given the scalar types to be
// used in the property maps
struct get_graph_filtered
{
252
    template <class Scalar>
253
254
255
256
    struct apply
    {
        // if the 'scalar' is the index map itself, use simply that, otherwise
        // get the specific property map
257
258
259
        typedef typename get_property_map_type<
            Scalar,
            GraphInterface::edge_index_map_t>::type edge_property_map;
260

261
262
263
        typedef typename get_property_map_type<
            Scalar,
            GraphInterface::vertex_index_map_t>::type vertex_property_map;
264
265
266
267

        typedef typename graph_filter::apply<GraphInterface::multigraph_t,
                                             edge_property_map,
                                             vertex_property_map>::type type;
268
    };
269
};
270

271
272
273
// this metafunction returns all the possible graph views
struct get_all_graph_views
{
274
    template <class FiltType,
Tiago Peixoto's avatar
Tiago Peixoto committed
275
276
277
278
279
              class AlwaysDirected = boost::mpl::bool_<false>,
              class NeverDirected = boost::mpl::bool_<false>,
              class AlwaysReversed = boost::mpl::bool_<false>,
              class NeverReversed = boost::mpl::bool_<false>,
              class NeverFiltered = boost::mpl::bool_<false> >
280
    struct apply
281
    {
282
283
        // filtered graphs
        struct filtered_graphs:
284
            boost::mpl::if_<NeverFiltered,
285
286
287
                            boost::mpl::vector1<GraphInterface::multigraph_t>,
                            boost::mpl::vector2<GraphInterface::multigraph_t,
                                                typename get_graph_filtered::apply<FiltType>::type>
288
                            >::type {};
289
290
291

        // filtered + reversed graphs
        struct reversed_graphs:
Tiago Peixoto's avatar
Tiago Peixoto committed
292
293
294
295
296
297
298
299
300
301
302
303
304
            boost::mpl::if_<AlwaysReversed,
                            typename boost::mpl::transform<filtered_graphs,
                                                           graph_reverse>::type,
                            typename boost::mpl::if_<
                                NeverReversed,
                                filtered_graphs,
                                typename boost::mpl::transform<
                                    filtered_graphs,
                                    graph_reverse,
                                    boost::mpl::back_inserter<filtered_graphs>
                                    >::type
                                >::type
                            >::type {};
305
306
307

        // undirected + filtereed + reversed graphs
        struct undirected_graphs:
Tiago Peixoto's avatar
Tiago Peixoto committed
308
309
310
311
312
313
314
315
316
317
318
319
320
            boost::mpl::if_<AlwaysDirected,
                            reversed_graphs,
                            typename boost::mpl::if_<
                                NeverDirected,
                                typename boost::mpl::transform<filtered_graphs,
                                                               graph_undirect>::type,
                                typename boost::mpl::transform<
                                    filtered_graphs,
                                    graph_undirect,
                                    boost::mpl::back_inserter<reversed_graphs>
                                    >::type
                                >::type
                            >::type {};
321
322
        typedef undirected_graphs type;
    };
Tiago Peixoto's avatar
Tiago Peixoto committed
323
324
};

325
typedef uint8_t filt_scalar_type;
326
327
328

// finally, this type should hold all the possible graph views
struct all_graph_views:
329
    get_all_graph_views::apply<filt_scalar_type>::type {};
330
331
332

// restricted graph views
struct always_directed:
333
    get_all_graph_views::apply<filt_scalar_type,boost::mpl::bool_<true> >::type {};
334
335

struct never_directed:
336
    get_all_graph_views::apply<filt_scalar_type,boost::mpl::bool_<false>,
Tiago Peixoto's avatar
Tiago Peixoto committed
337
                               boost::mpl::bool_<true> >::type {};
338
339

struct always_reversed:
340
    get_all_graph_views::apply<filt_scalar_type,boost::mpl::bool_<true>,
Tiago Peixoto's avatar
Tiago Peixoto committed
341
                               boost::mpl::bool_<false>,boost::mpl::bool_<true> >::type {};
342
343

struct never_reversed:
344
    get_all_graph_views::apply<filt_scalar_type,boost::mpl::bool_<false>,
Tiago Peixoto's avatar
Tiago Peixoto committed
345
346
                               boost::mpl::bool_<false>,boost::mpl::bool_<false>,
                               boost::mpl::bool_<true> >::type {};
347
348

struct always_directed_never_reversed:
349
    get_all_graph_views::apply<filt_scalar_type,boost::mpl::bool_<true>,
Tiago Peixoto's avatar
Tiago Peixoto committed
350
351
                               boost::mpl::bool_<false>,boost::mpl::bool_<false>,
                               boost::mpl::bool_<true> >::type {};
352

353
struct never_filtered:
354
    get_all_graph_views::apply<filt_scalar_type,boost::mpl::bool_<false>,
Tiago Peixoto's avatar
Tiago Peixoto committed
355
356
                               boost::mpl::bool_<false>,boost::mpl::bool_<false>,
                               boost::mpl::bool_<false>,boost::mpl::bool_<true> >::type {};
357
358

// sanity check
Tiago Peixoto's avatar
Tiago Peixoto committed
359
typedef boost::mpl::size<all_graph_views>::type n_views;
360
#ifndef NO_GRAPH_FILTERING
361
BOOST_MPL_ASSERT_RELATION(n_views::value, == , boost::mpl::int_<6>::value);
362
#else
Tiago Peixoto's avatar
Tiago Peixoto committed
363
BOOST_MPL_ASSERT_RELATION(n_views::value, == , boost::mpl::int_<3>::value);
364
#endif
Tiago Peixoto's avatar
Tiago Peixoto committed
365

366
367
// run_action() and gt_dispatch() implementation
// =============================================
368
369
370

// wrap action to be called, to deal with property maps, i.e., return version
// with no bounds checking.
371
template <class Action, class Wrap>
372
373
struct action_wrap
{
374
    action_wrap(Action a) : _a(a) {}
375
376

    template <class Type>
377
378
    auto& uncheck(boost::checked_vector_property_map
                   <Type,GraphInterface::vertex_index_map_t>& a, boost::mpl::true_) const
379
380
381
382
383
    {
        return a;
    }

    template <class Type>
384
385
    auto uncheck(boost::checked_vector_property_map
                 <Type,GraphInterface::vertex_index_map_t>& a, boost::mpl::false_) const
386
    {
387
        return a.get_unchecked();
388
389
390
    }

    template <class Type>
391
392
    auto& uncheck(boost::checked_vector_property_map
                   <Type,GraphInterface::edge_index_map_t>& a, boost::mpl::true_) const
393
394
395
396
397
    {
        return a;
    }

    template <class Type>
398
399
    auto uncheck(boost::checked_vector_property_map
                 <Type,GraphInterface::edge_index_map_t>& a, boost::mpl::false_) const
400
    {
401
        return a.get_unchecked();
402
403
404
    }

    template <class Type>
405
    auto uncheck(scalarS<Type>& a, boost::mpl::false_) const
406
    {
407
408
        auto pmap = uncheck(a._pmap, boost::mpl::false_());
        return scalarS<decltype(pmap)>(pmap);
409
410
411
    }

    //no op
Tiago Peixoto's avatar
Tiago Peixoto committed
412
    template <class Type, class DoWrap>
413
    Type& uncheck(Type&& a, DoWrap) const { return a; }
414

415
416
417
418
419
420
421
422
423
424
425
426
427
428
    template <class Type>
    auto& deference(Type* a) const
    {
        typedef typename std::remove_const<Type>::type type_t;
        typedef typename boost::mpl::find<detail::all_graph_views, type_t>::type iter_t;
        typedef typename boost::mpl::end<detail::all_graph_views>::type end_t;
        return deference_dispatch(a, typename std::is_same<iter_t, end_t>::type());
    }

    template <class Type>
    auto& deference_dispatch(Type*& a, std::true_type) const
    {
        return a;
    }
429

430
431
    template <class Type>
    Type& deference_dispatch(Type* a, std::false_type) const
432
    {
433
434
435
436
437
438
439
440
441
442
443
444
445
        return *a;
    }

    template <class Type>
    Type& deference(Type&& a) const
    {
        return a;
    }

    template <class... Ts>
    void operator()(Ts&&... as) const
    {
        _a(deference(uncheck(std::forward<Ts>(as), Wrap()))...);
446
    }
447
448
449
450

    Action _a;
};

451
452
453
454
455
// this takes a functor and type ranges and iterates through the type
// combinations when called with boost::any parameters, and calls the correct
// function
template <class Action, class Wrap, class... TRS>
struct action_dispatch
Tiago Peixoto's avatar
Tiago Peixoto committed
456
{
457
    action_dispatch(Action a) : _a(a) {}
Tiago Peixoto's avatar
Tiago Peixoto committed
458

459
460
    template <class... Args>
    void operator()(Args&&... args) const
461
    {
462
463
        bool found =
            boost::mpl::nested_for_each<TRS...>(_a, std::forward<Args>(args)...);
464
        if (!found)
465
        {
466
            vector<const std::type_info*> args_t = {(&(args).type())...};
467
            throw ActionNotFound(typeid(Action), args_t);
468
        }
Tiago Peixoto's avatar
Tiago Peixoto committed
469
470
    }

471
    action_wrap<Action, Wrap> _a;
Tiago Peixoto's avatar
Tiago Peixoto committed
472
473
};

474
} // details namespace
475

476
// dispatch "Action" across all type combinations
Tiago Peixoto's avatar
Tiago Peixoto committed
477
template <class GraphViews = detail::all_graph_views, class Wrap = boost::mpl::false_>
478
struct run_action
Tiago Peixoto's avatar
Tiago Peixoto committed
479
{
480
    template <class Action, class... TRS>
481
    auto operator()(GraphInterface& gi, Action a, TRS...)
482
    {
483
484
485
        auto dispatch = detail::action_dispatch<Action,Wrap,GraphViews,TRS...>(a);
        auto wrap = [dispatch, &gi](auto&&... args) { dispatch(gi.get_graph_view(), args...); };
        return wrap;
486
487
    }
};
488

489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
template <class Wrap = boost::mpl::false_>
struct gt_dispatch
{
    template <class Action, class... TRS>
    auto operator()(Action a, TRS...)
    {
        return detail::action_dispatch<Action,Wrap,TRS...>(a);
    }
};

typedef detail::all_graph_views all_graph_views;
typedef detail::always_directed always_directed;
typedef detail::never_directed never_directed;
typedef detail::always_reversed always_reversed;
typedef detail::never_reversed never_reversed;
typedef detail::always_directed_never_reversed always_directed_never_reversed;
typedef detail::never_filtered never_filtered;

507
508
509
// returns true if graph filtering was enabled at compile time
bool graph_filtering_enabled();

510
511
512
513

template <class Graph, class GraphInit>
std::shared_ptr<Graph> get_graph_ptr(GraphInterface& gi, GraphInit&, std::true_type)
{
514
    return gi.get_graph_ptr();
515
516
517
518
519
}

template <class Graph, class GraphInit>
std::shared_ptr<Graph> get_graph_ptr(GraphInterface&, GraphInit& g, std::false_type)
{
520
    return std::make_shared<Graph>(g);
521
522
523
524
525
526
527
528
529
530
}

// this function retrieves a graph view stored in graph_views, or stores one if
// non-existent
template <class Graph>
typename std::shared_ptr<Graph>
retrieve_graph_view(GraphInterface& gi, Graph& init)
{
    typedef typename std::remove_const<Graph>::type g_t;
    size_t index = boost::mpl::find<detail::all_graph_views,g_t>::type::pos::value;
531
    auto& graph_views = gi.get_graph_views();
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
    if (index >= graph_views.size())
        graph_views.resize(index + 1);
    boost::any& gview = graph_views[index];
    std::shared_ptr<g_t>* gptr = boost::any_cast<std::shared_ptr<g_t>>(&gview);
    if (gptr == 0)
    {
        std::shared_ptr<g_t> new_g =
            get_graph_ptr<g_t>(gi, init,
                               std::is_same<g_t, GraphInterface::multigraph_t>());
        gptr = &new_g;
        gview = new_g;
    }
    return *gptr;
}

547
} //graph_tool namespace
548

549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
// Overload add_vertex() and add_edge() to filtered graphs, so that the new
// descriptors are always valid

namespace boost
{
template <class Graph, class EdgeProperty, class VertexProperty>
typename graph_traits<filtered_graph<Graph,
                                     graph_tool::detail::MaskFilter<EdgeProperty>,
                                     graph_tool::detail::MaskFilter<VertexProperty>>>::vertex_descriptor
add_vertex(boost::filtered_graph<Graph,
                                 graph_tool::detail::MaskFilter<EdgeProperty>,
                                 graph_tool::detail::MaskFilter<VertexProperty>>& g)
{
    auto v = add_vertex(const_cast<Graph&>(g.m_g));
    auto& filt = g.m_vertex_pred.get_filter();
    auto cfilt = filt.get_checked();
    cfilt[v] = !g.m_vertex_pred.is_inverted();
    return v;
}

template <class Graph, class EdgeProperty, class VertexProperty, class Vertex>
std::pair<typename graph_traits<filtered_graph<Graph,
                                               graph_tool::detail::MaskFilter<EdgeProperty>,
                                               graph_tool::detail::MaskFilter<VertexProperty>>>::edge_descriptor, bool>
add_edge(Vertex s, Vertex t, filtered_graph<Graph,
                                            graph_tool::detail::MaskFilter<EdgeProperty>,
                                            graph_tool::detail::MaskFilter<VertexProperty>>& g)
{
    auto e = add_edge(s, t, const_cast<Graph&>(g.m_g));
    auto& filt = g.m_edge_pred.get_filter();
    auto cfilt = filt.get_checked();
    cfilt[e.first] = !g.m_edge_pred.is_inverted();
    return e;
}


} // namespace boost

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