ocrm.bsky.social
the game where you go into mines and start crafting! but for consoles (forked directly from smartcmd's github)
1//=======================================================================
2// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
3// Authors: Andrew Lumsdaine, Lie-Quan Lee, 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_GRAPH_PROPERTIES_HPP
11#define BOOST_GRAPH_PROPERTIES_HPP
12
13#include <boost/config.hpp>
14#include <boost/assert.hpp>
15#include <boost/pending/property.hpp>
16#include <boost/detail/workaround.hpp>
17
18// Include the property map library and extensions in the BGL.
19#include <boost/property_map/property_map.hpp>
20#include <boost/graph/property_maps/constant_property_map.hpp>
21#include <boost/graph/property_maps/null_property_map.hpp>
22
23#include <boost/graph/graph_traits.hpp>
24#include <boost/type_traits.hpp>
25#include <boost/limits.hpp>
26#include <boost/mpl/and.hpp>
27#include <boost/mpl/not.hpp>
28#include <boost/mpl/if.hpp>
29
30#if BOOST_WORKAROUND(BOOST_MSVC, < 1300)
31// Stay out of the way of the concept checking class
32# define Graph Graph_
33# define RandomAccessContainer RandomAccessContainer_
34#endif
35
36namespace boost {
37
38 enum default_color_type { white_color, gray_color, green_color, red_color, black_color };
39
40 template <class ColorValue>
41 struct color_traits {
42 static default_color_type white() { return white_color; }
43 static default_color_type gray() { return gray_color; }
44 static default_color_type green() { return green_color; }
45 static default_color_type red() { return red_color; }
46 static default_color_type black() { return black_color; }
47 };
48
49 // These functions are now obsolete, replaced by color_traits.
50 inline default_color_type white(default_color_type) { return white_color; }
51 inline default_color_type gray(default_color_type) { return gray_color; }
52 inline default_color_type green(default_color_type) { return green_color; }
53 inline default_color_type red(default_color_type) { return red_color; }
54 inline default_color_type black(default_color_type) { return black_color; }
55
56#ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
57 template <>
58 struct property_traits<default_color_type*> {
59 typedef default_color_type value_type;
60 typedef std::ptrdiff_t key_type;
61 typedef default_color_type& reference;
62 typedef lvalue_property_map_tag category;
63 };
64 // get/put already defined for T*
65#endif
66
67 struct graph_property_tag { };
68 struct vertex_property_tag { };
69 struct edge_property_tag { };
70
71 // See examples/edge_property.cpp for how to use this.
72#define BOOST_INSTALL_PROPERTY(KIND, NAME) \
73 template <> struct property_kind<KIND##_##NAME##_t> { \
74 typedef KIND##_property_tag type; \
75 }
76
77#define BOOST_DEF_PROPERTY(KIND, NAME) \
78 enum KIND##_##NAME##_t { KIND##_##NAME }; \
79 BOOST_INSTALL_PROPERTY(KIND, NAME)
80
81 // These three are defined in boost/pending/property.hpp
82 BOOST_INSTALL_PROPERTY(vertex, all);
83 BOOST_INSTALL_PROPERTY(edge, all);
84 BOOST_INSTALL_PROPERTY(graph, all);
85 BOOST_DEF_PROPERTY(vertex, index);
86 BOOST_DEF_PROPERTY(vertex, index1);
87 BOOST_DEF_PROPERTY(vertex, index2);
88 BOOST_DEF_PROPERTY(vertex, root);
89 BOOST_DEF_PROPERTY(edge, index);
90 BOOST_DEF_PROPERTY(edge, name);
91 BOOST_DEF_PROPERTY(edge, weight);
92 BOOST_DEF_PROPERTY(edge, weight2);
93 BOOST_DEF_PROPERTY(edge, color);
94 BOOST_DEF_PROPERTY(vertex, name);
95 BOOST_DEF_PROPERTY(graph, name);
96 BOOST_DEF_PROPERTY(vertex, distance);
97 BOOST_DEF_PROPERTY(vertex, distance2);
98 BOOST_DEF_PROPERTY(vertex, color);
99 BOOST_DEF_PROPERTY(vertex, degree);
100 BOOST_DEF_PROPERTY(vertex, in_degree);
101 BOOST_DEF_PROPERTY(vertex, out_degree);
102 BOOST_DEF_PROPERTY(vertex, current_degree);
103 BOOST_DEF_PROPERTY(vertex, priority);
104 BOOST_DEF_PROPERTY(vertex, discover_time);
105 BOOST_DEF_PROPERTY(vertex, finish_time);
106 BOOST_DEF_PROPERTY(vertex, predecessor);
107 BOOST_DEF_PROPERTY(vertex, rank);
108 BOOST_DEF_PROPERTY(vertex, centrality);
109 BOOST_DEF_PROPERTY(vertex, lowpoint);
110 BOOST_DEF_PROPERTY(vertex, potential);
111 BOOST_DEF_PROPERTY(vertex, update);
112 BOOST_DEF_PROPERTY(vertex, underlying);
113 BOOST_DEF_PROPERTY(edge, reverse);
114 BOOST_DEF_PROPERTY(edge, capacity);
115 BOOST_DEF_PROPERTY(edge, flow);
116 BOOST_DEF_PROPERTY(edge, residual_capacity);
117 BOOST_DEF_PROPERTY(edge, centrality);
118 BOOST_DEF_PROPERTY(edge, discover_time);
119 BOOST_DEF_PROPERTY(edge, update);
120 BOOST_DEF_PROPERTY(edge, finished);
121 BOOST_DEF_PROPERTY(edge, underlying);
122 BOOST_DEF_PROPERTY(graph, visitor);
123
124 // These tags are used for property bundles
125 // These three are defined in boost/pending/property.hpp
126 BOOST_INSTALL_PROPERTY(graph, bundle);
127 BOOST_INSTALL_PROPERTY(vertex, bundle);
128 BOOST_INSTALL_PROPERTY(edge, bundle);
129
130 // These tags are used to denote the owners and local descriptors
131 // for the vertices and edges of a distributed graph.
132 BOOST_DEF_PROPERTY(vertex, global);
133 BOOST_DEF_PROPERTY(vertex, owner);
134 BOOST_DEF_PROPERTY(vertex, local);
135 BOOST_DEF_PROPERTY(edge, global);
136 BOOST_DEF_PROPERTY(edge, owner);
137 BOOST_DEF_PROPERTY(edge, local);
138 BOOST_DEF_PROPERTY(vertex, local_index);
139 BOOST_DEF_PROPERTY(edge, local_index);
140
141#undef BOOST_DEF_PROPERTY
142
143 namespace detail {
144
145 template <typename G, typename Tag>
146 struct property_kind_from_graph: property_kind<Tag> {};
147
148#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
149 template <typename G, typename R, typename T>
150 struct property_kind_from_graph<G, R T::*> {
151 typedef typename boost::mpl::if_<
152 boost::is_base_of<T, typename vertex_bundle_type<G>::type>,
153 vertex_property_tag,
154 typename boost::mpl::if_<
155 boost::is_base_of<T, typename edge_bundle_type<G>::type>,
156 edge_property_tag,
157 typename boost::mpl::if_<
158 boost::is_base_of<T, typename graph_bundle_type<G>::type>,
159 graph_property_tag,
160 void>::type>::type>::type type;
161 };
162#endif
163
164 struct dummy_edge_property_selector {
165 template <class Graph, class Property, class Tag>
166 struct bind_ {
167 typedef identity_property_map type;
168 typedef identity_property_map const_type;
169 };
170 };
171 struct dummy_vertex_property_selector {
172 template <class Graph, class Property, class Tag>
173 struct bind_ {
174 typedef identity_property_map type;
175 typedef identity_property_map const_type;
176 };
177 };
178
179 } // namespace detail
180
181 // Graph classes can either partially specialize property_map
182 // or they can specialize these two selector classes.
183 template <class GraphTag>
184 struct edge_property_selector {
185 typedef detail::dummy_edge_property_selector type;
186 };
187
188 template <class GraphTag>
189 struct vertex_property_selector {
190 typedef detail::dummy_vertex_property_selector type;
191 };
192
193 namespace detail {
194
195 template <typename A> struct return_void {typedef void type;};
196
197 template <typename Graph, typename Enable = void>
198 struct graph_tag_or_void {
199 typedef void type;
200 };
201
202 template <typename Graph>
203 struct graph_tag_or_void<Graph, typename return_void<typename Graph::graph_tag>::type> {
204 typedef typename Graph::graph_tag type;
205 };
206
207 template <class Graph, class PropertyTag>
208 struct edge_property_map
209 : edge_property_selector<
210 typename graph_tag_or_void<Graph>::type
211 >::type::template bind_<
212 Graph,
213 typename edge_property_type<Graph>::type,
214 PropertyTag>
215 {};
216 template <class Graph, class PropertyTag>
217 struct vertex_property_map
218 : vertex_property_selector<
219 typename graph_tag_or_void<Graph>::type
220 >::type::template bind_<
221 Graph,
222 typename vertex_property_type<Graph>::type,
223 PropertyTag>
224 {};
225 } // namespace detail
226
227 template <class Graph, class Property, class Enable = void>
228 struct property_map:
229 mpl::if_<
230 is_same<typename detail::property_kind_from_graph<Graph, Property>::type, edge_property_tag>,
231 detail::edge_property_map<Graph, Property>,
232 detail::vertex_property_map<Graph, Property> >::type
233 {};
234
235 // shortcut for accessing the value type of the property map
236 template <class Graph, class Property>
237 class property_map_value {
238 typedef typename property_map<Graph, Property>::const_type PMap;
239 public:
240 typedef typename property_traits<PMap>::value_type type;
241 };
242
243 template <class Graph, class Property>
244 class graph_property {
245 public:
246 typedef typename property_value<
247 typename boost::graph_property_type<Graph>::type, Property
248 >::type type;
249 };
250
251 template <typename Graph> struct vertex_property: vertex_property_type<Graph> {};
252 template <typename Graph> struct edge_property: edge_property_type<Graph> {};
253
254 template <typename Graph>
255 class degree_property_map
256 : public put_get_helper<typename graph_traits<Graph>::degree_size_type,
257 degree_property_map<Graph> >
258 {
259 public:
260 typedef typename graph_traits<Graph>::vertex_descriptor key_type;
261 typedef typename graph_traits<Graph>::degree_size_type value_type;
262 typedef value_type reference;
263 typedef readable_property_map_tag category;
264 degree_property_map(const Graph& g) : m_g(g) { }
265 value_type operator[](const key_type& v) const {
266 return degree(v, m_g);
267 }
268 private:
269 const Graph& m_g;
270 };
271 template <typename Graph>
272 inline degree_property_map<Graph>
273 make_degree_map(const Graph& g) {
274 return degree_property_map<Graph>(g);
275 }
276
277 //========================================================================
278 // Iterator Property Map Generating Functions contributed by
279 // Kevin Vanhorn. (see also the property map generating functions
280 // in boost/property_map/property_map.hpp)
281
282#if !defined(BOOST_NO_STD_ITERATOR_TRAITS)
283 // A helper function for creating a vertex property map out of a
284 // random access iterator and the internal vertex index map from a
285 // graph.
286 template <class PropertyGraph, class RandomAccessIterator>
287 inline
288 iterator_property_map<
289 RandomAccessIterator,
290 typename property_map<PropertyGraph, vertex_index_t>::type,
291 typename std::iterator_traits<RandomAccessIterator>::value_type,
292 typename std::iterator_traits<RandomAccessIterator>::reference
293 >
294 make_iterator_vertex_map(RandomAccessIterator iter, const PropertyGraph& g)
295 {
296 return make_iterator_property_map(iter, get(vertex_index, g));
297 }
298
299 // Use this next function when vertex_descriptor is known to be an
300 // integer type, with values ranging from 0 to num_vertices(g).
301 //
302 template <class RandomAccessIterator>
303 inline
304 iterator_property_map<
305 RandomAccessIterator,
306 identity_property_map,
307 typename std::iterator_traits<RandomAccessIterator>::value_type,
308 typename std::iterator_traits<RandomAccessIterator>::reference
309 >
310 make_iterator_vertex_map(RandomAccessIterator iter)
311 {
312 return make_iterator_property_map(iter, identity_property_map());
313 }
314#endif
315
316 template <class PropertyGraph, class RandomAccessContainer>
317 inline
318 iterator_property_map<
319 typename RandomAccessContainer::iterator,
320 typename property_map<PropertyGraph, vertex_index_t>::type,
321 typename RandomAccessContainer::value_type,
322 typename RandomAccessContainer::reference
323 >
324 make_container_vertex_map(RandomAccessContainer& c, const PropertyGraph& g)
325 {
326 BOOST_ASSERT(c.size() >= num_vertices(g));
327 return make_iterator_vertex_map(c.begin(), g);
328 }
329
330 template <class RandomAccessContainer> inline
331 iterator_property_map<
332 typename RandomAccessContainer::iterator,
333 identity_property_map,
334 typename RandomAccessContainer::value_type,
335 typename RandomAccessContainer::reference
336 >
337 make_container_vertex_map(RandomAccessContainer& c)
338 {
339 return make_iterator_vertex_map(c.begin());
340 }
341
342#if defined (BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION)
343# define BOOST_GRAPH_NO_BUNDLED_PROPERTIES
344#endif
345
346#if BOOST_WORKAROUND(__SUNPRO_CC, BOOST_TESTED_AT(0x590)) && !defined (BOOST_GRAPH_NO_BUNDLED_PROPERTIES)
347// This compiler cannot define a partial specialization based on a
348// pointer-to-member type, as seen in boost/graph/subgraph.hpp line 985 (as of
349// trunk r53912)
350# define BOOST_GRAPH_NO_BUNDLED_PROPERTIES
351#endif
352
353// NOTE: These functions are declared, but never defined since they need to
354// be overloaded by graph implementations. However, we need them to be
355// declared for the functions below.
356template<typename Graph, typename Tag>
357typename graph_property<Graph, graph_bundle_t>::type&
358get_property(Graph& g, Tag);
359
360template<typename Graph, typename Tag>
361typename graph_property<Graph, graph_bundle_t>::type const&
362get_property(Graph const& g, Tag);
363
364#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
365// NOTE: This operation is a simple adaptor over the overloaded get_property
366// operations.
367template<typename Graph>
368inline typename graph_property<Graph, graph_bundle_t>::type&
369get_property(Graph& g) {
370 return get_property(g, graph_bundle);
371}
372
373template<typename Graph>
374inline typename graph_property<Graph, graph_bundle_t>::type const&
375get_property(const Graph& g) {
376 return get_property(g, graph_bundle);
377}
378#endif
379
380} // namespace boost
381
382#endif /* BOOST_GRAPH_PROPERTIES_HPP */