mwis.hpp

#include "search.hpp"

#include <boost/heap/fibonacci_heap.hpp>

#include <boost/graph/random.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/graph_concepts.hpp>
#include <boost/graph/adjacency_list.hpp>

#include <vector>
#include <functional>
#include <limits>
#include <numeric>
#include <algorithm>
#include <iostream>

namespace mwis {

/**
 * A function object which compares two elements by looking up the values
 * associated to them in a property map, and comparing these using Comparator
 * (by default, using operator <).
 */
template<typename PropertyMap,
         typename Comparator = std::less<
           typename boost::property_traits<PropertyMap>::value_type> >
class compare_by_property {
  PropertyMap _map;
  Comparator _comparator;
public:
  typedef typename boost::property_traits<PropertyMap>::key_type argument_type;
  typedef argument_type first_argument_type;
  typedef argument_type second_argument_type;
  typedef bool result_type;

  compare_by_property(PropertyMap map,
                      Comparator comparator = Comparator()):
    _map(map), _comparator(comparator)  {}

  bool operator()(const argument_type &a, const argument_type &b) const {
    return _comparator(get(_map, a), get(_map, b));
  }
};

/**
 * Convenience function to create a property map comparator.
 */
template<typename PropertyMap,
         typename Comparator = std::less<
           typename boost::property_traits<PropertyMap>::value_type> >
compare_by_property<PropertyMap, Comparator>
make_property_map_comparator(PropertyMap map,
                             Comparator comparator = Comparator()) {
  return compare_by_property<PropertyMap, Comparator>(map, comparator);
}

/**
 * Function object that returns true iff an element belongs to a container.
 *
 * Elements are searched by ussing the find method on the container.
 */
template<typename Container, typename Key>
class container_membership_test {
  const Container &_container;
public:
  container_membership_test(const Container &container):
    _container(container)
    {}