File: directed_graph.hpp

package info (click to toggle)
boost1.62 1.62.0+dfsg-4
  • links: PTS, VCS
  • area: main
  • in suites: stretch
  • size: 686,420 kB
  • sloc: cpp: 2,609,004; xml: 972,558; ansic: 53,674; python: 32,437; sh: 8,829; asm: 3,071; cs: 2,121; makefile: 964; perl: 859; yacc: 472; php: 132; ruby: 94; f90: 55; sql: 13; csh: 6
file content (701 lines) | stat: -rw-r--r-- 23,825 bytes parent folder | download | duplicates (10)
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
52
53
54
55
56
57
58
59
60
61
62
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
114
115
116
117
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
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
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
267
268
269
270
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
346
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
547
548
549
550
551
552
553
554
555
556
557
558
559
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
// (C) Copyright 2007-2009 Andrew Sutton
//
// Use, modification and distribution are subject to the
// Boost Software License, Version 1.0 (See accompanying file
// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)

#ifndef BOOST_GRAPH_DIRECTED_GRAPH_HPP
#define BOOST_GRAPH_DIRECTED_GRAPH_HPP

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/properties.hpp>
#include <boost/pending/property.hpp>
#include <boost/property_map/transform_value_property_map.hpp>
#include <boost/type_traits.hpp>
#include <boost/mpl/if.hpp>

namespace boost
{
struct directed_graph_tag { };

/**
 * The directed_graph class template is a simplified version of the BGL
 * adjacency list. This class is provided for ease of use, but may not
 * perform as well as custom-defined adjacency list classes. Instances of
 * this template model the BidirectionalGraph, VertexIndexGraph, and
 * EdgeIndexGraph concepts. The graph is also fully mutable, supporting
 * both insertions and removals of vertices and edges.
 *
 * @note Special care must be taken when removing vertices or edges since
 * those operations can invalidate the numbering of vertices.
 */
template <
    typename VertexProp = no_property,
    typename EdgeProp = no_property,
    typename GraphProp = no_property>
class directed_graph
{
public:
    typedef GraphProp graph_property_type;
    typedef VertexProp vertex_property_type;
    typedef EdgeProp edge_property_type;
    typedef typename lookup_one_property<GraphProp, graph_bundle_t>::type graph_bundled;
    typedef typename lookup_one_property<VertexProp, vertex_bundle_t>::type vertex_bundled;
    typedef typename lookup_one_property<EdgeProp, edge_bundle_t>::type edge_bundled;

public:
    // Embed indices into the vertex type.
    typedef property<vertex_index_t, unsigned, vertex_property_type> internal_vertex_property;
    typedef property<edge_index_t, unsigned, edge_property_type> internal_edge_property;
public:
    typedef adjacency_list<
        listS, listS, bidirectionalS,
        internal_vertex_property, internal_edge_property, GraphProp,
        listS
    > graph_type;

private:
    // storage selectors
    typedef typename graph_type::vertex_list_selector vertex_list_selector;
    typedef typename graph_type::edge_list_selector edge_list_selector;
    typedef typename graph_type::out_edge_list_selector out_edge_list_selector;
    typedef typename graph_type::directed_selector directed_selector;

public:
    // more commonly used graph types
    typedef typename graph_type::stored_vertex stored_vertex;
    typedef typename graph_type::vertices_size_type vertices_size_type;
    typedef typename graph_type::edges_size_type edges_size_type;
    typedef typename graph_type::degree_size_type degree_size_type;
    typedef typename graph_type::vertex_descriptor vertex_descriptor;
    typedef typename graph_type::edge_descriptor edge_descriptor;

    // iterator types
    typedef typename graph_type::vertex_iterator vertex_iterator;
    typedef typename graph_type::edge_iterator edge_iterator;
    typedef typename graph_type::out_edge_iterator out_edge_iterator;
    typedef typename graph_type::in_edge_iterator in_edge_iterator;
    typedef typename graph_type::adjacency_iterator adjacency_iterator;

