s_yu.cpp

#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <Eigen/Dense>

using namespace Eigen;
using namespace std;

MatrixXd readEdgeList(const string& filename, int& n) {
    ifstream file(filename);
    if (!file.is_open()) {
        cerr << "Error: Cannot open file " << filename << endl;
        exit(1);
    }

    vector<pair<int,int>> edges;
    int u, v;
    int max_node = -1;

    string line;
    while (getline(file, line)) {
        if (line.empty() || line[0] == '#') continue;
        stringstream ss(line);
        if (ss >> u >> v) {
            edges.emplace_back(u, v);
            max_node = max(max_node, max(u, v));
        }
    }

    n = max_node + 1;
    MatrixXd A = MatrixXd::Zero(n, n);
    for (auto& e : edges) {
        if (e.first != e.second) {
            A(e.first, e.second) = 1.0;
        }
    }
    return A;
}

MatrixXd makeColumnStochastic(const MatrixXd& A) {
    VectorXd col_sums = A.colwise().sum();
    MatrixXd Q = A;
    for (int j = 0; j < Q.cols(); j++) {
        if (col_sums(j) > 0)
            Q.col(j) /= col_sums(j);
    }
    return Q;
}

int main(int argc, char* argv[]) {
    if (argc < 2) {
        cerr << "Usage: " << argv[0] << " <edge_list_file.txt>\n";
        return 1;
    }

    int n;
    MatrixXd A = readEdgeList(argv[1], n);
    cout << "Graph has " << n << " nodes\n";

    MatrixXd Q = makeColumnStochastic(A);
    double c = 0.6;
    int K = 50;
    MatrixXd I = MatrixXd::Identity(Q.rows(), Q.cols());

    MatrixXd S = I;
    for (int iter = 0; iter < K; iter++) {
        S = (c / 2.0) * (Q.transpose() * S + S * Q) + (1 - c) * I;
    }

    cout << "Iterative SimRank* (" << K << " iters, top-left 5x5):\n" 
         << S.topLeftCorner(min(5,n), min(5,n)) << endl;

    return 0;
}