OKlibrary  0.2.1.6
OKlib::SetAlgorithms::Subsumption_elimination< ContainerSets, UniquenessTag, OrderTag, SizeTag > Class Template Reference

Functor template for eliminating all inclusions from a container. More...

#include <Subsumption.hpp>

List of all members.

Public Types

typedef SizeTag size_tag
typedef UniquenessTag uniqueness_tag
typedef OrderTag order_tag

Public Member Functions

template<typename Iterator >
void upward (ContainerSets &C, Iterator begin, const Iterator end) const
template<typename Iterator >
void upward (ContainerSets &C, Iterator begin, const Iterator end, SubsumptionsTags::do_not_use_size_of_hyperedges) const
template<typename Iterator >
void upward (ContainerSets &C, Iterator begin, const Iterator end, SubsumptionsTags::use_size_of_hyperedges) const
template<typename Iterator , typename Size >
bool cheque_unnecessary (const Iterator j, const Size size, SubsumptionsTags::hyperedges_sorted_by_size, SubsumptionsTags::hyperedges_are_unique) const
template<typename Iterator , typename Size >
bool cheque_unnecessary (const Iterator j, const Size size, SubsumptionsTags::hyperedges_sorted_by_size, SubsumptionsTags::hyperedges_may_not_be_unique) const
template<typename Iterator , typename Size >
bool cheque_unnecessary (const Iterator j, const Size size, SubsumptionsTags::hyperedges_may_not_be_sorted_by_size, SubsumptionsTags::hyperedges_are_unique) const
template<typename Iterator , typename Size >
bool cheque_unnecessary (const Iterator j, const Size size, SubsumptionsTags::hyperedges_may_not_be_sorted_by_size, SubsumptionsTags::hyperedges_may_not_be_unique) const
void operator() (ContainerSets &C) const
void eliminate (ContainerSets &C, SubsumptionsTags::hyperedges_sorted_by_size) const
void eliminate (ContainerSets &C, SubsumptionsTags::hyperedges_may_not_be_sorted_by_size) const

Detailed Description

template<class ContainerSets, class UniquenessTag = SubsumptionsTags::hyperedges_may_not_be_unique, class OrderTag = SubsumptionsTags::hyperedges_may_not_be_sorted_by_size, class SizeTag = typename boost::mpl::if_<typename OKlib::traits::has_size_function<ContainerSets>::type, SubsumptionsTags::use_size_of_hyperedges, SubsumptionsTags::do_not_use_size_of_hyperedges>::type>
class OKlib::SetAlgorithms::Subsumption_elimination< ContainerSets, UniquenessTag, OrderTag, SizeTag >

Functor template for eliminating all inclusions from a container.

Usage:

  • Default is Subsumption_elimination<Container_type>()(C), which changes C in-place.
  • Type-tags can be provided to specify that hyperedges are unique and/or that hyperedges are sorted by size (in increasing size; so that only forward-subsumption needs to be considered).
Todo:
Improve implementation
  • ContainerSets is conceptually a hypergraph; if ContainerSets actually is equipped with a (the) vertex-hyperedge graph, then for every hyperedge H we can run (efficiently) through all hyperedges H' with non-empty intersection with H and compute the size of H - H': if the size is 0, then H' <= H, if the size is |H'| - |H|, then H <= H'.
Todo:
Create the concept
  • The requirement must include that ContainerSets supports erase without invalidating iterators.

Definition at line 157 of file Subsumption.hpp.


Member Typedef Documentation

template<class ContainerSets , class UniquenessTag = SubsumptionsTags::hyperedges_may_not_be_unique, class OrderTag = SubsumptionsTags::hyperedges_may_not_be_sorted_by_size, class SizeTag = typename boost::mpl::if_<typename OKlib::traits::has_size_function<ContainerSets>::type, SubsumptionsTags::use_size_of_hyperedges, SubsumptionsTags::do_not_use_size_of_hyperedges>::type>
typedef OrderTag OKlib::SetAlgorithms::Subsumption_elimination< ContainerSets, UniquenessTag, OrderTag, SizeTag >::order_tag

Definition at line 161 of file Subsumption.hpp.

template<class ContainerSets , class UniquenessTag = SubsumptionsTags::hyperedges_may_not_be_unique, class OrderTag = SubsumptionsTags::hyperedges_may_not_be_sorted_by_size, class SizeTag = typename boost::mpl::if_<typename OKlib::traits::has_size_function<ContainerSets>::type, SubsumptionsTags::use_size_of_hyperedges, SubsumptionsTags::do_not_use_size_of_hyperedges>::type>
typedef SizeTag OKlib::SetAlgorithms::Subsumption_elimination< ContainerSets, UniquenessTag, OrderTag, SizeTag >::size_tag

