The algorithm implementing is more complex than the book says it's supposed to be, plus i don't think it's doing the calculations correctly. The algorithm is supposed to calculate the cost(in work-time or 'labor) of every commodity in an economy (millions/billions) so complexity is really important. Quote from book:
The input–output table for an economy is in practice likely to be mostly blanks. In reality each product has on average only a few tens or at most hundreds of inputs to its production rather than a million. This makes it more economical to represent the system in terms of a vector of lists rather than a matrix. In consequence, there are short-cuts which can be taken to arrive at a result. We can use another approach, that of successive approximation.The idea here is that as a first approximation we ignore all inputs to the production process apart from directly expended labour. This gives us a first, approximate estimate of each product’s labour value. It will be an underestimate because it ignores the non-labour inputs to the production process. To arrive at our second approximation we add in the non-labour inputs valued on the basis of the labour values computed in the first phase. This will get us one step closer to the true labour values. Repeated application of this process will give us the answer to the desired degree of accuracy. If about half the value of an average product is derived from direct labour inputs then each iteration round our approximation process will add one binary digit of significance to our answer. An answer correct to four significant decimal digits (which is better than the market can achieve) would require about 15 iterations round our approximation process.
The time order complexity of this algorithm is proportional to the number of products times the average number of inputs per product, times the desired accuracy of the result in digits. On our previous assumptions this could be computed on a supercomputer in a few minutes, rather than the thousands of years required for Gaussian elimination(8).
(8)Hodgson (1984, p. 170) states that the best method for solving an input–output table involves n^2 calculations. While he doesn’t give any explanation for this claim, we assume that he must be recognizing the use of an iterative technique (or else the complexity would be n^3), but he fails to recognise that the technical coefficient matrix would be sparse. A better use of data structures reduces the complexity substantially, as argued above.
My implementation: I don't understand the algorithm exactly, are you supposed to store indirect and direct and final labor separately? something is making my values increase exponentially rather than converge and become more precise like i think they are supposed to.
Code: (ioapprox.hpp)
#ifndef STRING
#define STRING
#include <string>
#endif
#ifndef FORWARD_LIST
#define FORWARD_LIST
#include <forward_list>
#endif
#ifndef ALGORITHM
#define ALGORITHM
#include <algorithm>
#endif
#ifndef IOSTREAM
#define IOSTREAM
#include <iostream>
#endif
struct com_node {
double key;
int active = 0;
std::string name;
std::forward_list<com_node*> input_list;
float direct_labor = 0;
float indirect_labor = 0;
float fin_labor = 0;
};
struct com_matrix {
double max_key = 0;
std::forward_list<com_node*> com_list;
void add(std::string, float);
void add_input(double, double);
void update_direct_labor();
void update_fin_labor();
void it_through_matrix(int xr);
void prt_matrix();
};
// Complexity: O(1)
void com_matrix::add(std::string cname, float pdlc) {
com_node * ind = new com_node;
ind->key = max_key; max_key++;
ind->direct_labor = pdlc;
ind->name = cname;
com_list.push_front(ind);
}//end add()
// Complexity: O(n)
void com_matrix::add_input(double ker1, double ker2) {
int sent = 0;
int sent2 = 0;
com_node * save1 = 0;
com_node * save2 = 0;
for (std::forward_list<com_node*>::const_iterator iterator3 = com_list.begin(); iterator3 != com_list.end(); ++iterator3) {
com_node * h = *iterator3;
if (h->key == ker1) {
sent = 1;
save1 = h;
}
}
for (std::forward_list<com_node*>::const_iterator iterator4 = com_list.begin(); iterator4 != com_list.end(); ++iterator4) {
com_node * b = *iterator4;
if (b->key == ker2) {
sent2 = 1;
save2 = b;
}
}
if (sent == 0 && sent2 == 0) {
save1->input_list.push_front(save2);
}
}//end add_input()
// Complexity: O(n^2)
void com_matrix::update_direct_labor() {
for (std::forward_list<com_node*>::const_iterator iterator = com_list.begin(); iterator != com_list.end(); ++iterator) {
com_node * k = *iterator;
float nidl = 0;
for (std::forward_list<com_node*>::const_iterator iterator2 = (k->input_list).begin(); iterator2 != (k->input_list).end(); ++iterator2) {
com_node * j = *iterator2;
nidl += j->fin_labor;
}//end for
k->indirect_labor = nidl;
}//end for
}//end update_direct_labor()
//Complexity O(n)
void com_matrix::update_fin_labor() {
for (std::forward_list<com_node*>::const_iterator iterator = com_list.begin(); iterator != com_list.end(); ++iterator) {
com_node * m = *iterator;
m->fin_labor = (m->direct_labor + m->indirect_labor);
}//end for
}//end update_fin_labor()
void com_matrix::prt_matrix() {
for (std::forward_list<com_node*>::const_iterator iterator = com_list.begin(); iterator != com_list.end(); ++iterator) {
com_node * v = *iterator;
std::cout << std::to_string(v->key) << " | " << v->name << " | " << std::to_string(v->fin_labor) << std::endl;
}//end for
std::cout << std::endl;
}//end prt_matrix()
// Complexity: Cubic, unfortunately
void com_matrix::it_through_matrix(int r = 15) {
for (int i = 0; i < r; i++) {
update_direct_labor();
update_fin_labor();
prt_matrix();
}//end for
}//end it_through_matrix()
more code (ioapprox.cpp)
#include "ioapprox.hpp"
int main() {
com_matrix g;
for (int i = 0; i < 1200; i++) {
g.add(std::to_string(i), rand());
}
for (int n = 0; n < 1200; n++) {
g.add_input(rand()%1200,rand()%1200);
}
g.it_through_matrix(3);
}