graph_adaptor.hh 30.9 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-2012 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 28 29 30 31
#include <boost/config.hpp>
#include <boost/iterator_adaptors.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/properties.hpp>

namespace boost {

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

45 46
    typedef typename vertex_property_type<Graph>::type vertex_property_type;
    typedef typename edge_property_type<Graph>::type edge_property_type;
47
    typedef typename Graph::graph_tag graph_tag;
48
    typedef Graph graph_type;
49

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

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

58 59 60
    typedef undirected_tag directed_category;
    typedef allow_parallel_edge_tag edge_parallel_category;
    typedef typename graph_traits<Graph>::traversal_category traversal_category;
61

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

    template<typename Descriptor>
69 70
    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
71
#endif // BOOST_GRAPH_NO_BUNDLED_PROPERTIES
72

Tiago Peixoto's avatar
Tiago Peixoto committed
73 74
    const Graph& OriginalGraph() const {return _g;}
    Graph& OriginalGraph() {return _g;}
75

Tiago Peixoto's avatar
Tiago Peixoto committed
76
private:
77
    Graph& _g;
Tiago Peixoto's avatar
Tiago Peixoto committed
78 79 80 81
};

#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
template<typename Graph>
82 83
struct vertex_bundle_type<UndirectedAdaptor<Graph> >:
        vertex_bundle_type<Graph> { };
Tiago Peixoto's avatar
Tiago Peixoto committed
84 85

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


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

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

107 108 109 110
    bool operator==(const EdgeDescriptor& e) const
    {
        return original_edge_t(e) == original_edge_t(*this);
    }
111

Tiago Peixoto's avatar
Tiago Peixoto committed
112 113 114 115 116 117 118
private:
    bool _inverted;
};

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

Tiago Peixoto's avatar
Tiago Peixoto committed
138
//    pointer operator->() const {return **this;}
139 140 141

    UndirectedAdaptorEdgeIterator& operator++()
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
142 143 144 145
        ++_iter;
        return *this;
    }

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

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

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

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

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

Tiago Peixoto's avatar
Tiago Peixoto committed
176 177 178 179 180 181 182 183

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

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

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

Tiago Peixoto's avatar
Tiago Peixoto committed
216
//    pointer operator->() const {return **this;}
217 218 219 220

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

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

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

Tiago Peixoto's avatar
Tiago Peixoto committed
244 245 246 247 248 249
        return *this;
    }

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

Tiago Peixoto's avatar
Tiago Peixoto committed
255 256
        return t;
    }
257

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

Tiago Peixoto's avatar
Tiago Peixoto committed
263 264 265 266
    bool operator!=(UndirectedAdaptorOutEdgeIterator iter) const
    {
        return !(*this == iter);
    }
267

Tiago Peixoto's avatar
Tiago Peixoto committed
268
protected:
269 270 271 272
    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
273 274 275 276 277 278 279 280 281
    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
//==============================================================================
282 283 284 285 286 287 288 289 290
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
291 292 293
{
public:
    UndirectedAdaptorAdjacencyIterator(){};
294 295
    UndirectedAdaptorAdjacencyIterator
        (UndirectedAdaptorOutEdgeIterator<Graph> iter,
296
         const UndirectedAdaptor<Graph>& g)
297 298
            :_iter(iter), _g(&g) {}

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

Tiago Peixoto's avatar
Tiago Peixoto committed
304
//    pointer operator->() const {return **this;}
305 306 307

    UndirectedAdaptorAdjacencyIterator& operator++()
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
308 309 310 311
        ++_iter;
        return *this;
    }

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

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

    UndirectedAdaptorAdjacencyIterator operator--(int)
    {
        UndirectedAdaptorAdjacencyIterator t = *this;
328
        --_iter;
Tiago Peixoto's avatar
Tiago Peixoto committed
329 330
        return t;
    }
331

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

Tiago Peixoto's avatar
Tiago Peixoto committed
337 338 339 340
    bool operator!=(UndirectedAdaptorAdjacencyIterator iter) const
    {
        return (iter._iter != _iter);
    }
341

Tiago Peixoto's avatar
Tiago Peixoto committed
342 343 344 345 346 347 348 349 350 351
private:
    UndirectedAdaptorOutEdgeIterator<Graph> _iter;
    UndirectedAdaptor<Graph> const * _g;
};

//==============================================================================
// graph_traits<UndirectedAdaptor>
// this defines all the necessary types associated with UndirectedAdaptor
//==============================================================================
template <class Graph>
352
struct graph_traits<UndirectedAdaptor<Graph> > {
Tiago Peixoto's avatar
Tiago Peixoto committed
353 354 355 356 357
    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;
358
    typedef typename graph_traits<Graph>::in_edge_iterator in_edge_iterator;
Tiago Peixoto's avatar
Tiago Peixoto committed
359 360
    typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
    typedef UndirectedAdaptorEdgeIterator<Graph> edge_iterator;
361

Tiago Peixoto's avatar
Tiago Peixoto committed
362
    typedef undirected_tag directed_category;
363
    typedef allow_parallel_edge_tag edge_parallel_category;
364
    typedef typename graph_traits<Graph>::traversal_category traversal_category;
Tiago Peixoto's avatar
Tiago Peixoto committed
365 366 367
    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;
368 369 370 371 372

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

375
template <class Graph>
376 377
struct graph_traits< const UndirectedAdaptor<Graph> >:
    public graph_traits<UndirectedAdaptor<Graph> > {};
378

Tiago Peixoto's avatar
Tiago Peixoto committed
379 380
//==============================================================================
// Nonmember functions
381
// these provide manipulation of the graph
Tiago Peixoto's avatar
Tiago Peixoto committed
382 383 384 385 386 387
//==============================================================================

//==============================================================================
// source(e,g)
//==============================================================================
template <class Graph>
388 389 390
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
391 392 393 394 395 396 397 398 399 400 401 402
{
    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>
403 404 405
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
406 407 408 409 410 411 412 413 414 415 416 417
{
    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>
418 419 420
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
421 422 423 424 425 426 427 428
{
    return vertex(n, g.OriginalGraph());
}

//==============================================================================
// vertices(g)
//==============================================================================
template <class Graph>
429 430 431
inline
std::pair<typename graph_traits<UndirectedAdaptor<Graph> >::vertex_iterator,
          typename graph_traits<UndirectedAdaptor<Graph> >::vertex_iterator >
Tiago Peixoto's avatar
Tiago Peixoto committed
432 433 434 435 436 437 438 439 440
vertices(const UndirectedAdaptor<Graph>& g)
{
    return vertices(g.OriginalGraph());
}

//==============================================================================
// edges(g)
//==============================================================================
template <class Graph>
441 442 443
inline
std::pair<typename graph_traits<UndirectedAdaptor<Graph> >::edge_iterator,
          typename graph_traits<UndirectedAdaptor<Graph> >::edge_iterator >
Tiago Peixoto's avatar
Tiago Peixoto committed
444 445
edges(const UndirectedAdaptor<Graph>& g)
{
446 447
    std::pair<typename graph_traits<Graph>::edge_iterator,
              typename graph_traits<Graph>::edge_iterator> range;
Tiago Peixoto's avatar
Tiago Peixoto committed
448
    range = edges(g.OriginalGraph());
449 450
    return make_pair(UndirectedAdaptorEdgeIterator<Graph>(range.first),
                     UndirectedAdaptorEdgeIterator<Graph>(range.second));
Tiago Peixoto's avatar
Tiago Peixoto committed
451 452 453 454 455 456
}

//==============================================================================
// out_edges(u,g)
//==============================================================================
template <class Graph>
457 458 459 460 461 462 463 464 465 466 467 468
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
469
    in_range = in_edges(u, g.OriginalGraph());
470 471 472 473 474 475 476 477 478

    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
479 480 481 482 483 484 485
    return std::make_pair(iter_begin, iter_end);
}

//==============================================================================
// adjacent_vertices(u,g)
//==============================================================================
template <class Graph>
486 487 488 489 490 491 492 493 494 495 496 497
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
498 499
    std::pair<edge_iter_t, edge_iter_t> edge_range;
    edge_range = out_edges(u,g);
500 501 502

    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
503 504 505 506 507 508
}

//==============================================================================
// num_vertices(g)
//==============================================================================
template <class Graph>
509
inline typename graph_traits<UndirectedAdaptor<Graph> >::vertices_size_type
Tiago Peixoto's avatar
Tiago Peixoto committed
510 511 512
num_vertices(const UndirectedAdaptor<Graph>& g)
{
    return num_vertices(g.OriginalGraph());
513
}
Tiago Peixoto's avatar
Tiago Peixoto committed
514 515 516 517 518

//==============================================================================
// num_edges(g)
//==============================================================================
template <class Graph>
519
inline typename graph_traits<UndirectedAdaptor<Graph> >::edges_size_type
Tiago Peixoto's avatar
Tiago Peixoto committed
520 521 522
num_edges(const UndirectedAdaptor<Graph>& g)
{
    return num_edges(g.OriginalGraph());
523
}
Tiago Peixoto's avatar
Tiago Peixoto committed
524 525 526 527 528

//==============================================================================
// out_degree(u,g)
//==============================================================================
template <class Graph>
529 530 531
inline typename graph_traits<UndirectedAdaptor<Graph> >::degree_size_type
out_degree
    (typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor u,
532
     const UndirectedAdaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
533 534 535 536 537 538 539 540
{
    return (out_degree(u, g.OriginalGraph())+in_degree(u,g.OriginalGraph()));
}

//==============================================================================
// degree(u,g)
//==============================================================================
template <class Graph>
541 542
inline typename graph_traits<UndirectedAdaptor<Graph> >::degree_size_type
degree(typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor u,
543
       const UndirectedAdaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
544 545 546 547 548 549 550 551
{
    return out_degree(u, g);
}


//==============================================================================
// add_vertex(g)
//==============================================================================
552 553
template <class Graph>
inline typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor
Tiago Peixoto's avatar
Tiago Peixoto committed
554 555 556 557 558 559 560 561 562
add_vertex(UndirectedAdaptor<Graph>& g)
{
    return add_vertex(g.OriginalGraph());
}

//==============================================================================
// add_vertex(vp,g)
//==============================================================================
template <class Graph, class VertexProperties>
563
inline typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor
564
add_vertex(const VertexProperties& p, UndirectedAdaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
565 566 567 568 569 570 571 572
{
    return add_vertex(p, g.OriginalGraph());
}

//==============================================================================
// clear_vertex(u,g)
//==============================================================================
template <class Graph>
573 574 575
inline void clear_vertex
    (typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor u,
     UndirectedAdaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
576 577 578 579 580 581 582 583
{
    clear_vertex(u, g.OriginalGraph());
}

//==============================================================================
// remove_vertex(u,g)
//==============================================================================
template <class Graph>
584 585 586
inline void remove_vertex
    (typename graph_traits<UndirectedAdaptor<Graph> >::vertex_descriptor u,
     UndirectedAdaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
587 588 589 590 591 592 593 594
{
    remove_vertex(u, g.OriginalGraph());
}

//==============================================================================
// add_edge(u,v,g)
//==============================================================================
template <class Graph>
595 596 597 598 599 600 601 602 603 604 605 606 607
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
608 609 610 611 612 613
}

//==============================================================================
// add_edge(u,v,ep,g)
//==============================================================================
template <class Graph, class EdgeProperties>
614 615 616 617 618 619 620 621 622 623 624 625 626
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
627 628 629 630 631 632
}

//==============================================================================
// remove_edge(u,v,g)
//==============================================================================
template <class Graph>
633 634 635 636
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
637 638 639 640 641 642 643 644 645
{
    remove_edge(u,v,g.OriginalGraph());
    remove_edge(v,u,g.OriginalGraph());
}

//==============================================================================
// remove_edge(e,g)
//==============================================================================
template <class Graph>
646 647 648
inline void remove_edge
    (typename graph_traits<UndirectedAdaptor<Graph> >::edge_descriptor e,
     UndirectedAdaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
649
{
650 651
    remove_edge(typename graph_traits<Graph>::edge_descriptor(e),
                g.OriginalGraph());
Tiago Peixoto's avatar
Tiago Peixoto committed
652 653 654 655 656 657
}

//==============================================================================
// remove_edge(e_iter,g)
//==============================================================================
template <class Graph>
658 659 660
inline void remove_edge
    (typename graph_traits<UndirectedAdaptor<Graph> >::out_edge_iterator iter,
     UndirectedAdaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
661 662 663 664 665 666 667 668
{
    remove_edge(*iter, g);
}

//==============================================================================
// remove_out_edge_if(v,predicate,g)
//==============================================================================
template <class Graph, class Predicate>
669 670 671
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
672 673
{
    std::list<typename UndirectedAdaptor<Graph>::EdgeDescriptor> removed_edges;
674 675 676
    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
677 678 679 680
    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);
681

Tiago Peixoto's avatar
Tiago Peixoto committed
682 683 684 685 686 687 688
    for(typeof(removed_edges.begin()) iter = removed_edges.begin();
        iter != removed_edges.end(); ++iter)
        remove_edge(*iter,g);
}


//==============================================================================
689
// Property maps
Tiago Peixoto's avatar
Tiago Peixoto committed
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
//==============================================================================

//==============================================================================
// 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;
740
    typedef typename property_map<Graph, PropertyTag>::const_type const_type;
Tiago Peixoto's avatar
Tiago Peixoto committed
741 742 743 744 745 746
};

//==============================================================================
// property_map<UndirectedAdaptor, T Bundle::*>
//==============================================================================
template <typename Graph, typename T, typename Bundle>
747
class property_map<UndirectedAdaptor<Graph>, T Bundle::*>
Tiago Peixoto's avatar
Tiago Peixoto committed
748 749 750 751 752 753 754 755 756 757 758
{
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>
759
inline typename property_map<UndirectedAdaptor<Graph>, PropertyTag>::type
760
get(PropertyTag tag, UndirectedAdaptor<Graph>& g)
Tiago Peixoto's avatar
Tiago Peixoto committed
761 762 763 764 765
{
    return get(tag, g.OriginalGraph());
}

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

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

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

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

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

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

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

} // namespace boost


#endif // GRAPH_ADAPTOR_HH