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) 2007  Tiago de Paula Peixoto <tiago@forked.de>
Tiago Peixoto's avatar
Tiago Peixoto committed
4
5
6
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
Tiago Peixoto's avatar
Tiago Peixoto committed
7
// as published by the Free Software Foundation; either version 3
Tiago Peixoto's avatar
Tiago Peixoto committed
8
9
10
11
12
13
14
15
// of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
16
// along with this program. If not, see <http://www.gnu.org/licenses/>.
Tiago Peixoto's avatar
Tiago Peixoto committed
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#ifndef GRAPH_ADAPTOR_HH
#define GRAPH_ADAPTOR_HH

#include <boost/config.hpp>
#include <boost/iterator_adaptors.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/filtered_graph.hpp>

namespace boost {

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

44
45
46
    typedef typename Graph::vertex_property_type vertex_property_type;
    typedef typename Graph::edge_property_type edge_property_type;
    typedef typename Graph::graph_tag graph_tag;
47
    typedef Graph graph_type;
48

Tiago Peixoto's avatar
Tiago Peixoto committed
49
50
    class EdgeDescriptor;
    typedef Graph original_graph_t;
51

52
53
54
55
56
    typedef typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor
        vertex_descriptor;
    typedef typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor
        edge_descriptor;

57

Tiago Peixoto's avatar
Tiago Peixoto committed
58
59
60
#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
    // Bundled properties support
    template<typename Descriptor>
61
62
    typename graph::detail::bundled_result<Graph, Descriptor>::type&
        operator[](Descriptor x) { return this->m_g[x]; }
Tiago Peixoto's avatar
Tiago Peixoto committed
63
64

    template<typename Descriptor>
65
66
    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
67
#endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES
68
69


Tiago Peixoto's avatar
Tiago Peixoto committed
70
71
    const Graph& OriginalGraph() const {return _g;}
    Graph& OriginalGraph() {return _g;}
72

Tiago Peixoto's avatar
Tiago Peixoto committed
73
74
75
76
77
78
private:
    Graph &_g;
};

#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
template<typename Graph>
79
80
struct vertex_bundle_type<UndirectedAdaptor<Graph> >:
        vertex_bundle_type<Graph> { };
Tiago Peixoto's avatar
Tiago Peixoto committed
81
82

template<typename Graph>
83
84
struct edge_bundle_type<UndirectedAdaptor<Graph> >:
        edge_bundle_type<Graph> { };
Tiago Peixoto's avatar
Tiago Peixoto committed
85
86
87
88
89
90
#endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES


//==============================================================================
// UndirectedAdaptor::EdgeDescriptor
//==============================================================================
91
92
93
template <class Graph>
class UndirectedAdaptor<Graph>::EdgeDescriptor:
        public graph_traits<Graph>::edge_descriptor
Tiago Peixoto's avatar
Tiago Peixoto committed
94
95
96
97
98
{
public:
    typedef typename graph_traits<Graph>::edge_descriptor original_edge_t;
    EdgeDescriptor(){}
    EdgeDescriptor(original_edge_t e): original_edge_t(e), _inverted(false) {}
99
100
101
    EdgeDescriptor(const original_edge_t &e,  bool inverted):
        original_edge_t(e), _inverted(inverted) {}

Tiago Peixoto's avatar
Tiago Peixoto committed
102
    bool IsInverted() const {return _inverted;}
103

104
105
106
107
    bool operator==(const EdgeDescriptor& e) const
    {
        return original_edge_t(e) == original_edge_t(*this);
    }
108

Tiago Peixoto's avatar
Tiago Peixoto committed
109
110
111
112
113
114
115
private:
    bool _inverted;
};

//==============================================================================
// UndirectedAdaptorEdgeIterator
//==============================================================================
116
template <typename Graph>
Tiago Peixoto's avatar
Tiago Peixoto committed
117
118
class UndirectedAdaptorEdgeIterator
    : public iterator<std::bidirectional_iterator_tag,
119
120
                      typename UndirectedAdaptor<Graph>::EdgeDescriptor,
                      std::ptrdiff_t,
