graph_adaptor.hh 31 KB
Newer Older
Tiago Peixoto's avatar
Tiago Peixoto committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// graph-tool -- a general graph modification and manipulation thingy
//
// Copyright (C) 2006  Tiago de Paula Peixoto <tiago@forked.de>
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// 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
// along with this program; if not, write to the Free Software
// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.

#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>

//==============================================================================
// The functions and classes in this file allow the user to
// treat a directed graph with parallel edges as an undirected graph with 
// parallel edges (UndirectedAdaptor), and a graph with parallel edges as a 
// graph without parallel edges (ParallelFilter).
//==============================================================================

namespace boost {

//==============================================================================
// UndirectedAdaptor
// This class encapsulates a directed graph with parallel edges and provides a 
// view of the graph as undirected with parallel edges.
// Encapsulated graph must be: VertexListGraph, EdgeListGraph, IncidenceGraph, 
//                             AdjacencyGraph, VertexMutableGraph, 
//                             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)){}

52
53
54
55
56
    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;
    typedef typename Graph::graph_type graph_type;

Tiago Peixoto's avatar
Tiago Peixoto committed
57
58
    class EdgeDescriptor;
    typedef Graph original_graph_t;
59
60
61
62

    typedef typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor vertex_descriptor;
    typedef typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor edge_descriptor;

Tiago Peixoto's avatar
Tiago Peixoto committed
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
    
#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
    // Bundled properties support
    template<typename Descriptor>
    typename graph::detail::bundled_result<Graph, Descriptor>::type& operator[](Descriptor x) { return this->m_g[x]; }

    template<typename Descriptor>
    typename graph::detail::bundled_result<Graph, Descriptor>::type const& operator[](Descriptor x) const { return this->m_g[x]; }
#endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES
    
    
    const Graph& OriginalGraph() const {return _g;}
    Graph& OriginalGraph() {return _g;}
    
private:
    Graph &_g;
};

#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
template<typename Graph>
struct vertex_bundle_type<UndirectedAdaptor<Graph> > : vertex_bundle_type<Graph> { };

template<typename Graph>
struct edge_bundle_type<UndirectedAdaptor<Graph> > : edge_bundle_type<Graph> { };
#endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES


//==============================================================================
// UndirectedAdaptor::EdgeDescriptor
//==============================================================================
template <class Graph> 
class UndirectedAdaptor<Graph>::EdgeDescriptor: public graph_traits<Graph>::edge_descriptor
{
public:
    typedef typename graph_traits<Graph>::edge_descriptor original_edge_t;
    EdgeDescriptor(){}
    EdgeDescriptor(original_edge_t e): original_edge_t(e), _inverted(false) {}
    EdgeDescriptor(const original_edge_t &e,  bool inverted): original_edge_t(e), _inverted(inverted) {}
    
    bool IsInverted() const {return _inverted;}
        
private:
    bool _inverted;
};

//==============================================================================
// UndirectedAdaptorEdgeIterator
//==============================================================================
template <typename Graph> 
class UndirectedAdaptorEdgeIterator
    : public iterator<std::bidirectional_iterator_tag,
114
115
116
117
                      typename UndirectedAdaptor<Graph>::EdgeDescriptor,
                      std::ptrdiff_t,
                      typename UndirectedAdaptor<Graph>::EdgeDescriptor*, 
                      typename UndirectedAdaptor<Graph>::EdgeDescriptor>  //not a reference!
