Count paths on a lattice graph.

count_path_mp.cpp

// Count paths on a lattice graph.

#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <algorithm>

#include <gmp.h>

using namespace std;

struct Node {
    int idx;
    Node* child[3];
    mpz_t cnt;

    Node(int idx) : idx(idx) {
        mpz_init_set_ui(cnt, 0);
        fill(child, child + 3, static_cast<Node*>(NULL));
    }

    void Count(mpz_t& n) {
        if (mpz_cmp_ui(cnt, 0) > 0) {
            mpz_set(n, cnt);
            return;
        }
        mpz_t w;
        mpz_init(w);
        for (int i = 0; child[i]; i++) {
            child[i]->Count(w);
            mpz_add(cnt, cnt, w);
        }
        mpz_clear(w);
        mpz_set(n, cnt);
    }
};

void read_data(const char* filename, vector<Node*>& nodes)
{
    fstream fs(filename, ios_base::in);
    string line;
    stringstream ss;
    int x[4];
    int n;

    getline(fs, line);
    ss.str(line);
    ss >> n;
    for (int i = 0; i < n; i++) nodes.push_back(new Node(i));
    mpz_set_ui(nodes[1]->cnt, 1);

    while (getline(fs, line)) {
        ss.clear();  ss.str(line);
        for (int i = 0; ss >> x[i]; i++);
        n = 0;
        for (int i = 1; i < 3; i++) {
            if (x[i] == 0) continue;
            nodes[x[0]]->child[n++] = nodes[x[i]];
        }
    }
}

int main(int argc, char* argv[])
{
    if (argc < 2) {
        cerr << "Usage: " << argv[0] << " datafile" <<endl;
        exit(1);
    }

    vector<Node*> nodes;

    read_data(argv[1], nodes);
    mpz_t cnt;
    mpz_init(cnt);
    nodes[2]->Count(cnt);

    cout << "Count: " << mpz_get_str(NULL, 10, cnt) << endl;

    mpz_clear(cnt);

    return 0;
}