    // miscellaneous types
    typedef directed_graph_tag graph_tag;
    typedef typename graph_type::directed_category directed_category;
    typedef typename graph_type::edge_parallel_category edge_parallel_category;
    typedef typename graph_type::traversal_category traversal_category;

    typedef std::size_t vertex_index_type;
    typedef std::size_t edge_index_type;

    directed_graph(GraphProp const& p = GraphProp())
        : m_graph(p), m_num_vertices(0), m_num_edges(0), m_max_vertex_index(0)
        , m_max_edge_index(0)
    { }

    directed_graph(directed_graph const& x)
        : m_graph(x.m_graph), m_num_vertices(x.m_num_vertices), m_num_edges(x.m_num_edges)
        , m_max_vertex_index(x.m_max_vertex_index), m_max_edge_index(x.m_max_edge_index)
    { }

    directed_graph(vertices_size_type n, GraphProp const& p = GraphProp())
        : m_graph(n, p), m_num_vertices(n), m_num_edges(0), m_max_vertex_index(n)
        , m_max_edge_index(0)
    { renumber_vertex_indices(); }

    template <typename EdgeIterator>
    directed_graph(EdgeIterator f,
                   EdgeIterator l,
                   vertices_size_type n,
                   edges_size_type m = 0,
                   GraphProp const& p = GraphProp())
        : m_graph(f, l, n, m, p), m_num_vertices(n), m_num_edges(0)
        , m_max_vertex_index(n), m_max_edge_index(0)
    {
        // Unfortunately, we have to renumber the entire graph.
        renumber_indices();

        // Can't always guarantee that the number of edges is actually
        // m if distance(f, l) != m (or is undefined).
        m_num_edges = m_max_edge_index = boost::num_edges(m_graph);
    }

    directed_graph& operator=(directed_graph const& g) {
        if(&g != this) {
            m_graph = g.m_graph;
            m_num_vertices = g.m_num_vertices;
            m_num_edges = g.m_num_edges;
            m_max_vertex_index = g.m_max_vertex_index;
            m_max_edge_index = g.m_max_edge_index;
        }
        return *this;
    }

    // The impl_() methods are not part of the public interface.
    graph_type& impl()
    { return m_graph; }

    graph_type const& impl() const
    { return m_graph; }

    // The following methods are not part of the public interface
    vertices_size_type num_vertices() const
    { return m_num_vertices; }


private:
    // This helper function manages the attribution of vertex indices.
    vertex_descriptor make_index(vertex_descriptor v) {
        boost::put(vertex_index, m_graph, v, m_max_vertex_index);
        m_num_vertices++;
        m_max_vertex_index++;
        return v;
    }
public:
    vertex_descriptor add_vertex()
    { return make_index(boost::add_vertex(m_graph)); }

    vertex_descriptor add_vertex(vertex_property_type const& p)
    { return make_index(boost::add_vertex(internal_vertex_property(0u, p), m_graph)); }

    void clear_vertex(vertex_descriptor v)
    {
        m_num_edges -= boost::degree(v, m_graph);
        boost::clear_vertex(v, m_graph);
    }

    void remove_vertex(vertex_descriptor v)
    {
        boost::remove_vertex(v, m_graph);
        --m_num_vertices;
    }

    edges_size_type num_edges() const
    { return m_num_edges; }

private:
    // A helper function for managing edge index attributes.
    std::pair<edge_descriptor, bool> const&
    make_index(std::pair<edge_descriptor, bool> const& x)
    {
        if(x.second) {
            boost::put(edge_index, m_graph, x.first, m_max_edge_index);
            ++m_num_edges;
            ++m_max_edge_index;
        }
        return x;
    }
public:
    std::pair<edge_descriptor, bool>
    add_edge(vertex_descriptor u, vertex_descriptor v)
    { return make_index(boost::add_edge(u, v, m_graph)); }

    std::pair<edge_descriptor, bool>
    add_edge(vertex_descriptor u, vertex_descriptor v, edge_property_type const& p)
    { return make_index(boost::add_edge(u, v, internal_edge_property(0u, p), m_graph)); }