Tiago Peixoto's avatar
Tiago Peixoto committed
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
{
public:
    UndirectedAdaptorEdgeIterator() {}
    explicit UndirectedAdaptorEdgeIterator(typename graph_traits<Graph>::edge_iterator &iter):_iter(iter){}
    typename UndirectedAdaptor<Graph>::EdgeDescriptor operator*() const
    {
        return (typename UndirectedAdaptor<Graph>::EdgeDescriptor(*_iter, false));
    }     
    
//    pointer operator->() const {return **this;}
         
    UndirectedAdaptorEdgeIterator& operator++() 
    { 
        ++_iter;
        return *this;
    }

    UndirectedAdaptorEdgeIterator operator++(int) 
    { 
        UndirectedAdaptorEdgeIterator t = *this;
        ++_iter;
        return t;
    }
                
    UndirectedAdaptorEdgeIterator& operator--()
    {
        --_iter;         
        return *this;
    }

    UndirectedAdaptorEdgeIterator operator--(int)
    {
        UndirectedAdaptorEdgeIterator t = *this;
        --_iter;                     
        return t;
    }

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

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

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

//==============================================================================
// UndirectedAdaptorOutEdgeIterator
// this will iterate through both in_edges and out_edges of the underlying graph
//==============================================================================  
template <typename Graph> 
class UndirectedAdaptorOutEdgeIterator 
    : public iterator<std::bidirectional_iterator_tag,
177
178
179
180
                      typename UndirectedAdaptor<Graph>::EdgeDescriptor,
                      std::ptrdiff_t,
                      typename UndirectedAdaptor<Graph>::EdgeDescriptor*, 
                      typename UndirectedAdaptor<Graph>::EdgeDescriptor> //not a reference 
Tiago Peixoto's avatar
Tiago Peixoto committed
181
182
183
184
{
public:
    UndirectedAdaptorOutEdgeIterator() {};
    UndirectedAdaptorOutEdgeIterator(typename graph_traits<Graph>::out_edge_iterator out_iter, 
185
186
187
188
189
                                     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)
Tiago Peixoto's avatar
Tiago Peixoto committed
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
    :_out_range(out_range), _in_range(in_range), _out_iter(out_iter), _in_iter(in_iter) {};                  

    typename UndirectedAdaptor<Graph>::EdgeDescriptor operator*() const
    {
        if ( _out_iter != _out_range.second )
            return (typename UndirectedAdaptor<Graph>::EdgeDescriptor(*_out_iter,false));
        else
            return (typename UndirectedAdaptor<Graph>::EdgeDescriptor(*_in_iter, true));        
    }     
    
//    pointer operator->() const {return **this;}
         
    UndirectedAdaptorOutEdgeIterator& operator++() 
    { 
        if (_out_iter != _out_range.second) 
            ++_out_iter;
        else
            ++_in_iter;
        return *this;
    }

    UndirectedAdaptorOutEdgeIterator operator++(int) 
    { 
        UndirectedAdaptorOutEdgeIterator t = *this;
        if (_out_iter != _out_range.second) 
            ++_out_iter;
        else
            ++_in_iter;
        return t;
    }
                
    UndirectedAdaptorOutEdgeIterator& operator--()
    {
        if (_in_iter == _in_range.first) 
           --_out_iter;
        else
           --_in_iter;
           
        return *this;
    }

    UndirectedAdaptorOutEdgeIterator operator--(int)
    {
        UndirectedAdaptorOutEdgeIterator t = *this;
        if (_in_iter == _in_range.first) 
           --_out_iter;
        else
           --_in_iter;
                     
        return t;
    }
  
    bool operator==(UndirectedAdaptorOutEdgeIterator iter) const
    {
        return (_out_iter == iter._out_iter &&  _in_iter == iter._in_iter);
    }
    
    bool operator!=(UndirectedAdaptorOutEdgeIterator iter) const
    {
        return !(*this == iter);
    }
    
protected:
    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;
    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
//==============================================================================
template <typename Graph> 
class UndirectedAdaptorAdjacencyIterator 
    : public iterator<std::bidirectional_iterator_tag,
267
268
269
270
                      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
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
{
public:
    UndirectedAdaptorAdjacencyIterator(){};
    UndirectedAdaptorAdjacencyIterator (UndirectedAdaptorOutEdgeIterator<Graph> iter, const UndirectedAdaptor<Graph> &g) 
    :_iter(iter), _g(&g) {}
    
    typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor operator*() const
    {
        return target(*_iter,*_g);
    }     
    
//    pointer operator->() const {return **this;}
         
    UndirectedAdaptorAdjacencyIterator& operator++() 
    { 
        ++_iter;
        return *this;
    }

    UndirectedAdaptorAdjacencyIterator operator++(int) 
    { 
        UndirectedAdaptorAdjacencyIterator t = *this;
        ++_iter;
        return t;
    }
                
    UndirectedAdaptorAdjacencyIterator& operator--()
    {
        --_iter;           
        return *this;
    }

    UndirectedAdaptorAdjacencyIterator operator--(int)
    {
        UndirectedAdaptorAdjacencyIterator t = *this;
        --_iter;                     
        return t;
    }
  
    bool operator==(UndirectedAdaptorAdjacencyIterator iter) const
    {
        return (iter._iter == _iter);
    }
    
    bool operator!=(UndirectedAdaptorAdjacencyIterator iter) const
    {
        return (iter._iter != _iter);
    }
    
private:
    UndirectedAdaptorOutEdgeIterator<Graph> _iter;
    UndirectedAdaptor<Graph> const * _g;
};

//==============================================================================
// undirected_adaptor_traversal_category
//==============================================================================
struct undirected_adaptor_traversal_category : 
    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>
struct graph_traits< UndirectedAdaptor<Graph> > {
    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;
346
    typedef typename graph_traits<Graph>::in_edge_iterator in_edge_iterator;
Tiago Peixoto's avatar
Tiago Peixoto committed
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
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
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
    typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
    typedef UndirectedAdaptorEdgeIterator<Graph> edge_iterator;
    
    typedef undirected_tag directed_category;
    typedef allow_parallel_edge_tag edge_parallel_category; 
    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;
    
    static vertex_descriptor null_vertex() {return graph_traits<Graph>::null_vertex();}
};

//==============================================================================
// Nonmember functions
// these provide manipulation to the graph
//==============================================================================

//==============================================================================
// source(e,g)
//==============================================================================
template <class Graph>
typename graph_traits< UndirectedAdaptor<Graph> >::vertex_descriptor
source(typename graph_traits< UndirectedAdaptor<Graph> >::edge_descriptor e, const UndirectedAdaptor<Graph>& g)
{
    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>
typename graph_traits< UndirectedAdaptor<Graph> >::vertex_descriptor
target(typename graph_traits< UndirectedAdaptor<Graph> >::edge_descriptor e, const UndirectedAdaptor<Graph>& g)
{
    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>
typename graph_traits< UndirectedAdaptor<Graph> >::vertex_descriptor
vertex(typename graph_traits< UndirectedAdaptor<Graph> >::vertices_size_type n, const UndirectedAdaptor<Graph>& g)
{
    return vertex(n, g.OriginalGraph());
}

//==============================================================================
// vertices(g)
//==============================================================================
template <class Graph>
inline std::pair<typename graph_traits< UndirectedAdaptor<Graph> >::vertex_iterator,typename graph_traits< UndirectedAdaptor<Graph> >::vertex_iterator >  
vertices(const UndirectedAdaptor<Graph>& g)
{
    return vertices(g.OriginalGraph());
}

//==============================================================================
// edges(g)
//==============================================================================
template <class Graph>
inline std::pair<typename graph_traits< UndirectedAdaptor<Graph> >::edge_iterator, typename graph_traits< UndirectedAdaptor<Graph> >::edge_iterator >  
edges(const UndirectedAdaptor<Graph>& g)
{
    std::pair<typename graph_traits<Graph>::edge_iterator, typename graph_traits<Graph>::edge_iterator> range;
    range = edges(g.OriginalGraph());
    return make_pair(UndirectedAdaptorEdgeIterator<Graph>(range.first), UndirectedAdaptorEdgeIterator<Graph>(range.second));
}

//==============================================================================
// out_edges(u,g)
//==============================================================================
template <class Graph>
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());          
    in_range = in_edges(u, g.OriginalGraph());
    
    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);
    
    return std::make_pair(iter_begin, iter_end);
}

//==============================================================================
// adjacent_vertices(u,g)
//==============================================================================
template <class Graph>
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;
    
    std::pair<edge_iter_t, edge_iter_t> edge_range;
    edge_range = out_edges(u,g);
        
    return std::make_pair(adj_iter_t(edge_range.first, g), adj_iter_t(edge_range.second, g));
}

