fmp_transducer_maker.thxx 6.91 KB
Newer Older
Michaël Cadilhac's avatar
Michaël Cadilhac committed
1
//							-*- C++ -*-
2
// fmp_transducer_maker.thxx: this file is part of the Vaucanson project.
Michaël Cadilhac's avatar
Michaël Cadilhac committed
3
//
4
// Vaucanson, a generic library for finite state machines.
Michaël Cadilhac's avatar
Michaël Cadilhac committed
5
//
6
// Copyright (C) 2005, 2006, 2008 The Vaucanson Group.
Michaël Cadilhac's avatar
Michaël Cadilhac committed
7
//
8
9
10
11
// 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
// of the License, or (at your option) any later version.
Michaël Cadilhac's avatar
Michaël Cadilhac committed
12
//
13
// The complete GNU General Public Licence Notice can be found as the
14
// `COPYING' file in the root directory.
Michaël Cadilhac's avatar
Michaël Cadilhac committed
15
//
16
// The Vaucanson Group consists of people listed in the `AUTHORS' file.
17
//
Michaël Cadilhac's avatar
Michaël Cadilhac committed
18

19
/*
Akim Demaille's avatar
Akim Demaille committed
20
 * CPP guard should not be inserted here as
Michaël Cadilhac's avatar
Michaël Cadilhac committed
21
22
23
24
 * VCSN_CONTEXT_NAMESPACE could be changed.
 */

#include <vaucanson/algorithms/minimization_hopcroft.hh>
25
#include <vaucanson/algorithms/evaluation_fmp.hh>
Michaël Cadilhac's avatar
Michaël Cadilhac committed
26
27
28
#include <vaucanson/algorithms/aut_to_exp.hh>
#include <vaucanson/algorithms/trim.hh>
#include <vaucanson/algorithms/realtime.hh>
29

