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#ifndef BOOST_GRAPH_RELAX_HPP
10#define BOOST_GRAPH_RELAX_HPP
11
12#include <functional>
13#include <boost/limits.hpp> // for numeric limits
14#include <boost/graph/graph_traits.hpp>
15#include <boost/property_map/property_map.hpp>
16
17namespace boost {
18
19 // The following version of the plus functor prevents
20 // problems due to overflow at positive infinity.
21
22 template <class T>
23 struct closed_plus
24 {
25 const T inf;
26
27 closed_plus() : inf((std::numeric_limits<T>::max)()) { }
28 closed_plus(T inf) : inf(inf) { }
29
30 T operator()(const T& a, const T& b) const {
31 using namespace std;
32 if (a == inf) return inf;
33 if (b == inf) return inf;
34 return a + b;
35 }
36 };
37
38 template <class Graph, class WeightMap,
39 class PredecessorMap, class DistanceMap,
40 class BinaryFunction, class BinaryPredicate>
41 bool relax(typename graph_traits<Graph>::edge_descriptor e,
42 const Graph& g, const WeightMap& w,
43 PredecessorMap& p, DistanceMap& d,
44 const BinaryFunction& combine, const BinaryPredicate& compare)
45 {
46 typedef typename graph_traits<Graph>::directed_category DirCat;
47 bool is_undirected = is_same<DirCat, undirected_tag>::value;
48 typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
49 Vertex u = source(e, g), v = target(e, g);
50 typedef typename property_traits<DistanceMap>::value_type D;
51 typedef typename property_traits<WeightMap>::value_type W;
52 const D d_u = get(d, u);
53 const D d_v = get(d, v);
54 const W& w_e = get(w, e);
55
56 // The seemingly redundant comparisons after the distance puts are to
57 // ensure that extra floating-point precision in x87 registers does not
58 // lead to relax() returning true when the distance did not actually
59 // change.
60 if ( compare(combine(d_u, w_e), d_v) ) {
61 put(d, v, combine(d_u, w_e));
62 if (compare(get(d, v), d_v)) {
63 put(p, v, u);
64 return true;
65 } else {
66 return false;
67 }
68 } else if (is_undirected && compare(combine(d_v, w_e), d_u)) {
69 put(d, u, combine(d_v, w_e));
70 if (compare(get(d, u), d_u)) {
71 put(p, u, v);
72 return true;
73 } else {
74 return false;
75 }
76 } else
77 return false;
78 }
79
80 template <class Graph, class WeightMap,
81 class PredecessorMap, class DistanceMap>
82 bool relax(typename graph_traits<Graph>::edge_descriptor e,
83 const Graph& g, WeightMap w, PredecessorMap p, DistanceMap d)
84 {
85 typedef typename property_traits<DistanceMap>::value_type D;
86 typedef closed_plus<D> Combine;
87 typedef std::less<D> Compare;
88 return relax(e, g, w, p, d, Combine(), Compare());
89 }
90
91} // namespace boost
92
93#endif /* BOOST_GRAPH_RELAX_HPP */