graph kruskal_minimum_spanning_tree

Giriş
Kruskal algoritması "Disjoint set" ile gerçekleştirilebilir. Açıklaması şöyle

Path compression and other optimizations like union-by-rank should be applied any time you call the find operation on your disjoint-set forest.

One way to see this: from the perspective of Kruskal's algorithm, you just need to be able to call find and union and have them work correctly. You shouldn't need to worry about the details of how you're making find and union work correctly, just that they do. It's the responsibility of the disjoint-set forest to ensure that everything runs quickly, and so the calls to find are where you'll see the compression occurring.

İmzası şöyle

template <class Graph, class OutputIterator, class P, class T, class R>
OutputIterator kruskal_minimum_spanning_tree(
  Graph& g, 
  OutputIterator tree_edges, 
  const bgl_named_params<P, T, R>& params = all defaults
);

Örnek
Bir graph'ın weight alanlarına bakarak çalışır. Dolayısıyla weight map verilmesi gerekir. Şöyle yaparız

typedef adjacency_list<vecS, vecS, undirectedS, 
                       property<vertex_name_t,char>,
                       property<edge_weight_t,float>
                      > InternalPropGraph;


vector<edge_t> mst;
kruskal_minimum_spanning_tree(g, std::back_inserter(mst), 
                        weight_map( get(&Edge::weight, g) );

BOOST_SCOPE_EXIT Macrosu

Örnek
Şöyle yaparız.

auto prevState{currState};
currState = newState;
BOOST_SCOPE_EXIT(&currState, &prevState)
{
  currState = prevState;
} BOOST_SCOPE_EXIT_END

typeindex

Giriş
Şu satırı dahil ederiz.

#include <boost/type_index.hpp>

BOOST_TYPE_INDEX_REGISTER_CLASS
Örnek

Kalıtım varsa şöyle yaparız.

class A {
public:
    BOOST_TYPE_INDEX_REGISTER_CLASS
    virtual ~A(){}
};

struct B: public A {
    BOOST_TYPE_INDEX_REGISTER_CLASS
};

type_id Sınıfı
hash_code metodu
Bu metodun sonucu portable olmak zorunda değil.

pretty_name metodu
T tipi için şöyle yaparız.

boost::typeindex::type_id<T>().pretty_name();

std::string için biraz tuhaf bir çıktı veriyor. Şunu alırız.

std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >

type_id _with_cvr Sınıfı
pretty_name metodu

Şöyle yaparız

#include <boost/type_index.hpp>

cout << boost::typeindex::type_id_with_cvr<decltype(v)::value_type>().pretty_name();

Çıktı olarak şunu alırız

// when compiled with gcc:
std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >

Diğer
custom type_index
boost örneği şöyle.

namespace my_namespace { namespace detail {
    template <class T> struct typenum;
    template <> struct typenum<void>{       enum {value = 0}; };
    template <> struct typenum<std::string>{       enum {value = 1}; };

    struct my_typeinfo {const char* const type_;};

    const my_typeinfo infos[2] = {
        {"void"}, {"std::string"}
    };
  ...
}

geometry within metodu

within - polygon + polygon
Şöyle yaparız.

using Pt = bg::model::d2::point_xy<int>;
using Poly = bg::model::polygon<Pt>;
using Multi = bg::model::multi_polygon<Poly>;

Poly const a {{ { 0,0 }, { 0,3 }, { 3,3 }, { 3,0 }, { 0,0 }} };
Poly const b {{ { 1,1 }, { 1,2 }, { 2,2 }, { 2,1 }, { 1,1 }} };

return bg::intersects(a, b);

within - franklin 

Açıklaması şöyle.

"If a point is located exactly on the border of a geometry, the result depends on the strategy. The default strategy (Winding (coordinate system agnostic)) returns false in that case."

franklin tam üst üste gelen noktalar için true döner. Şöyle yaparız.

Şu satırı dahil ederiz.

#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
#include <boost/geometry/geometries/polygon.hpp>

#include <boost/geometry/strategies/cartesian/point_in_poly_franklin.hpp>

Elimizde bir polygon olsun.

typedef boost::geometry::model::d2::point_xy<double> point_type;
typedef boost::geometry::model::polygon<point_type> polygon_type;
typedef boost::geometry::model::segment<point_type> seg;
typedef boost::geometry::strategy::within::franklin
  <point_type, point_type, void> fran;

Bu polygon'u dolduralım.

polygon_type poly;

boost::geometry::read_wkt("POLYGON((2 1.3,2.4 1.7,2.8 1.8,3.4 1.2,...))", poly);

point_type p(4, 1);

Şöyle yaparız.

fran fran_;

cout << "within: " << (boost::geometry::within(p, poly,fran_) ? "yes" : "no");

within metodu ile covered_by sanırım aynı şeyi yapıyorlar.

cout << "within: " << (boost::geometry::covered_by(p, poly) ? "yes" : "no");

Örnek
Şöyle yaparız.

bool is_inside(const polygon& convex_polygon, const point p) noexcept
{
  const auto n = convex_polygon.size();

  const auto sense = determine_side(line{convex_polygon[n - 1], convex_polygon[0]}, p);
  if(sense == side::center)
  {
    return false;
  }

  for(auto i = 0u; i + 1 < n; ++i)
  {
    auto new_sense = determine_side(line{convex_polygon[i], convex_polygon[i + 1]}, p);

    if(new_sense != sense)
    {
      return false;
    }
  }
  return true;
}