graph_adaptor.hh 31.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-2016 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 GRAPH_ADAPTOR_HH
#define GRAPH_ADAPTOR_HH

21
22
#include <list>

Tiago Peixoto's avatar
Tiago Peixoto committed
23
24
#include <boost/config.hpp>
#include <boost/iterator_adaptors.hpp>
25
#include <boost/range/join.hpp>
Tiago Peixoto's avatar
Tiago Peixoto committed
26
27
28
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/properties.hpp>

29
30
#include "transform_iterator.hh"

Tiago Peixoto's avatar
Tiago Peixoto committed
31
32
33
34
namespace boost {

//==============================================================================
// UndirectedAdaptor
35
// This class encapsulates a directed graph with parallel edges and provides a
Tiago Peixoto's avatar
Tiago Peixoto committed
36
// view of the graph as undirected with parallel edges.
37
38
39
40
// Encapsulated graph can be: VertexListGraph, EdgeListGraph, IncidenceGraph,
//                            AdjacencyGraph, VertexMutableGraph,
//                            EdgeMutableGraph, VertexMutablePropertyGraph,
//                            EdgeMutablePropertyGraph, BidirectionalGraph
Tiago Peixoto's avatar
Tiago Peixoto committed
41
42
43
44
45
// The undirected graph obeys the same concepts.
//==============================================================================
template <class Graph> class UndirectedAdaptor
{
public:
46
    UndirectedAdaptor(const Graph& g) : _g(const_cast<Graph&>(g)){}
Tiago Peixoto's avatar
Tiago Peixoto committed
47

48
49
    typedef typename vertex_property_type<Graph>::type vertex_property_type;
    typedef typename edge_property_type<Graph>::type edge_property_type;
50
    typedef typename Graph::graph_tag graph_tag;
51
    typedef Graph graph_type;
52

Tiago Peixoto's avatar
Tiago Peixoto committed
53
    typedef Graph original_graph_t;
54

55
56
    typedef typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor
        vertex_descriptor;
57
    typedef typename graph_traits<UndirectedAdaptor<Graph> >::edge_descriptor
58
59
        edge_descriptor;

60
61
62
    typedef undirected_tag directed_category;
    typedef allow_parallel_edge_tag edge_parallel_category;
    typedef typename graph_traits<Graph>::traversal_category traversal_category;
63

Tiago Peixoto's avatar
Tiago Peixoto committed
64
65
66
#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
    // Bundled properties support
    template<typename Descriptor>
67
68
    typename graph::detail::bundled_result<Graph, Descriptor>::type&
        operator[](Descriptor x) { return this->m_g[x]; }
Tiago Peixoto's avatar
Tiago Peixoto committed
69
70

    template<typename Descriptor>
71
72
    typename graph::detail::bundled_result<Graph, Descriptor>::type const&
        operator[](Descriptor x) const { return this->m_g[x]; }
Tiago Peixoto's avatar
Tiago Peixoto committed
73
#endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES
74

75
76
    const Graph& original_graph() const {return _g;}
    Graph& original_graph() {return _g;}
77

78
79
    static vertex_descriptor null_vertex() {graph_traits<Graph>::null_vertex();}

Tiago Peixoto's avatar
Tiago Peixoto committed
80
private:
81
    Graph& _g;
Tiago Peixoto's avatar
Tiago Peixoto committed
82
83
84
85
};

#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
template<typename Graph>
86
87
struct vertex_bundle_type<UndirectedAdaptor<Graph> >:
        vertex_bundle_type<Graph> { };
Tiago Peixoto's avatar
Tiago Peixoto committed
88
89

template<typename Graph>
90
91
struct edge_bundle_type<UndirectedAdaptor<Graph> >:
        edge_bundle_type<Graph> { };
Tiago Peixoto's avatar
Tiago Peixoto committed
92
93
#endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES

94
template <class Graph>
95
struct get_iterator_category
96
{
97
98
    typedef typename graph_traits<Graph>::out_edge_iterator iter_t;
    typedef typename std::iterator_traits<iter_t>::iterator_category type;
99
};
100

Tiago Peixoto's avatar
Tiago Peixoto committed
101

102
template <class Graph>
103
class joined_edge_iterator
104
    : public boost::iterator_facade<joined_edge_iterator<Graph>,
105
106
107
                                    typename graph_traits<Graph>::edge_descriptor,
                                    typename get_iterator_category<Graph>::type,
                                    typename graph_traits<Graph>::edge_descriptor>
108
{
109
 public:
110
111
112
    typedef typename graph_traits<Graph>::in_edge_iterator in_iter_t;
    typedef typename graph_traits<Graph>::out_edge_iterator out_iter_t;

113
    joined_edge_iterator() {}
114
115
116
    template <class InRange, class OutRange>
    __attribute__((always_inline))
    explicit joined_edge_iterator(InRange&& range1, OutRange&& range2,
117
                                  bool begin)
118
119
        : _range1(std::forward<InRange>(range1)),
          _range2(std::forward<OutRange>(range2))
120
    {
121
        if (!begin)
122
        {
123
124
            _range1.first = _range1.second;
            _range2.first = _range2.second;
125
126
        }
    }
Tiago Peixoto's avatar
Tiago Peixoto committed
127

128
129
 private:
    friend class boost::iterator_core_access;
130
    __attribute__((always_inline))
131
    void increment()
132
    {
133
134
        if (_range1.first == _range1.second)
            ++_range2.first;
135
        else
136
            ++_range1.first;
137
    }
138

139
140
    typedef typename std::iterator_traits<in_iter_t>::difference_type diff_t;
    __attribute__((always_inline))
141
142
    void advance(diff_t n)
    {
143
        diff_t d1 = _range1.second - _range1.first;
144
145
        if (n < d1)
        {
146
            _range1.first += n;
147
148
149
        }
        else
        {
150
151
            _range1.first = _range1.second;
            _range2.first += n - d1;
152
153
        }
    }
154

155
156
    __attribute__((always_inline))
    diff_t distance_to(joined_edge_iterator const& other) const
157
    {
158
159
        return (other._range1.first - _range1.first) +
            (other._range2.first - _range2.first);
160
    }
Tiago Peixoto's avatar
Tiago Peixoto committed
161

162
    __attribute__((always_inline))
163
    bool equal(joined_edge_iterator const& other) const
164
    {
165
166
167
168
169
        return (_range2.first == other._range2.first &&
                _range1.first == other._range1.first);
    }

    template <class Edge>
170
171
    __attribute__((always_inline))
    Edge inv(Edge e) const
172
    {
173
        e.inv ^= true;
174
        return e;
175
    }
176

177
    __attribute__((always_inline))
178
    typename graph_traits<Graph>::edge_descriptor dereference() const
179
    {
180
181
        if (_range1.first == _range1.second)
            return *_range2.first;
182
        else
183
            return inv(*_range1.first);
184
185
    }

186
187
    std::pair<in_iter_t, in_iter_t> _range1;
    std::pair<out_iter_t, out_iter_t> _range2;
188
};
189

190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
template <class Graph>
class joined_neighbour_iterator
    : public boost::iterator_facade<joined_neighbour_iterator<Graph>,
                                    typename graph_traits<Graph>::vertex_descriptor,
                                    typename get_iterator_category<Graph>::type,
                                    typename graph_traits<Graph>::vertex_descriptor>
{
 public:
    typedef typename Graph::in_adjacency_iterator in_iter_t;
    typedef typename graph_traits<Graph>::adjacency_iterator out_iter_t;

    joined_neighbour_iterator() {}
    template <class InRange, class OutRange>
    explicit joined_neighbour_iterator(InRange&& range1, OutRange&& range2,
                                       bool begin)
        : _range1(std::forward<InRange>(range1)),
          _range2(std::forward<OutRange>(range2))
    {
        if (!begin)
        {
            _range1.first = _range1.second;
            _range2.first = _range2.second;
        }
    }
214

215
216
 private:
    friend class boost::iterator_core_access;
Tiago Peixoto's avatar
Tiago Peixoto committed
217

218
219
220
221
222
223
224
225
    __attribute__((always_inline))
    void increment()
    {
        if (_range1.first == _range1.second)
            ++_range2.first;
        else
            ++_range1.first;
    }
Tiago Peixoto's avatar
Tiago Peixoto committed
226

227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
    typedef typename std::iterator_traits<in_iter_t>::difference_type diff_t;
    __attribute__((always_inline))
    void advance(diff_t n)
    {
        diff_t d1 = _range1.second - _range1.first;
        if (n < d1)
        {
            _range1.first += n;
        }
        else
        {
            _range1.first = _range1.second;
            _range2.first += n - d1;
        }
    }

    __attribute__((always_inline))
    diff_t distance_to(joined_neighbour_iterator const& other) const
    {
        return (other._range1.first - _range1.first) +
            (other._range2.first - _range2.first);
    }
Tiago Peixoto's avatar
Tiago Peixoto committed
249

250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
    __attribute__((always_inline))
    bool equal(joined_neighbour_iterator const& other) const
    {
        return (_range2.first == other._range2.first &&
                _range1.first == other._range1.first);
    }

    __attribute__((always_inline))
    typename graph_traits<Graph>::vertex_descriptor dereference() const
    {
        if (_range1.first == _range1.second)
            return *_range2.first;
        else
            return *_range1.first;
    }

    std::pair<in_iter_t, in_iter_t> _range1;
    std::pair<out_iter_t, out_iter_t> _range2;
};
269

Tiago Peixoto's avatar
Tiago Peixoto committed
270
271
272
273
274
//==============================================================================
// graph_traits<UndirectedAdaptor>
// this defines all the necessary types associated with UndirectedAdaptor
//==============================================================================
template <class Graph>
275
struct graph_traits<UndirectedAdaptor<Graph> > {
Tiago Peixoto's avatar
Tiago Peixoto committed
276
    typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
277
    typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
Tiago Peixoto's avatar
Tiago Peixoto committed
278

279
280
281
    typedef joined_neighbour_iterator<Graph> adjacency_iterator;
    typedef joined_edge_iterator<Graph> out_edge_iterator;
    typedef joined_edge_iterator<Graph> in_edge_iterator;
Tiago Peixoto's avatar
Tiago Peixoto committed
282
    typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
283
    typedef typename graph_traits<Graph>::edge_iterator edge_iterator;
284

285

Tiago Peixoto's avatar
Tiago Peixoto committed
286
    typedef undirected_tag directed_category;
287
    typedef allow_parallel_edge_tag edge_parallel_category;
288
    typedef typename graph_traits<Graph>::traversal_category traversal_category;
Tiago Peixoto's avatar
Tiago Peixoto committed
289
290
291
    typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
    typedef typename graph_traits<Graph>::edges_size_type edges_size_type;
    typedef typename graph_traits<Graph>::degree_size_type degree_size_type;
292
293
294
295
296