    void remove_edge(vertex_descriptor u, vertex_descriptor v)
    {
        // find all edges, (u, v)
        std::vector<edge_descriptor> edges;
        out_edge_iterator i, i_end;
        for(boost::tie(i, i_end) = boost::out_edges(u, m_graph); i != i_end; ++i) {
            if(boost::target(*i, m_graph) == v) {
                edges.push_back(*i);
            }
        }
        // remove all edges, (u, v)
        typename std::vector<edge_descriptor>::iterator
        j = edges.begin(), j_end = edges.end();
        for( ; j != j_end; ++j) {
            remove_edge(*j);
        }
    }

    void remove_edge(edge_iterator i)
    {
        remove_edge(*i);
    }

    void remove_edge(edge_descriptor e)
    {
        boost::remove_edge(e, m_graph);
        --m_num_edges;
    }

    vertex_index_type max_vertex_index() const
    { return m_max_vertex_index; }

    void
    renumber_vertex_indices()
    {
        vertex_iterator i, end;
        boost::tie(i, end) = vertices(m_graph);
        m_max_vertex_index = renumber_vertex_indices(i, end, 0);
    }

    void
    remove_vertex_and_renumber_indices(vertex_iterator i)
    {
        vertex_iterator j = next(i), end = vertices(m_graph).second;
        vertex_index_type n = get(vertex_index, m_graph, *i);

        // remove the offending vertex and renumber everything after
        remove_vertex(*i);
        m_max_vertex_index = renumber_vertex_indices(j, end, n);
    }

    edge_index_type
    max_edge_index() const
    { return m_max_edge_index; }

    void
    renumber_edge_indices()
    {
        edge_iterator i, end;
        boost::tie(i, end) = edges(m_graph);
        m_max_edge_index = renumber_edge_indices(i, end, 0);
    }

    void
    remove_edge_and_renumber_indices(edge_iterator i)
    {
        edge_iterator j = next(i), end = edges(m_graph).second;
        edge_index_type n = get(edge_index, m_graph, *i);

        // remove the offending edge and renumber everything after
        remove_edge(*i);
        m_max_edge_index = renumber_edge_indices(j, end, n);
    }

    void
    renumber_indices()
    {
        renumber_vertex_indices();
        renumber_edge_indices();
    }

    // bundled property support
#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
    vertex_bundled& operator[](vertex_descriptor v)
    { return m_graph[v]; }

    vertex_bundled const& operator[](vertex_descriptor v) const
    { return m_graph[v]; }

    edge_bundled& operator[](edge_descriptor e)
    { return m_graph[e]; }

    edge_bundled const& operator[](edge_descriptor e) const
    { return m_graph[e]; }

    graph_bundled& operator[](graph_bundle_t)
    { return get_property(*this); }

    graph_bundled const& operator[](graph_bundle_t) const
    { return get_property(*this); }
#endif

    // Graph concepts
    static vertex_descriptor null_vertex()
    { return graph_type::null_vertex(); }

    void clear()
    {
        m_graph.clear();
        m_num_vertices = m_max_vertex_index = 0;
        m_num_edges = m_max_edge_index = 0;
    }

    void swap(directed_graph& g)
    {
        m_graph.swap(g.m_graph);
        std::swap(m_num_vertices, g.m_num_vertices);
        std::swap(m_max_vertex_index, g.m_max_vertex_index);
        std::swap(m_num_edges, g.m_num_edges);
        std::swap(m_max_edge_index, g.m_max_edge_index);
    }

private:
    vertices_size_type
    renumber_vertex_indices(vertex_iterator i,
                            vertex_iterator end,
                            vertices_size_type n)
    {
        typedef typename property_map<graph_type, vertex_index_t>::type IndexMap;
        IndexMap indices = get(vertex_index, m_graph);
        for( ; i != end; ++i) {
            indices[*i] = n++;
        }
        return n;
    }