//==============================================================================
// num_vertices(g)
//==============================================================================
template <class Graph>
typename graph_traits< UndirectedAdaptor<Graph> >::vertices_size_type
num_vertices(const UndirectedAdaptor<Graph>& g)
{
    return num_vertices(g.OriginalGraph());
}  

//==============================================================================
// num_edges(g)
//==============================================================================
template <class Graph>
typename graph_traits< UndirectedAdaptor<Graph> >::edges_size_type
num_edges(const UndirectedAdaptor<Graph>& g)
{
    return num_edges(g.OriginalGraph());
}  

//==============================================================================
// out_degree(u,g)
//==============================================================================
template <class Graph>
typename graph_traits< UndirectedAdaptor<Graph> >::degree_size_type
out_degree(typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor u, const UndirectedAdaptor<Graph> &g)
{
    return (out_degree(u, g.OriginalGraph())+in_degree(u,g.OriginalGraph()));
}

//==============================================================================
// degree(u,g)
//==============================================================================
template <class Graph>
typename graph_traits< UndirectedAdaptor<Graph> >::degree_size_type
degree(typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor u, const UndirectedAdaptor<Graph> &g)
{
    return out_degree(u, g);
}


//==============================================================================
// add_vertex(g)
//==============================================================================
template <class Graph>  
typename graph_traits< UndirectedAdaptor<Graph> >::vertex_descriptor
add_vertex(UndirectedAdaptor<Graph>& g)
{
    return add_vertex(g.OriginalGraph());
}

