source: NonGTP/Boost/boost/graph/adjacency_matrix.hpp @ 857

Revision 857, 37.6 KB checked in by igarcia, 19 years ago (diff)
Line 
1//=======================================================================
2// Copyright 2001 University of Notre Dame.
3// Author: Jeremy G. Siek
4//
5// Distributed under the Boost Software License, Version 1.0. (See
6// accompanying file LICENSE_1_0.txt or copy at
7// http://www.boost.org/LICENSE_1_0.txt)
8//=======================================================================
9
10#ifndef BOOST_ADJACENCY_MATRIX_HPP
11#define BOOST_ADJACENCY_MATRIX_HPP
12
13#include <boost/config.hpp>
14#include <vector>
15#include <memory>
16#include <cassert>
17#include <boost/limits.hpp>
18#include <boost/iterator.hpp>
19#include <boost/graph/graph_traits.hpp>
20#include <boost/graph/graph_selectors.hpp>
21#include <boost/pending/ct_if.hpp>
22#include <boost/graph/adjacency_iterator.hpp>
23#include <boost/graph/detail/edge.hpp>
24#include <boost/iterator/iterator_adaptor.hpp>
25#include <boost/iterator/filter_iterator.hpp>
26#include <boost/pending/integer_range.hpp>
27#include <boost/graph/properties.hpp>
28#include <boost/tuple/tuple.hpp>
29
30namespace boost {
31 
32  namespace detail {
33
34    template <class Directed, class Vertex>
35    class matrix_edge_desc_impl : public edge_desc_impl<Directed,Vertex>
36    {
37      typedef edge_desc_impl<Directed,Vertex> Base;
38    public:
39      matrix_edge_desc_impl() { }
40      matrix_edge_desc_impl(bool exists, Vertex s, Vertex d,
41                            const void* ep = 0)
42        : Base(s, d, ep), m_exists(exists) { }
43      bool exists() const { return m_exists; }
44    private:
45      bool m_exists;
46    };
47
48    struct does_edge_exist {
49      template <class Edge>
50      bool operator()(const Edge& e) const { return e.exists(); }
51    };
52
53    template <typename EdgeProperty>
54    bool get_edge_exists(const std::pair<bool, EdgeProperty>& stored_edge, int) {
55      return stored_edge.first;
56    }
57    template <typename EdgeProperty>
58    void set_edge_exists(
59        std::pair<bool, EdgeProperty>& stored_edge,
60        bool flag,
61        int
62        ) {
63      stored_edge.first = flag;
64    }
65
66    template <typename EdgeProxy>
67    bool get_edge_exists(const EdgeProxy& edge_proxy, ...) {
68      return edge_proxy;
69    }
70    template <typename EdgeProxy>
71    EdgeProxy& set_edge_exists(EdgeProxy& edge_proxy, bool flag, ...) {
72      edge_proxy = flag;
73      return edge_proxy; // just to avoid never used warning
74    }
75
76
77
78    template <typename EdgeProperty>
79    const EdgeProperty&
80    get_property(const std::pair<bool, EdgeProperty>& stored_edge) {
81      return stored_edge.second;
82    }
83    template <typename EdgeProperty>
84    EdgeProperty&
85    get_property(std::pair<bool, EdgeProperty>& stored_edge) {
86      return stored_edge.second;
87    }
88
89    template <typename StoredEdgeProperty, typename EdgeProperty>
90    inline void
91    set_property(std::pair<bool, StoredEdgeProperty>& stored_edge,
92                 const EdgeProperty& ep, int) {
93      stored_edge.second = ep;
94    }
95
96    inline const no_property& get_property(const char&) {
97      static no_property s_prop;
98      return s_prop;
99    }
100    inline no_property& get_property(char&) {
101      static no_property s_prop;
102      return s_prop;
103    }
104    template <typename EdgeProxy, typename EdgeProperty>
105    inline void
106    set_property(EdgeProxy, const EdgeProperty&, ...) {}
107   
108    //=======================================================================
109    // Directed Out Edge Iterator
110
111    template <
112        typename VertexDescriptor, typename MatrixIter
113      , typename VerticesSizeType, typename EdgeDescriptor
114    >
115    struct dir_adj_matrix_out_edge_iter
116      : iterator_adaptor<
117            dir_adj_matrix_out_edge_iter<VertexDescriptor, MatrixIter,  VerticesSizeType, EdgeDescriptor>
118          , MatrixIter
119          , EdgeDescriptor
120          , use_default
121          , EdgeDescriptor
122          , std::ptrdiff_t
123        >
124    {
125        typedef iterator_adaptor<
126            dir_adj_matrix_out_edge_iter<VertexDescriptor, MatrixIter,  VerticesSizeType, EdgeDescriptor>
127          , MatrixIter
128          , EdgeDescriptor
129          , use_default
130          , EdgeDescriptor
131          , std::ptrdiff_t
132        > super_t;
133       
134        dir_adj_matrix_out_edge_iter() { }
135       
136        dir_adj_matrix_out_edge_iter(
137            const MatrixIter& i
138          , const VertexDescriptor& src
139          , const VerticesSizeType& n
140           )
141            : super_t(i), m_src(src), m_targ(0), m_n(n)
142        { }
143
144        void increment() {
145            ++this->base_reference();
146            ++m_targ;
147        }
148       
149        inline EdgeDescriptor
150        dereference() const
151        {
152            return EdgeDescriptor(get_edge_exists(*this->base(), 0), m_src, m_targ,
153                                  &get_property(*this->base()));
154        }
155        VertexDescriptor m_src, m_targ;
156        VerticesSizeType m_n;
157    };
158
159    //=======================================================================
160    // Undirected Out Edge Iterator
161
162    template <
163        typename VertexDescriptor, typename MatrixIter
164      , typename VerticesSizeType, typename EdgeDescriptor
165    >
166    struct undir_adj_matrix_out_edge_iter
167      : iterator_adaptor<
168            undir_adj_matrix_out_edge_iter<VertexDescriptor, MatrixIter,  VerticesSizeType, EdgeDescriptor>
169          , MatrixIter
170          , EdgeDescriptor
171          , use_default
172          , EdgeDescriptor
173          , std::ptrdiff_t
174        >
175    {
176        typedef iterator_adaptor<
177            undir_adj_matrix_out_edge_iter<VertexDescriptor, MatrixIter,  VerticesSizeType, EdgeDescriptor>
178          , MatrixIter
179          , EdgeDescriptor
180          , use_default
181          , EdgeDescriptor
182          , std::ptrdiff_t
183        > super_t;
184       
185        undir_adj_matrix_out_edge_iter() { }
186       
187        undir_adj_matrix_out_edge_iter(
188            const MatrixIter& i
189          , const VertexDescriptor& src
190          , const VerticesSizeType& n
191        )
192          : super_t(i), m_src(src), m_inc(src), m_targ(0), m_n(n)
193        {}
194
195        void increment()
196        {
197            if (m_targ < m_src)     // first half
198            {
199                ++this->base_reference();
200            }
201            else if (m_targ < m_n - 1)
202            {                  // second half
203                ++m_inc;
204                this->base_reference() += m_inc;
205            }
206            else
207            {                  // past-the-end
208                this->base_reference() += m_n - m_src;
209            }
210            ++m_targ;
211        }
212       
213        inline EdgeDescriptor
214        dereference() const
215        {
216            return EdgeDescriptor(
217                get_edge_exists(*this->base(), 0), m_src, m_targ
218              , &get_property(*this->base())
219            );
220        }
221       
222        VertexDescriptor m_src, m_inc, m_targ;
223        VerticesSizeType m_n;
224    };
225
226    //=======================================================================
227    // Edge Iterator
228
229    template <typename Directed, typename MatrixIter,
230              typename VerticesSizeType, typename EdgeDescriptor>
231    struct adj_matrix_edge_iter
232      : iterator_adaptor<
233            adj_matrix_edge_iter<Directed, MatrixIter,  VerticesSizeType, EdgeDescriptor>
234          , MatrixIter
235          , EdgeDescriptor
236          , use_default
237          , EdgeDescriptor
238          , std::ptrdiff_t
239        >
240    {
241        typedef iterator_adaptor<
242            adj_matrix_edge_iter<Directed, MatrixIter,  VerticesSizeType, EdgeDescriptor>
243          , MatrixIter
244          , EdgeDescriptor
245          , use_default
246          , EdgeDescriptor
247          , std::ptrdiff_t
248        > super_t;
249       
250        adj_matrix_edge_iter() { }
251       
252        adj_matrix_edge_iter(const MatrixIter& i, const MatrixIter& start, const VerticesSizeType& n)
253            : super_t(i), m_start(start), m_src(0), m_targ(0), m_n(n) { }
254
255        void increment()
256        {
257            increment_dispatch(this->base_reference(), Directed());
258        }
259       
260        void increment_dispatch(MatrixIter& i, directedS)
261        {
262            ++i;
263            if (m_targ == m_n - 1)
264            {
265                m_targ = 0;
266                ++m_src;
267            }
268            else
269            {
270                ++m_targ;
271            }
272        }
273       
274        void increment_dispatch(MatrixIter& i, undirectedS)
275        {
276            ++i;
277            if (m_targ == m_src)
278            {
279                m_targ = 0;
280                ++m_src;
281            }
282            else
283            {
284                ++m_targ;
285            }
286        }
287
288        inline EdgeDescriptor
289        dereference() const
290        {
291            return EdgeDescriptor(
292                get_edge_exists(
293                    *this->base(), 0), m_src, m_targ, &get_property(*this->base())
294            );
295        }
296     
297        MatrixIter m_start;
298        VerticesSizeType m_src, m_targ, m_n;
299    };
300
301  } // namespace detail
302
303  //=========================================================================
304  // Adjacency Matrix Traits
305  template <typename Directed = directedS>
306  class adjacency_matrix_traits {
307    typedef typename Directed::is_bidir_t is_bidir;
308    typedef typename Directed::is_directed_t is_directed;
309  public:
310    typedef typename boost::ct_if_t<is_bidir,
311      bidirectional_tag,
312      typename boost::ct_if_t<is_directed,
313        directed_tag, undirected_tag
314      >::type
315    >::type directed_category;
316   
317    typedef disallow_parallel_edge_tag edge_parallel_category;
318   
319    typedef std::size_t vertex_descriptor;
320
321    typedef detail::matrix_edge_desc_impl<directed_category,
322      vertex_descriptor> edge_descriptor;
323  };
324
325  struct adjacency_matrix_class_tag { };
326
327  struct adj_matrix_traversal_tag :
328    public virtual adjacency_matrix_tag,
329    public virtual vertex_list_graph_tag,
330    public virtual incidence_graph_tag,
331    public virtual adjacency_graph_tag,
332    public virtual edge_list_graph_tag { };
333 
334  //=========================================================================
335  // Adjacency Matrix Class
336  template <typename Directed = directedS,
337            typename VertexProperty = no_property,
338            typename EdgeProperty = no_property,
339            typename GraphProperty = no_property,
340            typename Allocator = std::allocator<bool> >
341  class adjacency_matrix {
342    typedef adjacency_matrix self;
343    typedef adjacency_matrix_traits<Directed> Traits;
344   
345  public:
346#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
347    typedef typename detail::retag_property_list<vertex_bundle_t, VertexProperty>::type
348      vertex_property_type;
349    typedef typename detail::retag_property_list<edge_bundle_t, EdgeProperty>::type
350      edge_property_type;
351     
352  private:
353    typedef typename detail::retag_property_list<vertex_bundle_t, VertexProperty>::retagged
354      maybe_vertex_bundled;
355
356    typedef typename detail::retag_property_list<edge_bundle_t, EdgeProperty>::retagged
357      maybe_edge_bundled;
358   
359  public:
360    // The types that are actually bundled
361    typedef typename ct_if<(is_same<maybe_vertex_bundled, no_property>::value),
362                           no_vertex_bundle,
363                           maybe_vertex_bundled>::type vertex_bundled;
364    typedef typename ct_if<(is_same<maybe_edge_bundled, no_property>::value),
365                           no_edge_bundle,
366                           maybe_edge_bundled>::type edge_bundled;
367#else
368    typedef EdgeProperty     edge_property_type;
369    typedef VertexProperty   vertex_property_type;
370    typedef no_vertex_bundle vertex_bundled;
371    typedef no_edge_bundle   edge_bundled;
372#endif
373
374  public: // should be private
375    typedef typename ct_if_t<typename has_property<edge_property_type>::type,
376      std::pair<bool, edge_property_type>, char>::type StoredEdge;
377#if (defined(BOOST_MSVC) && BOOST_MSVC <= 1300) || defined(BOOST_NO_STD_ALLOCATOR)
378    typedef std::vector<StoredEdge> Matrix;
379#else
380    // This causes internal compiler error for MSVC
381    typedef typename Allocator::template rebind<StoredEdge>::other Alloc;
382    typedef std::vector<StoredEdge, Alloc> Matrix;
383#endif
384    typedef typename Matrix::iterator MatrixIter;
385    typedef typename Matrix::size_type size_type;
386  public:
387    // Graph concept required types
388    typedef typename Traits::vertex_descriptor vertex_descriptor;
389    typedef typename Traits::edge_descriptor edge_descriptor;
390    typedef typename Traits::directed_category directed_category;
391    typedef typename Traits::edge_parallel_category edge_parallel_category;
392    typedef adj_matrix_traversal_tag traversal_category;
393
394    static vertex_descriptor null_vertex()
395    {
396      return (std::numeric_limits<vertex_descriptor>::max)();
397    }
398     
399    //private: if friends worked, these would be private
400
401    typedef detail::dir_adj_matrix_out_edge_iter<
402        vertex_descriptor, MatrixIter, size_type, edge_descriptor
403    > DirOutEdgeIter;
404
405    typedef detail::undir_adj_matrix_out_edge_iter<
406        vertex_descriptor, MatrixIter, size_type, edge_descriptor
407    > UnDirOutEdgeIter;
408
409    typedef typename ct_if_t<
410        typename Directed::is_directed_t, DirOutEdgeIter, UnDirOutEdgeIter
411    >::type unfiltered_out_edge_iter;
412   
413    typedef detail::adj_matrix_edge_iter<
414        Directed, MatrixIter, size_type, edge_descriptor
415    > unfiltered_edge_iter;
416   
417  public:
418
419    // IncidenceGraph concept required types
420    typedef filter_iterator<detail::does_edge_exist, unfiltered_out_edge_iter>
421      out_edge_iterator;
422
423    typedef size_type degree_size_type;
424
425    // BidirectionalGraph required types
426    typedef void in_edge_iterator;
427
428    // AdjacencyGraph required types
429     typedef typename adjacency_iterator_generator<self,
430       vertex_descriptor, out_edge_iterator>::type adjacency_iterator;
431
432    // VertexListGraph required types
433    typedef size_type vertices_size_type;
434    typedef integer_range<vertex_descriptor> VertexList;
435    typedef typename VertexList::iterator vertex_iterator;
436
437    // EdgeListGrpah required types
438    typedef size_type edges_size_type;
439    typedef filter_iterator<
440        detail::does_edge_exist, unfiltered_edge_iter
441    > edge_iterator;
442
443    // PropertyGraph required types
444    typedef adjacency_matrix_class_tag graph_tag;
445
446    // Constructor required by MutableGraph
447    adjacency_matrix(vertices_size_type n_vertices)
448      : m_matrix(Directed::is_directed ?
449                 (n_vertices * n_vertices)
450                 : (n_vertices * (n_vertices + 1) / 2)),
451      m_vertex_set(0, n_vertices),
452      m_vertex_properties(n_vertices),
453      m_num_edges(0) { }
454
455#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
456    // Directly access a vertex or edge bundle
457    vertex_bundled& operator[](vertex_descriptor v)
458    { return get(vertex_bundle, *this)[v]; }
459
460    const vertex_bundled& operator[](vertex_descriptor v) const
461    { return get(vertex_bundle, *this)[v]; }
462
463    edge_bundled& operator[](edge_descriptor e)
464    { return get(edge_bundle, *this)[e]; }
465
466    const edge_bundled& operator[](edge_descriptor e) const
467    { return get(edge_bundle, *this)[e]; }
468#endif
469   
470    //private: if friends worked, these would be private
471
472    typename Matrix::const_reference
473    get_edge(vertex_descriptor u, vertex_descriptor v) const {
474      if (Directed::is_directed)
475        return m_matrix[u * m_vertex_set.size() + v];
476      else {
477        if (v > u)
478          std::swap(u, v);
479        return m_matrix[u * (u + 1)/2 + v];
480      }
481    }
482    typename Matrix::reference
483    get_edge(vertex_descriptor u, vertex_descriptor v) {
484      if (Directed::is_directed)
485        return m_matrix[u * m_vertex_set.size() + v];
486      else {
487        if (v > u)
488          std::swap(u, v);
489        return m_matrix[u * (u + 1)/2 + v];
490      }
491    }
492
493    Matrix m_matrix;
494    VertexList m_vertex_set;
495    std::vector<vertex_property_type> m_vertex_properties;
496    size_type m_num_edges;
497  };
498 
499  //=========================================================================
500  // Functions required by the AdjacencyMatrix concept
501
502  template <typename D, typename VP, typename EP, typename GP, typename A>
503  std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor,
504            bool>
505  edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
506       typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v,
507       const adjacency_matrix<D,VP,EP,GP,A>& g)
508  {
509    bool exists = detail::get_edge_exists(g.get_edge(u,v), 0);
510    typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor
511      e(exists, u, v, &detail::get_property(g.get_edge(u,v)));
512    return std::make_pair(e, exists);
513  }
514
515  //=========================================================================
516  // Functions required by the IncidenceGraph concept
517
518  // O(1)
519  template <typename VP, typename EP, typename GP, typename A>
520  std::pair<typename adjacency_matrix<directedS,VP,EP,GP,A>::out_edge_iterator,
521            typename adjacency_matrix<directedS,VP,EP,GP,A>::out_edge_iterator>
522  out_edges
523    (typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_descriptor u,
524     const adjacency_matrix<directedS,VP,EP,GP,A>& g_)
525  {
526    typedef adjacency_matrix<directedS,VP,EP,GP,A> Graph;
527    Graph& g = const_cast<Graph&>(g_);
528    typename Graph::vertices_size_type offset = u * g.m_vertex_set.size();
529    typename Graph::MatrixIter f = g.m_matrix.begin() + offset;
530    typename Graph::MatrixIter l = f + g.m_vertex_set.size();
531    typename Graph::unfiltered_out_edge_iter
532          first(f, u, g.m_vertex_set.size())
533        , last(l, u, g.m_vertex_set.size());
534    detail::does_edge_exist pred;
535    typedef typename Graph::out_edge_iterator out_edge_iterator;
536    return std::make_pair(out_edge_iterator(pred, first, last),
537                          out_edge_iterator(pred, last, last));
538  }
539
540  // O(1)
541  template <typename VP, typename EP, typename GP, typename A>
542  std::pair<
543    typename adjacency_matrix<undirectedS,VP,EP,GP,A>::out_edge_iterator,
544    typename adjacency_matrix<undirectedS,VP,EP,GP,A>::out_edge_iterator>
545  out_edges
546    (typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_descriptor u,
547     const adjacency_matrix<undirectedS,VP,EP,GP,A>& g_)
548  {
549    typedef adjacency_matrix<undirectedS,VP,EP,GP,A> Graph;
550    Graph& g = const_cast<Graph&>(g_);
551    typename Graph::vertices_size_type offset = u * (u + 1) / 2;
552    typename Graph::MatrixIter f = g.m_matrix.begin() + offset;
553    typename Graph::MatrixIter l = g.m_matrix.end();
554
555    typename Graph::unfiltered_out_edge_iter
556        first(f, u, g.m_vertex_set.size())
557      , last(l, u, g.m_vertex_set.size());
558   
559    detail::does_edge_exist pred;
560    typedef typename Graph::out_edge_iterator out_edge_iterator;
561    return std::make_pair(out_edge_iterator(pred, first, last),
562                          out_edge_iterator(pred, last, last));
563  }
564 
565  // O(N)
566  template <typename D, typename VP, typename EP, typename GP, typename A> 
567  typename adjacency_matrix<D,VP,EP,GP,A>::degree_size_type
568  out_degree(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
569             const adjacency_matrix<D,VP,EP,GP,A>& g)
570  {
571    typename adjacency_matrix<D,VP,EP,GP,A>::degree_size_type n = 0;
572    typename adjacency_matrix<D,VP,EP,GP,A>::out_edge_iterator f, l;
573    for (tie(f, l) = out_edges(u, g); f != l; ++f)
574      ++n;
575    return n;
576  }
577
578  // O(1)
579  template <typename D, typename VP, typename EP, typename GP, typename A,
580    typename Dir, typename Vertex> 
581  typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor
582  source(const detail::matrix_edge_desc_impl<Dir,Vertex>& e,
583         const adjacency_matrix<D,VP,EP,GP,A>&)
584  {
585    return e.m_source;
586  }
587
588  // O(1)
589  template <typename D, typename VP, typename EP, typename GP, typename A,
590    typename Dir, typename Vertex> 
591  typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor
592  target(const detail::matrix_edge_desc_impl<Dir,Vertex>& e,
593         const adjacency_matrix<D,VP,EP,GP,A>&)
594  {
595    return e.m_target;
596  }
597
598  //=========================================================================
599  // Functions required by the AdjacencyGraph concept
600
601  template <typename D, typename VP, typename EP, typename GP, typename A>
602  std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::adjacency_iterator,
603            typename adjacency_matrix<D,VP,EP,GP,A>::adjacency_iterator>
604  adjacent_vertices
605    (typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
606     const adjacency_matrix<D,VP,EP,GP,A>& g_)
607  {
608      typedef adjacency_matrix<D,VP,EP,GP,A> Graph;
609      const Graph& cg = static_cast<const Graph&>(g_);
610      Graph& g = const_cast<Graph&>(cg);
611      typedef typename Graph::adjacency_iterator adjacency_iterator;
612      typename Graph::out_edge_iterator first, last;
613      boost::tie(first, last) = out_edges(u, g);
614      return std::make_pair(adjacency_iterator(first, &g),
615                            adjacency_iterator(last, &g));
616  }
617
618  //=========================================================================
619  // Functions required by the VertexListGraph concept
620
621  template <typename D, typename VP, typename EP, typename GP, typename A>
622  std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::vertex_iterator,
623            typename adjacency_matrix<D,VP,EP,GP,A>::vertex_iterator>
624  vertices(const adjacency_matrix<D,VP,EP,GP,A>& g_) {
625    typedef adjacency_matrix<D,VP,EP,GP,A> Graph;
626    Graph& g = const_cast<Graph&>(g_);
627    return std::make_pair(g.m_vertex_set.begin(), g.m_vertex_set.end());
628  }
629
630  template <typename D, typename VP, typename EP, typename GP, typename A>
631  typename adjacency_matrix<D,VP,EP,GP,A>::vertices_size_type
632  num_vertices(const adjacency_matrix<D,VP,EP,GP,A>& g) {
633    return g.m_vertex_set.size();
634  }
635 
636  //=========================================================================
637  // Functions required by the EdgeListGraph concept
638 
639  template <typename D, typename VP, typename EP, typename GP, typename A>
640  std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_iterator,
641            typename adjacency_matrix<D,VP,EP,GP,A>::edge_iterator>
642  edges(const adjacency_matrix<D,VP,EP,GP,A>& g_)
643  {
644    typedef adjacency_matrix<D,VP,EP,GP,A> Graph;
645    Graph& g = const_cast<Graph&>(g_);
646   
647    typename Graph::unfiltered_edge_iter
648      first(g.m_matrix.begin(), g.m_matrix.begin(),
649                                    g.m_vertex_set.size()),
650      last(g.m_matrix.end(), g.m_matrix.begin(),
651                                    g.m_vertex_set.size());
652    detail::does_edge_exist pred;
653    typedef typename Graph::edge_iterator edge_iterator;
654    return std::make_pair(edge_iterator(pred, first, last),
655                          edge_iterator(pred, last, last));
656  }
657
658  // O(1)
659  template <typename D, typename VP, typename EP, typename GP, typename A>
660  typename adjacency_matrix<D,VP,EP,GP,A>::edges_size_type
661  num_edges(const adjacency_matrix<D,VP,EP,GP,A>& g)
662  {
663    return g.m_num_edges;
664  }
665 
666  //=========================================================================
667  // Functions required by the MutableGraph concept
668
669  // O(1)
670  template <typename D, typename VP, typename EP, typename GP, typename A>
671  std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor, bool>
672  add_edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
673           typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v,
674           const EP& ep,
675           adjacency_matrix<D,VP,EP,GP,A>& g)
676  {
677    typedef typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor
678      edge_descriptor;
679    if (detail::get_edge_exists(g.get_edge(u,v), 0) == false) {
680      ++(g.m_num_edges);
681      detail::set_property(g.get_edge(u,v), ep, 0);
682      detail::set_edge_exists(g.get_edge(u,v), true, 0);
683      return std::make_pair
684        (edge_descriptor(true, u, v, &detail::get_property(g.get_edge(u,v))),
685         true);
686    } else
687      return std::make_pair
688        (edge_descriptor(true, u, v, &detail::get_property(g.get_edge(u,v))),
689         false);
690  }
691  // O(1)
692  template <typename D, typename VP, typename EP, typename GP, typename A>
693  std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor, bool>
694  add_edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
695           typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v,
696           adjacency_matrix<D,VP,EP,GP,A>& g)
697  {
698    EP ep;
699    return add_edge(u, v, ep, g);
700  }
701
702  // O(1) 
703  template <typename D, typename VP, typename EP, typename GP, typename A>
704  void
705  remove_edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
706              typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v,
707              adjacency_matrix<D,VP,EP,GP,A>& g)
708  {
709    --(g.m_num_edges);
710    detail::set_edge_exists(g.get_edge(u,v), false, 0);
711  }
712
713  // O(1)
714  template <typename D, typename VP, typename EP, typename GP, typename A>
715  void
716  remove_edge(typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor e,
717              adjacency_matrix<D,VP,EP,GP,A>& g)
718  {
719    remove_edge(source(e, g), target(e, g), g);
720  }
721
722 
723  template <typename D, typename VP, typename EP, typename GP, typename A>
724  inline typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor
725  add_vertex(adjacency_matrix<D,VP,EP,GP,A>& g) {
726    // UNDER CONSTRUCTION
727    assert(false);
728    return *vertices(g).first;
729  }
730
731  template <typename D, typename VP, typename EP, typename GP, typename A>
732  inline typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor
733  add_vertex(const VP& vp, adjacency_matrix<D,VP,EP,GP,A>& g) {
734    // UNDER CONSTRUCTION
735    assert(false);
736    return *vertices(g).first;
737  }
738
739  template <typename D, typename VP, typename EP, typename GP, typename A>
740  inline void
741  remove_vertex(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
742                adjacency_matrix<D,VP,EP,GP,A>& g)
743  {
744    // UNDER CONSTRUCTION
745    assert(false);
746  }
747
748  // O(V)
749  template <typename VP, typename EP, typename GP, typename A>
750  void
751  clear_vertex
752    (typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_descriptor u,
753     adjacency_matrix<directedS,VP,EP,GP,A>& g)
754  {
755    typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_iterator
756      vi, vi_end;
757    for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
758      remove_edge(u, *vi, g);
759    for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
760      remove_edge(*vi, u, g);
761  }
762
763  // O(V)
764  template <typename VP, typename EP, typename GP, typename A>
765  void
766  clear_vertex
767    (typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_descriptor u,
768     adjacency_matrix<undirectedS,VP,EP,GP,A>& g)
769  {
770    typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_iterator
771      vi, vi_end;
772    for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
773      remove_edge(u, *vi, g);
774  }
775
776  //=========================================================================
777  // Vertex Property Map
778 
779  template <typename GraphPtr, typename Vertex, typename T, typename R,
780    typename Tag>
781  class adj_matrix_vertex_property_map
782    : public put_get_helper<R,
783         adj_matrix_vertex_property_map<GraphPtr, Vertex, T, R, Tag> >
784  {
785  public:
786    typedef T value_type;
787    typedef R reference;
788    typedef Vertex key_type;
789    typedef boost::lvalue_property_map_tag category;
790    adj_matrix_vertex_property_map() { }
791    adj_matrix_vertex_property_map(GraphPtr g) : m_g(g) { }
792    inline reference operator[](key_type v) const {
793      return get_property_value(m_g->m_vertex_properties[v], Tag());
794    }
795    GraphPtr m_g;
796  };
797
798  template <class Property, class Vertex>
799  struct adj_matrix_vertex_id_map
800    : public boost::put_get_helper<Vertex,
801        adj_matrix_vertex_id_map<Property, Vertex> >
802  {
803    typedef Vertex value_type;
804    typedef Vertex reference;
805    typedef Vertex key_type;
806    typedef boost::readable_property_map_tag category;
807     adj_matrix_vertex_id_map() { }
808    template <class Graph>
809    inline adj_matrix_vertex_id_map(const Graph&) { }
810    inline value_type operator[](key_type v) const { return v; }
811  };
812
813  namespace detail {
814
815    struct adj_matrix_any_vertex_pa {
816      template <class Tag, class Graph, class Property>
817      struct bind_ {
818        typedef typename property_value<Property,Tag>::type Value;
819        typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
820       
821        typedef adj_matrix_vertex_property_map<Graph*, Vertex, Value, Value&,
822          Tag> type;
823        typedef adj_matrix_vertex_property_map<const Graph*, Vertex, Value,
824          const Value&, Tag> const_type;
825      };
826    };
827    struct adj_matrix_id_vertex_pa {
828      template <class Tag, class Graph, class Property>
829      struct bind_ {
830        typedef typename Graph::vertex_descriptor Vertex;
831        typedef adj_matrix_vertex_id_map<Property, Vertex> type;
832        typedef adj_matrix_vertex_id_map<Property, Vertex> const_type;
833      };
834    };
835
836    template <class Tag>
837    struct adj_matrix_choose_vertex_pa_helper {
838      typedef adj_matrix_any_vertex_pa type;
839    };
840    template <>
841    struct adj_matrix_choose_vertex_pa_helper<vertex_index_t> {
842      typedef adj_matrix_id_vertex_pa type;
843    };
844
845    template <class Tag, class Graph, class Property>
846    struct adj_matrix_choose_vertex_pa {
847      typedef typename adj_matrix_choose_vertex_pa_helper<Tag>::type Helper;
848      typedef typename Helper::template bind_<Tag,Graph,Property> Bind;
849      typedef typename Bind::type type;
850      typedef typename Bind::const_type const_type;
851    };
852
853    struct adj_matrix_vertex_property_selector {
854      template <class Graph, class Property, class Tag>
855      struct bind_ {
856        typedef adj_matrix_choose_vertex_pa<Tag,Graph,Property> Choice;
857        typedef typename Choice::type type;
858        typedef typename Choice::const_type const_type;
859      };
860    };
861
862  } // namespace detail
863
864  template <>
865  struct vertex_property_selector<adjacency_matrix_class_tag> {
866    typedef detail::adj_matrix_vertex_property_selector type;
867  };
868 
869  //=========================================================================
870  // Edge Property Map
871
872
873  template <typename Directed, typename Property, typename Vertex,
874    typename T, typename R, typename Tag>
875  class adj_matrix_edge_property_map
876    : public put_get_helper<R,
877         adj_matrix_edge_property_map<Directed, Property, Vertex, T, R, Tag> >
878  {
879  public:
880    typedef T value_type;
881    typedef R reference;
882    typedef detail::matrix_edge_desc_impl<Directed, Vertex> key_type;
883    typedef boost::lvalue_property_map_tag category;
884    inline reference operator[](key_type e) const {
885      Property& p = *(Property*)e.get_property();
886      return get_property_value(p, Tag());
887    }
888  };
889  struct adj_matrix_edge_property_selector {
890    template <class Graph, class Property, class Tag>
891    struct bind_ {
892      typedef typename property_value<Property,Tag>::type T;
893      typedef typename Graph::vertex_descriptor Vertex;
894      typedef adj_matrix_edge_property_map<typename Graph::directed_category,
895        Property, Vertex, T, T&, Tag> type;
896      typedef adj_matrix_edge_property_map<typename Graph::directed_category,
897        Property, Vertex, T, const T&, Tag> const_type;
898    };
899  };
900  template <>
901  struct edge_property_selector<adjacency_matrix_class_tag> {
902    typedef adj_matrix_edge_property_selector type;
903  };
904
905  //=========================================================================
906  // Functions required by PropertyGraph
907
908  namespace detail {
909
910    template <typename Property, typename D, typename VP, typename EP,
911              typename GP, typename A>
912    typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
913      Property>::type
914    get_dispatch(adjacency_matrix<D,VP,EP,GP,A>& g, Property,
915                 vertex_property_tag)
916    {
917      typedef adjacency_matrix<D,VP,EP,GP,A> Graph;
918      typedef typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
919        Property>::type PA;
920      return PA(&g);
921    }
922    template <typename Property, typename D, typename VP, typename EP,
923              typename GP, typename A>
924    typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
925      Property>::type
926    get_dispatch(adjacency_matrix<D,VP,EP,GP,A>&, Property,
927                 edge_property_tag)
928    {
929      typedef typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
930        Property>::type PA;
931      return PA();
932    }
933    template <typename Property, typename D, typename VP, typename EP,
934              typename GP, typename A>
935    typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
936      Property>::const_type
937    get_dispatch(const adjacency_matrix<D,VP,EP,GP,A>& g, Property,
938                 vertex_property_tag)
939    {
940      typedef adjacency_matrix<D,VP,EP,GP,A> Graph;
941      typedef typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
942        Property>::const_type PA;
943      return PA(&g);
944    }
945    template <typename Property, typename D, typename VP, typename EP,
946              typename GP, typename A>
947    typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
948      Property>::const_type
949    get_dispatch(const adjacency_matrix<D,VP,EP,GP,A>&, Property,
950                 edge_property_tag)
951    {
952      typedef typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
953        Property>::const_type PA;
954      return PA();
955    }
956
957  } // namespace detail
958
959  template <typename Property, typename D, typename VP, typename EP,
960            typename GP, typename A>
961  inline
962  typename property_map<adjacency_matrix<D,VP,EP,GP,A>, Property>::type
963  get(Property p, adjacency_matrix<D,VP,EP,GP,A>& g)
964  {
965    typedef typename property_kind<Property>::type Kind;
966    return detail::get_dispatch(g, p, Kind());
967  }
968
969  template <typename Property, typename D, typename VP, typename EP,
970            typename GP, typename A>
971  inline
972  typename property_map<adjacency_matrix<D,VP,EP,GP,A>, Property>::const_type
973  get(Property p, const adjacency_matrix<D,VP,EP,GP,A>& g)
974  {
975    typedef typename property_kind<Property>::type Kind;
976    return detail::get_dispatch(g, p, Kind());
977  }
978
979  template <typename Property, typename D, typename VP, typename EP,
980            typename GP, typename A, typename Key>
981  inline
982  typename property_traits<
983    typename property_map<adjacency_matrix<D,VP,EP,GP,A>, Property>::const_type
984  >::value_type
985  get(Property p, const adjacency_matrix<D,VP,EP,GP,A>& g,
986      const Key& key)
987  {
988    return get(get(p, g), key);
989  }
990
991  template <typename Property, typename D, typename VP, typename EP,
992            typename GP, typename A, typename Key, typename Value>
993  inline void
994  put(Property p, adjacency_matrix<D,VP,EP,GP,A>& g,
995      const Key& key, const Value& value)
996  {
997    typedef adjacency_matrix<D,VP,EP,GP,A> Graph;
998    typedef typename boost::property_map<Graph, Property>::type Map;
999    Map pmap = get(p, g);
1000    put(pmap, key, value);
1001  }
1002 
1003  //=========================================================================
1004  // Other Functions
1005
1006  template <typename D, typename VP, typename EP, typename GP, typename A> 
1007  typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor
1008  vertex(typename adjacency_matrix<D,VP,EP,GP,A>::vertices_size_type n,
1009         const adjacency_matrix<D,VP,EP,GP,A>& g)
1010  {
1011    return n;
1012  }
1013
1014  // Support for bundled properties
1015#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
1016  template <typename Directed, typename VertexProperty, typename EdgeProperty, typename GraphProperty,
1017            typename Allocator, typename T, typename Bundle>
1018  inline
1019  typename property_map<adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>,
1020                        T Bundle::*>::type
1021  get(T Bundle::* p, adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>& g)
1022  {
1023    typedef typename property_map<adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>,
1024                                  T Bundle::*>::type
1025      result_type;
1026    return result_type(&g, p);
1027  }
1028
1029  template <typename Directed, typename VertexProperty, typename EdgeProperty, typename GraphProperty,
1030            typename Allocator, typename T, typename Bundle>
1031  inline
1032  typename property_map<adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>,
1033                        T Bundle::*>::const_type
1034  get(T Bundle::* p, adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator> const & g)
1035  {
1036    typedef typename property_map<adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>,
1037                                  T Bundle::*>::const_type
1038      result_type;
1039    return result_type(&g, p);
1040  }
1041   
1042  template <typename Directed, typename VertexProperty, typename EdgeProperty, typename GraphProperty,
1043            typename Allocator, typename T, typename Bundle, typename Key>
1044  inline T
1045  get(T Bundle::* p, adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator> const & g,
1046      const Key& key)
1047  {
1048    return get(get(p, g), key);
1049  }
1050
1051  template <typename Directed, typename VertexProperty, typename EdgeProperty, typename GraphProperty,
1052            typename Allocator, typename T, typename Bundle, typename Key>
1053  inline void
1054  put(T Bundle::* p, adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>& g,
1055      const Key& key, const T& value)
1056  {
1057    put(get(p, g), key, value);
1058  }
1059
1060#endif
1061
1062} // namespace boost
1063
1064#endif // BOOST_ADJACENCY_MATRIX_HPP
Note: See TracBrowser for help on using the repository browser.