Definition at line 159 of file Subsumption.hpp.

template<class ContainerSets , class UniquenessTag = SubsumptionsTags::hyperedges_may_not_be_unique, class OrderTag = SubsumptionsTags::hyperedges_may_not_be_sorted_by_size, class SizeTag = typename boost::mpl::if_<typename OKlib::traits::has_size_function<ContainerSets>::type, SubsumptionsTags::use_size_of_hyperedges, SubsumptionsTags::do_not_use_size_of_hyperedges>::type>
typedef UniquenessTag OKlib::SetAlgorithms::Subsumption_elimination< ContainerSets, UniquenessTag, OrderTag, SizeTag >::uniqueness_tag

Definition at line 160 of file Subsumption.hpp.


Member Function Documentation

template<class ContainerSets , class UniquenessTag = SubsumptionsTags::hyperedges_may_not_be_unique, class OrderTag = SubsumptionsTags::hyperedges_may_not_be_sorted_by_size, class SizeTag = typename boost::mpl::if_<typename OKlib::traits::has_size_function<ContainerSets>::type, SubsumptionsTags::use_size_of_hyperedges, SubsumptionsTags::do_not_use_size_of_hyperedges>::type>
template<typename Iterator , typename Size >
bool OKlib::SetAlgorithms::Subsumption_elimination< ContainerSets, UniquenessTag, OrderTag, SizeTag >::cheque_unnecessary ( const Iterator  j,
const Size  size,
SubsumptionsTags::hyperedges_sorted_by_size  ,
SubsumptionsTags::hyperedges_are_unique   
) const [inline]
template<class ContainerSets , class UniquenessTag = SubsumptionsTags::hyperedges_may_not_be_unique, class OrderTag = SubsumptionsTags::hyperedges_may_not_be_sorted_by_size, class SizeTag = typename boost::mpl::if_<typename OKlib::traits::has_size_function<ContainerSets>::type, SubsumptionsTags::use_size_of_hyperedges, SubsumptionsTags::do_not_use_size_of_hyperedges>::type>
template<typename Iterator , typename Size >
bool OKlib::SetAlgorithms::Subsumption_elimination< ContainerSets, UniquenessTag, OrderTag, SizeTag >::cheque_unnecessary ( const Iterator  j,
const Size  size,
SubsumptionsTags::hyperedges_sorted_by_size  ,
SubsumptionsTags::hyperedges_may_not_be_unique   
) const [inline]

Definition at line 198 of file Subsumption.hpp.

template<class ContainerSets , class UniquenessTag = SubsumptionsTags::hyperedges_may_not_be_unique, class OrderTag = SubsumptionsTags::hyperedges_may_not_be_sorted_by_size, class SizeTag = typename boost::mpl::if_<typename OKlib::traits::has_size_function<ContainerSets>::type, SubsumptionsTags::use_size_of_hyperedges, SubsumptionsTags::do_not_use_size_of_hyperedges>::type>
template<typename Iterator , typename Size >
bool OKlib::SetAlgorithms::Subsumption_elimination< ContainerSets, UniquenessTag, OrderTag, SizeTag >::cheque_unnecessary ( const Iterator  j,
const Size  size,
SubsumptionsTags::hyperedges_may_not_be_sorted_by_size  ,
SubsumptionsTags::hyperedges_are_unique   
) const [inline]

Definition at line 203 of file Subsumption.hpp.

template<class ContainerSets , class UniquenessTag = SubsumptionsTags::hyperedges_may_not_be_unique, class OrderTag = SubsumptionsTags::hyperedges_may_not_be_sorted_by_size, class SizeTag = typename boost::mpl::if_<typename OKlib::traits::has_size_function<ContainerSets>::type, SubsumptionsTags::use_size_of_hyperedges, SubsumptionsTags::do_not_use_size_of_hyperedges>::type>
template<typename Iterator , typename Size >
bool OKlib::SetAlgorithms::Subsumption_elimination< ContainerSets, UniquenessTag, OrderTag, SizeTag >::cheque_unnecessary ( const Iterator  j,
const Size  size,
SubsumptionsTags::hyperedges_may_not_be_sorted_by_size  ,
SubsumptionsTags::hyperedges_may_not_be_unique   
) const [inline]