//==============================================================================
// add_vertex(vp,g)
//==============================================================================
template <class Graph, class VertexProperties>
typename graph_traits< UndirectedAdaptor<Graph> >::vertex_descriptor
add_vertex(const VertexProperties &p, UndirectedAdaptor<Graph>& g)
{
    return add_vertex(p, g.OriginalGraph());
}

//==============================================================================
// clear_vertex(u,g)
//==============================================================================
template <class Graph>
void clear_vertex(typename graph_traits< UndirectedAdaptor<Graph> >::vertex_descriptor u, UndirectedAdaptor<Graph>& g)
{
    clear_vertex(u, g.OriginalGraph());
}

//==============================================================================
// remove_vertex(u,g)
//==============================================================================
template <class Graph>
void remove_vertex(typename graph_traits< UndirectedAdaptor<Graph> >::vertex_descriptor u, UndirectedAdaptor<Graph>& g)
{
    remove_vertex(u, g.OriginalGraph());
}

//==============================================================================
// add_edge(u,v,g)
//==============================================================================
template <class Graph>
std::pair<typename graph_traits< UndirectedAdaptor<Graph> >::edge_descriptor,bool>
add_edge(typename graph_traits< UndirectedAdaptor<Graph> >::vertex_descriptor u,
547
         typename graph_traits< UndirectedAdaptor<Graph> >::vertex_descriptor v, UndirectedAdaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
548
549
550
551
552
553
554
555
556
557
558
{
    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);
}

//==============================================================================
// add_edge(u,v,ep,g)
//==============================================================================
template <class Graph, class EdgeProperties>
std::pair<typename graph_traits< UndirectedAdaptor<Graph> >::edge_descriptor,bool>
add_edge(typename graph_traits< UndirectedAdaptor<Graph> >::vertex_descriptor u, 
559
         typename graph_traits< UndirectedAdaptor<Graph> >::vertex_descriptor v, const EdgeProperties& ep, UndirectedAdaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
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
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
{
    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);   
}

