OKlibrary  0.2.1.6
Namespaces | Classes | Functions | Variables
OKlib::SetAlgorithms Namespace Reference

Components for sets-related algorithms and datastructures. More...

Namespaces

namespace  SubsumptionsTags
namespace  Testobjects
namespace  tests

Classes

class  MapValue
 Adaptor to create a functor from a map in the sense of the C++ standard. More...
class  Test_MapValue
class  Disjoint
 Unary predicate checking whether a set B is disjoint to the given set A. More...
class  Union
 Functor: Given a range (input iterators) of ordered sequences, which are given as input-iterator-ranges, and an output iterator, compute the union. More...
class  Intersection
 Functor: Given a range (input iterators) of ordered sequences, which are given as input-iterator-ranges, and an output iterator, compute the intersection. More...
class  TestOperation
class  Test_Union
class  Test_Intersection
struct  Size
struct  Sum_sizes
class  Test_Sum_sizes
struct  Get_underlying_iterator
struct  Get_underlying_iterator< boost::reverse_iterator< Iterator > >
struct  Get_underlying_iterator< std::reverse_iterator< Iterator > >
class  Erase
 Functor template for (generically) erasing an element from a container while maintaining the element-specifying iterator. More...
struct  Erase< std::set< T > >
struct  Erase< std::multiset< T > >
class  Subsumption_elimination
 Functor template for eliminating all inclusions from a container. More...
class  Test_Subsumption_elimination
class  Subsumption_hypergraph
 Constructing the subsumption hypergraph. More...

Functions

template<class Map >
MapValue< Map >::result_type map_value (const Map &map, const typename MapValue< Map >::argument_type &x)
template<typename InputIterator_sets , typename OutputIterator >
OutputIterator union_sets (const InputIterator_sets begin_sets, const InputIterator_sets end_sets, const OutputIterator out)
template<typename InputIterator_sets , typename OutputIterator >
OutputIterator intersection_sets (const InputIterator_sets begin_sets, const InputIterator_sets end_sets, const OutputIterator out)
template<typename InputIterator_sets >
boost::range_size< typename
InputIterator_sets::value_type >
::type 		sum_sizes (const InputIterator_sets begin, const InputIterator_sets end)
template<class ContainerSets >
void subsumption_elimination_upward (ContainerSets &C)
template<class ContainerSets >
void subsumption_elimination (ContainerSets &C)
template<class RangeF , class RangeG >
Subsumption_hypergraph< RangeF,
RangeG >::set_system_type 		subsumption_hypergraph (const RangeF &f_range, const RangeG &g_range)
 Computes the subsumption hypergraph.

Variables

Test_Sum_sizes< Sum_sizes > test_sum_sizes
Test_Subsumption_elimination
< Subsumption_elimination > 		test_subsumption_elimination

Detailed Description

Components for sets-related algorithms and datastructures.

Function Documentation

template<typename InputIterator_sets , typename OutputIterator >
OutputIterator OKlib::SetAlgorithms::intersection_sets ( const InputIterator_sets  begin_sets,
const InputIterator_sets  end_sets,
const OutputIterator  out 
) [inline]

Definition at line 206 of file BasicSetOperations.hpp.

Referenced by OKlib::SATCompetition::ResultDatabase< result_iterator_type >::intersection(), and OKlib::Combinatorics::Hypergraphs::Transversals::Bounded::Bounded_transversals_bv< SetSystem >::operator()().

template<class Map >
MapValue<Map>::result_type OKlib::SetAlgorithms::map_value ( const Map &  map,
const typename MapValue< Map >::argument_type &  x 
)

Definition at line 56 of file BasicMapOperations.hpp.

Referenced by OKlib::SATCompetition::LexicographicalEvaluation< IndexedDatabase, SeriesPolicy, NumberType >::evaluation(), OKlib::SATCompetition::LexicographicalEvaluationRandom< indexed_database >::evaluation(), and OKlib::SATCompetition::Scoring_from_file< ParserExtension, ResultClass, SeriesPursePolicy >::Scoring_from_file().

template<class ContainerSets >
void OKlib::SetAlgorithms::subsumption_elimination ( ContainerSets &  C) [inline]

Definition at line 233 of file Subsumption.hpp.

template<class ContainerSets >
void OKlib::SetAlgorithms::subsumption_elimination_upward ( ContainerSets &  C) [inline]

Definition at line 228 of file Subsumption.hpp.

template<class RangeF , class RangeG >
Subsumption_hypergraph<RangeF, RangeG>::set_system_type OKlib::SetAlgorithms::subsumption_hypergraph ( const RangeF &  f_range,
const RangeG &  g_range 
)

Computes the subsumption hypergraph.

Given two ordered set system as ranges f_range and g_range (of type RangeF and RangeG respectively), yielding hypergraphs F and G, constructs the standardised ordered subsumption hypergraph.

The subsumption hypergraph is returned as the hyperedge list (H_1,...,H_|G|) where for all 1 <= j <= |G| we have that H_j is the sublist of (1,...,|F|) of those i where F_i contained in G_j, while H_j is a list of Ints where Int is the size type of f_range.

The Maxima-specification is subsumption_std_ohg(F,G) (see ComputerAlgebra/Hypergraphs/Lisp/Basics.mac).

Parameters:
f_rangethe conceptual vertices of the subsumption hypergraph, i.e., the list of sets which subsumes elements of g_range.
g_rangethe list of sets which are mapped to hyperedges, i.e., the sets which are subsumed by elements of f_range.
Returns:
the std::vector of hyperedges in the subsumption hypergraph of f_range (subsuming sets) w.r.t g_range (subsumed sets).

Definition at line 261 of file SubsumptionHypergraph.hpp.

References OKlib::SetAlgorithms::Subsumption_hypergraph< RangeF, RangeG, Int >::hyperedges.

Referenced by main().

template<typename InputIterator_sets >
boost::range_size<typename InputIterator_sets::value_type>::type OKlib::SetAlgorithms::sum_sizes ( const InputIterator_sets  begin,
const InputIterator_sets  end 
) [inline]

Definition at line 53 of file SequenceOperations.hpp.

template<typename InputIterator_sets , typename OutputIterator >
OutputIterator OKlib::SetAlgorithms::union_sets ( const InputIterator_sets  begin_sets,
const InputIterator_sets  end_sets,
const OutputIterator  out 
) [inline]

Definition at line 129 of file BasicSetOperations.hpp.

Variable Documentation

Test_Subsumption_elimination<Subsumption_elimination> OKlib::SetAlgorithms::test_subsumption_elimination

Definition at line 17 of file Subsumption_Testobjects.hpp.

Test_Sum_sizes<Sum_sizes> OKlib::SetAlgorithms::test_sum_sizes

Definition at line 17 of file SequenceOperations_Testobjects.hpp.