121
122
123
                      typename UndirectedAdaptor<Graph>::EdgeDescriptor*,
                      typename UndirectedAdaptor<Graph>::EdgeDescriptor>
                      // not a reference!
Tiago Peixoto's avatar
Tiago Peixoto committed
124
125
126
{
public:
    UndirectedAdaptorEdgeIterator() {}
127
128
    explicit UndirectedAdaptorEdgeIterator
        (typename graph_traits<Graph>::edge_iterator &iter):_iter(iter){}
Tiago Peixoto's avatar
Tiago Peixoto committed
129
130
    typename UndirectedAdaptor<Graph>::EdgeDescriptor operator*() const
    {
131
132
133
134
        return (typename UndirectedAdaptor<Graph>::EdgeDescriptor(*_iter,
                                                                  false));
    }

Tiago Peixoto's avatar
Tiago Peixoto committed
135
//    pointer operator->() const {return **this;}
136
137
138

    UndirectedAdaptorEdgeIterator& operator++()
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
139
140
141
142
        ++_iter;
        return *this;
    }

143
144
    UndirectedAdaptorEdgeIterator operator++(int)
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
145
146
147
148
        UndirectedAdaptorEdgeIterator t = *this;
        ++_iter;
        return t;
    }
149

Tiago Peixoto's avatar
Tiago Peixoto committed
150
151
    UndirectedAdaptorEdgeIterator& operator--()
    {
152
        --_iter;
Tiago Peixoto's avatar
Tiago Peixoto committed
153
154
155
156
157
158
        return *this;
    }

    UndirectedAdaptorEdgeIterator operator--(int)
    {
        UndirectedAdaptorEdgeIterator t = *this;
159
        --_iter;
Tiago Peixoto's avatar
Tiago Peixoto committed
160
161
162
163
164
165
166
167
168
169
170
171
        return t;
    }

    bool operator==(UndirectedAdaptorEdgeIterator iter) const
    {
        return (_iter == iter._iter);
    }

    bool operator!=(UndirectedAdaptorEdgeIterator iter) const
    {
        return (_iter != iter._iter);
    }
172

Tiago Peixoto's avatar
Tiago Peixoto committed
173
174
175
176
177
178
179
180

private:
    typename graph_traits<Graph>::edge_iterator _iter;
};

//==============================================================================
// UndirectedAdaptorOutEdgeIterator
// this will iterate through both in_edges and out_edges of the underlying graph
181
182
183
//==============================================================================
template <typename Graph>
class UndirectedAdaptorOutEdgeIterator
Tiago Peixoto's avatar
Tiago Peixoto committed
184
    : public iterator<std::bidirectional_iterator_tag,
185
186
                      typename UndirectedAdaptor<Graph>::EdgeDescriptor,
                      std::ptrdiff_t,
187
188
189
                      typename UndirectedAdaptor<Graph>::EdgeDescriptor*,
                      typename UndirectedAdaptor<Graph>::EdgeDescriptor>
                      //not a reference
Tiago Peixoto's avatar
Tiago Peixoto committed
190
191
192
{
public:
    UndirectedAdaptorOutEdgeIterator() {};
193
194
195
196
197
198
199
200
201
    UndirectedAdaptorOutEdgeIterator
        (typename graph_traits<Graph>::out_edge_iterator out_iter,
         typename graph_traits<Graph>::in_edge_iterator in_iter,
         const std::pair<typename graph_traits<Graph>::out_edge_iterator,
         typename graph_traits<Graph>::out_edge_iterator> out_range,
         const std::pair<typename graph_traits<Graph>::in_edge_iterator,
         typename graph_traits<Graph>::in_edge_iterator> in_range)
            : _out_range(out_range), _in_range(in_range),
              _out_iter(out_iter), _in_iter(in_iter) {};
Tiago Peixoto's avatar
Tiago Peixoto committed
202
203
204
205

    typename UndirectedAdaptor<Graph>::EdgeDescriptor operator*() const
    {
        if ( _out_iter != _out_range.second )
206
207
            return (typename UndirectedAdaptor<Graph>::EdgeDescriptor
                    (*_out_iter,false));
Tiago Peixoto's avatar
Tiago Peixoto committed
208
        else
209
210
211
212
            return (typename UndirectedAdaptor<Graph>::EdgeDescriptor
                    (*_in_iter, true));
    }

Tiago Peixoto's avatar
Tiago Peixoto committed
213
//    pointer operator->() const {return **this;}
214
215
216
217

    UndirectedAdaptorOutEdgeIterator& operator++()
    {
        if (_out_iter != _out_range.second)
Tiago Peixoto's avatar
Tiago Peixoto committed
218
219
220
221
222
223
            ++_out_iter;
        else
            ++_in_iter;
        return *this;
    }

224
225
    UndirectedAdaptorOutEdgeIterator operator++(int)
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
226
        UndirectedAdaptorOutEdgeIterator t = *this;
227
        if (_out_iter != _out_range.second)
Tiago Peixoto's avatar
Tiago Peixoto committed
228
229
230
231
232
            ++_out_iter;
        else
            ++_in_iter;
        return t;
    }
