SP.cpp.in

/*
 * Copyright (C) 2024-2026  landerrosette <57791410+landerrosette@users.noreply.github.com>
 *
 * 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 3 of the License, or
 * (at your option) any later version.
 *
 * 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.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
 */

/******************************************************************************
 * % ./DijkstraSP tinyEWD.txt 0
 * 0 to 0 (0.00):
 * 0 to 1 (1.05): 0->4 0.38  4->5 0.35  5->1 0.32
 * 0 to 2 (0.26): 0->2 0.26
 * 0 to 3 (0.99): 0->2 0.26  2->7 0.34  7->3 0.39
 * 0 to 4 (0.38): 0->4 0.38
 * 0 to 5 (0.73): 0->4 0.38  4->5 0.35
 * 0 to 6 (1.51): 0->2 0.26  2->7 0.34  7->3 0.39  3->6 0.52
 * 0 to 7 (0.60): 0->2 0.26  2->7 0.34
 *
 * % ./AcyclicSP tinyEWDAG.txt 5
 * 5 to 0 (0.73): 5->4 0.35  4->0 0.38
 * 5 to 1 (0.32): 5->1 0.32
 * 5 to 2 (0.62): 5->7 0.28  7->2 0.34
 * 5 to 3 (0.61): 5->1 0.32  1->3 0.29
 * 5 to 4 (0.35): 5->4 0.35
 * 5 to 5 (0.00):
 * 5 to 6 (1.13): 5->1 0.32  1->3 0.29  3->6 0.52
 * 5 to 7 (0.28): 5->7 0.28
 *
 * % ./BellmanFordSP tinyEWDn.txt 0
 * 0 to 0 (0.00):
 * 0 to 1 (0.93): 0->2 0.26  2->7 0.34  7->3 0.39  3->6 0.52  6->4 -1.25  4->5 0.35  5->1 0.32
 * 0 to 2 (0.26): 0->2 0.26
 * 0 to 3 (0.99): 0->2 0.26  2->7 0.34  7->3 0.39
 * 0 to 4 (0.26): 0->2 0.26  2->7 0.34  7->3 0.39  3->6 0.52  6->4 -1.25
 * 0 to 5 (0.61): 0->2 0.26  2->7 0.34  7->3 0.39  3->6 0.52  6->4 -1.25  4->5 0.35
 * 0 to 6 (1.51): 0->2 0.26  2->7 0.34  7->3 0.39  3->6 0.52
 * 0 to 7 (0.60): 0->2 0.26  2->7 0.34
 ******************************************************************************/

#include "algs4/@SP@.hpp"

#include <fstream>
#include <iomanip>
#include <iostream>
#include <string>

int main(int argc, char* argv[]) {
    if (argc < 3) {
        std::cerr << "Not enough arguments" << std::endl;
        return 1;
    }
    std::ifstream in(argv[1]);
    if (!in.is_open()) {
        std::cerr << "Cannot open file: " << argv[1] << std::endl;
        return 1;
    }
    algs4::EdgeWeightedDigraph G(in);
    int s = std::stoi(argv[2]);
    if (s < 0 || s >= G.V()) {
        std::cerr << "Source vertex out of range" << std::endl;
        return 1;
    }
    algs4::@SP@ sp(G, s);
    for (int t = 0; t < G.V(); ++t) {
        std::cout << s << " to " << t;
        std::cout << " (" << std::fixed << std::setprecision(2) << std::setw(4) << sp.distTo(t) << "): ";
        if (sp.hasPathTo(t))
            for (const auto& e : sp.pathTo(t)) std::cout << e << " ";
        std::cout << std::endl;
    }
    return 0;
}