//==============================================================================
// remove_edge(u,v,g)
//==============================================================================
template <class Graph>
void remove_edge(typename graph_traits< UndirectedAdaptor<Graph> >::vertex_descriptor u,
                 typename graph_traits< UndirectedAdaptor<Graph> >::vertex_descriptor v,
                 UndirectedAdaptor<Graph>& g)
{
    remove_edge(u,v,g.OriginalGraph());
    remove_edge(v,u,g.OriginalGraph());
}

//==============================================================================
// remove_edge(e,g)
//==============================================================================
template <class Graph>
void remove_edge(typename graph_traits< UndirectedAdaptor<Graph> >::edge_descriptor e, UndirectedAdaptor<Graph>& g)
{
    remove_edge(typename graph_traits<Graph>::edge_descriptor(e), g.OriginalGraph());
}

//==============================================================================
// remove_edge(e_iter,g)
//==============================================================================
template <class Graph>
void remove_edge(typename graph_traits< UndirectedAdaptor<Graph> >::out_edge_iterator iter, UndirectedAdaptor<Graph>& g)
{
    remove_edge(*iter, g);
}

//==============================================================================
// remove_out_edge_if(v,predicate,g)
//==============================================================================
template <class Graph, class Predicate>
void remove_out_edge_if(typename graph_traits< UndirectedAdaptor<Graph> >::vertex_descriptor v, Predicate predicate, UndirectedAdaptor<Graph>& g)
{
    std::list<typename UndirectedAdaptor<Graph>::EdgeDescriptor> removed_edges;
    typedef typename graph_traits< UndirectedAdaptor<Graph> >::out_edge_iterator iter_t;
    std::pair<iter_t, iter_t> edge_range;              
    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);
    
    for(typeof(removed_edges.begin()) iter = removed_edges.begin();
        iter != removed_edges.end(); ++iter)
        remove_edge(*iter,g);
}


//==============================================================================
// property maps
//==============================================================================

//==============================================================================
// 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;
    typedef typename property_map<const Graph, PropertyTag>::const_type const_type;
    //typedef typename property_map<Graph, PropertyTag>::const_type const type;
};

//==============================================================================
// property_map<UndirectedAdaptor, T Bundle::*>
//==============================================================================
template <typename Graph, typename T, typename Bundle>
class property_map<UndirectedAdaptor<Graph>, T Bundle::*>  
{
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>
typename property_map<UndirectedAdaptor<Graph>, PropertyTag>::type
get(PropertyTag tag, UndirectedAdaptor<Graph> &g)
{
    return get(tag, g.OriginalGraph());
}

//==============================================================================
// const get(tag,g) 
//==============================================================================
template <class PropertyTag, class Graph>
typename property_map<UndirectedAdaptor<Graph>, PropertyTag>::const_type
get(PropertyTag tag, const UndirectedAdaptor<Graph> &g)
{
    return get(tag, g.OriginalGraph());
}

//==============================================================================
// get(tag,g,v)
//==============================================================================
template <class PropertyTag, class Graph>
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)
{
    return get(tag, g.OriginalGraph(), v);
}

//==============================================================================
// get(tag,g,e)
//==============================================================================
template <class PropertyTag, class Graph>
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)
{
    return get(tag, g.OriginalGraph(), e.OriginalEdge());
}

//==============================================================================
// put(tag, g, v, value)
//==============================================================================
template <class Graph, class PropertyTag, class Value>
void put(PropertyTag tag, UndirectedAdaptor<Graph> &g, typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor v, const Value &value)
{
    put(tag, g.OriginalGraph(), v, value);
}

//==============================================================================
// put(tag, g, e, value)
//==============================================================================
template <class Graph, class PropertyTag, class X, class Value>
void put(PropertyTag tag, const UndirectedAdaptor<Graph> &g, typename graph_traits<UndirectedAdaptor<Graph> >::edge_descriptor e, const Value &value)
{
    put(tag, g.OriginalGraph(), e.OriginalEdge(), value);
}

//==============================================================================
// get_property(g,tag)
//==============================================================================
template <class Graph, class GraphProperties, class GraphPropertyTag>
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>
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