233

Tiago Peixoto's avatar
Tiago Peixoto committed
234
235
    UndirectedAdaptorOutEdgeIterator& operator--()
    {
236
        if (_in_iter == _in_range.first)
Tiago Peixoto's avatar
Tiago Peixoto committed
237
238
239
           --_out_iter;
        else
           --_in_iter;
240

Tiago Peixoto's avatar
Tiago Peixoto committed
241
242
243
244
245
246
        return *this;
    }

    UndirectedAdaptorOutEdgeIterator operator--(int)
    {
        UndirectedAdaptorOutEdgeIterator t = *this;
247
        if (_in_iter == _in_range.first)
Tiago Peixoto's avatar
Tiago Peixoto committed
248
249
250
           --_out_iter;
        else
           --_in_iter;
251

Tiago Peixoto's avatar
Tiago Peixoto committed
252
253
        return t;
    }
254

Tiago Peixoto's avatar
Tiago Peixoto committed
255
256
257
258
    bool operator==(UndirectedAdaptorOutEdgeIterator iter) const
    {
        return (_out_iter == iter._out_iter &&  _in_iter == iter._in_iter);
    }
259

Tiago Peixoto's avatar
Tiago Peixoto committed
260
261
262
263
    bool operator!=(UndirectedAdaptorOutEdgeIterator iter) const
    {
        return !(*this == iter);
    }
264

Tiago Peixoto's avatar
Tiago Peixoto committed
265
protected:
266
267
268
269
    std::pair<typename graph_traits<Graph>::out_edge_iterator,
              typename graph_traits<Graph>::out_edge_iterator> _out_range;
    std::pair<typename graph_traits<Graph>::in_edge_iterator,
              typename graph_traits<Graph>::in_edge_iterator> _in_range;
Tiago Peixoto's avatar
Tiago Peixoto committed
270
271
272
273
274
275
276
277
278
    typename graph_traits<Graph>::out_edge_iterator _out_iter;
    typename graph_traits<Graph>::in_edge_iterator _in_iter;
};

//==============================================================================
// UndirectedAdaptorAdjacencyIterator
// just keeps an internal reference to out_edge_iterator and calls target() when
// referenced
//==============================================================================
279
280
281
282
283
284
285
286
287
template <typename Graph>
class UndirectedAdaptorAdjacencyIterator
    : public iterator
        <std::bidirectional_iterator_tag,
         typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor,
         std::ptrdiff_t,
         typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor*,
         typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor>
         //not a reference
Tiago Peixoto's avatar
Tiago Peixoto committed
288
289
290
{
public:
    UndirectedAdaptorAdjacencyIterator(){};
291
292
293
294
295
    UndirectedAdaptorAdjacencyIterator
        (UndirectedAdaptorOutEdgeIterator<Graph> iter,
         const UndirectedAdaptor<Graph> &g)
            :_iter(iter), _g(&g) {}

Tiago Peixoto's avatar
Tiago Peixoto committed
296
297
298
    typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor operator*() const
    {
        return target(*_iter,*_g);
299
300
    }

Tiago Peixoto's avatar
Tiago Peixoto committed
301
//    pointer operator->() const {return **this;}
302
303
304

    UndirectedAdaptorAdjacencyIterator& operator++()
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
305
306
307
308
        ++_iter;
        return *this;
    }