    static vertex_descriptor null_vertex()
    {
        return graph_traits<Graph>::null_vertex();
    }
297
298
299
300
301
302
303

private:
    typedef is_convertible<typename std::iterator_traits<typename graph_traits<Graph>::out_edge_iterator>::iterator_category,
                           std::random_access_iterator_tag> is_orig_ra;
    typedef is_convertible<typename std::iterator_traits<out_edge_iterator>::iterator_category,
                           std::random_access_iterator_tag> is_ra;
    BOOST_STATIC_ASSERT((!is_orig_ra::value || is_ra::value));
Tiago Peixoto's avatar
Tiago Peixoto committed
304
305
};

306
template <class Graph>
307
308
struct graph_traits< const UndirectedAdaptor<Graph> >:
    public graph_traits<UndirectedAdaptor<Graph> > {};
309

Tiago Peixoto's avatar
Tiago Peixoto committed
310
311
//==============================================================================
// Nonmember functions
312
// these provide manipulation of the graph
Tiago Peixoto's avatar
Tiago Peixoto committed
313
314
315
316
317
318
//==============================================================================

//==============================================================================
// source(e,g)
//==============================================================================
template <class Graph>
319
inline typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor
320
source(const typename graph_traits<UndirectedAdaptor<Graph> >::edge_descriptor& e,
321
       const UndirectedAdaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
322
{
323
    if (e.inv)
324
        return target(e, g.original_graph());
Tiago Peixoto's avatar
Tiago Peixoto committed
325
    else
326
        return source(e, g.original_graph());
Tiago Peixoto's avatar
Tiago Peixoto committed
327
328
329
330
331
332
}

//==============================================================================
// target(e,g)
//==============================================================================
template <class Graph>
333
inline typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor
334
target(const typename graph_traits<UndirectedAdaptor<Graph> >::edge_descriptor& e,
335
       const UndirectedAdaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
336
{
337
    if (e.inv)
338
        return source(e, g.original_graph());
Tiago Peixoto's avatar
Tiago Peixoto committed
339
    else
340
        return target(e, g.original_graph());
Tiago Peixoto's avatar
Tiago Peixoto committed
341
342
343
344
345
346
}

//==============================================================================
// vertex(n,g)
//==============================================================================
template <class Graph>
347
inline
348
typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor
349
350
vertex(typename graph_traits<UndirectedAdaptor<Graph> >::vertices_size_type n,
       const UndirectedAdaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
351
{
352
    return vertex(n, g.original_graph());
Tiago Peixoto's avatar
Tiago Peixoto committed
353
354
355
356
357
358
}

//==============================================================================
// vertices(g)
//==============================================================================
template <class Graph>
359
inline
360
361
std::pair<typename graph_traits<UndirectedAdaptor<Graph> >::vertex_iterator,
          typename graph_traits<UndirectedAdaptor<Graph> >::vertex_iterator >
Tiago Peixoto's avatar
Tiago Peixoto committed
362
363
vertices(const UndirectedAdaptor<Graph>& g)
{
364
    return vertices(g.original_graph());
Tiago Peixoto's avatar
Tiago Peixoto committed
365
366
367
368
369
370
}

//==============================================================================
// edges(g)
//==============================================================================
template <class Graph>
371
inline
372
373
std::pair<typename graph_traits<UndirectedAdaptor<Graph> >::edge_iterator,
          typename graph_traits<UndirectedAdaptor<Graph> >::edge_iterator >
Tiago Peixoto's avatar
Tiago Peixoto committed
374
375
edges(const UndirectedAdaptor<Graph>& g)
{
376
    return edges(g.original_graph());
Tiago Peixoto's avatar
Tiago Peixoto committed
377
378
}

379
380
381
382
//==============================================================================
// edge(u, v, g)
//==============================================================================
template <class Graph>
383
inline
384
385
386
387
388
389
std::pair<typename graph_traits<UndirectedAdaptor<Graph> >::edge_descriptor,
          bool>
edge(typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor u,
     typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor v,
     const UndirectedAdaptor<Graph>& g)
{
390
    auto res = edge(u, v, g.original_graph());
391
392
393

    if (!res.second)
    {
394
        res = edge(v, u, g.original_graph());
395
        res.first.inv = true;
396
    }
397
398

    return res;
399
400
}

Tiago Peixoto's avatar
Tiago Peixoto committed
401
402
403
404
//==============================================================================
// out_edges(u,g)
//==============================================================================
template <class Graph>
405
406
inline __attribute__((always_inline))
std::pair<typename graph_traits<UndirectedAdaptor<Graph>>::out_edge_iterator,
407
          typename graph_traits<UndirectedAdaptor<Graph>>::out_edge_iterator>
408
out_edges(typename graph_traits<UndirectedAdaptor<Graph>>::vertex_descriptor u,
409
410
          const UndirectedAdaptor<Graph>& g)
{
411
    typedef joined_edge_iterator<Graph> iter_t;
412
413
414
415
    auto ies = in_edges(u, g.original_graph());
    auto oes = out_edges(u, g.original_graph());
    return std::make_pair(iter_t(ies, oes, true),
                          iter_t(ies, oes, false));
Tiago Peixoto's avatar
Tiago Peixoto committed
416
417
}

418
419
420
421
//==============================================================================
// in_edges(u,g)
//==============================================================================
template <class Graph>
422
423
424
425
inline __attribute__((always_inline))
std::pair<typename graph_traits<UndirectedAdaptor<Graph>>::in_edge_iterator,
          typename graph_traits<UndirectedAdaptor<Graph>>::in_edge_iterator >
in_edges(typename graph_traits<UndirectedAdaptor<Graph>>::vertex_descriptor u,
426
427
         const UndirectedAdaptor<Graph>& g)
{
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
    return out_edges(u, g);
}

//==============================================================================
// out_neighbours(u, g)
//==============================================================================
template <class Graph>
inline __attribute__((always_inline))
std::pair<typename graph_traits<UndirectedAdaptor<Graph> >::adjacency_iterator,
          typename graph_traits<UndirectedAdaptor<Graph> >::adjacency_iterator>
out_neighbours(typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor u,
               const UndirectedAdaptor<Graph>& g)
{
    typedef joined_neighbour_iterator<Graph> iter_t;
    auto ins = in_neighbours(u, g.original_graph());
    auto ons = out_neighbours(u, g.original_graph());
    return std::make_pair(iter_t(ins, ons, true),
                          iter_t(ins, ons, false));
}

//==============================================================================
// in_neighbours(u, g)
//==============================================================================
template <class Graph>
inline __attribute__((always_inline))
std::pair<typename graph_traits<UndirectedAdaptor<Graph> >::adjacency_iterator,
          typename graph_traits<UndirectedAdaptor<Graph> >::adjacency_iterator>
in_neighbours(typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor u,
              const UndirectedAdaptor<Graph>& g)
{
    return out_neighbours(u, g);
459
460
}

Tiago Peixoto's avatar
Tiago Peixoto committed
461
462
463
464
//==============================================================================
// adjacent_vertices(u,g)
//==============================================================================
template <class Graph>
465
inline __attribute__((always_inline))
466
467
468
469
470
471
std::pair<typename graph_traits<UndirectedAdaptor<Graph> >::adjacency_iterator,
          typename graph_traits<UndirectedAdaptor<Graph> >::adjacency_iterator>
adjacent_vertices
    (typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor u,
     const UndirectedAdaptor<Graph>& g)
{
472
    return out_neighbours(u, g);
Tiago Peixoto's avatar
Tiago Peixoto committed
473
474
475
476
477
478
}

//==============================================================================
// num_vertices(g)
//==============================================================================
template <class Graph>
479
inline __attribute__((always_inline))
480
typename graph_traits<UndirectedAdaptor<Graph> >::vertices_size_type
Tiago Peixoto's avatar
Tiago Peixoto committed
481
482
num_vertices(const UndirectedAdaptor<Graph>& g)
{
483
    return num_vertices(g.original_graph());
484
}
Tiago Peixoto's avatar
Tiago Peixoto committed
485
486
487
488
489

//==============================================================================
// num_edges(g)
//==============================================================================
template <class Graph>
490
491
inline __attribute__((always_inline))
typename graph_traits<UndirectedAdaptor<Graph> >::edges_size_type
Tiago Peixoto's avatar
Tiago Peixoto committed
492
493
num_edges(const UndirectedAdaptor<Graph>& g)
{
494
    return num_edges(g.original_graph());
495
}
Tiago Peixoto's avatar
Tiago Peixoto committed
496
497
498
499
500

//==============================================================================
// out_degree(u,g)
//==============================================================================
template <class Graph>
501
inline __attribute__((always_inline))
502
503
504
typename graph_traits<UndirectedAdaptor<Graph> >::degree_size_type
out_degree(typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor u,
           const UndirectedAdaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
505
{
506
507
    return (out_degree(u, g.original_graph()) +
            in_degree(u, g.original_graph()));
508
509
510
511
512
513
}

//==============================================================================
// in_degree(u,g)
//==============================================================================
template <class Graph>
514
inline
515
516
517
518
519
typename graph_traits<UndirectedAdaptor<Graph> >::degree_size_type
in_degree(typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor u,
          const UndirectedAdaptor<Graph>& g)
{
    return out_degree(u, g);
Tiago Peixoto's avatar
Tiago Peixoto committed
520
521
522
523
524
525
}

//==============================================================================
// degree(u,g)
//==============================================================================
template <class Graph>
526
inline __attribute__((always_inline))
527
typename graph_traits<UndirectedAdaptor<Graph> >::degree_size_type
528
degree(typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor u,
529
       const UndirectedAdaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
530
531
532
533
534
535
536
537
{
    return out_degree(u, g);
}


//==============================================================================
// add_vertex(g)
//==============================================================================
538
template <class Graph>
539
inline __attribute__((always_inline))
540
typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor
Tiago Peixoto's avatar
Tiago Peixoto committed
541
542
add_vertex(UndirectedAdaptor<Graph>& g)
{
543
    return add_vertex(g.original_graph());
Tiago Peixoto's avatar
Tiago Peixoto committed
544
545
546
547
548
549
}

//==============================================================================
// add_vertex(vp,g)
//==============================================================================
template <class Graph, class VertexProperties>
550
551
inline __attribute__((always_inline))
typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor
552
add_vertex(const VertexProperties& p, UndirectedAdaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
553
{
554
    return add_vertex(p, g.original_graph());
Tiago Peixoto's avatar
Tiago Peixoto committed
555
556
557
558
559
560
}

//==============================================================================
// clear_vertex(u,g)
//==============================================================================
template <class Graph>
561
inline __attribute__((always_inline))
562
563
void clear_vertex(typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor u,
                  UndirectedAdaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
564
{
565
    clear_vertex(u, g.original_graph());
Tiago Peixoto's avatar
Tiago Peixoto committed
566
567
568
569
570
571
}

//==============================================================================
// remove_vertex(u,g)
//==============================================================================
template <class Graph>
572
inline __attribute__((always_inline))
573
574
void remove_vertex(typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor u,
                   UndirectedAdaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
575
{
576
    remove_vertex(u, g.original_graph());
Tiago Peixoto's avatar
Tiago Peixoto committed
577
578
}

579
580
581
582
//==============================================================================
// remove_vertex_fast(u,g)
//==============================================================================
template <class Graph>
583
inline __attribute__((always_inline))
584
585
void remove_vertex_fast(typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor u,
                        UndirectedAdaptor<Graph>& g)
586
{
587
    remove_vertex_fast(u, g.original_graph());
588
589
}

Tiago Peixoto's avatar
Tiago Peixoto committed
590
591
592
593
//==============================================================================
// add_edge(u,v,g)
//==============================================================================
template <class Graph>
594
inline __attribute__((always_inline))
595
596
597
598
599
600
std::pair<typename graph_traits<UndirectedAdaptor<Graph> >::edge_descriptor,
          bool>
add_edge(typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor u,
         typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor v,
         UndirectedAdaptor<Graph>& g)
{
601
    return add_edge(u, v, g.original_graph());
Tiago Peixoto's avatar
Tiago Peixoto committed
602
603
604
605
606
607
}

//==============================================================================
// add_edge(u,v,ep,g)
//==============================================================================
template <class Graph, class EdgeProperties>
608
inline __attribute__((always_inline))
609
610
611
612
613
614
std::pair<typename graph_traits<UndirectedAdaptor<Graph> >::edge_descriptor,
          bool>
add_edge(typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor u,
         typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor v,
         const EdgeProperties& ep, UndirectedAdaptor<Graph>& g)
{
615
    return add_edge(u, v, ep, g.original_graph());
Tiago Peixoto's avatar
Tiago Peixoto committed
616
617
618
619
620
621
}

//==============================================================================
// remove_edge(u,v,g)
//==============================================================================
template <class Graph>
622
inline __attribute__((always_inline))
623
624
625
void remove_edge(typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor u,
                 typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor v,
                 UndirectedAdaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
626
{
627
628
629
    auto e = edge(u, v, g);
    if (e.second)
        remove_edge(e.first, g);
Tiago Peixoto's avatar
Tiago Peixoto committed
630
631
632
633
634
635
}

//==============================================================================
// remove_edge(e,g)
//==============================================================================
template <class Graph>
636
inline __attribute__((always_inline))
637
638
void remove_edge(const typename graph_traits<UndirectedAdaptor<Graph> >::edge_descriptor& e,
                 UndirectedAdaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
639
{
640
    remove_edge(e, g.original_graph());
Tiago Peixoto's avatar
Tiago Peixoto committed
641
642
643
644
645
646
}

//==============================================================================
// remove_edge(e_iter,g)
//==============================================================================
template <class Graph>
647
inline __attribute__((always_inline))
648
void remove_edge(const typename graph_traits<UndirectedAdaptor<Graph> >::out_edge_iterator& iter,
649
                 UndirectedAdaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
650
651
652
653
654
655
656
657
{
    remove_edge(*iter, g);
}

//==============================================================================
// remove_out_edge_if(v,predicate,g)
//==============================================================================
template <class Graph, class Predicate>
658
inline
659
660
void remove_out_edge_if(typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor v,
                        Predicate predicate, UndirectedAdaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
661
{
662
663
664
    std::vector<typename UndirectedAdaptor<Graph>::EdgeDescriptor> removed_edges;
    auto edge_range = out_edges(v,g);
    for(auto iter = edge_range.first; iter != edge_range.second; ++iter)
Tiago Peixoto's avatar
Tiago Peixoto committed
665
        if (predicate(*iter))
666
667
668
            removed_edges.push_back(*iter);
    for(auto& e : removed_edges)
        remove_edge(e, g);
Tiago Peixoto's avatar
Tiago Peixoto committed
669
670
}

671
672
673
674
//==============================================================================
// remove_in_edge_if(v,predicate,g)
//==============================================================================
template <class Graph, class Predicate>
675
inline
676
677
678
void remove_in_edge_if(typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor v,
                       Predicate predicate, UndirectedAdaptor<Graph>& g)
{
679
680
681
    std::vector<typename UndirectedAdaptor<Graph>::EdgeDescriptor> removed_edges;
    auto edge_range = in_edges(v,g);
    for(auto iter = edge_range.first; iter != edge_range.second; ++iter)
682
        if (predicate(*iter))
683
684
685
            removed_edges.push_back(*iter);
    for(auto& e : removed_edges)
        remove_edge(e, g);
686
687
}

Tiago Peixoto's avatar
Tiago Peixoto committed
688
689

//==============================================================================
690
// Property maps
Tiago Peixoto's avatar
Tiago Peixoto committed
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
//==============================================================================

//==============================================================================
// vertex_property<UndirectedAdaptor>
//==============================================================================
template <class Graph>
class vertex_property<UndirectedAdaptor<Graph> >
{
public:
    typedef typename vertex_property<Graph>::type type;
};

//==============================================================================
// vertex_property_type<UndirectedAdaptor>
//==============================================================================
template <class Graph>
class vertex_property_type<UndirectedAdaptor<Graph> >
{
public:
    typedef typename vertex_property_type<Graph>::type type;
};

//==============================================================================
// edge_property<UndirectedAdaptor>
//==============================================================================
template <class Graph>
class edge_property<UndirectedAdaptor<Graph> >
{
public:
    typedef typename edge_property<Graph>::type type;
};

//==============================================================================
// edge_property_type<UndirectedAdaptor>
//==============================================================================
template <class Graph>
class edge_property_type<UndirectedAdaptor<Graph> >
{
public:
    typedef typename edge_property_type<Graph>::type type;
};

//==============================================================================
// property_map<UndirecterdAdaptor, PropertyTag>
//==============================================================================
template <class Graph, class PropertyTag>
class property_map<UndirectedAdaptor<Graph>, PropertyTag>
{
public:
    typedef typename property_map<Graph, PropertyTag>::type type;
741
    typedef typename property_map<Graph, PropertyTag>::const_type const_type;
Tiago Peixoto's avatar
Tiago Peixoto committed
742
743
744
745
746
747
};

//==============================================================================
// property_map<UndirectedAdaptor, T Bundle::*>
//==============================================================================
template <typename Graph, typename T, typename Bundle>
748
class property_map<UndirectedAdaptor<Graph>, T Bundle::*>
Tiago Peixoto's avatar
Tiago Peixoto committed
749
750
751
752
753
754
755
756
757
758
759
{
public:
    typedef typename property_map<Graph, T Bundle::*>::type type;
    typedef typename property_map<Graph, T Bundle::*>::const_type const_type;
};


//==============================================================================
// get(tag,g)
//==============================================================================
template <class PropertyTag, class Graph>
760
inline
761
typename property_map<UndirectedAdaptor<Graph>, PropertyTag>::type
762
get(PropertyTag tag, UndirectedAdaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
763
{
764
    return get(tag, g.original_graph());
Tiago Peixoto's avatar
Tiago Peixoto committed
765
766
767
}

//==============================================================================
768
// const get(tag,g)
Tiago Peixoto's avatar
Tiago Peixoto committed
769
770
//==============================================================================
template <class PropertyTag, class Graph>
771
inline
772
typename property_map<UndirectedAdaptor<Graph>, PropertyTag>::const_type
773
get(PropertyTag tag, const UndirectedAdaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
774
{
775
    return get(tag, g.original_graph());
Tiago Peixoto's avatar
Tiago Peixoto committed
776
777
778
779
780
781
}

//==============================================================================
// get(tag,g,v)
//==============================================================================
template <class PropertyTag, class Graph>
782
inline
783
784
785
typename property_traits
    <typename property_map<UndirectedAdaptor<Graph>,
                           PropertyTag>::const_type >::value_type
786
get(PropertyTag tag, const UndirectedAdaptor<Graph>& g,
787
    typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor v)
Tiago Peixoto's avatar
Tiago Peixoto committed
788
{
789
    return get(tag, g.original_graph(), v);
Tiago Peixoto's avatar
Tiago Peixoto committed
790
791
792
793
794
795
}

//==============================================================================
// get(tag,g,e)
//==============================================================================
template <class PropertyTag, class Graph>
796
inline
797
798
799
typename property_traits
    <typename property_map<UndirectedAdaptor<Graph>,
                           PropertyTag>::const_type >::value_type
800
get(PropertyTag tag, const UndirectedAdaptor<Graph>& g,
801
    const typename graph_traits<UndirectedAdaptor<Graph> >::edge_descriptor& e)
Tiago Peixoto's avatar
Tiago Peixoto committed
802
{
803
    return get(tag, g.original_graph(), e);
Tiago Peixoto's avatar
Tiago Peixoto committed
804
805
806
807
808
809
}

//==============================================================================
// put(tag, g, v, value)
//==============================================================================
template <class Graph, class PropertyTag, class Value>
810
inline
811
void put(PropertyTag tag, UndirectedAdaptor<Graph>& g,
812
         typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor v,
813
         const Value& value)
Tiago Peixoto's avatar
Tiago Peixoto committed
814
{
815
    put(tag, g.original_graph(), v, value);
Tiago Peixoto's avatar
Tiago Peixoto committed
816
817
818
819
820
821
}

//==============================================================================
// put(tag, g, e, value)
//==============================================================================
template <class Graph, class PropertyTag, class X, class Value>
822
inline
823
void put(PropertyTag tag, const UndirectedAdaptor<Graph>& g,
824
         const typename graph_traits<UndirectedAdaptor<Graph> >::edge_descriptor& e,
825
         const Value &value)
Tiago Peixoto's avatar
Tiago Peixoto committed
826
{
827
    put(tag, g.original_graph(), e, value);
Tiago Peixoto's avatar
Tiago Peixoto committed
828
829
830
831
832
833
}

//==============================================================================
// get_property(g,tag)
//==============================================================================
template <class Graph, class GraphProperties, class GraphPropertyTag>
834
inline
Tiago Peixoto's avatar
Tiago Peixoto committed
835
typename property_value<GraphProperties, GraphPropertyTag>::type&
836
get_property(UndirectedAdaptor<Graph>& g, GraphPropertyTag tag)
Tiago Peixoto's avatar
Tiago Peixoto committed
837
{
838
    get_property(g.original_graph(), tag);
Tiago Peixoto's avatar
Tiago Peixoto committed
839
840
841
842
843
844
}

//==============================================================================
// const get_property(g,tag)
//==============================================================================
template <class Graph, class GraphProperties, class GraphPropertyTag>
845
inline
Tiago Peixoto's avatar
Tiago Peixoto committed
846
const typename property_value<GraphProperties, GraphPropertyTag>::type&
847
get_property(const UndirectedAdaptor<Graph>& g, GraphPropertyTag tag)
Tiago Peixoto's avatar
Tiago Peixoto committed
848
{
849
    get_property(g.original_graph(), tag);
Tiago Peixoto's avatar
Tiago Peixoto committed
850
851
852
853
854
855
}

} // namespace boost


#endif // GRAPH_ADAPTOR_HH