/usr/include/polymake/matroid/modular_cut.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 112 113 114 115 116 117 118 119 120 121 122 123 124 125 | /* 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_MODULAR_CUT_H__
#define __POLYMAKE_MATROID_MODULAR_CUT_H__
#include "polymake/Array.h"
#include "polymake/Set.h"
#include "polymake/PowerSet.h"
#include "polymake/Map.h"
#include "polymake/graph/Lattice.h"
#include "polymake/graph/Decoration.h"
#include "polymake/graph/LatticeTools.h"
#include <list>
namespace polymake { namespace matroid {
using graph::Lattice;
using graph::lattice::Sequential;
using graph::lattice::BasicDecoration;
namespace {
template<typename HDType>
bool covering_condition(const Set<int>& Cset, const HDType& LF, const Map<Set<int>, int>& index_of, bool verbose) {
for (typename Entire<Subsets_of_k<const Set<int>&> >::const_iterator pit=entire(all_subsets_of_k(Cset, 2)); !pit.at_end(); ++pit) {
const Set<int> p(*pit);
const int x(p.front()), y(p.back());
const int join = index_of[LF.face(x) * LF.face(y)];
/*
Because of not(a => b) being equivalent to a and (not b),
not(x or y covers x^y => x^y in C)
is equivalent to
(x or y covers x^y), and x^y notin C
*/
if (!Cset.contains(join) &&
(LF.in_adjacent_nodes(x).contains(join) ||
LF.in_adjacent_nodes(y).contains(join))) {
if (verbose) cout << "The given set does not satisfy the covering condition because "
<< "at least one of " << LF.face(x) << " and " << LF.face(y)
<< " strictly covers their intersection " << LF.face(x) * LF.face(y)
<< ", which is not in the cut"
<< endl;
return false;
}
}
return true;
}
} // end anonymous namespace
/*
A modular cut is a subset C of a lattice of flats such that
(1) C is convex, i.e. x,z in C, x<y<z implies y in C
(2) C contains {0,...,n-1}
(3) x,y in C, x covers x^y implies x^y in C.
*/
template<typename SetType>
bool is_modular_cut_impl(const Array<SetType>& C, const Lattice<BasicDecoration, Sequential>& LF, bool verbose)
{
// prepare data structures for lattice of flats
Map<Set<int>, int> index_of;
for (int i=0; i<=LF.rank(); ++i) {
for (auto fit = entire(LF.nodes_of_rank(i)); !fit.at_end(); ++fit) {
index_of[LF.face(*fit)] = *fit;
}
}
Set<int> Cset;
for (typename Entire<Array<SetType> >::const_iterator cit = entire(C); !cit.at_end(); ++cit) {
Map<Set<int>, int>::const_iterator tmp = index_of.find(*cit);
if(tmp == index_of.end()){
if (verbose) cout << "The given array is not a modular cut because "
<< *cit << " is not a flat of the given matroid."
<< endl;
return false;
}
Cset += tmp->second;
}
if (!Cset.contains(LF.top_node())) {
if (verbose) cout << "The given set is not a modular cut because "
<< "it does not contain the set " << LF.face(LF.top_node()) << "."
<< endl;
return false;
}
if (!is_convex_subset(Cset, LF, verbose)) {
if (verbose) cout << "The given set is not a modular cut because "
<< "it is not convex."
<< endl;
return false;
}
if (!covering_condition(Cset, LF, index_of, verbose)) {
if (verbose) cout << "The given set is not a modular cut because "
<< "it does not satisfy the covering condition."
<< endl;
return false;
}
return true;
}
} }
#endif // __POLYMAKE_MATROID_MODULAR_CUT_H__
// Local Variables:
// mode:C++
// c-basic-offset:3
// indent-tabs-mode:nil
// End:
|