309
310
    UndirectedAdaptorAdjacencyIterator operator++(int)
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
311
312
313
314
        UndirectedAdaptorAdjacencyIterator t = *this;
        ++_iter;
        return t;
    }
315

Tiago Peixoto's avatar
Tiago Peixoto committed
316
317
    UndirectedAdaptorAdjacencyIterator& operator--()
    {
318
        --_iter;
Tiago Peixoto's avatar
Tiago Peixoto committed
319
320
321
322
323
324
        return *this;
    }

    UndirectedAdaptorAdjacencyIterator operator--(int)
    {
        UndirectedAdaptorAdjacencyIterator t = *this;
325
        --_iter;
Tiago Peixoto's avatar
Tiago Peixoto committed
326
327
        return t;
    }
328

Tiago Peixoto's avatar
Tiago Peixoto committed
329
330
331
332
    bool operator==(UndirectedAdaptorAdjacencyIterator iter) const
    {
        return (iter._iter == _iter);
    }
333

Tiago Peixoto's avatar
Tiago Peixoto committed
334
335
336
337
    bool operator!=(UndirectedAdaptorAdjacencyIterator iter) const
    {
        return (iter._iter != _iter);
    }
338

Tiago Peixoto's avatar
Tiago Peixoto committed
339
340
341
342
343
344
345
346
private:
    UndirectedAdaptorOutEdgeIterator<Graph> _iter;
    UndirectedAdaptor<Graph> const * _g;
};

//==============================================================================
// undirected_adaptor_traversal_category
//==============================================================================
347
struct undirected_adaptor_traversal_category :
Tiago Peixoto's avatar
Tiago Peixoto committed
348
349
350
351
352
353
354
355
356
357
358
    public virtual bidirectional_graph_tag,
    public virtual adjacency_graph_tag,
    public virtual vertex_list_graph_tag,
    public virtual edge_list_graph_tag { };


//==============================================================================
// graph_traits<UndirectedAdaptor>
// this defines all the necessary types associated with UndirectedAdaptor
//==============================================================================
template <class Graph>
359
struct graph_traits<UndirectedAdaptor<Graph> > {
Tiago Peixoto's avatar
Tiago Peixoto committed
360
361
362
363
364
    typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
    typedef typename UndirectedAdaptor<Graph>::EdgeDescriptor edge_descriptor;

    typedef UndirectedAdaptorAdjacencyIterator<Graph> adjacency_iterator;
    typedef UndirectedAdaptorOutEdgeIterator<Graph> out_edge_iterator;
365
    typedef typename graph_traits<Graph>::in_edge_iterator in_edge_iterator;
Tiago Peixoto's avatar
Tiago Peixoto committed
366
367
    typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
    typedef UndirectedAdaptorEdgeIterator<Graph> edge_iterator;
368

Tiago Peixoto's avatar
Tiago Peixoto committed
369
    typedef undirected_tag directed_category;
370
    typedef allow_parallel_edge_tag edge_parallel_category;
Tiago Peixoto's avatar
Tiago Peixoto committed
371
372
373
374
    typedef undirected_adaptor_traversal_category traversal_category;
    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;
375
376
377
378
379

    static vertex_descriptor null_vertex()
    {
        return graph_traits<Graph>::null_vertex();
    }
Tiago Peixoto's avatar
Tiago Peixoto committed
380
381
};

382
template <class Graph>
383
384
struct graph_traits< const UndirectedAdaptor<Graph> >:
    public graph_traits<UndirectedAdaptor<Graph> > {};
385

Tiago Peixoto's avatar
Tiago Peixoto committed
386
387
//==============================================================================
// Nonmember functions
388
// these provide manipulation of the graph
Tiago Peixoto's avatar
Tiago Peixoto committed
389
390
391
392
393
394
//==============================================================================

