graph_preprocess.cpp

#include <algorithm>
#include <cstddef>
#include <limits>
#include <stdexcept>
#include <unordered_map>
#include <utility>
#include <vector>

// Keep this Edge shape compatible with SSSP.cpp.
#ifndef SSSP_EDGE_DEFINED
#define SSSP_EDGE_DEFINED
struct Edge {
    int to;
    double w;
};
#endif

struct OriginalEdge {
    int u;
    int v;
    double w;
};

struct PreprocessedGraph {
    // Graph in the transformed constant-degree form.
    std::vector<std::vector<Edge>> transformedGraph;
    int transformedSource = -1;

    // For each original vertex, list of transformed vertices representing it.
    std::vector<std::vector<int>> originalToTransformedNodes;
};

namespace {

using Pair = std::pair<int, int>;

struct PairHash {
    std::size_t operator()(const Pair& p) const noexcept {
        return (static_cast<std::size_t>(static_cast<unsigned int>(p.first)) << 32U) ^
               static_cast<std::size_t>(static_cast<unsigned int>(p.second));
    }
};

}  // namespace

// Paper-style preprocessing from Section 2 (constant-degree transformation):
// 1) For each original vertex v, create one transformed node x_vw per in/out neighbor w.
// 2) Connect these nodes in a directed 0-weight cycle.
// 3) Replace each original edge (u, v, w_uv) with edge x_uv -> x_vu of weight w_uv.
//
// The returned transformed graph can be fed directly into BMSSPSolver.
PreprocessedGraph PreprocessGraphToConstantDegree(
    int numVertices,
    const std::vector<OriginalEdge>& edges,
    int source) {
    if (numVertices <= 0) {
        throw std::invalid_argument("numVertices must be positive");
    }
    if (source < 0 || source >= numVertices) {
        throw std::invalid_argument("source out of range");
    }

    std::vector<std::vector<int>> neighbors(static_cast<std::size_t>(numVertices));
    neighbors.reserve(static_cast<std::size_t>(numVertices));

    // Build undirected incident-neighbor sets (in/out neighbors combined).
    for (const OriginalEdge& e : edges) {
        if (e.u < 0 || e.u >= numVertices || e.v < 0 || e.v >= numVertices) {
            throw std::invalid_argument("edge endpoint out of range");
        }
        if (e.w < 0.0) {
            throw std::invalid_argument("edge weight must be non-negative");
        }
        neighbors[static_cast<std::size_t>(e.u)].push_back(e.v);
        neighbors[static_cast<std::size_t>(e.v)].push_back(e.u);
    }
    for (auto& nbrs : neighbors) {
        std::sort(nbrs.begin(), nbrs.end());
        nbrs.erase(std::unique(nbrs.begin(), nbrs.end()), nbrs.end());
    }

    std::unordered_map<Pair, int, PairHash> gadgetNodeId;
    gadgetNodeId.reserve(edges.size() * 2U + static_cast<std::size_t>(numVertices) * 4U);

    PreprocessedGraph out;
    out.originalToTransformedNodes.resize(static_cast<std::size_t>(numVertices));

    // Assign transformed node IDs for every required x_vw.
    for (int v = 0; v < numVertices; ++v) {
        auto& reps = out.originalToTransformedNodes[static_cast<std::size_t>(v)];
        const auto& nbrs = neighbors[static_cast<std::size_t>(v)];

        // If isolated (or source-only disconnected case), keep one self representative.
        if (nbrs.empty()) {
            int id = static_cast<int>(out.transformedGraph.size());
            out.transformedGraph.emplace_back();
            reps.push_back(id);
            gadgetNodeId[{v, v}] = id;
            continue;
        }

        reps.reserve(nbrs.size());
        for (int w : nbrs) {
            int id = static_cast<int>(out.transformedGraph.size());
            out.transformedGraph.emplace_back();
            reps.push_back(id);
            gadgetNodeId[{v, w}] = id;
        }
    }

    // Add 0-weight cycle edges inside each original vertex gadget.
    for (int v = 0; v < numVertices; ++v) {
        const auto& reps = out.originalToTransformedNodes[static_cast<std::size_t>(v)];
        if (reps.size() <= 1U) {
            continue;
        }
        const std::size_t deg = reps.size();
        for (std::size_t i = 0; i < deg; ++i) {
            int from = reps[i];
            int to = reps[(i + 1U) % deg];
            out.transformedGraph[static_cast<std::size_t>(from)].push_back({to, 0.0});
        }
    }

    // Redirect each original edge to x_uv -> x_vu with original weight.
    for (const OriginalEdge& e : edges) {
        auto itFrom = gadgetNodeId.find({e.u, e.v});
        auto itTo = gadgetNodeId.find({e.v, e.u});
        if (itFrom == gadgetNodeId.end() || itTo == gadgetNodeId.end()) {
            throw std::runtime_error("internal preprocessing error building gadget nodes");
        }
        int from = itFrom->second;
        int to = itTo->second;
        out.transformedGraph[static_cast<std::size_t>(from)].push_back({to, e.w});
    }

    // Any representative of source works because gadget cycle is 0-weight connected.
    out.transformedSource = out.originalToTransformedNodes[static_cast<std::size_t>(source)].empty()
                                ? -1
                                : out.originalToTransformedNodes[static_cast<std::size_t>(source)][0];
    if (out.transformedSource < 0) {
        throw std::runtime_error("failed to create transformed source");
    }

    return out;
}

// Convert transformed distances back to original-vertex distances:
// distance(v) = min distance among all transformed representatives of v.
std::vector<double> RecoverOriginalDistances(
    const std::vector<double>& transformedDistances,
    const std::vector<std::vector<int>>& originalToTransformedNodes) {
    const double INF = std::numeric_limits<double>::infinity();
    std::vector<double> out(originalToTransformedNodes.size(), INF);

    for (std::size_t v = 0; v < originalToTransformedNodes.size(); ++v) {
        double best = INF;
        for (int node : originalToTransformedNodes[v]) {
            if (node < 0 || static_cast<std::size_t>(node) >= transformedDistances.size()) continue;
            best = std::min(best, transformedDistances[static_cast<std::size_t>(node)]);
        }
        out[v] = best;
    }
    return out;
}