graph_adaptor.hh 25.1 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-2019 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
25
26
27
#include <boost/config.hpp>
#include <boost/iterator_adaptors.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/properties.hpp>

28
29
#include "transform_iterator.hh"

Tiago Peixoto's avatar
Tiago Peixoto committed
30
31
32
namespace boost {

//==============================================================================
33
// undirected_adaptor
34
// This class encapsulates a directed graph with parallel edges and provides a
Tiago Peixoto's avatar
Tiago Peixoto committed
35
36
// view of the graph as undirected with parallel edges.
//==============================================================================
37
template <class Graph> class undirected_adaptor
Tiago Peixoto's avatar
Tiago Peixoto committed
38
39
{
public:
40
    undirected_adaptor(const Graph& g) : _g(const_cast<Graph&>(g)){}
Tiago Peixoto's avatar
Tiago Peixoto committed
41

42
43
    typedef typename vertex_property_type<Graph>::type vertex_property_type;
    typedef typename edge_property_type<Graph>::type edge_property_type;
44
    typedef typename Graph::graph_tag graph_tag;
45
    typedef Graph graph_type;
46

Tiago Peixoto's avatar
Tiago Peixoto committed
47
    typedef Graph original_graph_t;
48

49
    typedef typename graph_traits<undirected_adaptor<Graph> >::vertex_descriptor
50
        vertex_descriptor;
51
    typedef typename graph_traits<undirected_adaptor<Graph> >::edge_descriptor
52
53
        edge_descriptor;

54
55
56
    typedef undirected_tag directed_category;
    typedef allow_parallel_edge_tag edge_parallel_category;
    typedef typename graph_traits<Graph>::traversal_category traversal_category;
57

58
59
60
    typedef typename Graph::out_edge_iterator all_edge_iterator;
    typedef typename Graph::out_edge_iterator all_edge_iterator_reversed;

61
62
    const Graph& original_graph() const {return _g;}
    Graph& original_graph() {return _g;}
63

64
65
    static vertex_descriptor null_vertex() {graph_traits<Graph>::null_vertex();}

Tiago Peixoto's avatar
Tiago Peixoto committed
66
private:
67
    Graph& _g;
Tiago Peixoto's avatar
Tiago Peixoto committed
68
69
};

70
template <class Graph>
71
struct get_iterator_category
72
{
73
74
    typedef typename graph_traits<Graph>::out_edge_iterator iter_t;
    typedef typename std::iterator_traits<iter_t>::iterator_category type;
75
};
76

Tiago Peixoto's avatar
Tiago Peixoto committed
77
78

//==============================================================================
79
80
// graph_traits<undirected_adaptor>
// this defines all the necessary types associated with undirected_adaptor
Tiago Peixoto's avatar
Tiago Peixoto committed
81
82
//==============================================================================
template <class Graph>
83
struct graph_traits<undirected_adaptor<Graph> > {
Tiago Peixoto's avatar
Tiago Peixoto committed
84
    typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
85
    typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
Tiago Peixoto's avatar
Tiago Peixoto committed
86

87
88
89
    typedef typename graph_traits<Graph>::adjacency_iterator adjacency_iterator;
    typedef typename graph_traits<Graph>::out_edge_iterator out_edge_iterator;
    typedef typename graph_traits<Graph>::in_edge_iterator in_edge_iterator;
Tiago Peixoto's avatar
Tiago Peixoto committed
90
    typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
91
    typedef typename graph_traits<Graph>::edge_iterator edge_iterator;
92

93

Tiago Peixoto's avatar
Tiago Peixoto committed
94
    typedef undirected_tag directed_category;
95
    typedef allow_parallel_edge_tag edge_parallel_category;
96
    typedef typename graph_traits<Graph>::traversal_category traversal_category;
Tiago Peixoto's avatar
Tiago Peixoto committed
97
98
99
    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;
100
101
102
103
104

    static vertex_descriptor null_vertex()
    {
        return graph_traits<Graph>::null_vertex();
    }
105
106
107
108
109
110
111

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
112
113
};

114
template <class Graph>
115
116
struct graph_traits< const undirected_adaptor<Graph> >:
    public graph_traits<undirected_adaptor<Graph> > {};
117

Tiago Peixoto's avatar
Tiago Peixoto committed
118
119
//==============================================================================
// Nonmember functions
120
// these provide manipulation of the graph
Tiago Peixoto's avatar
Tiago Peixoto committed
121
122
123
124
125
126
//==============================================================================

//==============================================================================
// source(e,g)
//==============================================================================
template <class Graph>
127
[[gnu::always_inline]] [[gnu::flatten]] [[gnu::pure]] inline
128
129
130
auto
source(const typename graph_traits<undirected_adaptor<Graph> >::edge_descriptor& e,
       const undirected_adaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
131
{
132
    return source(e, g.original_graph());
Tiago Peixoto's avatar
Tiago Peixoto committed
133
134
135
136
137
138
}

//==============================================================================
// target(e,g)
//==============================================================================
template <class Graph>
139
[[gnu::always_inline]] [[gnu::flatten]] [[gnu::pure]] inline
140
141
142
auto
target(const typename graph_traits<undirected_adaptor<Graph> >::edge_descriptor& e,
       const undirected_adaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
143
{
144
    return target(e, g.original_graph());
Tiago Peixoto's avatar
Tiago Peixoto committed
145
146
147
148
149
150
}

//==============================================================================
// vertex(n,g)
//==============================================================================
template <class Graph>
151
[[gnu::always_inline]] [[gnu::flatten]] [[gnu::pure]] inline
152
153
154
auto
vertex(typename graph_traits<undirected_adaptor<Graph> >::vertices_size_type n,
       const undirected_adaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
155
{
156
    return vertex(n, g.original_graph());
Tiago Peixoto's avatar
Tiago Peixoto committed
157
158
159
160
161
162
}

//==============================================================================
// vertices(g)
//==============================================================================
template <class Graph>
163
[[gnu::always_inline]] [[gnu::flatten]] inline
164
165
auto
vertices(const undirected_adaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
166
{
167
    return vertices(g.original_graph());
Tiago Peixoto's avatar
Tiago Peixoto committed
168
169
170
171
172
173
}

//==============================================================================
// edges(g)
//==============================================================================
template <class Graph>
174
[[gnu::always_inline]] [[gnu::flatten]] inline
175
176
auto
edges(const undirected_adaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
177
{
178
    return edges(g.original_graph());
Tiago Peixoto's avatar
Tiago Peixoto committed
179
180
}

181
182
183
184
//==============================================================================
// edge(u, v, g)
//==============================================================================
template <class Graph>
185
[[gnu::flatten]] inline
186
187
188
189
auto
edge(typename graph_traits<undirected_adaptor<Graph> >::vertex_descriptor u,
     typename graph_traits<undirected_adaptor<Graph> >::vertex_descriptor v,
     const undirected_adaptor<Graph>& g)
190
{
191
    auto res = edge(u, v, g.original_graph());
192
193
194

    if (!res.second)
    {
195
        res = edge(v, u, g.original_graph());
196
        std::swap(res.first.s, res.first.t);
197
    }
198
199

    return res;
200
201
}

Tiago Peixoto's avatar
Tiago Peixoto committed
202
203
204
205
//==============================================================================
// out_edges(u,g)
//==============================================================================
template <class Graph>
206
[[gnu::always_inline]] [[gnu::flatten]] inline
207
208
209
auto
out_edges(typename graph_traits<undirected_adaptor<Graph>>::vertex_descriptor u,
          const undirected_adaptor<Graph>& g)
210
{
211
    return _all_edges_out(u, g.original_graph());
Tiago Peixoto's avatar
Tiago Peixoto committed
212
213
}

214
template <class Graph>
215
[[gnu::always_inline]] [[gnu::flatten]] inline
216
217
218
219
220
221
222
auto
_all_edges_out(typename graph_traits<undirected_adaptor<Graph>>::vertex_descriptor u,
               const undirected_adaptor<Graph>& g)
{
    return out_edges(u, g);
}

223
224
225
226
//==============================================================================
// in_edges(u,g)
//==============================================================================
template <class Graph>
227
[[gnu::always_inline]] [[gnu::flatten]] inline
228
auto
Tiago Peixoto's avatar
Tiago Peixoto committed
229
230
in_edges(typename graph_traits<undirected_adaptor<Graph>>::vertex_descriptor,
         const undirected_adaptor<Graph>&)
231
232
233
234
235
236
237
{
    typedef typename graph_traits<undirected_adaptor<Graph>>::in_edge_iterator
        iter_t;
    return std::make_pair(iter_t(), iter_t());
}

template <class Graph>
238
[[gnu::always_inline]] [[gnu::flatten]] inline
239
240
241
auto
_all_edges_in(typename graph_traits<undirected_adaptor<Graph>>::vertex_descriptor u,
               const undirected_adaptor<Graph>& g)
242
{
243
    return _all_edges_in(u, g.original_graph());
244
245
}

246
template <class Graph>
247
[[gnu::always_inline]] [[gnu::flatten]] inline
248
249
250
251
252
253
254
auto
all_edges(typename graph_traits<undirected_adaptor<Graph>>::vertex_descriptor u,
          const undirected_adaptor<Graph>& g)
{
    return out_edges(u, g);
}

255
//==============================================================================
256
// out_neighbors(u, g)
257
258
//==============================================================================
template <class Graph>
259
[[gnu::always_inline]] [[gnu::flatten]] inline
260
auto
261
out_neighbors(typename graph_traits<undirected_adaptor<Graph> >::vertex_descriptor u,
262
               const undirected_adaptor<Graph>& g)
263
{
264
    return all_neighbors(u, g.original_graph());
265
266
267
}

//==============================================================================
268
// in_neighbors(u, g)
269
270
//==============================================================================
template <class Graph>
271
[[gnu::always_inline]] [[gnu::flatten]] inline
272
auto
273
in_neighbors(typename graph_traits<undirected_adaptor<Graph> >::vertex_descriptor u,
274
275
              const undirected_adaptor<Graph>& g)
{
276
    return out_neighbors(u, g);
277
278
279
}

//==============================================================================
280
// all_neighbors(u, g)
281
282
//==============================================================================
template <class Graph>
283
[[gnu::always_inline]] [[gnu::flatten]] inline
284
auto
285
all_neighbors(typename graph_traits<undirected_adaptor<Graph> >::vertex_descriptor u,
286
               const undirected_adaptor<Graph>& g)
287
{
288
    return out_neighbors(u, g);
289
290
}

Tiago Peixoto's avatar
Tiago Peixoto committed
291
292
293
294
//==============================================================================
// adjacent_vertices(u,g)
//==============================================================================
template <class Graph>
295
[[gnu::always_inline]] [[gnu::flatten]] inline
296
auto
297
adjacent_vertices
298
299
    (typename graph_traits<undirected_adaptor<Graph> >::vertex_descriptor u,
     const undirected_adaptor<Graph>& g)
300
{
301
    return out_neighbors(u, g);
Tiago Peixoto's avatar
Tiago Peixoto committed
302
303
304
305
306
307
}

//==============================================================================
// num_vertices(g)
//==============================================================================
template <class Graph>
308
[[gnu::always_inline]] [[gnu::flatten]] inline
309
310
auto
num_vertices(const undirected_adaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
311
{
312
    return num_vertices(g.original_graph());
313
}
Tiago Peixoto's avatar
Tiago Peixoto committed
314
315
316
317
318

//==============================================================================
// num_edges(g)
//==============================================================================
template <class Graph>
319
[[gnu::always_inline]] [[gnu::flatten]] inline
320
321
auto
num_edges(const undirected_adaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
322
{
323
    return num_edges(g.original_graph());
324
}
Tiago Peixoto's avatar
Tiago Peixoto committed
325
326
327
328
329

//==============================================================================
// out_degree(u,g)
//==============================================================================
template <class Graph>
330
[[gnu::always_inline]] [[gnu::flatten]] inline
331
332
333
auto
out_degree(typename graph_traits<undirected_adaptor<Graph> >::vertex_descriptor u,
           const undirected_adaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
334
{
335
    return degree(u, g.original_graph());
336
337
338
339
340
341
}

//==============================================================================
// in_degree(u,g)
//==============================================================================
template <class Graph>
342
[[gnu::always_inline]] [[gnu::flatten]] inline
343
auto
Tiago Peixoto's avatar
Tiago Peixoto committed
344
345
in_degree(typename graph_traits<undirected_adaptor<Graph> >::vertex_descriptor,
          const undirected_adaptor<Graph>&)
346
{
347
    return 0;
Tiago Peixoto's avatar
Tiago Peixoto committed
348
349
350
351
352
353
}

//==============================================================================
// degree(u,g)
//==============================================================================
template <class Graph>
354
[[gnu::always_inline]] [[gnu::flatten]] inline
355
356
357
auto
degree(typename graph_traits<undirected_adaptor<Graph> >::vertex_descriptor u,
       const undirected_adaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
358
359
360
361
362
363
364
365
{
    return out_degree(u, g);
}


//==============================================================================
// add_vertex(g)
//==============================================================================
366
template <class Graph>
367
[[gnu::flatten]] inline
368
369
auto
add_vertex(undirected_adaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
370
{
371
    return add_vertex(g.original_graph());
Tiago Peixoto's avatar
Tiago Peixoto committed
372
373
374
375
376
377
}

//==============================================================================
// add_vertex(vp,g)
//==============================================================================
template <class Graph, class VertexProperties>
378
[[gnu::flatten]] inline
379
380
auto
add_vertex(const VertexProperties& p, undirected_adaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
381
{
382
    return add_vertex(p, g.original_graph());
Tiago Peixoto's avatar
Tiago Peixoto committed
383
384
385
386
387
388
}

//==============================================================================
// clear_vertex(u,g)
//==============================================================================
template <class Graph>
389
[[gnu::flatten]] inline
390
391
void clear_vertex(typename graph_traits<undirected_adaptor<Graph> >::vertex_descriptor u,
                  undirected_adaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
392
{
393
    clear_vertex(u, g.original_graph());
Tiago Peixoto's avatar
Tiago Peixoto committed
394
395
}

396
397
398
399
//==============================================================================
// clear_vertex(u,g,pred)
//==============================================================================
template <class Graph, class Pred>
400
[[gnu::flatten]] inline
401
402
403
404
405
406
void clear_vertex(typename graph_traits<undirected_adaptor<Graph> >::vertex_descriptor u,
                  undirected_adaptor<Graph>& g, Pred&& pred)
{
    clear_vertex(u, g.original_graph(), pred);
}

Tiago Peixoto's avatar
Tiago Peixoto committed
407
408
409
410
//==============================================================================
// remove_vertex(u,g)
//==============================================================================
template <class Graph>
411
[[gnu::flatten]] inline
412
413
void remove_vertex(typename graph_traits<undirected_adaptor<Graph> >::vertex_descriptor u,
                   undirected_adaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
414
{
415
    remove_vertex(u, g.original_graph());
Tiago Peixoto's avatar
Tiago Peixoto committed
416
417
}

418
419
420
421
//==============================================================================
// remove_vertex_fast(u,g)
//==============================================================================
template <class Graph>
422
[[gnu::flatten]] inline
423
424
void remove_vertex_fast(typename graph_traits<undirected_adaptor<Graph> >::vertex_descriptor u,
                        undirected_adaptor<Graph>& g)
425
{
426
    remove_vertex_fast(u, g.original_graph());
427
428
}

Tiago Peixoto's avatar
Tiago Peixoto committed
429
430
431
432
//==============================================================================
// add_edge(u,v,g)
//==============================================================================
template <class Graph>
433
[[gnu::flatten]] inline
434
std::pair<typename graph_traits<undirected_adaptor<Graph> >::edge_descriptor,
435
          bool>
436
437
438
add_edge(typename graph_traits<undirected_adaptor<Graph> >::vertex_descriptor u,
         typename graph_traits<undirected_adaptor<Graph> >::vertex_descriptor v,
         undirected_adaptor<Graph>& g)
439
{
440
    return add_edge(u, v, g.original_graph());
Tiago Peixoto's avatar
Tiago Peixoto committed
441
442
443
444
445
446
}

//==============================================================================
// add_edge(u,v,ep,g)
//==============================================================================
template <class Graph, class EdgeProperties>
447
[[gnu::flatten]] inline
448
449
450
451
auto
add_edge(typename graph_traits<undirected_adaptor<Graph> >::vertex_descriptor u,
         typename graph_traits<undirected_adaptor<Graph> >::vertex_descriptor v,
         const EdgeProperties& ep, undirected_adaptor<Graph>& g)
452
{
453
    return add_edge(u, v, ep, g.original_graph());
Tiago Peixoto's avatar
Tiago Peixoto committed
454
455
456
457
458
459
}

//==============================================================================
// remove_edge(u,v,g)
//==============================================================================
template <class Graph>
460
[[gnu::flatten]] inline
461
462
463
void remove_edge(typename graph_traits<undirected_adaptor<Graph> >::vertex_descriptor u,
                 typename graph_traits<undirected_adaptor<Graph> >::vertex_descriptor v,
                 undirected_adaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
464
{
465
466
467
    auto e = edge(u, v, g);
    if (e.second)
        remove_edge(e.first, g);
Tiago Peixoto's avatar
Tiago Peixoto committed
468
469
470
471
472
473
}

//==============================================================================
// remove_edge(e,g)
//==============================================================================
template <class Graph>
474
[[gnu::flatten]] inline
475
476
void remove_edge(typename graph_traits<undirected_adaptor<Graph> >::edge_descriptor e,
                 undirected_adaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
477
{
478
    auto& u = g.original_graph();
479
    u.reverse_edge(e);
480
    remove_edge(e, u);
Tiago Peixoto's avatar
Tiago Peixoto committed
481
482
483
484
485
486
}

//==============================================================================
// remove_edge(e_iter,g)
//==============================================================================
template <class Graph>
487
[[gnu::flatten]] inline
488
489
void remove_edge(const typename graph_traits<undirected_adaptor<Graph> >::out_edge_iterator& iter,
                 undirected_adaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
490
491
492
493
494
495
496
497
{
    remove_edge(*iter, g);
}

//==============================================================================
// remove_out_edge_if(v,predicate,g)
//==============================================================================
template <class Graph, class Predicate>
498
inline
499
500
void remove_out_edge_if(typename graph_traits<undirected_adaptor<Graph> >::vertex_descriptor v,
                        Predicate predicate, undirected_adaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
501
{
502
    std::vector<typename undirected_adaptor<Graph>::EdgeDescriptor> removed_edges;
503
504
    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
505
        if (predicate(*iter))
506
507
508
            removed_edges.push_back(*iter);
    for(auto& e : removed_edges)
        remove_edge(e, g);
Tiago Peixoto's avatar
Tiago Peixoto committed
509
510
}

511
512
513
514
//==============================================================================
// remove_in_edge_if(v,predicate,g)
//==============================================================================
template <class Graph, class Predicate>
515
516
void remove_in_edge_if(typename graph_traits<undirected_adaptor<Graph> >::vertex_descriptor v,
                       Predicate predicate, undirected_adaptor<Graph>& g)
517
{
518
    std::vector<typename undirected_adaptor<Graph>::EdgeDescriptor> removed_edges;
519
520
    auto edge_range = in_edges(v,g);
    for(auto iter = edge_range.first; iter != edge_range.second; ++iter)
521
        if (predicate(*iter))
522
523
524
            removed_edges.push_back(*iter);
    for(auto& e : removed_edges)
        remove_edge(e, g);
525
526
}

Tiago Peixoto's avatar
Tiago Peixoto committed
527
528

//==============================================================================
529
// Property maps
Tiago Peixoto's avatar
Tiago Peixoto committed
530
531
532
//==============================================================================

//==============================================================================
533
// vertex_property<undirected_adaptor>
Tiago Peixoto's avatar
Tiago Peixoto committed
534
535
//==============================================================================
template <class Graph>
536
class vertex_property<undirected_adaptor<Graph> >
Tiago Peixoto's avatar
Tiago Peixoto committed
537
538
539
540
541
542
{
public:
    typedef typename vertex_property<Graph>::type type;
};

//==============================================================================
543
// vertex_property_type<undirected_adaptor>
Tiago Peixoto's avatar
Tiago Peixoto committed
544
545
//==============================================================================
template <class Graph>
546
class vertex_property_type<undirected_adaptor<Graph> >
Tiago Peixoto's avatar
Tiago Peixoto committed
547
548
549
550
551
552
{
public:
    typedef typename vertex_property_type<Graph>::type type;
};

//==============================================================================
553
// edge_property<undirected_adaptor>
Tiago Peixoto's avatar
Tiago Peixoto committed
554
555
//==============================================================================
template <class Graph>
556
class edge_property<undirected_adaptor<Graph> >
Tiago Peixoto's avatar
Tiago Peixoto committed
557
558
559
560
561
562
{
public:
    typedef typename edge_property<Graph>::type type;
};

//==============================================================================
563
// edge_property_type<undirected_adaptor>
Tiago Peixoto's avatar
Tiago Peixoto committed
564
565
//==============================================================================
template <class Graph>
566
class edge_property_type<undirected_adaptor<Graph> >
Tiago Peixoto's avatar
Tiago Peixoto committed
567
568
569
570
571
572
573
574
575
{
public:
    typedef typename edge_property_type<Graph>::type type;
};

//==============================================================================
// property_map<UndirecterdAdaptor, PropertyTag>
//==============================================================================
template <class Graph, class PropertyTag>
576
class property_map<undirected_adaptor<Graph>, PropertyTag>
Tiago Peixoto's avatar
Tiago Peixoto committed
577
578
579
{
public:
    typedef typename property_map<Graph, PropertyTag>::type type;
580
    typedef typename property_map<Graph, PropertyTag>::const_type const_type;
Tiago Peixoto's avatar
Tiago Peixoto committed
581
582
583
};

//==============================================================================
584
// property_map<undirected_adaptor, T Bundle::*>
Tiago Peixoto's avatar
Tiago Peixoto committed
585
586
//==============================================================================
template <typename Graph, typename T, typename Bundle>
587
class property_map<undirected_adaptor<Graph>, T Bundle::*>
Tiago Peixoto's avatar
Tiago Peixoto committed
588
589
590
591
592
593
594
595
596
597
598
{
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>
599
inline
600
601
typename property_map<undirected_adaptor<Graph>, PropertyTag>::type
get(PropertyTag tag, undirected_adaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
602
{
603
    return get(tag, g.original_graph());
Tiago Peixoto's avatar
Tiago Peixoto committed
604
605
606
}

//==============================================================================
607
// const get(tag,g)
Tiago Peixoto's avatar
Tiago Peixoto committed
608
609
//==============================================================================
template <class PropertyTag, class Graph>
610
inline
611
612
typename property_map<undirected_adaptor<Graph>, PropertyTag>::const_type
get(PropertyTag tag, const undirected_adaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
613
{
614
    return get(tag, g.original_graph());
Tiago Peixoto's avatar
Tiago Peixoto committed
615
616
617
618
619
620
}

//==============================================================================
// get(tag,g,v)
//==============================================================================
template <class PropertyTag, class Graph>
621
inline
622
typename property_traits
623
    <typename property_map<undirected_adaptor<Graph>,
624
                           PropertyTag>::const_type >::value_type
625
626
get(PropertyTag tag, const undirected_adaptor<Graph>& g,
    typename graph_traits<undirected_adaptor<Graph> >::vertex_descriptor v)
Tiago Peixoto's avatar
Tiago Peixoto committed
627
{
628
    return get(tag, g.original_graph(), v);
Tiago Peixoto's avatar
Tiago Peixoto committed
629
630
631
632
633
634
}

//==============================================================================
// get(tag,g,e)
//==============================================================================
template <class PropertyTag, class Graph>
635
inline
636
typename property_traits
637
    <typename property_map<undirected_adaptor<Graph>,
638
                           PropertyTag>::const_type >::value_type
639
640
get(PropertyTag tag, const undirected_adaptor<Graph>& g,
    const typename graph_traits<undirected_adaptor<Graph> >::edge_descriptor& e)
Tiago Peixoto's avatar
Tiago Peixoto committed
641
{
642
    return get(tag, g.original_graph(), e);
Tiago Peixoto's avatar
Tiago Peixoto committed
643
644
645
646
647
648
}

//==============================================================================
// put(tag, g, v, value)
//==============================================================================
template <class Graph, class PropertyTag, class Value>
649
inline
650
651
void put(PropertyTag tag, undirected_adaptor<Graph>& g,
         typename graph_traits<undirected_adaptor<Graph> >::vertex_descriptor v,
652
         const Value& value)
Tiago Peixoto's avatar
Tiago Peixoto committed
653
{
654
    put(tag, g.original_graph(), v, value);
Tiago Peixoto's avatar
Tiago Peixoto committed
655
656
657
658
659
660
}

//==============================================================================
// put(tag, g, e, value)
//==============================================================================
template <class Graph, class PropertyTag, class X, class Value>
661
inline
662
663
void put(PropertyTag tag, const undirected_adaptor<Graph>& g,
         const typename graph_traits<undirected_adaptor<Graph> >::edge_descriptor& e,
664
         const Value &value)
Tiago Peixoto's avatar
Tiago Peixoto committed
665
{
666
    put(tag, g.original_graph(), e, value);
Tiago Peixoto's avatar
Tiago Peixoto committed
667
668
669
670
671
672
}

//==============================================================================
// get_property(g,tag)
//==============================================================================
template <class Graph, class GraphProperties, class GraphPropertyTag>
673
inline
Tiago Peixoto's avatar
Tiago Peixoto committed
674
typename property_value<GraphProperties, GraphPropertyTag>::type&
675
get_property(undirected_adaptor<Graph>& g, GraphPropertyTag tag)
Tiago Peixoto's avatar
Tiago Peixoto committed
676
{
677
    get_property(g.original_graph(), tag);
Tiago Peixoto's avatar
Tiago Peixoto committed
678
679
680
681
682
683
}

//==============================================================================
// const get_property(g,tag)
//==============================================================================
template <class Graph, class GraphProperties, class GraphPropertyTag>
684
inline
Tiago Peixoto's avatar
Tiago Peixoto committed
685
const typename property_value<GraphProperties, GraphPropertyTag>::type&
686
get_property(const undirected_adaptor<Graph>& g, GraphPropertyTag tag)
Tiago Peixoto's avatar
Tiago Peixoto committed
687
{
688
    get_property(g.original_graph(), tag);
Tiago Peixoto's avatar
Tiago Peixoto committed
689
690
691
692
693
694
}

} // namespace boost


#endif // GRAPH_ADAPTOR_HH