//==============================================================================
// source(e,g)
//==============================================================================
template <class Graph>
395
396
397
inline typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor
source(typename graph_traits<UndirectedAdaptor<Graph> >::edge_descriptor e,
       const UndirectedAdaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
398
399
400
401
402
403
404
405
406
407
408
409
{
    typedef typename graph_traits<Graph>::edge_descriptor original_edge_t;
    if (e.IsInverted())
        return target(original_edge_t(e), g.OriginalGraph());
    else
        return source(original_edge_t(e), g.OriginalGraph());
}

//==============================================================================
// target(e,g)
//==============================================================================
template <class Graph>
410
411
412
inline typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor
target(typename graph_traits<UndirectedAdaptor<Graph> >::edge_descriptor e,
       const UndirectedAdaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
413
414
415
416
417
418
419
420
421
422
423
424
{
    typedef typename graph_traits<Graph>::edge_descriptor original_edge_t;
    if (e.IsInverted())
        return source(original_edge_t(e), g.OriginalGraph());
    else
        return target(original_edge_t(e), g.OriginalGraph());
}

//==============================================================================
// vertex(n,g)
//==============================================================================
template <class Graph>
425
426
427
inline typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor
vertex(typename graph_traits<UndirectedAdaptor<Graph> >::vertices_size_type n,
       const UndirectedAdaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
428
429
430
431
432
433
434
435
{
    return vertex(n, g.OriginalGraph());
}

//==============================================================================
// vertices(g)
//==============================================================================
template <class Graph>
436
437
438
inline
std::pair<typename graph_traits<UndirectedAdaptor<Graph> >::vertex_iterator,
          typename graph_traits<UndirectedAdaptor<Graph> >::vertex_iterator >
Tiago Peixoto's avatar
Tiago Peixoto committed
439
440
441
442
443
444
445
446
447
vertices(const UndirectedAdaptor<Graph>& g)
{
    return vertices(g.OriginalGraph());
}

//==============================================================================
// edges(g)
//==============================================================================
template <class Graph>
448
449
450
inline
std::pair<typename graph_traits<UndirectedAdaptor<Graph> >::edge_iterator,
          typename graph_traits<UndirectedAdaptor<Graph> >::edge_iterator >
Tiago Peixoto's avatar
Tiago Peixoto committed
451
452
edges(const UndirectedAdaptor<Graph>& g)
{
453
454
    std::pair<typename graph_traits<Graph>::edge_iterator,
              typename graph_traits<Graph>::edge_iterator> range;
Tiago Peixoto's avatar
Tiago Peixoto committed
455
    range = edges(g.OriginalGraph());
456
457
    return make_pair(UndirectedAdaptorEdgeIterator<Graph>(range.first),
                     UndirectedAdaptorEdgeIterator<Graph>(range.second));
Tiago Peixoto's avatar
Tiago Peixoto committed
458
459
460
461
462
463
}

//==============================================================================
// out_edges(u,g)
//==============================================================================
template <class Graph>
464
465
466
467
468
469
470
471
472
473
474
475
inline
std::pair<typename graph_traits<UndirectedAdaptor<Graph> >::out_edge_iterator,
          typename graph_traits<UndirectedAdaptor<Graph> >::out_edge_iterator >
out_edges(typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor u,
          const UndirectedAdaptor<Graph>& g)
{
    std::pair<typename graph_traits<Graph>::out_edge_iterator,
              typename graph_traits<Graph>::out_edge_iterator> out_range;
    std::pair<typename graph_traits<Graph>::in_edge_iterator,
              typename graph_traits<Graph>::in_edge_iterator> in_range;

    out_range = out_edges(u, g.OriginalGraph());
Tiago Peixoto's avatar
Tiago Peixoto committed
476
    in_range = in_edges(u, g.OriginalGraph());
477
478
479
480
481
482
483
484
485

    typedef typename graph_traits<UndirectedAdaptor<Graph> >::out_edge_iterator
        OutIter;

    OutIter iter_begin = OutIter(out_range.first, in_range.first, out_range,
                                 in_range);
    OutIter iter_end   = OutIter(out_range.second, in_range.second, out_range,
                                 in_range);

Tiago Peixoto's avatar
Tiago Peixoto committed
486
487
488
489
490
491
492
    return std::make_pair(iter_begin, iter_end);
}

//==============================================================================
// adjacent_vertices(u,g)
//==============================================================================
template <class Graph>
493
494
495
496
497
498
499
500
501
502
503
504
inline
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)
{
    typedef typename graph_traits<UndirectedAdaptor<Graph> >::out_edge_iterator
        edge_iter_t;
    typedef typename graph_traits<UndirectedAdaptor<Graph> >::adjacency_iterator
        adj_iter_t;

Tiago Peixoto's avatar
Tiago Peixoto committed
505
506
    std::pair<edge_iter_t, edge_iter_t> edge_range;
    edge_range = out_edges(u,g);
507
508
509

    return std::make_pair(adj_iter_t(edge_range.first, g),
                          adj_iter_t(edge_range.second, g));
Tiago Peixoto's avatar
Tiago Peixoto committed
510
511
512
513
514
515
}

//==============================================================================
// num_vertices(g)
//==============================================================================
template <class Graph>
516
inline typename graph_traits<UndirectedAdaptor<Graph> >::vertices_size_type
Tiago Peixoto's avatar
Tiago Peixoto committed
517
518
519
num_vertices(const UndirectedAdaptor<Graph>& g)
{
    return num_vertices(g.OriginalGraph());
520
}
Tiago Peixoto's avatar
Tiago Peixoto committed
521
522
523
524
525

//==============================================================================
// num_edges(g)
//==============================================================================
template <class Graph>
526
inline typename graph_traits<UndirectedAdaptor<Graph> >::edges_size_type
Tiago Peixoto's avatar
Tiago Peixoto committed
527
528
529
num_edges(const UndirectedAdaptor<Graph>& g)
{
    return num_edges(g.OriginalGraph());
530
}
Tiago Peixoto's avatar
Tiago Peixoto committed
531
532
533
534
535

//==============================================================================
// out_degree(u,g)
//==============================================================================
template <class Graph>
536
537
538
539
inline 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
540
541
542
543
544
545
546
547
{
    return (out_degree(u, g.OriginalGraph())+in_degree(u,g.OriginalGraph()));
}

//==============================================================================
// degree(u,g)
//==============================================================================
template <class Graph>
548
549
550
inline typename graph_traits<UndirectedAdaptor<Graph> >::degree_size_type
degree(typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor u,
       const UndirectedAdaptor<Graph> &g)
Tiago Peixoto's avatar
Tiago Peixoto committed
551
552
553
554
555
556
557
558
{
    return out_degree(u, g);
}


//==============================================================================
// add_vertex(g)
//==============================================================================
559
560
template <class Graph>
inline typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor
Tiago Peixoto's avatar
Tiago Peixoto committed
561
562
563
564
565
566
567
568
569
add_vertex(UndirectedAdaptor<Graph>& g)
{
    return add_vertex(g.OriginalGraph());
}

//==============================================================================
// add_vertex(vp,g)
//==============================================================================
template <class Graph, class VertexProperties>
570
inline typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor
Tiago Peixoto's avatar
Tiago Peixoto committed
571
572
573
574
575
576
577
578
579
add_vertex(const VertexProperties &p, UndirectedAdaptor<Graph>& g)
{
    return add_vertex(p, g.OriginalGraph());
}

//==============================================================================
// clear_vertex(u,g)
//==============================================================================
template <class Graph>
580
581
582
inline void clear_vertex
    (typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor u,
     UndirectedAdaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
583
584
585
586
587
588
589
590
{
    clear_vertex(u, g.OriginalGraph());
}

//==============================================================================
// remove_vertex(u,g)
//==============================================================================
template <class Graph>
591
592
593
inline void remove_vertex
    (typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor u,
     UndirectedAdaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
594
595
596
597
598
599
600
601
{
    remove_vertex(u, g.OriginalGraph());
}

//==============================================================================
// add_edge(u,v,g)
//==============================================================================
template <class Graph>
602
603
604
605
606
607
608
609
610
611
612
613
614
inline
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)
{
    std::pair<typename graph_traits<Graph>::edge_descriptor, bool> retval =
        add_edge(u,v,g.OriginalGraph());
    return std::make_pair
        (typename graph_traits<UndirectedAdaptor<Graph> >::edge_descriptor
         (retval.first,false),
         retval.second);
Tiago Peixoto's avatar
Tiago Peixoto committed
615
616
617
618
619
620
}

//==============================================================================
// add_edge(u,v,ep,g)
//==============================================================================
template <class Graph, class EdgeProperties>
621
622
623
624
625
626
627
628
629
630
631
632
633
inline
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)
{
    std::pair<typename graph_traits<Graph>::edge_descriptor, bool> retval =
        add_edge(u,v,ep,g.OriginalGraph());
    return std::make_pair
        (typename graph_traits<UndirectedAdaptor<Graph> >::edge_descriptor
         (retval.first,false),
         retval.second);
Tiago Peixoto's avatar
Tiago Peixoto committed
634
635
636
637
638
639
}

//==============================================================================
// remove_edge(u,v,g)
//==============================================================================
template <class Graph>
640
641
642
643
inline 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
644
645
646
647
648
649
650
651
652
{
    remove_edge(u,v,g.OriginalGraph());
    remove_edge(v,u,g.OriginalGraph());
}

//==============================================================================
// remove_edge(e,g)
//==============================================================================
template <class Graph>
653
654
655
inline void remove_edge
    (typename graph_traits<UndirectedAdaptor<Graph> >::edge_descriptor e,
     UndirectedAdaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
656
{
657
658
    remove_edge(typename graph_traits<Graph>::edge_descriptor(e),
                g.OriginalGraph());
Tiago Peixoto's avatar
Tiago Peixoto committed
659
660
661
662
663
664
}

//==============================================================================
// remove_edge(e_iter,g)
//==============================================================================
template <class Graph>
665
666
667
inline void remove_edge
    (typename graph_traits<UndirectedAdaptor<Graph> >::out_edge_iterator iter,
     UndirectedAdaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
668
669
670
671
672
673
674
675
{
    remove_edge(*iter, g);
}

//==============================================================================
// remove_out_edge_if(v,predicate,g)
//==============================================================================
template <class Graph, class Predicate>
676
677
678
inline 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
679
680
{
    std::list<typename UndirectedAdaptor<Graph>::EdgeDescriptor> removed_edges;
681
682
683
    typedef typename graph_traits<UndirectedAdaptor<Graph> >::out_edge_iterator
        iter_t;
    std::pair<iter_t, iter_t> edge_range;
Tiago Peixoto's avatar
Tiago Peixoto committed
684
685
686
687
    edge_range = out_edges(v,g);
    for(iter_t iter = edge_range.first; iter != edge_range.second; ++iter)
        if (predicate(*iter))
            removed_edges.push_front(*iter);
688

Tiago Peixoto's avatar
Tiago Peixoto committed
689
690
691
692
693
694
695
    for(typeof(removed_edges.begin()) iter = removed_edges.begin();
        iter != removed_edges.end(); ++iter)
        remove_edge(*iter,g);
}


//==============================================================================
696
// Property maps
Tiago Peixoto's avatar
Tiago Peixoto committed
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
741
742
743
744
745
746
//==============================================================================

//==============================================================================
// 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;
747
748
    typedef typename property_map<const Graph, PropertyTag>::const_type
        const_type;
Tiago Peixoto's avatar
Tiago Peixoto committed
749
750
751
752
753
754
755
    //typedef typename property_map<Graph, PropertyTag>::const_type const type;
};

//==============================================================================
// property_map<UndirectedAdaptor, T Bundle::*>
//==============================================================================
template <typename Graph, typename T, typename Bundle>
756
class property_map<UndirectedAdaptor<Graph>, T Bundle::*>
Tiago Peixoto's avatar
Tiago Peixoto committed
757
758
759
760
761
762
763
764
765
766
767
{
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>
768
inline typename property_map<UndirectedAdaptor<Graph>, PropertyTag>::type
Tiago Peixoto's avatar
Tiago Peixoto committed
769
770
771
772
773
774
get(PropertyTag tag, UndirectedAdaptor<Graph> &g)
{
    return get(tag, g.OriginalGraph());
}

//==============================================================================
775
// const get(tag,g)
Tiago Peixoto's avatar
Tiago Peixoto committed
776
777
//==============================================================================
template <class PropertyTag, class Graph>
778
inline typename property_map<UndirectedAdaptor<Graph>, PropertyTag>::const_type
Tiago Peixoto's avatar
Tiago Peixoto committed
779
780
781
782
783
784
785
786
787
get(PropertyTag tag, const UndirectedAdaptor<Graph> &g)
{
    return get(tag, g.OriginalGraph());
}

//==============================================================================
// get(tag,g,v)
//==============================================================================
template <class PropertyTag, class Graph>
788
789
790
791
792
793
inline
typename property_traits
    <typename property_map<UndirectedAdaptor<Graph>,
                           PropertyTag>::const_type >::value_type
get(PropertyTag tag, const UndirectedAdaptor<Graph> &g,
    typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor v)
Tiago Peixoto's avatar
Tiago Peixoto committed
794
795
796
797
798
799
800
801
{
    return get(tag, g.OriginalGraph(), v);
}

//==============================================================================
// get(tag,g,e)
//==============================================================================
template <class PropertyTag, class Graph>
802
803
804
805
806
807
inline
typename property_traits
    <typename property_map<UndirectedAdaptor<Graph>,
                           PropertyTag>::const_type >::value_type
get(PropertyTag tag, const UndirectedAdaptor<Graph> &g,
    typename graph_traits<UndirectedAdaptor<Graph> >::edge_descriptor e)
Tiago Peixoto's avatar
Tiago Peixoto committed
808
809
810
811
812
813
814
815
{
    return get(tag, g.OriginalGraph(), e.OriginalEdge());
}

//==============================================================================
// put(tag, g, v, value)
//==============================================================================
template <class Graph, class PropertyTag, class Value>
816
817
818
819
inline
void put(PropertyTag tag, UndirectedAdaptor<Graph> &g,
         typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor v,
         const Value &value)
Tiago Peixoto's avatar
Tiago Peixoto committed
820
821
822
823
824
825
826
827
{
    put(tag, g.OriginalGraph(), v, value);
}

//==============================================================================
// put(tag, g, e, value)
//==============================================================================
template <class Graph, class PropertyTag, class X, class Value>
828
829
830
831
inline
void put(PropertyTag tag, const UndirectedAdaptor<Graph> &g,
         typename graph_traits<UndirectedAdaptor<Graph> >::edge_descriptor e,
         const Value &value)
Tiago Peixoto's avatar
Tiago Peixoto committed
832
833
834
835
836
837
838
839
{
    put(tag, g.OriginalGraph(), e.OriginalEdge(), value);
}

//==============================================================================
// get_property(g,tag)
//==============================================================================
template <class Graph, class GraphProperties, class GraphPropertyTag>
840
inline
Tiago Peixoto's avatar
Tiago Peixoto committed
841
842
843
844
845
846
847
848
849
850
typename property_value<GraphProperties, GraphPropertyTag>::type&
get_property(UndirectedAdaptor<Graph> &g, GraphPropertyTag tag)
{
    get_property(g.OriginalGraph(), tag);
}

//==============================================================================
// const get_property(g,tag)
//==============================================================================
template <class Graph, class GraphProperties, class GraphPropertyTag>
851
inline
Tiago Peixoto's avatar
Tiago Peixoto committed
852
853
854
855
856
857
858
859
860
861
const typename property_value<GraphProperties, GraphPropertyTag>::type&
get_property(const UndirectedAdaptor<Graph> &g, GraphPropertyTag tag)
{
    get_property(g.OriginalGraph(), tag);
}

} // namespace boost


#endif // GRAPH_ADAPTOR_HH