Definition at line 207 of file Subsumption.hpp.

template<class ContainerSets , class UniquenessTag = SubsumptionsTags::hyperedges_may_not_be_unique, class OrderTag = SubsumptionsTags::hyperedges_may_not_be_sorted_by_size, class SizeTag = typename boost::mpl::if_<typename OKlib::traits::has_size_function<ContainerSets>::type, SubsumptionsTags::use_size_of_hyperedges, SubsumptionsTags::do_not_use_size_of_hyperedges>::type>
void OKlib::SetAlgorithms::Subsumption_elimination< ContainerSets, UniquenessTag, OrderTag, SizeTag >::eliminate ( ContainerSets &  C,
SubsumptionsTags::hyperedges_sorted_by_size   
) const [inline]
template<class ContainerSets , class UniquenessTag = SubsumptionsTags::hyperedges_may_not_be_unique, class OrderTag = SubsumptionsTags::hyperedges_may_not_be_sorted_by_size, class SizeTag = typename boost::mpl::if_<typename OKlib::traits::has_size_function<ContainerSets>::type, SubsumptionsTags::use_size_of_hyperedges, SubsumptionsTags::do_not_use_size_of_hyperedges>::type>
void OKlib::SetAlgorithms::Subsumption_elimination< ContainerSets, UniquenessTag, OrderTag, SizeTag >::eliminate ( ContainerSets &  C,
SubsumptionsTags::hyperedges_may_not_be_sorted_by_size   
) const [inline]
template<class ContainerSets , class UniquenessTag = SubsumptionsTags::hyperedges_may_not_be_unique, class OrderTag = SubsumptionsTags::hyperedges_may_not_be_sorted_by_size, class SizeTag = typename boost::mpl::if_<typename OKlib::traits::has_size_function<ContainerSets>::type, SubsumptionsTags::use_size_of_hyperedges, SubsumptionsTags::do_not_use_size_of_hyperedges>::type>
void OKlib::SetAlgorithms::Subsumption_elimination< ContainerSets, UniquenessTag, OrderTag, SizeTag >::operator() ( ContainerSets &  C) const [inline]
template<class ContainerSets , class UniquenessTag = SubsumptionsTags::hyperedges_may_not_be_unique, class OrderTag = SubsumptionsTags::hyperedges_may_not_be_sorted_by_size, class SizeTag = typename boost::mpl::if_<typename OKlib::traits::has_size_function<ContainerSets>::type, SubsumptionsTags::use_size_of_hyperedges, SubsumptionsTags::do_not_use_size_of_hyperedges>::type>
template<typename Iterator >
void OKlib::SetAlgorithms::Subsumption_elimination< ContainerSets, UniquenessTag, OrderTag, SizeTag >::upward ( ContainerSets &  C,
Iterator  begin,
const Iterator  end 
) const [inline]
template<class ContainerSets , class UniquenessTag = SubsumptionsTags::hyperedges_may_not_be_unique, class OrderTag = SubsumptionsTags::hyperedges_may_not_be_sorted_by_size, class SizeTag = typename boost::mpl::if_<typename OKlib::traits::has_size_function<ContainerSets>::type, SubsumptionsTags::use_size_of_hyperedges, SubsumptionsTags::do_not_use_size_of_hyperedges>::type>
template<typename Iterator >
void OKlib::SetAlgorithms::Subsumption_elimination< ContainerSets, UniquenessTag, OrderTag, SizeTag >::upward ( ContainerSets &  C,
Iterator  begin,
const Iterator  end,
SubsumptionsTags::do_not_use_size_of_hyperedges   
) const [inline]

Definition at line 169 of file Subsumption.hpp.

References Latex_Handler::begin(), and end.

template<class ContainerSets , class UniquenessTag = SubsumptionsTags::hyperedges_may_not_be_unique, class OrderTag = SubsumptionsTags::hyperedges_may_not_be_sorted_by_size, class SizeTag = typename boost::mpl::if_<typename OKlib::traits::has_size_function<ContainerSets>::type, SubsumptionsTags::use_size_of_hyperedges, SubsumptionsTags::do_not_use_size_of_hyperedges>::type>
template<typename Iterator >
void OKlib::SetAlgorithms::Subsumption_elimination< ContainerSets, UniquenessTag, OrderTag, SizeTag >::upward ( ContainerSets &  C,
Iterator  begin,
const Iterator  end,
SubsumptionsTags::use_size_of_hyperedges   
) const [inline]

The documentation for this class was generated from the following file: