ocrm.bsky.social
the game where you go into mines and start crafting! but for consoles (forked directly from smartcmd's github)
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
7#ifndef BOOST_GRAPH_ECCENTRICITY_HPP
8#define BOOST_GRAPH_ECCENTRICITY_HPP
9
10#include <boost/next_prior.hpp>
11#include <boost/config.hpp>
12#include <boost/graph/detail/geodesic.hpp>
13#include <boost/concept/assert.hpp>
14
15namespace boost
16{
17template <typename Graph,
18 typename DistanceMap,
19 typename Combinator>
20inline typename property_traits<DistanceMap>::value_type
21eccentricity(const Graph& g, DistanceMap dist, Combinator combine)
22{
23 BOOST_CONCEPT_ASSERT(( GraphConcept<Graph> ));
24 typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
25 BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<DistanceMap,Vertex> ));
26 typedef typename property_traits<DistanceMap>::value_type Distance;
27
28 return detail::combine_distances(g, dist, combine, Distance(0));
29}
30
31template <typename Graph, typename DistanceMap>
32inline typename property_traits<DistanceMap>::value_type
33eccentricity(const Graph& g, DistanceMap dist)
34{
35 BOOST_CONCEPT_ASSERT(( GraphConcept<Graph> ));
36 typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
37 BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<DistanceMap,Vertex> ));
38 typedef typename property_traits<DistanceMap>::value_type Distance;
39
40 return eccentricity(g, dist, detail::maximize<Distance>());
41}
42
43template <typename Graph, typename DistanceMatrix, typename EccentricityMap>
44inline std::pair<typename property_traits<EccentricityMap>::value_type,
45 typename property_traits<EccentricityMap>::value_type>
46all_eccentricities(const Graph& g, const DistanceMatrix& dist, EccentricityMap ecc)
47{
48 BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph> ));
49 typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
50 typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
51 BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<DistanceMatrix,Vertex> ));
52 typedef typename property_traits<DistanceMatrix>::value_type DistanceMap;
53 BOOST_CONCEPT_ASSERT(( WritablePropertyMapConcept<EccentricityMap,Vertex> ));
54 typedef typename property_traits<EccentricityMap>::value_type Eccentricity;
55 BOOST_USING_STD_MIN();
56 BOOST_USING_STD_MAX();
57
58 Eccentricity
59 r = numeric_values<Eccentricity>::infinity(),
60 d = numeric_values<Eccentricity>::zero();
61 VertexIterator i, end;
62 boost::tie(i, end) = vertices(g);
63 for(boost::tie(i, end) = vertices(g); i != end; ++i) {
64 DistanceMap dm = get(dist, *i);
65 Eccentricity e = eccentricity(g, dm);
66 put(ecc, *i, e);
67
68 // track the radius and diameter at the same time
69 r = min BOOST_PREVENT_MACRO_SUBSTITUTION (r, e);
70 d = max BOOST_PREVENT_MACRO_SUBSTITUTION (d, e);
71 }
72 return std::make_pair(r, d);
73}
74
75template <typename Graph, typename EccentricityMap>
76inline std::pair<typename property_traits<EccentricityMap>::value_type,
77 typename property_traits<EccentricityMap>::value_type>
78radius_and_diameter(const Graph& g, EccentricityMap ecc)
79{
80 BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph> ));
81 typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
82 typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;
83 BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<EccentricityMap, Vertex> ));
84 typedef typename property_traits<EccentricityMap>::value_type Eccentricity;
85 BOOST_USING_STD_MIN();
86 BOOST_USING_STD_MAX();
87
88 VertexIterator i, end;
89 boost::tie(i, end) = vertices(g);
90 Eccentricity radius = get(ecc, *i);
91 Eccentricity diameter = get(ecc, *i);
92 for(i = boost::next(i); i != end; ++i) {
93 Eccentricity cur = get(ecc, *i);
94 radius = min BOOST_PREVENT_MACRO_SUBSTITUTION (radius, cur);
95 diameter = max BOOST_PREVENT_MACRO_SUBSTITUTION (diameter, cur);
96 }
97 return std::make_pair(radius, diameter);
98}
99
100
101template <typename Graph, typename EccentricityMap>
102inline typename property_traits<EccentricityMap>::value_type
103radius(const Graph& g, EccentricityMap ecc)
104{ return radius_and_diameter(g, ecc).first; }
105
106
107template <typename Graph, typename EccentricityMap>
108inline typename property_traits<EccentricityMap>::value_type
109diameter(const Graph& g, EccentricityMap ecc)
110{ return radius_and_diameter(g, ecc).second; }
111
112} /* namespace boost */
113
114#endif