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 Computes a matroid fan in its chains-of-flats structure.
27 */
28
29 #include "polymake/client.h"
30 #include "polymake/Matrix.h"
31 #include "polymake/IncidenceMatrix.h"
32 #include "polymake/Rational.h"
33 #include "polymake/Vector.h"
34 #include "polymake/Set.h"
35 #include "polymake/graph/Lattice.h"
36 #include "polymake/graph/Decoration.h"
37 #include "polymake/graph/maximal_chains.h"
38 #include "polymake/tropical/specialcycles.h"
39
40 namespace polymake { namespace tropical {
41
42 using graph::Lattice;
43 using graph::lattice::Sequential;
44 using graph::lattice::BasicDecoration;
45
46 template <typename Addition>
matroid_fan_from_flats(BigObject matroid)47 BigObject matroid_fan_from_flats(BigObject matroid)
48 {
49 // Extract properties
50 const Int n = matroid.give("N_ELEMENTS");
51 const Set<Int> loops = matroid.give("LOOPS");
52 if (loops.size() != 0) {
53 return empty_cycle<Addition>(n-1);
54 }
55 BigObject flats_obj = matroid.give("LATTICE_OF_FLATS");
56 Lattice<BasicDecoration, Sequential> flats(flats_obj);
57 IncidenceMatrix<> chains_incidence( maximal_chains( flats, false,false));
58 const IncidenceMatrix<> faces = flats_obj.give("FACES");
59
60 const Int empty_index = flats_obj.give("BOTTOM_NODE");
61 const Int top_index = flats_obj.give("TOP_NODE");
62
63 // Create rays
64 const Matrix<Rational> unitm = zero_vector<Rational>() | unit_matrix<Rational>(n);
65 Matrix<Rational> rays(faces.rows(), n+1);
66 rays(empty_index,0) = 1;
67 for (Int f = 1; f < faces.rows()-1; ++f) {
68 rays.row(f) = Addition::orientation() * accumulate(rows(unitm.minor(faces.row(f),All)), operations::add());
69 }
70 const auto extreme_nodes = scalar2set(top_index);
71 chains_incidence = chains_incidence.minor(All, ~extreme_nodes);
72 rays = rays.minor(~extreme_nodes, All);
73
74 return BigObject("Cycle", mlist<Addition>(),
75 "PROJECTIVE_VERTICES", rays,
76 "MAXIMAL_POLYTOPES", chains_incidence,
77 "WEIGHTS", ones_vector<Integer>(chains_incidence.rows()));
78 }
79
80 UserFunctionTemplate4perl("# @category Matroids"
81 "# Computes the fan of a matroid in its chains-of-flats subdivision."
82 "# Note that this is potentially very slow for large matroids."
83 "# @param matroid::Matroid A matroid. Should be loopfree."
84 "# @tparam Addition Min or max, determines the matroid fan coordinates."
85 "# @return Cycle<Addition>",
86 "matroid_fan_from_flats<Addition>(matroid::Matroid)");
87 } }
88