exterior_property.hpp 4.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114
  1. // (C) Copyright 2007-2009 Andrew Sutton
  2. //
  3. // Use, modification and distribution are subject to the
  4. // Boost Software License, Version 1.0 (See accompanying file
  5. // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
  6. #ifndef BOOST_GRAPH_EXTERIOR_PROPERTY_HPP
  7. #define BOOST_GRAPH_EXTERIOR_PROPERTY_HPP
  8. #include <vector>
  9. #include <boost/graph/property_maps/container_property_map.hpp>
  10. #include <boost/graph/property_maps/matrix_property_map.hpp>
  11. namespace boost
  12. {
  13. namespace detail
  14. {
  15. // The vector matrix provides a little abstraction over vector
  16. // types that makes matrices easier to work with.
  17. template < typename Value > struct vector_matrix
  18. {
  19. typedef std::vector< Value > container_type;
  20. typedef std::vector< container_type > matrix_type;
  21. typedef container_type value_type;
  22. typedef container_type& reference;
  23. typedef const container_type const_reference;
  24. typedef container_type* pointer;
  25. typedef typename matrix_type::size_type size_type;
  26. // Instantiate the matrix over n elements (creates an n by n matrix).
  27. // The graph has to be passed in order to ensure the index maps
  28. // are constructed correctly when returning indexible elements.
  29. inline vector_matrix(size_type n) : m_matrix(n, container_type(n)) {}
  30. inline reference operator[](size_type n) { return m_matrix[n]; }
  31. inline const_reference operator[](size_type n) const
  32. {
  33. return m_matrix[n];
  34. }
  35. matrix_type m_matrix;
  36. };
  37. } /* namespace detail */
  38. /**
  39. * The exterior_property metafunction defines an appropriate set of types for
  40. * creating an exterior property. An exterior property is comprised of a both
  41. * a container and a property map that acts as its abstraction. An extension
  42. * of this metafunction will select an appropriate "matrix" property that
  43. * records values for pairs of vertices.
  44. *
  45. * @todo This does not currently support the ability to define exterior
  46. * properties for graph types that do not model the IndexGraph concepts. A
  47. * solution should not be especially difficult, but will require an extension
  48. * of type traits to affect the type selection.
  49. */
  50. template < typename Graph, typename Key, typename Value >
  51. struct exterior_property
  52. {
  53. typedef Key key_type;
  54. typedef Value value_type;
  55. typedef std::vector< Value > container_type;
  56. typedef container_property_map< Graph, Key, container_type > map_type;
  57. typedef detail::vector_matrix< Value > matrix_type;
  58. typedef matrix_property_map< Graph, Key, matrix_type > matrix_map_type;
  59. private:
  60. exterior_property() {}
  61. exterior_property(const exterior_property&) {}
  62. };
  63. /**
  64. * Define a the container and property map types requried to create an exterior
  65. * vertex property for the given value type. The Graph parameter is required to
  66. * model the VertexIndexGraph concept.
  67. */
  68. template < typename Graph, typename Value > struct exterior_vertex_property
  69. {
  70. typedef exterior_property< Graph,
  71. typename graph_traits< Graph >::vertex_descriptor, Value >
  72. property_type;
  73. typedef typename property_type::key_type key_type;
  74. typedef typename property_type::value_type value_type;
  75. typedef typename property_type::container_type container_type;
  76. typedef typename property_type::map_type map_type;
  77. typedef typename property_type::matrix_type matrix_type;
  78. typedef typename property_type::matrix_map_type matrix_map_type;
  79. };
  80. /**
  81. * Define a the container and property map types requried to create an exterior
  82. * edge property for the given value type. The Graph parameter is required to
  83. * model the EdgeIndexGraph concept.
  84. */
  85. template < typename Graph, typename Value > struct exterior_edge_property
  86. {
  87. typedef exterior_property< Graph,
  88. typename graph_traits< Graph >::edge_descriptor, Value >
  89. property_type;
  90. typedef typename property_type::key_type key_type;
  91. typedef typename property_type::value_type value_type;
  92. typedef typename property_type::container_type container_type;
  93. typedef typename property_type::map_type map_type;
  94. typedef typename property_type::matrix_type matrix_type;
  95. typedef typename property_type::matrix_map_type matrix_map_type;
  96. };
  97. } /* namespace boost */
  98. #endif