1 /*
2 This program is free software; you can redistribute it and/or
3 modify it under the terms of the GNU General Public License
4 as published by the Free Software Foundation; either version 2
5 of the License, or (at your option) any later version.
6
7 This program is distributed in the hope that it will be useful,
8 but WITHOUT ANY WARRANTY; without even the implied warranty of
9 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 GNU General Public License for more details.
11
12 You should have received a copy of the GNU General Public License
13 along with this program; if not, write to the Free Software
14 Foundation, Inc., 51 Franklin Street, Fifth Floor,
15 Boston, MA 02110-1301, USA.
16
17 ---
18 Copyright (C) 2011 - 2015, Simon Hampe <simon.hampe@googlemail.com>
19
20 ---
21 Copyright (c) 2016-2021
22 Ewgenij Gawrilow, Michael Joswig, and the polymake team
23 Technische Universität Berlin, Germany
24 https://polymake.org
25
26 Reconstructs the matroid from a bergman fan.
27 */
28
29
30 #include "polymake/client.h"
31 #include "polymake/Rational.h"
32 #include "polymake/Matrix.h"
33 #include "polymake/Array.h"
34 #include "polymake/Set.h"
35 #include "polymake/PowerSet.h"
36 #include "polymake/list"
37 #include "polymake/tropical/specialcycles.h"
38 #include "polymake/tropical/misc_tools.h"
39 #include "polymake/tropical/thomog.h"
40
41 namespace polymake { namespace tropical {
42
43 template <typename Addition>
matroid_from_fan(BigObject cycle)44 BigObject matroid_from_fan(BigObject cycle)
45 {
46 // Find rank and ground set
47 Int ambient_dim = cycle.give("PROJECTIVE_AMBIENT_DIM");
48 Int n = ambient_dim+1;
49 Int dim = cycle.give("PROJECTIVE_DIM");
50 Int r = dim+1;
51
52 if (dim == ambient_dim) {
53 return call_function("matroid::uniform_matroid", n, n);
54 }
55
56 // FIXME Testing this could be done in a more efficient way by
57 // finding all cones containing the origin and testing for
58 // complementarity with unit vectors.
59 // Take all r-sets and check if they are a basis
60 Array<Set<Int>> rsets{ all_subsets_of_k(sequence(0,n), r) };
61 std::list<Set<Int>> bases;
62 for (const auto& rset : rsets) {
63 BigObject hp = affine_linear_space<Addition>(unit_matrix<Rational>(n).minor(~rset, All));
64 BigObject inter = call_function("intersect", cycle, hp);
65 bool empty = call_function("is_empty", inter);
66 if (!empty) bases.push_back(rset);
67 }
68 return BigObject("matroid::Matroid",
69 "N_ELEMENTS", n,
70 "BASES", Array<Set<Int>>(bases));
71 }
72
73 UserFunctionTemplate4perl("# @category Matroids"
74 "# Takes the bergman fan of a matroid and reconstructs the corresponding matroid"
75 "# The fan has to be given in its actual matroid coordinates, not as an isomorphic"
76 "# transform. The actual subdivision is not relevant."
77 "# @param Cycle<Addition> A tropical cycle, the Bergman fan of a matroid"
78 "# @return matroid::Matroid",
79 "matroid_from_fan<Addition>(Cycle<Addition>)");
80 } }
81