30
31
namespace vcsn
{
32
  namespace VCSN_GRAPH_IMPL
33
  {
34
    VCSN_CONTEXT_NAMESPACE
35
    {
36

37
38
      template <class FirstInputIterator, class SecondInputIterator>
      automata_set_t make_automata_set(const FirstInputIterator first_begin,
39
40
41
				       const FirstInputIterator first_end,
				       const SecondInputIterator second_begin,
				       const SecondInputIterator second_end)
42
      {
43
44
	first_alphabet_t first_alpha;

45
46
47
	for (FirstInputIterator e = first_begin; e != first_end; ++e)
	  first_alpha.insert(*e);

48
49
	second_alphabet_t second_alpha;

50
51
52
	for (SecondInputIterator e = second_begin; e != second_end; ++e)
	  second_alpha.insert(*e);

53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
	semiring_t	semiring;
	first_monoid_t	mA(first_alpha);
	second_monoid_t	mB(second_alpha);
	monoid_t	freemonoidproduct(mA, mB);
	series_set_t	series(semiring, freemonoidproduct);

	return automata_set_t(series);
      }

      template <class FirstInputIterator, class SecondInputIterator>
      automata_set_t make_automata_set(const FirstInputIterator first_begin,
				       const FirstInputIterator first_end,
				       const SecondInputIterator second_begin,
				       const SecondInputIterator second_end,
				       const monoid_rep_t& mrep,
				       const first_monoid_rep_t& mrep1,
				       const second_monoid_rep_t& mrep2,
70
				       const series_rep_t& srep)
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
      {
	first_alphabet_t first_alpha;

	for (FirstInputIterator e = first_begin; e != first_end; ++e)
	  first_alpha.insert(*e);

	second_alphabet_t second_alpha;

	for (SecondInputIterator e = second_begin; e != second_end; ++e)
	  second_alpha.insert(*e);

	semiring_t	semiring;
	first_monoid_t	mA(first_alpha, mrep1);
	second_monoid_t	mB(second_alpha, mrep2);
	monoid_t	freemonoidproduct(mA, mB, mrep);
	series_set_t	series(semiring, freemonoidproduct, srep);
87
88

	return automata_set_t(series);
89
90
      }

91
92
93
94
95
96
97
98
99
      template <class FirstInputIterator, class SecondInputIterator>
      automaton_t make_automaton(const FirstInputIterator first_begin,
				 const FirstInputIterator first_end,
				 const SecondInputIterator second_begin,
				 const SecondInputIterator second_end)
      {
	return automaton_t(make_automata_set(first_begin, first_end,
					     second_begin, second_end));
      }
100
101
102

      template <class FirstInputIterator, class SecondInputIterator>
      automaton_t make_automaton(const FirstInputIterator first_begin,
103
104
105
106
107
108
				 const FirstInputIterator first_end,
				 const SecondInputIterator second_begin,
				 const SecondInputIterator second_end,
				 const monoid_rep_t& mrep,
				 const first_monoid_rep_t& mrep1,
				 const second_monoid_rep_t& mrep2,
109
				 const series_rep_t& srep)
110
      {
111
112
113
	return automaton_t(make_automata_set(first_begin, first_end,
					     second_begin, second_end,
					     mrep, mrep1, mrep2,
114
					     srep));
115
116
117
118
119
120
121
122
      }

      template <class T1, class T2>
      automaton_t make_automaton(const T1& first_alphabet,
				 const T2& second_alphabet)
      {
	return make_automaton(first_alphabet.begin(), first_alphabet.end(),
			      second_alphabet.begin(), second_alphabet.end());
123
124
125
126
      }

      template <class T1, class T2>
      automaton_t make_automaton(const T1& first_alphabet,
127
128
129
130
				 const T2& second_alphabet,
				 const monoid_rep_t& mrep,
				 const first_monoid_rep_t& mrep1,
				 const second_monoid_rep_t& mrep2,
131
				 const series_rep_t& srep)
132
133
      {
	return make_automaton(first_alphabet.begin(), first_alphabet.end(),
134
			      second_alphabet.begin(), second_alphabet.end(),
135
			      mrep, mrep1, mrep2, srep);
136
137
138
139
140
141
142
      }

      template <class FirstIterator, class SecondIterator>
      monoid_elt_t make_couple(const FirstIterator first_begin,
			       const FirstIterator first_end,
			       const SecondIterator second_begin,
			       const SecondIterator second_end,
143
144
			       const first_monoid_elt_value_t& first_exp,
			       const second_monoid_elt_value_t& second_exp)
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
      {
	first_alphabet_t	first_alpha;
	for (FirstIterator e = first_begin; e != first_end; ++e)
	  first_alpha.insert(*e);

	second_alphabet_t	second_alpha;
	for (SecondIterator e = second_begin; e != second_end; ++e)
	  second_alpha.insert(*e);

	monoid_t		fmp (first_alpha, second_alpha);
	monoid_elt_value_t	fmp_elt_value (first_exp, second_exp);

	return Element<monoid_t, monoid_elt_value_t> (fmp, fmp_elt_value);
      }

      template <class T1, class T2>
      monoid_elt_t make_couple(const T1& first_alphabet,
			       const T2& second_alphabet,
163
164
			       const first_monoid_elt_value_t& first_exp,
			       const second_monoid_elt_value_t& second_exp)
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
      {
	return make_couple(first_alphabet.begin(), first_alphabet.end(),
			   second_alphabet.begin(), second_alphabet.end(),
			   first_exp, second_exp);
      }


      template <typename TransStruct,
	        typename TransImpl,
	        typename SeriesStruct,
	        typename SeriesImpl,
	        typename S,
	        typename T>
      AUTOMATON_CONTEXT::rat_exp_t
      do_evaluation(const vcsn::AutomataBase<TransStruct>&,
		    const TransImpl&,
		    const SeriesStruct&,
		    const vcsn::rat::exp<S, T>& input,
		    const Element<TransStruct, TransImpl>& t,
		    const Element<SeriesStruct, SeriesImpl>&)
      {
	AUTOMATON_CONTEXT::automaton_t w = AUTOMATON_CONTEXT::make_automaton(t.structure().series()
	    .monoid().first_monoid().alphabet());
	AUTOMATON_CONTEXT::automaton_t result = AUTOMATON_CONTEXT::make_automaton(t.structure().series()
	    .monoid().second_monoid().alphabet());
	standard_of(w, input);
	evaluation_fmp(t, quotient(w), result);

	return aut_to_exp(generalized(quotient(realtime(trim(result)))),
	    DMChooser());
      }


      template <typename TransStruct,
	        typename TransImpl,
	        typename ArgStruct,
	        typename ArgImpl>
      AUTOMATON_CONTEXT::rat_exp_t
      evaluation(const Element<TransStruct, TransImpl>& t,
		 const Element<ArgStruct, ArgImpl>& input)
      {
	return do_evaluation(t.structure(), t.value(),
			     input.structure(), input.value(),
			     t, input);
      }


    } // End of VCSN_CONTEXT_NAMESPACE.
  } // End of VCSN_GRAPH_IMPL.
214
} // End of namespace vcsn.