/usr/include/polymake/matroid/revlex_bases.h is in libpolymake-dev-common 3.2r2-3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 | /* Copyright (c) 1997-2018
Ewgenij Gawrilow, Michael Joswig (Technische Universitaet Berlin, Germany)
http://www.polymake.org
This program is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by the
Free Software Foundation; either version 2, or (at your option) any
later version: http://www.gnu.org/licenses/gpl.txt.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
--------------------------------------------------------------------------------
*/
#ifndef __POLYMAKE_MATROID_REVLEX_BASES_H__
#define __POLYMAKE_MATROID_REVLEX_BASES_H__
#include "polymake/Array.h"
#include "polymake/Set.h"
#include "polymake/PowerSet.h"
#include "polymake/Integer.h"
#include "polymake/matroid/check_axioms.h"
namespace polymake { namespace matroid {
namespace {
template<typename Container>
bool revlex(const Container& a, const Container& b)
{
assert (a.size() == b.size());
for (typename Entire<Container>::const_reverse_iterator ait = rentire(a), bit = rentire(b); !ait.at_end(); ++ait, ++bit) {
if (*ait < *bit) return true;
if (*ait > *bit) return false;
}
return false;
}
} // end anonymous namespace
// TODO: replace with backward traversal of Subsets_of_k when implemented
inline
Array<Set<int> > make_revlex_bases(int n, int r)
{
Array<Set<int>> revlex_bases(int(Integer::binom(n,r)));
auto rit = entire(revlex_bases);
for (Entire<Subsets_of_k<const sequence&> >::const_iterator bit(entire(all_subsets_of_k(sequence(0,n), r))); !bit.at_end(); ++bit, ++rit)
*rit = Set<int>(*bit);
std::sort(revlex_bases.begin(), revlex_bases.end(), revlex<Set<int> >);
return revlex_bases;
}
template<typename Container>
std::string bases_to_revlex_encoding_impl(const Container& bases,
int rank,
int n_elements)
{
Set<Set<int> > bases_set;
for (typename Entire<Container>::const_iterator ait = entire(bases); !ait.at_end(); ++ait)
bases_set += *ait; // must do this instead of "Set<Set<int> > bases_set(entire(bases));" to get the Set tree right and enable searching
const Array<Set<int> > revlex_bases = make_revlex_bases(n_elements, rank);
std::string encoding;
for (Entire<Array<Set<int> > >::const_iterator bit = entire(revlex_bases); !bit.at_end(); ++bit)
encoding += (bases_set.contains(*bit)
? '*'
: '0');
return encoding;
}
template<typename Container>
Array<Set<int> > bases_from_revlex_encoding_impl(const Container& revlex_encoding,
int rank,
int n_elements,
bool dual = false,
bool check = false)
{
const Array<Set<int> > revlex_bases = make_revlex_bases(n_elements, rank);
Array<Set<int> > matroid_bases(std::count(revlex_encoding.begin(), revlex_encoding.end(), '*') +
std::count(revlex_encoding.begin(), revlex_encoding.end(), '1'));
Entire<Array<Set<int> > >::iterator mbit = entire(matroid_bases);
Entire<Array<Set<int> > >::const_iterator rbit = entire(revlex_bases);
for (typename Entire<Container>::const_iterator sit = entire(revlex_encoding); !sit.at_end(); ++sit, ++rbit) {
if (*sit == '*' || *sit == '1') {
*mbit = (dual
? Set<int>(sequence(0,n_elements) - *rbit)
: *rbit);
++mbit;
}
}
if (check && !check_basis_exchange_axiom_impl(matroid_bases, true))
throw std::runtime_error("The given revlex string did not correspond to a matroid.");
return matroid_bases;
}
} }
#endif // __POLYMAKE_MATROID_REVLEX_BASES_H__
// Local Variables:
// mode:C++
// c-basic-offset:3
// indent-tabs-mode:nil
// End:
|