    vertices_size_type
    renumber_edge_indices(edge_iterator i,
                        edge_iterator end,
                        vertices_size_type n)
    {
        typedef typename property_map<graph_type, edge_index_t>::type IndexMap;
        IndexMap indices = get(edge_index, m_graph);
        for( ; i != end; ++i) {
            indices[*i] = n++;
        }
        return n;
    }

    graph_type m_graph;
    vertices_size_type m_num_vertices;
    edges_size_type m_num_edges;
    vertex_index_type m_max_vertex_index;
    edge_index_type m_max_edge_index;
};

#define DIRECTED_GRAPH_PARAMS typename VP, typename EP, typename GP
#define DIRECTED_GRAPH directed_graph<VP,EP,GP>

// IncidenceGraph concepts
template <DIRECTED_GRAPH_PARAMS>
inline typename DIRECTED_GRAPH::vertex_descriptor
source(typename DIRECTED_GRAPH::edge_descriptor e, DIRECTED_GRAPH const& g)
{ return source(e, g.impl()); }

template <DIRECTED_GRAPH_PARAMS>
inline typename DIRECTED_GRAPH::vertex_descriptor
target(typename DIRECTED_GRAPH::edge_descriptor e, DIRECTED_GRAPH const& g)
{ return target(e, g.impl()); }

template <DIRECTED_GRAPH_PARAMS>
inline typename DIRECTED_GRAPH::degree_size_type
out_degree(typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH const& g)
{ return out_degree(v, g.impl()); }

template <DIRECTED_GRAPH_PARAMS>
inline std::pair<
    typename DIRECTED_GRAPH::out_edge_iterator,
    typename DIRECTED_GRAPH::out_edge_iterator
>
out_edges(typename DIRECTED_GRAPH::vertex_descriptor v,
        DIRECTED_GRAPH const& g)
{ return out_edges(v, g.impl()); }

// BidirectionalGraph concepts
template <DIRECTED_GRAPH_PARAMS>
inline typename DIRECTED_GRAPH::degree_size_type
in_degree(typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH const& g)
{ return in_degree(v, g.impl()); }

template <DIRECTED_GRAPH_PARAMS>
inline std::pair<
    typename DIRECTED_GRAPH::in_edge_iterator,
    typename DIRECTED_GRAPH::in_edge_iterator
>
in_edges(typename DIRECTED_GRAPH::vertex_descriptor v,
        DIRECTED_GRAPH const& g)
{ return in_edges(v, g.impl()); }


template <DIRECTED_GRAPH_PARAMS>
inline typename DIRECTED_GRAPH::degree_size_type
degree(typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH const& g)
{ return degree(v, g.impl()); }

// AdjacencyGraph concepts
template <DIRECTED_GRAPH_PARAMS>
inline std::pair<
    typename DIRECTED_GRAPH::adjacency_iterator,
    typename DIRECTED_GRAPH::adjacency_iterator
    >
adjacent_vertices(typename DIRECTED_GRAPH::vertex_descriptor v,
                  DIRECTED_GRAPH const& g)
{ return adjacent_vertices(v, g.impl()); }

template <DIRECTED_GRAPH_PARAMS>
typename DIRECTED_GRAPH::vertex_descriptor
vertex(typename DIRECTED_GRAPH::vertices_size_type n,
       DIRECTED_GRAPH const& g)
{ return vertex(n, g.impl()); }

template <DIRECTED_GRAPH_PARAMS>
std::pair<typename DIRECTED_GRAPH::edge_descriptor, bool>
edge(typename DIRECTED_GRAPH::vertex_descriptor u,
     typename DIRECTED_GRAPH::vertex_descriptor v,
     DIRECTED_GRAPH const& g)
{ return edge(u, v, g.impl()); }

// VertexListGraph concepts
template <DIRECTED_GRAPH_PARAMS>
inline typename DIRECTED_GRAPH::vertices_size_type
num_vertices(DIRECTED_GRAPH const& g)
{ return g.num_vertices(); }

template <DIRECTED_GRAPH_PARAMS>
inline std::pair<
    typename DIRECTED_GRAPH::vertex_iterator,
    typename DIRECTED_GRAPH::vertex_iterator
>
vertices(DIRECTED_GRAPH const& g)
{ return vertices(g.impl()); }

// EdgeListGraph concepts
template <DIRECTED_GRAPH_PARAMS>
inline typename DIRECTED_GRAPH::edges_size_type
num_edges(DIRECTED_GRAPH const& g)
{ return g.num_edges(); }

template <DIRECTED_GRAPH_PARAMS>
inline std::pair<
    typename DIRECTED_GRAPH::edge_iterator,
    typename DIRECTED_GRAPH::edge_iterator
>
edges(DIRECTED_GRAPH const& g)
{ return edges(g.impl()); }

// MutableGraph concepts
template <DIRECTED_GRAPH_PARAMS>
inline typename DIRECTED_GRAPH::vertex_descriptor
add_vertex(DIRECTED_GRAPH& g)
{ return g.add_vertex(); }

template <DIRECTED_GRAPH_PARAMS>
inline typename DIRECTED_GRAPH::vertex_descriptor
add_vertex(typename DIRECTED_GRAPH::vertex_property_type const& p,
           DIRECTED_GRAPH& g)
{ return g.add_vertex(p); }

template <DIRECTED_GRAPH_PARAMS>
inline void
clear_vertex(typename DIRECTED_GRAPH::vertex_descriptor v,
DIRECTED_GRAPH& g)
{ return g.clear_vertex(v); }

template <DIRECTED_GRAPH_PARAMS>
inline void
remove_vertex(typename DIRECTED_GRAPH::vertex_descriptor v,
              DIRECTED_GRAPH& g)
{ return g.remove_vertex(v); }

template <DIRECTED_GRAPH_PARAMS>
inline std::pair<typename DIRECTED_GRAPH::edge_descriptor, bool>
add_edge(typename DIRECTED_GRAPH::vertex_descriptor u,
         typename DIRECTED_GRAPH::vertex_descriptor v,
         DIRECTED_GRAPH& g)
{ return g.add_edge(u, v); }

template <DIRECTED_GRAPH_PARAMS>
inline std::pair<typename DIRECTED_GRAPH::edge_descriptor, bool>
add_edge(typename DIRECTED_GRAPH::vertex_descriptor u,
         typename DIRECTED_GRAPH::vertex_descriptor v,
         typename DIRECTED_GRAPH::edge_property_type const& p,
         DIRECTED_GRAPH& g)
{ return g.add_edge(u, v, p); }

template <DIRECTED_GRAPH_PARAMS>
inline void remove_edge(typename DIRECTED_GRAPH::vertex_descriptor u,
                        typename DIRECTED_GRAPH::vertex_descriptor v,
                        DIRECTED_GRAPH& g)
{ return g.remove_edge(u, v); }


template <DIRECTED_GRAPH_PARAMS>
inline void remove_edge(typename DIRECTED_GRAPH::edge_descriptor e, DIRECTED_GRAPH& g)
{ return g.remove_edge(e); }

template <DIRECTED_GRAPH_PARAMS>
inline void remove_edge(typename DIRECTED_GRAPH::edge_iterator i, DIRECTED_GRAPH& g)
{ return g.remove_edge(i); }

template <DIRECTED_GRAPH_PARAMS, class Predicate>
inline void remove_edge_if(Predicate pred, DIRECTED_GRAPH& g)
{ return remove_edge_if(pred, g.impl()); }

template <DIRECTED_GRAPH_PARAMS, class Predicate>
inline void
remove_out_edge_if(typename DIRECTED_GRAPH::vertex_descriptor v,
                   Predicate pred,
                   DIRECTED_GRAPH& g)
{ return remove_out_edge_if(v, pred, g.impl()); }

template <DIRECTED_GRAPH_PARAMS, class Predicate>
inline void
remove_in_edge_if(typename DIRECTED_GRAPH::vertex_descriptor v,
                Predicate pred,
                DIRECTED_GRAPH& g)
{ return remove_in_edge_if(v, pred, g.impl()); }

template <DIRECTED_GRAPH_PARAMS, typename Property>
struct property_map<DIRECTED_GRAPH, Property>: property_map<typename DIRECTED_GRAPH::graph_type, Property> {};

template <DIRECTED_GRAPH_PARAMS>
struct property_map<DIRECTED_GRAPH, vertex_all_t> {
  typedef transform_value_property_map<
            detail::remove_first_property,
            typename property_map<typename DIRECTED_GRAPH::graph_type, vertex_all_t>::const_type>
    const_type;
  typedef transform_value_property_map<
            detail::remove_first_property,
            typename property_map<typename DIRECTED_GRAPH::graph_type, vertex_all_t>::type>
    type;
};

template <DIRECTED_GRAPH_PARAMS>
struct property_map<DIRECTED_GRAPH, edge_all_t> {
  typedef transform_value_property_map<
            detail::remove_first_property,
            typename property_map<typename DIRECTED_GRAPH::graph_type, edge_all_t>::const_type>
    const_type;
  typedef transform_value_property_map<
            detail::remove_first_property,
            typename property_map<typename DIRECTED_GRAPH::graph_type, edge_all_t>::type>
    type;
};

// PropertyGraph concepts
template <DIRECTED_GRAPH_PARAMS, typename Property>
inline typename property_map<DIRECTED_GRAPH, Property>::type
get(Property p, DIRECTED_GRAPH& g)
{ return get(p, g.impl()); }

template <DIRECTED_GRAPH_PARAMS, typename Property>
inline typename property_map<DIRECTED_GRAPH, Property>::const_type
get(Property p, DIRECTED_GRAPH const& g)
{ return get(p, g.impl()); }

template <DIRECTED_GRAPH_PARAMS>
inline typename property_map<DIRECTED_GRAPH, vertex_all_t>::type
get(vertex_all_t, DIRECTED_GRAPH& g)
{ return typename property_map<DIRECTED_GRAPH, vertex_all_t>::type(detail::remove_first_property(), get(vertex_all, g.impl())); }

template <DIRECTED_GRAPH_PARAMS>
inline typename property_map<DIRECTED_GRAPH, vertex_all_t>::const_type
get(vertex_all_t, DIRECTED_GRAPH const& g)
{ return typename property_map<DIRECTED_GRAPH, vertex_all_t>::const_type(detail::remove_first_property(), get(vertex_all, g.impl())); }

template <DIRECTED_GRAPH_PARAMS>
inline typename property_map<DIRECTED_GRAPH, edge_all_t>::type
get(edge_all_t, DIRECTED_GRAPH& g)
{ return typename property_map<DIRECTED_GRAPH, edge_all_t>::type(detail::remove_first_property(), get(edge_all, g.impl())); }

template <DIRECTED_GRAPH_PARAMS>
inline typename property_map<DIRECTED_GRAPH, edge_all_t>::const_type
get(edge_all_t, DIRECTED_GRAPH const& g)
{ return typename property_map<DIRECTED_GRAPH, edge_all_t>::const_type(detail::remove_first_property(), get(edge_all, g.impl())); }

template <DIRECTED_GRAPH_PARAMS, typename Property, typename Key>
inline typename property_traits<
    typename property_map<
        typename DIRECTED_GRAPH::graph_type, Property
    >::const_type
>::value_type
get(Property p, DIRECTED_GRAPH const& g, Key const& k)
{ return get(p, g.impl(), k); }

template <DIRECTED_GRAPH_PARAMS, typename Key>
inline typename property_traits<
    typename property_map<
        typename DIRECTED_GRAPH::graph_type, vertex_all_t
    >::const_type
>::value_type
get(vertex_all_t, DIRECTED_GRAPH const& g, Key const& k)
{ return get(vertex_all, g.impl(), k).m_base; }

template <DIRECTED_GRAPH_PARAMS, typename Key>
inline typename property_traits<
    typename property_map<
        typename DIRECTED_GRAPH::graph_type, edge_all_t
    >::const_type
>::value_type
get(edge_all_t, DIRECTED_GRAPH const& g, Key const& k)
{ return get(edge_all, g.impl(), k).m_base; }

template <DIRECTED_GRAPH_PARAMS, typename Property, typename Key, typename Value>
inline void put(Property p, DIRECTED_GRAPH& g, Key const& k, Value const& v)
{ put(p, g.impl(), k, v); }

template <DIRECTED_GRAPH_PARAMS, typename Key, typename Value>
inline void put(vertex_all_t, DIRECTED_GRAPH& g, Key const& k, Value const& v)
{ put(vertex_all, g.impl(), k,
      typename DIRECTED_GRAPH::internal_vertex_property(get(vertex_index, g.impl(), k), v));
}

template <DIRECTED_GRAPH_PARAMS, typename Key, typename Value>
inline void put(edge_all_t, DIRECTED_GRAPH& g, Key const& k, Value const& v)
{ put(edge_all, g.impl(), k,
      typename DIRECTED_GRAPH::internal_vertex_property(get(edge_index, g.impl(), k), v));
}

template <DIRECTED_GRAPH_PARAMS, class Property>
typename graph_property<DIRECTED_GRAPH, Property>::type&
get_property(DIRECTED_GRAPH& g, Property p)
{ return get_property(g.impl(), p); }

template <DIRECTED_GRAPH_PARAMS, class Property>
typename graph_property<DIRECTED_GRAPH, Property>::type const&
get_property(DIRECTED_GRAPH const& g, Property p)
{ return get_property(g.impl(), p); }

template <DIRECTED_GRAPH_PARAMS, class Property, class Value>
void
set_property(DIRECTED_GRAPH& g, Property p, Value v)
{ return set_property(g.impl(), p, v); }

// Vertex index management

template <DIRECTED_GRAPH_PARAMS>
inline typename DIRECTED_GRAPH::vertex_index_type
get_vertex_index(typename DIRECTED_GRAPH::vertex_descriptor v,
                DIRECTED_GRAPH const& g)
{ return get(vertex_index, g, v); }

template <DIRECTED_GRAPH_PARAMS>
typename DIRECTED_GRAPH::vertex_index_type
max_vertex_index(DIRECTED_GRAPH const& g)
{ return g.max_vertex_index(); }

template <DIRECTED_GRAPH_PARAMS>
inline void
renumber_vertex_indices(DIRECTED_GRAPH& g)
{ g.renumber_vertex_indices(); }

template <DIRECTED_GRAPH_PARAMS>
inline void
remove_vertex_and_renumber_indices(typename DIRECTED_GRAPH::vertex_iterator i,
                                DIRECTED_GRAPH& g)
{ g.remove_vertex_and_renumber_indices(i); }

// Edge index management
template <DIRECTED_GRAPH_PARAMS>
inline typename DIRECTED_GRAPH::edge_index_type
get_edge_index(typename DIRECTED_GRAPH::edge_descriptor v, DIRECTED_GRAPH const& g)
{ return get(edge_index, g, v); }

template <DIRECTED_GRAPH_PARAMS>
typename DIRECTED_GRAPH::edge_index_type
max_edge_index(DIRECTED_GRAPH const& g)
{ return g.max_edge_index(); }

template <DIRECTED_GRAPH_PARAMS>
inline void renumber_edge_indices(DIRECTED_GRAPH& g)
{ g.renumber_edge_indices(); }

template <DIRECTED_GRAPH_PARAMS>
inline void
remove_edge_and_renumber_indices(typename DIRECTED_GRAPH::edge_iterator i,
                                 DIRECTED_GRAPH& g)
{ g.remove_edge_and_renumber_indices(i); }

// Index management
template <DIRECTED_GRAPH_PARAMS>
inline void
renumber_indices(DIRECTED_GRAPH& g)
{ g.renumber_indices(); }

// Mutability Traits
template <DIRECTED_GRAPH_PARAMS>
struct graph_mutability_traits<DIRECTED_GRAPH> {
    typedef mutable_property_graph_tag category;
};

#undef DIRECTED_GRAPH_PARAMS
#undef DIRECTED_GRAPH

} /* namespace boost */

#endif