1 //=======================================================================
2 // Copyright 2001 University of Notre Dame.
3 // Copyright 2006 Trustees of Indiana University
4 // Authors: Jeremy G. Siek and Douglas Gregor <dgregor@cs.indiana.edu>
6 // Distributed under the Boost Software License, Version 1.0. (See
7 // accompanying file LICENSE_1_0.txt or copy at
8 // http://www.boost.org/LICENSE_1_0.txt)
9 //=======================================================================
11 #ifndef BOOST_ADJACENCY_MATRIX_HPP
12 #define BOOST_ADJACENCY_MATRIX_HPP
14 #include <boost/config.hpp>
18 #include <boost/limits.hpp>
19 #include <boost/iterator.hpp>
20 #include <boost/graph/graph_traits.hpp>
21 #include <boost/graph/graph_selectors.hpp>
22 #include <boost/pending/ct_if.hpp>
23 #include <boost/graph/adjacency_iterator.hpp>
24 #include <boost/graph/detail/edge.hpp>
25 #include <boost/iterator/iterator_adaptor.hpp>
26 #include <boost/iterator/filter_iterator.hpp>
27 #include <boost/pending/integer_range.hpp>
28 #include <boost/graph/properties.hpp>
29 #include <boost/tuple/tuple.hpp>
30 #include <boost/static_assert.hpp>
31 #include <boost/type_traits/ice.hpp>
37 template <class Directed, class Vertex>
38 class matrix_edge_desc_impl : public edge_desc_impl<Directed,Vertex>
40 typedef edge_desc_impl<Directed,Vertex> Base;
42 matrix_edge_desc_impl() { }
43 matrix_edge_desc_impl(bool exists, Vertex s, Vertex d,
45 : Base(s, d, ep), m_exists(exists) { }
46 bool exists() const { return m_exists; }
51 struct does_edge_exist {
53 bool operator()(const Edge& e) const { return e.exists(); }
56 template <typename EdgeProperty>
57 bool get_edge_exists(const std::pair<bool, EdgeProperty>& stored_edge, int) {
58 return stored_edge.first;
60 template <typename EdgeProperty>
62 std::pair<bool, EdgeProperty>& stored_edge,
66 stored_edge.first = flag;
69 template <typename EdgeProxy>
70 bool get_edge_exists(const EdgeProxy& edge_proxy, ...) {
73 template <typename EdgeProxy>
74 EdgeProxy& set_edge_exists(EdgeProxy& edge_proxy, bool flag, ...) {
76 return edge_proxy; // just to avoid never used warning
81 template <typename EdgeProperty>
83 get_property(const std::pair<bool, EdgeProperty>& stored_edge) {
84 return stored_edge.second;
86 template <typename EdgeProperty>
88 get_property(std::pair<bool, EdgeProperty>& stored_edge) {
89 return stored_edge.second;
92 template <typename StoredEdgeProperty, typename EdgeProperty>
94 set_property(std::pair<bool, StoredEdgeProperty>& stored_edge,
95 const EdgeProperty& ep, int) {
96 stored_edge.second = ep;
99 inline const no_property& get_property(const char&) {
100 static no_property s_prop;
103 inline no_property& get_property(char&) {
104 static no_property s_prop;
107 template <typename EdgeProxy, typename EdgeProperty>
109 set_property(EdgeProxy, const EdgeProperty&, ...) {}
111 //=======================================================================
112 // Directed Out Edge Iterator
115 typename VertexDescriptor, typename MatrixIter
116 , typename VerticesSizeType, typename EdgeDescriptor
118 struct dir_adj_matrix_out_edge_iter
120 dir_adj_matrix_out_edge_iter<VertexDescriptor, MatrixIter, VerticesSizeType, EdgeDescriptor>
128 typedef iterator_adaptor<
129 dir_adj_matrix_out_edge_iter<VertexDescriptor, MatrixIter, VerticesSizeType, EdgeDescriptor>
137 dir_adj_matrix_out_edge_iter() { }
139 dir_adj_matrix_out_edge_iter(
141 , const VertexDescriptor& src
142 , const VerticesSizeType& n
144 : super_t(i), m_src(src), m_targ(0), m_n(n)
148 ++this->base_reference();
152 inline EdgeDescriptor
155 return EdgeDescriptor(get_edge_exists(*this->base(), 0), m_src, m_targ,
156 &get_property(*this->base()));
158 VertexDescriptor m_src, m_targ;
159 VerticesSizeType m_n;
162 //=======================================================================
163 // Directed In Edge Iterator
166 typename VertexDescriptor, typename MatrixIter
167 , typename VerticesSizeType, typename EdgeDescriptor
169 struct dir_adj_matrix_in_edge_iter
171 dir_adj_matrix_in_edge_iter<VertexDescriptor, MatrixIter, VerticesSizeType, EdgeDescriptor>
179 typedef iterator_adaptor<
180 dir_adj_matrix_in_edge_iter<VertexDescriptor, MatrixIter, VerticesSizeType, EdgeDescriptor>
188 dir_adj_matrix_in_edge_iter() { }
190 dir_adj_matrix_in_edge_iter(
192 , const MatrixIter& last
193 , const VertexDescriptor& tgt
194 , const VerticesSizeType& n
196 : super_t(i), m_last(last), m_src(0), m_targ(tgt), m_n(n)
200 if (VerticesSizeType(m_last - this->base_reference()) >= m_n) {
201 this->base_reference() += m_n;
204 this->base_reference() = m_last;
208 inline EdgeDescriptor
211 return EdgeDescriptor(get_edge_exists(*this->base(), 0), m_src, m_targ,
212 &get_property(*this->base()));
215 VertexDescriptor m_src, m_targ;
216 VerticesSizeType m_n;
219 //=======================================================================
220 // Undirected Out Edge Iterator
223 typename VertexDescriptor, typename MatrixIter
224 , typename VerticesSizeType, typename EdgeDescriptor
226 struct undir_adj_matrix_out_edge_iter
228 undir_adj_matrix_out_edge_iter<VertexDescriptor, MatrixIter, VerticesSizeType, EdgeDescriptor>
236 typedef iterator_adaptor<
237 undir_adj_matrix_out_edge_iter<VertexDescriptor, MatrixIter, VerticesSizeType, EdgeDescriptor>
245 undir_adj_matrix_out_edge_iter() { }
247 undir_adj_matrix_out_edge_iter(
249 , const VertexDescriptor& src
250 , const VerticesSizeType& n
252 : super_t(i), m_src(src), m_inc(src), m_targ(0), m_n(n)
257 if (m_targ < m_src) // first half
259 ++this->base_reference();
261 else if (m_targ < m_n - 1)
264 this->base_reference() += m_inc;
268 this->base_reference() += m_n - m_src;
273 inline EdgeDescriptor
276 return EdgeDescriptor(
277 get_edge_exists(*this->base(), 0), m_src, m_targ
278 , &get_property(*this->base())
282 VertexDescriptor m_src, m_inc, m_targ;
283 VerticesSizeType m_n;
286 //=======================================================================
287 // Undirected In Edge Iterator
290 typename VertexDescriptor, typename MatrixIter
291 , typename VerticesSizeType, typename EdgeDescriptor
293 struct undir_adj_matrix_in_edge_iter
295 undir_adj_matrix_in_edge_iter<VertexDescriptor, MatrixIter, VerticesSizeType, EdgeDescriptor>
303 typedef iterator_adaptor<
304 undir_adj_matrix_in_edge_iter<VertexDescriptor, MatrixIter, VerticesSizeType, EdgeDescriptor>
312 undir_adj_matrix_in_edge_iter() { }
314 undir_adj_matrix_in_edge_iter(
316 , const VertexDescriptor& src
317 , const VerticesSizeType& n
319 : super_t(i), m_src(src), m_inc(src), m_targ(0), m_n(n)
324 if (m_targ < m_src) // first half
326 ++this->base_reference();
328 else if (m_targ < m_n - 1)
331 this->base_reference() += m_inc;
335 this->base_reference() += m_n - m_src;
340 inline EdgeDescriptor
343 return EdgeDescriptor(
344 get_edge_exists(*this->base(), 0), m_targ, m_src
345 , &get_property(*this->base())
349 VertexDescriptor m_src, m_inc, m_targ;
350 VerticesSizeType m_n;
353 //=======================================================================
356 template <typename Directed, typename MatrixIter,
357 typename VerticesSizeType, typename EdgeDescriptor>
358 struct adj_matrix_edge_iter
360 adj_matrix_edge_iter<Directed, MatrixIter, VerticesSizeType, EdgeDescriptor>
368 typedef iterator_adaptor<
369 adj_matrix_edge_iter<Directed, MatrixIter, VerticesSizeType, EdgeDescriptor>
377 adj_matrix_edge_iter() { }
379 adj_matrix_edge_iter(const MatrixIter& i, const MatrixIter& start, const VerticesSizeType& n)
380 : super_t(i), m_start(start), m_src(0), m_targ(0), m_n(n) { }
384 increment_dispatch(this->base_reference(), Directed());
387 void increment_dispatch(MatrixIter& i, directedS)
390 if (m_targ == m_n - 1)
401 void increment_dispatch(MatrixIter& i, undirectedS)
415 inline EdgeDescriptor
418 return EdgeDescriptor(
420 *this->base(), 0), m_src, m_targ, &get_property(*this->base())
425 VerticesSizeType m_src, m_targ, m_n;
428 } // namespace detail
430 //=========================================================================
431 // Adjacency Matrix Traits
432 template <typename Directed = directedS>
433 class adjacency_matrix_traits {
434 typedef typename Directed::is_directed_t is_directed;
436 // The bidirectionalS tag is not allowed with the adjacency_matrix
437 // graph type. Instead, use directedS, which also provides the
438 // functionality required for a Bidirectional Graph (in_edges,
440 #if !defined(_MSC_VER) || _MSC_VER > 1300
441 BOOST_STATIC_ASSERT(type_traits::ice_not<(is_same<Directed, bidirectionalS>::value)>::value);
444 typedef typename boost::ct_if_t<is_directed,
445 bidirectional_tag, undirected_tag>::type
448 typedef disallow_parallel_edge_tag edge_parallel_category;
450 typedef std::size_t vertex_descriptor;
452 typedef detail::matrix_edge_desc_impl<directed_category,
453 vertex_descriptor> edge_descriptor;
456 struct adjacency_matrix_class_tag { };
458 struct adj_matrix_traversal_tag :
459 public virtual adjacency_matrix_tag,
460 public virtual vertex_list_graph_tag,
461 public virtual incidence_graph_tag,
462 public virtual adjacency_graph_tag,
463 public virtual edge_list_graph_tag { };
465 //=========================================================================
466 // Adjacency Matrix Class
467 template <typename Directed = directedS,
468 typename VertexProperty = no_property,
469 typename EdgeProperty = no_property,
470 typename GraphProperty = no_property,
471 typename Allocator = std::allocator<bool> >
472 class adjacency_matrix {
473 typedef adjacency_matrix self;
474 typedef adjacency_matrix_traits<Directed> Traits;
477 #if !defined(BOOST_MSVC) || BOOST_MSVC > 1300
478 // The bidirectionalS tag is not allowed with the adjacency_matrix
479 // graph type. Instead, use directedS, which also provides the
480 // functionality required for a Bidirectional Graph (in_edges,
482 BOOST_STATIC_ASSERT(!(is_same<Directed, bidirectionalS>::value));
485 #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
486 typedef typename detail::retag_property_list<vertex_bundle_t, VertexProperty>::type
487 vertex_property_type;
488 typedef typename detail::retag_property_list<edge_bundle_t, EdgeProperty>::type
492 typedef typename detail::retag_property_list<vertex_bundle_t, VertexProperty>::retagged
493 maybe_vertex_bundled;
495 typedef typename detail::retag_property_list<edge_bundle_t, EdgeProperty>::retagged
499 // The types that are actually bundled
500 typedef typename ct_if<(is_same<maybe_vertex_bundled, no_property>::value),
502 maybe_vertex_bundled>::type vertex_bundled;
503 typedef typename ct_if<(is_same<maybe_edge_bundled, no_property>::value),
505 maybe_edge_bundled>::type edge_bundled;
507 typedef EdgeProperty edge_property_type;
508 typedef VertexProperty vertex_property_type;
509 typedef no_vertex_bundle vertex_bundled;
510 typedef no_edge_bundle edge_bundled;
513 public: // should be private
514 typedef typename ct_if_t<typename has_property<edge_property_type>::type,
515 std::pair<bool, edge_property_type>, char>::type StoredEdge;
516 #if (defined(BOOST_MSVC) && BOOST_MSVC <= 1300) || defined(BOOST_NO_STD_ALLOCATOR)
517 typedef std::vector<StoredEdge> Matrix;
519 // This causes internal compiler error for MSVC
520 typedef typename Allocator::template rebind<StoredEdge>::other Alloc;
521 typedef std::vector<StoredEdge, Alloc> Matrix;
523 typedef typename Matrix::iterator MatrixIter;
524 typedef typename Matrix::size_type size_type;
526 // Graph concept required types
527 typedef typename Traits::vertex_descriptor vertex_descriptor;
528 typedef typename Traits::edge_descriptor edge_descriptor;
529 typedef typename Traits::directed_category directed_category;
530 typedef typename Traits::edge_parallel_category edge_parallel_category;
531 typedef adj_matrix_traversal_tag traversal_category;
533 static vertex_descriptor null_vertex()
535 return (std::numeric_limits<vertex_descriptor>::max)();
538 //private: if friends worked, these would be private
540 typedef detail::dir_adj_matrix_out_edge_iter<
541 vertex_descriptor, MatrixIter, size_type, edge_descriptor
544 typedef detail::undir_adj_matrix_out_edge_iter<
545 vertex_descriptor, MatrixIter, size_type, edge_descriptor
548 typedef typename ct_if_t<
549 typename Directed::is_directed_t, DirOutEdgeIter, UnDirOutEdgeIter
550 >::type unfiltered_out_edge_iter;
552 typedef detail::dir_adj_matrix_in_edge_iter<
553 vertex_descriptor, MatrixIter, size_type, edge_descriptor
556 typedef detail::undir_adj_matrix_in_edge_iter<
557 vertex_descriptor, MatrixIter, size_type, edge_descriptor
560 typedef typename ct_if_t<
561 typename Directed::is_directed_t, DirInEdgeIter, UnDirInEdgeIter
562 >::type unfiltered_in_edge_iter;
564 typedef detail::adj_matrix_edge_iter<
565 Directed, MatrixIter, size_type, edge_descriptor
566 > unfiltered_edge_iter;
570 // IncidenceGraph concept required types
571 typedef filter_iterator<detail::does_edge_exist, unfiltered_out_edge_iter>
574 typedef size_type degree_size_type;
576 // BidirectionalGraph required types
577 typedef filter_iterator<detail::does_edge_exist, unfiltered_in_edge_iter>
580 // AdjacencyGraph required types
581 typedef typename adjacency_iterator_generator<self,
582 vertex_descriptor, out_edge_iterator>::type adjacency_iterator;
584 // VertexListGraph required types
585 typedef size_type vertices_size_type;
586 typedef integer_range<vertex_descriptor> VertexList;
587 typedef typename VertexList::iterator vertex_iterator;
589 // EdgeListGraph required types
590 typedef size_type edges_size_type;
591 typedef filter_iterator<
592 detail::does_edge_exist, unfiltered_edge_iter
595 // PropertyGraph required types
596 typedef adjacency_matrix_class_tag graph_tag;
598 // Constructor required by MutableGraph
599 adjacency_matrix(vertices_size_type n_vertices)
600 : m_matrix(Directed::is_directed ?
601 (n_vertices * n_vertices)
602 : (n_vertices * (n_vertices + 1) / 2)),
603 m_vertex_set(0, n_vertices),
604 m_vertex_properties(n_vertices),
607 #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
608 // Directly access a vertex or edge bundle
609 vertex_bundled& operator[](vertex_descriptor v)
610 { return get(vertex_bundle, *this)[v]; }
612 const vertex_bundled& operator[](vertex_descriptor v) const
613 { return get(vertex_bundle, *this)[v]; }
615 edge_bundled& operator[](edge_descriptor e)
616 { return get(edge_bundle, *this)[e]; }
618 const edge_bundled& operator[](edge_descriptor e) const
619 { return get(edge_bundle, *this)[e]; }
622 //private: if friends worked, these would be private
624 typename Matrix::const_reference
625 get_edge(vertex_descriptor u, vertex_descriptor v) const {
626 if (Directed::is_directed)
627 return m_matrix[u * m_vertex_set.size() + v];
631 return m_matrix[u * (u + 1)/2 + v];
634 typename Matrix::reference
635 get_edge(vertex_descriptor u, vertex_descriptor v) {
636 if (Directed::is_directed)
637 return m_matrix[u * m_vertex_set.size() + v];
641 return m_matrix[u * (u + 1)/2 + v];
646 VertexList m_vertex_set;
647 std::vector<vertex_property_type> m_vertex_properties;
648 size_type m_num_edges;
651 //=========================================================================
652 // Functions required by the AdjacencyMatrix concept
654 template <typename D, typename VP, typename EP, typename GP, typename A>
655 std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor,
657 edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
658 typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v,
659 const adjacency_matrix<D,VP,EP,GP,A>& g)
661 bool exists = detail::get_edge_exists(g.get_edge(u,v), 0);
662 typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor
663 e(exists, u, v, &detail::get_property(g.get_edge(u,v)));
664 return std::make_pair(e, exists);
667 //=========================================================================
668 // Functions required by the IncidenceGraph concept
671 template <typename VP, typename EP, typename GP, typename A>
672 std::pair<typename adjacency_matrix<directedS,VP,EP,GP,A>::out_edge_iterator,
673 typename adjacency_matrix<directedS,VP,EP,GP,A>::out_edge_iterator>
675 (typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_descriptor u,
676 const adjacency_matrix<directedS,VP,EP,GP,A>& g_)
678 typedef adjacency_matrix<directedS,VP,EP,GP,A> Graph;
679 Graph& g = const_cast<Graph&>(g_);
680 typename Graph::vertices_size_type offset = u * g.m_vertex_set.size();
681 typename Graph::MatrixIter f = g.m_matrix.begin() + offset;
682 typename Graph::MatrixIter l = f + g.m_vertex_set.size();
683 typename Graph::unfiltered_out_edge_iter
684 first(f, u, g.m_vertex_set.size())
685 , last(l, u, g.m_vertex_set.size());
686 detail::does_edge_exist pred;
687 typedef typename Graph::out_edge_iterator out_edge_iterator;
688 return std::make_pair(out_edge_iterator(pred, first, last),
689 out_edge_iterator(pred, last, last));
693 template <typename VP, typename EP, typename GP, typename A>
695 typename adjacency_matrix<undirectedS,VP,EP,GP,A>::out_edge_iterator,
696 typename adjacency_matrix<undirectedS,VP,EP,GP,A>::out_edge_iterator>
698 (typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_descriptor u,
699 const adjacency_matrix<undirectedS,VP,EP,GP,A>& g_)
701 typedef adjacency_matrix<undirectedS,VP,EP,GP,A> Graph;
702 Graph& g = const_cast<Graph&>(g_);
703 typename Graph::vertices_size_type offset = u * (u + 1) / 2;
704 typename Graph::MatrixIter f = g.m_matrix.begin() + offset;
705 typename Graph::MatrixIter l = g.m_matrix.end();
707 typename Graph::unfiltered_out_edge_iter
708 first(f, u, g.m_vertex_set.size())
709 , last(l, u, g.m_vertex_set.size());
711 detail::does_edge_exist pred;
712 typedef typename Graph::out_edge_iterator out_edge_iterator;
713 return std::make_pair(out_edge_iterator(pred, first, last),
714 out_edge_iterator(pred, last, last));
718 template <typename D, typename VP, typename EP, typename GP, typename A>
719 typename adjacency_matrix<D,VP,EP,GP,A>::degree_size_type
720 out_degree(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
721 const adjacency_matrix<D,VP,EP,GP,A>& g)
723 typename adjacency_matrix<D,VP,EP,GP,A>::degree_size_type n = 0;
724 typename adjacency_matrix<D,VP,EP,GP,A>::out_edge_iterator f, l;
725 for (tie(f, l) = out_edges(u, g); f != l; ++f)
731 template <typename D, typename VP, typename EP, typename GP, typename A,
732 typename Dir, typename Vertex>
733 typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor
734 source(const detail::matrix_edge_desc_impl<Dir,Vertex>& e,
735 const adjacency_matrix<D,VP,EP,GP,A>&)
741 template <typename D, typename VP, typename EP, typename GP, typename A,
742 typename Dir, typename Vertex>
743 typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor
744 target(const detail::matrix_edge_desc_impl<Dir,Vertex>& e,
745 const adjacency_matrix<D,VP,EP,GP,A>&)
750 //=========================================================================
751 // Functions required by the BidirectionalGraph concept
754 template <typename VP, typename EP, typename GP, typename A>
755 std::pair<typename adjacency_matrix<directedS,VP,EP,GP,A>::in_edge_iterator,
756 typename adjacency_matrix<directedS,VP,EP,GP,A>::in_edge_iterator>
758 (typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_descriptor u,
759 const adjacency_matrix<directedS,VP,EP,GP,A>& g_)
761 typedef adjacency_matrix<directedS,VP,EP,GP,A> Graph;
762 Graph& g = const_cast<Graph&>(g_);
763 typename Graph::MatrixIter f = g.m_matrix.begin() + u;
764 typename Graph::MatrixIter l = g.m_matrix.end();
765 typename Graph::unfiltered_in_edge_iter
766 first(f, l, u, g.m_vertex_set.size())
767 , last(l, l, u, g.m_vertex_set.size());
768 detail::does_edge_exist pred;
769 typedef typename Graph::in_edge_iterator in_edge_iterator;
770 return std::make_pair(in_edge_iterator(pred, first, last),
771 in_edge_iterator(pred, last, last));
775 template <typename VP, typename EP, typename GP, typename A>
777 typename adjacency_matrix<undirectedS,VP,EP,GP,A>::in_edge_iterator,
778 typename adjacency_matrix<undirectedS,VP,EP,GP,A>::in_edge_iterator>
780 (typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_descriptor u,
781 const adjacency_matrix<undirectedS,VP,EP,GP,A>& g_)
783 typedef adjacency_matrix<undirectedS,VP,EP,GP,A> Graph;
784 Graph& g = const_cast<Graph&>(g_);
785 typename Graph::vertices_size_type offset = u * (u + 1) / 2;
786 typename Graph::MatrixIter f = g.m_matrix.begin() + offset;
787 typename Graph::MatrixIter l = g.m_matrix.end();
789 typename Graph::unfiltered_in_edge_iter
790 first(f, u, g.m_vertex_set.size())
791 , last(l, u, g.m_vertex_set.size());
793 detail::does_edge_exist pred;
794 typedef typename Graph::in_edge_iterator in_edge_iterator;
795 return std::make_pair(in_edge_iterator(pred, first, last),
796 in_edge_iterator(pred, last, last));
800 template <typename D, typename VP, typename EP, typename GP, typename A>
801 typename adjacency_matrix<D,VP,EP,GP,A>::degree_size_type
802 in_degree(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
803 const adjacency_matrix<D,VP,EP,GP,A>& g)
805 typename adjacency_matrix<D,VP,EP,GP,A>::degree_size_type n = 0;
806 typename adjacency_matrix<D,VP,EP,GP,A>::in_edge_iterator f, l;
807 for (tie(f, l) = in_edges(u, g); f != l; ++f)
812 //=========================================================================
813 // Functions required by the AdjacencyGraph concept
815 template <typename D, typename VP, typename EP, typename GP, typename A>
816 std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::adjacency_iterator,
817 typename adjacency_matrix<D,VP,EP,GP,A>::adjacency_iterator>
819 (typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
820 const adjacency_matrix<D,VP,EP,GP,A>& g_)
822 typedef adjacency_matrix<D,VP,EP,GP,A> Graph;
823 const Graph& cg = static_cast<const Graph&>(g_);
824 Graph& g = const_cast<Graph&>(cg);
825 typedef typename Graph::adjacency_iterator adjacency_iterator;
826 typename Graph::out_edge_iterator first, last;
827 boost::tie(first, last) = out_edges(u, g);
828 return std::make_pair(adjacency_iterator(first, &g),
829 adjacency_iterator(last, &g));
832 //=========================================================================
833 // Functions required by the VertexListGraph concept
835 template <typename D, typename VP, typename EP, typename GP, typename A>
836 std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::vertex_iterator,
837 typename adjacency_matrix<D,VP,EP,GP,A>::vertex_iterator>
838 vertices(const adjacency_matrix<D,VP,EP,GP,A>& g_) {
839 typedef adjacency_matrix<D,VP,EP,GP,A> Graph;
840 Graph& g = const_cast<Graph&>(g_);
841 return std::make_pair(g.m_vertex_set.begin(), g.m_vertex_set.end());
844 template <typename D, typename VP, typename EP, typename GP, typename A>
845 typename adjacency_matrix<D,VP,EP,GP,A>::vertices_size_type
846 num_vertices(const adjacency_matrix<D,VP,EP,GP,A>& g) {
847 return g.m_vertex_set.size();
850 //=========================================================================
851 // Functions required by the EdgeListGraph concept
853 template <typename D, typename VP, typename EP, typename GP, typename A>
854 std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_iterator,
855 typename adjacency_matrix<D,VP,EP,GP,A>::edge_iterator>
856 edges(const adjacency_matrix<D,VP,EP,GP,A>& g_)
858 typedef adjacency_matrix<D,VP,EP,GP,A> Graph;
859 Graph& g = const_cast<Graph&>(g_);
861 typename Graph::unfiltered_edge_iter
862 first(g.m_matrix.begin(), g.m_matrix.begin(),
863 g.m_vertex_set.size()),
864 last(g.m_matrix.end(), g.m_matrix.begin(),
865 g.m_vertex_set.size());
866 detail::does_edge_exist pred;
867 typedef typename Graph::edge_iterator edge_iterator;
868 return std::make_pair(edge_iterator(pred, first, last),
869 edge_iterator(pred, last, last));
873 template <typename D, typename VP, typename EP, typename GP, typename A>
874 typename adjacency_matrix<D,VP,EP,GP,A>::edges_size_type
875 num_edges(const adjacency_matrix<D,VP,EP,GP,A>& g)
877 return g.m_num_edges;
880 //=========================================================================
881 // Functions required by the MutableGraph concept
884 template <typename D, typename VP, typename EP, typename GP, typename A>
885 std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor, bool>
886 add_edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
887 typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v,
889 adjacency_matrix<D,VP,EP,GP,A>& g)
891 typedef typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor
893 if (detail::get_edge_exists(g.get_edge(u,v), 0) == false) {
895 detail::set_property(g.get_edge(u,v), ep, 0);
896 detail::set_edge_exists(g.get_edge(u,v), true, 0);
897 return std::make_pair
898 (edge_descriptor(true, u, v, &detail::get_property(g.get_edge(u,v))),
901 return std::make_pair
902 (edge_descriptor(true, u, v, &detail::get_property(g.get_edge(u,v))),
906 template <typename D, typename VP, typename EP, typename GP, typename A>
907 std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor, bool>
908 add_edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
909 typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v,
910 adjacency_matrix<D,VP,EP,GP,A>& g)
913 return add_edge(u, v, ep, g);
917 template <typename D, typename VP, typename EP, typename GP, typename A>
919 remove_edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
920 typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v,
921 adjacency_matrix<D,VP,EP,GP,A>& g)
924 detail::set_edge_exists(g.get_edge(u,v), false, 0);
928 template <typename D, typename VP, typename EP, typename GP, typename A>
930 remove_edge(typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor e,
931 adjacency_matrix<D,VP,EP,GP,A>& g)
933 remove_edge(source(e, g), target(e, g), g);
937 template <typename D, typename VP, typename EP, typename GP, typename A>
938 inline typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor
939 add_vertex(adjacency_matrix<D,VP,EP,GP,A>& g) {
940 // UNDER CONSTRUCTION
942 return *vertices(g).first;
945 template <typename D, typename VP, typename EP, typename GP, typename A>
946 inline typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor
947 add_vertex(const VP& vp, adjacency_matrix<D,VP,EP,GP,A>& g) {
948 // UNDER CONSTRUCTION
950 return *vertices(g).first;
953 template <typename D, typename VP, typename EP, typename GP, typename A>
955 remove_vertex(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u,
956 adjacency_matrix<D,VP,EP,GP,A>& g)
958 // UNDER CONSTRUCTION
963 template <typename VP, typename EP, typename GP, typename A>
966 (typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_descriptor u,
967 adjacency_matrix<directedS,VP,EP,GP,A>& g)
969 typename adjacency_matrix<directedS,VP,EP,GP,A>::vertex_iterator
971 for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
972 remove_edge(u, *vi, g);
973 for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
974 remove_edge(*vi, u, g);
978 template <typename VP, typename EP, typename GP, typename A>
981 (typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_descriptor u,
982 adjacency_matrix<undirectedS,VP,EP,GP,A>& g)
984 typename adjacency_matrix<undirectedS,VP,EP,GP,A>::vertex_iterator
986 for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
987 remove_edge(u, *vi, g);
990 //=========================================================================
991 // Vertex Property Map
993 template <typename GraphPtr, typename Vertex, typename T, typename R,
995 class adj_matrix_vertex_property_map
996 : public put_get_helper<R,
997 adj_matrix_vertex_property_map<GraphPtr, Vertex, T, R, Tag> >
1000 typedef T value_type;
1001 typedef R reference;
1002 typedef Vertex key_type;
1003 typedef boost::lvalue_property_map_tag category;
1004 adj_matrix_vertex_property_map() { }
1005 adj_matrix_vertex_property_map(GraphPtr g) : m_g(g) { }
1006 inline reference operator[](key_type v) const {
1007 return get_property_value(m_g->m_vertex_properties[v], Tag());
1012 template <class Property, class Vertex>
1013 struct adj_matrix_vertex_id_map
1014 : public boost::put_get_helper<Vertex,
1015 adj_matrix_vertex_id_map<Property, Vertex> >
1017 typedef Vertex value_type;
1018 typedef Vertex reference;
1019 typedef Vertex key_type;
1020 typedef boost::readable_property_map_tag category;
1021 adj_matrix_vertex_id_map() { }
1022 template <class Graph>
1023 inline adj_matrix_vertex_id_map(const Graph&) { }
1024 inline value_type operator[](key_type v) const { return v; }
1029 struct adj_matrix_any_vertex_pa {
1030 template <class Tag, class Graph, class Property>
1032 typedef typename property_value<Property,Tag>::type Value;
1033 typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
1035 typedef adj_matrix_vertex_property_map<Graph*, Vertex, Value, Value&,
1037 typedef adj_matrix_vertex_property_map<const Graph*, Vertex, Value,
1038 const Value&, Tag> const_type;
1041 struct adj_matrix_id_vertex_pa {
1042 template <class Tag, class Graph, class Property>
1044 typedef typename Graph::vertex_descriptor Vertex;
1045 typedef adj_matrix_vertex_id_map<Property, Vertex> type;
1046 typedef adj_matrix_vertex_id_map<Property, Vertex> const_type;
1050 template <class Tag>
1051 struct adj_matrix_choose_vertex_pa_helper {
1052 typedef adj_matrix_any_vertex_pa type;
1055 struct adj_matrix_choose_vertex_pa_helper<vertex_index_t> {
1056 typedef adj_matrix_id_vertex_pa type;
1059 template <class Tag, class Graph, class Property>
1060 struct adj_matrix_choose_vertex_pa {
1061 typedef typename adj_matrix_choose_vertex_pa_helper<Tag>::type Helper;
1062 typedef typename Helper::template bind_<Tag,Graph,Property> Bind;
1063 typedef typename Bind::type type;
1064 typedef typename Bind::const_type const_type;
1067 struct adj_matrix_vertex_property_selector {
1068 template <class Graph, class Property, class Tag>
1070 typedef adj_matrix_choose_vertex_pa<Tag,Graph,Property> Choice;
1071 typedef typename Choice::type type;
1072 typedef typename Choice::const_type const_type;
1076 } // namespace detail
1079 struct vertex_property_selector<adjacency_matrix_class_tag> {
1080 typedef detail::adj_matrix_vertex_property_selector type;
1083 //=========================================================================
1084 // Edge Property Map
1087 template <typename Directed, typename Property, typename Vertex,
1088 typename T, typename R, typename Tag>
1089 class adj_matrix_edge_property_map
1090 : public put_get_helper<R,
1091 adj_matrix_edge_property_map<Directed, Property, Vertex, T, R, Tag> >
1094 typedef T value_type;
1095 typedef R reference;
1096 typedef detail::matrix_edge_desc_impl<Directed, Vertex> key_type;
1097 typedef boost::lvalue_property_map_tag category;
1098 inline reference operator[](key_type e) const {
1099 Property& p = *(Property*)e.get_property();
1100 return get_property_value(p, Tag());
1103 struct adj_matrix_edge_property_selector {
1104 template <class Graph, class Property, class Tag>
1106 typedef typename property_value<Property,Tag>::type T;
1107 typedef typename Graph::vertex_descriptor Vertex;
1108 typedef adj_matrix_edge_property_map<typename Graph::directed_category,
1109 Property, Vertex, T, T&, Tag> type;
1110 typedef adj_matrix_edge_property_map<typename Graph::directed_category,
1111 Property, Vertex, T, const T&, Tag> const_type;
1115 struct edge_property_selector<adjacency_matrix_class_tag> {
1116 typedef adj_matrix_edge_property_selector type;
1119 //=========================================================================
1120 // Functions required by PropertyGraph
1124 template <typename Property, typename D, typename VP, typename EP,
1125 typename GP, typename A>
1126 typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
1128 get_dispatch(adjacency_matrix<D,VP,EP,GP,A>& g, Property,
1129 vertex_property_tag)
1131 typedef adjacency_matrix<D,VP,EP,GP,A> Graph;
1132 typedef typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
1136 template <typename Property, typename D, typename VP, typename EP,
1137 typename GP, typename A>
1138 typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
1140 get_dispatch(adjacency_matrix<D,VP,EP,GP,A>&, Property,
1143 typedef typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
1147 template <typename Property, typename D, typename VP, typename EP,
1148 typename GP, typename A>
1149 typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
1150 Property>::const_type
1151 get_dispatch(const adjacency_matrix<D,VP,EP,GP,A>& g, Property,
1152 vertex_property_tag)
1154 typedef adjacency_matrix<D,VP,EP,GP,A> Graph;
1155 typedef typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
1156 Property>::const_type PA;
1159 template <typename Property, typename D, typename VP, typename EP,
1160 typename GP, typename A>
1161 typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
1162 Property>::const_type
1163 get_dispatch(const adjacency_matrix<D,VP,EP,GP,A>&, Property,
1166 typedef typename boost::property_map<adjacency_matrix<D,VP,EP,GP,A>,
1167 Property>::const_type PA;
1171 } // namespace detail
1173 template <typename Property, typename D, typename VP, typename EP,
1174 typename GP, typename A>
1176 typename property_map<adjacency_matrix<D,VP,EP,GP,A>, Property>::type
1177 get(Property p, adjacency_matrix<D,VP,EP,GP,A>& g)
1179 typedef typename property_kind<Property>::type Kind;
1180 return detail::get_dispatch(g, p, Kind());
1183 template <typename Property, typename D, typename VP, typename EP,
1184 typename GP, typename A>
1186 typename property_map<adjacency_matrix<D,VP,EP,GP,A>, Property>::const_type
1187 get(Property p, const adjacency_matrix<D,VP,EP,GP,A>& g)
1189 typedef typename property_kind<Property>::type Kind;
1190 return detail::get_dispatch(g, p, Kind());
1193 template <typename Property, typename D, typename VP, typename EP,
1194 typename GP, typename A, typename Key>
1196 typename property_traits<
1197 typename property_map<adjacency_matrix<D,VP,EP,GP,A>, Property>::const_type
1199 get(Property p, const adjacency_matrix<D,VP,EP,GP,A>& g,
1202 return get(get(p, g), key);
1205 template <typename Property, typename D, typename VP, typename EP,
1206 typename GP, typename A, typename Key, typename Value>
1208 put(Property p, adjacency_matrix<D,VP,EP,GP,A>& g,
1209 const Key& key, const Value& value)
1211 typedef adjacency_matrix<D,VP,EP,GP,A> Graph;
1212 typedef typename boost::property_map<Graph, Property>::type Map;
1213 Map pmap = get(p, g);
1214 put(pmap, key, value);
1217 //=========================================================================
1220 template <typename D, typename VP, typename EP, typename GP, typename A>
1221 typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor
1222 vertex(typename adjacency_matrix<D,VP,EP,GP,A>::vertices_size_type n,
1223 const adjacency_matrix<D,VP,EP,GP,A>& g)
1228 // Support for bundled properties
1229 #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
1230 template <typename Directed, typename VertexProperty, typename EdgeProperty, typename GraphProperty,
1231 typename Allocator, typename T, typename Bundle>
1233 typename property_map<adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>,
1235 get(T Bundle::* p, adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>& g)
1237 typedef typename property_map<adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>,
1240 return result_type(&g, p);
1243 template <typename Directed, typename VertexProperty, typename EdgeProperty, typename GraphProperty,
1244 typename Allocator, typename T, typename Bundle>
1246 typename property_map<adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>,
1247 T Bundle::*>::const_type
1248 get(T Bundle::* p, adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator> const & g)
1250 typedef typename property_map<adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>,
1251 T Bundle::*>::const_type
1253 return result_type(&g, p);
1256 template <typename Directed, typename VertexProperty, typename EdgeProperty, typename GraphProperty,
1257 typename Allocator, typename T, typename Bundle, typename Key>
1259 get(T Bundle::* p, adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator> const & g,
1262 return get(get(p, g), key);
1265 template <typename Directed, typename VertexProperty, typename EdgeProperty, typename GraphProperty,
1266 typename Allocator, typename T, typename Bundle, typename Key>
1268 put(T Bundle::* p, adjacency_matrix<Directed, VertexProperty, EdgeProperty, GraphProperty, Allocator>& g,
1269 const Key& key, const T& value)
1271 put(get(p, g), key, value);
1276 } // namespace boost
1278 #endif // BOOST_ADJACENCY_MATRIX_HPP