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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
|
# Copyright (c) 1997-2024
# Ewgenij Gawrilow, Michael Joswig, and the polymake team
# Technische Universität Berlin, Germany
# https://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.
#-------------------------------------------------------------------------------
# TODO: introduce "tropical Monomials" interpreting "DD x" as "x ** DD"
# and get rid of this function
# This file contains methods to parse a tropical polynomial in the form
# "max(3x+4,...)" and the like.
# @category Data Conversion
# This converts a string into a tropical polynomial. The syntax for the string is as follows:
# It is of the form "min(...)" or "max(...)" or "min{...}" or "max{...}", where ...
# is a comma-separated list of sums of the form "a + bx + c + dy + ...", where a,c are
# rational numbers, b,d are Ints and x,y are variables.
# Such a sum can contain several such terms for the same variable and they need not be in any order.
# Any text that starts with a letter and does not contain any of +-*,(){} or whitespace can be a variable.
# A term in a sum can be of the form "3x", "3*x", but "x3"will be interpreted as 1 * "x3".
# Coefficients should not contain letters and there is no evaluation of arithmetic, i.e. "(2+4)*x" does
# not work (though "2x+4x" would be fine).
# In fact, further brackets should only be used (but are not necessary!) for single coefficienst,
# e.g. "(-3)*x".
# Warning: The parser will remove all brackets before parsing the individual sums.
# If no further arguments are given, the function will take the number of occurring variables
# as total number of variables and create a ring for the result. The variables will be sorted alphabetically.
# @param String s The string to be parsed
# @param String vars Optional list of variables. If this is given, all variables used in s must match one of the variables in this list.
# @return Polynomial<TropicalNumber<__Addition__, Rational>>, where __Addition__ depends on
# whether min or max was used in the string.
user_function toTropicalPolynomial(String; @) {
my ($string,@vars) = @_;
# Remove any whitespace before parsing
$string =~ s/\s+//g;
# Check if variables have been given
my $vars_defined = (scalar(@vars) > 0);
my $varset = new Set<String>(\@vars);
if ($vars_defined) {
# If there are double variables, throw an error
if ($varset->size() < scalar(@vars)) {
die "Error: Variable names must be unique.";
}
}
# First separate min/max from the list of the functions
# The first part will contain min or max, the second the rest
my @minmax_separator = ($string =~ /^(max|min)[\(\{](.+)[\)\}]$/i);
if (scalar(@minmax_separator) != 2) {
die "Error: Wrong syntax. See documentation.";
}
# Determine whether we're using min or max
my $minmax = $minmax_separator[0] =~ /^min$/i ? typeof Min : typeof Max;
# Remove any brackets from the function list and separate by commas
$minmax_separator[1] =~ s/[\(\{\)\}]+//g;
my @functionlist = split /,/, $minmax_separator[1];
# This will store the monomials
# The i-th element corresponds to the i-th function. It is a reference to a hash,
# which maps variable names to exponents.
# We need this, since we might not know until the end how many variables we have and
# what order they appear in.
my @monomial_maps=();
# This stores the coefficients of each function.
my $coefficients = new Vector<TropicalNumber<$minmax>>(scalar(@functionlist));
# Now parse every single function by splitting at + or -
for my $index (0 .. scalar(@functionlist)-1) {
my %functionCoeffMap = ();
$coefficients->[$index] = new TropicalNumber<$minmax>(0);
# We split along any consecutive sequence of + and -, keeping the actual signs for counting
my @termlist = split(/[\+\-]+/,$functionlist[$index]); #We split along any consecutive sequence of + and -
my @signlist = ($functionlist[$index] =~ /[\+\-]+/g);
# If the first terms empty that means there are signs before the actual first term
if ($termlist[0] eq "") {
shift(@termlist);
}
# If not then we don't have a sign for the first term and add it
else {
@signlist = ("+",@signlist);
}
# If the last term is empty that means there is an empty term at the end.
if ($termlist[scalar(@termlist)-1] eq "") {
die "Error: Empy term at the end of function $functionlist[$index]";
}
# Now every element in signlist corresponds to an element in termlist. We count the number of -'s
# to determine the actual sign.
for my $termindex (0 .. scalar(@termlist)-1) {
my $minussigns = scalar(($signlist[$termindex] =~ tr/\-//));
if ($minussigns % 2) { #If the number of -'s is odd, set sign to -
$termlist[$termindex] = "-" . $termlist[$termindex];
}
}
# Now parse every single term
for my $term (@termlist){
# Separate into coefficient and variable
my @termsep = ($term =~ /^(\-?[^a-zA-Z\*]*)?\*?([a-zA-Z]+[^\+\-\(\)\{\}]*)?$/);
# Check for basic validity
# If both parts are empty, we have a term of the form "*", which is nonsense
if (scalar(@termsep) != 2) {
die "Error: $term has invalid form. See documentation for allowed syntax.";
}
if ($termsep[0] eq "" && $termsep[1] eq "") {
die "Error: $term has invalid form. See documentation for allowed syntax.";
}
# Parse the coefficient (if there is none, set it to 1, since there must be a variable)
my $rational_termcoeff = new Rational($termsep[0] eq ""? 1: ($termsep[0] eq "-"? -1 : $termsep[0]));
my $termcoeff = new TropicalNumber<$minmax>($rational_termcoeff);
# If there's no variable, add to the coefficient, otherwise add to the correct monomial
# Note that we're already using tropical arithmetic here!
if ($termsep[1] eq "") {
$coefficients->[$index] *= $termcoeff;
} else {
# Add the variable, if none were given in the function call.
if (!$vars_defined) {
$varset = $varset + (new String($termsep[1]));
}
# Otherwise check if it's an allowed variable
elsif (!$varset->contains($termsep[1])) {
die "Error: Variable $termsep[1] is not in the list of variables.";
}
}
# Save the coefficient in the hash map
if (!defined($functionCoeffMap{$termsep[1]})) {
$functionCoeffMap{$termsep[1]} = $termcoeff;
} else {
$functionCoeffMap{$termsep[1]} *= $termcoeff;
}
}#END parse all terms
$monomial_maps[$index] = \%functionCoeffMap;
} #END for(functionlist)
# If no variables were given, we remove double variables and sort them alphabetically
if (!$vars_defined) {
if ($varset->size() == 0) {
die "Error: There must be at least one variable.";
}
@vars = sort(@{$varset});
}
# Now create exponent matrix
my $monom_matrix = new Matrix<Int>(scalar(@functionlist), scalar(@vars));
for my $func (0 .. scalar(@functionlist)-1) {
my $hashref = $monomial_maps[$func];
my %monmap = %$hashref;
for my $v (0 .. scalar(@vars)-1) {
$monom_matrix->elem($func,$v) = defined($monmap{$vars[$v]})? $monmap{$vars[$v]} : 0;
}
}
return new Polynomial<TropicalNumber<$minmax>>($coefficients, $monom_matrix);
}#END toTropicalPolynomial(String,...)
# Local Variables:
# mode: perl
# cperl-indent-level:3
# indent-tabs-mode:nil
# End:
|
