ctmc_ssg.h

Go to the documentation of this file.

/*
 * Copyright (c) 2012-2026, QORE Lab, Imperial College London
 * All rights reserved.
 */
#ifndef LINE_API_MC_CTMC_SSG_H
#define LINE_API_MC_CTMC_SSG_H
 
/**
 * @file
 * @ingroup api_mc
 * Ports of matlab/src/api/mc/ctmc_ssg.m and ctmc_ssg_reachability.m: the
 * state space of a network as SolverCTMC enumerates it, in the reference's
 * three views.
 *
 *   stateSpace        one row per network state, the per-node local rows
 *                     concatenated in stateful-node order
 *   stateSpaceAggr    (nstates x nstations*nclasses), the per-station job
 *                     counts of each state (`State.toMarginal`)
 *   stateSpaceHashed  (nstates x nstateful), the 1-based row of each node's
 *                     local space that the state occupies
 *   nodeStateSpace    the per-node local spaces the hashes index into, the
 *                     reference's `sn.space`
 *
 * The reference writes `nodeStateSpace` back onto `sn.space` and returns the
 * struct; this NetworkStruct carries no `space` member (the analyzer rebuilds
 * it per solve), so the node spaces are returned on the result instead.
 *
 * `ctmc_ssg` is the FULL enumeration (`State.spaceGenerator`): every state the
 * encoding admits, reachable or not. The reference refuses a fork-join model
 * here, because a Fork firing does not conserve the per-chain population the
 * lattice walks; `ctmc_ssg_reachability` is the reachable walk
 * (`State.reachableSpaceGenerator`) from the model's initial state, which is
 * the one those models need.
 *
 * The enumeration itself is `qn::space_generator` and
 * `ctmc::reachable_space_generator`, shared with SolverCTMC, so a space listed
 * here is the space the solver solves.
 */
 
#include <cstddef>
#include <map>
#include <vector>
 
#include "line/lang/qn/network_struct.h"
#include "line/lang/qn/state.h"
#include "line/lang/qn/state_events.h"
#include "line/num/number.h"
#include "line/solvers/ctmc/solver_ctmc.h"
#include "line/solvers/ctmc/solver_ctmc_analyzer.h"
#include "line/util/error.h"
#include "line/util/matrix.h"
 
namespace line {
namespace mc {
 
/** The reference's options read here: `options.cutoff` and the state cap. */
struct CtmcSsgOptions {
    /** Per-class population bound for the open classes (`options.cutoff`); 0 = closed. */
    std::vector<std::size_t> cutoff;
    /** Optional (nstations x nclasses) bound, the reference's matrix `options.cutoff`. */
    std::vector<std::vector<std::size_t>> cutoff_mat;
    /** Refuse beyond this many states (the reference's ctmc_max_states). */
    std::size_t state_max = 3000000;
};
 
/** The reference's `[stateSpace, stateSpaceAggr, stateSpaceHashed, nodeStateSpace]`. */
template <class T>
struct CtmcSsgResult {
    Matrix<T> state_space;
    Matrix<T> state_space_aggr;
    /** 1-based row of `node_state_space[isf]` each state occupies at node isf. */
    std::vector<std::vector<std::size_t>> state_space_hashed;
    /** One local space per stateful node, rows in first-seen order. */
    std::vector<Matrix<T>> node_state_space;
    /** The enumerated states as the solvers consume them (port-only convenience). */
    std::vector<qn::NetState<T>> space;
};
 
namespace ssg_detail {
 
/** The three matrix views from an enumerated space. */
template <class T>
CtmcSsgResult<T> assemble(const qn::NetworkStruct<T>& sn, std::vector<qn::NetState<T>> space) {
    const T zero = num_traits<T>::from_int(0);
    const std::size_t S = sn.nof_stateful();
    CtmcSsgResult<T> out;
 
    // per-node local spaces and the hash of every state into them
    std::vector<std::map<std::vector<T>, std::size_t>> seen(S);
    std::vector<std::vector<std::vector<T>>> rows(S);
    out.state_space_hashed.assign(space.size(), std::vector<std::size_t>(S, 0));
    std::size_t width = 0;
    for (std::size_t st = 0; st < space.size(); ++st) {
        std::size_t w = 0;
        for (std::size_t f = 0; f < S && f < space[st].local.size(); ++f) {
            const std::vector<T>& loc = space[st].local[f];
            w += loc.size();
            typename std::map<std::vector<T>, std::size_t>::const_iterator it = seen[f].find(loc);
            if (it == seen[f].end()) {
                rows[f].push_back(loc);
                seen[f][loc] = rows[f].size();  // 1-based
                out.state_space_hashed[st][f] = rows[f].size();
            } else {
                out.state_space_hashed[st][f] = it->second;
            }
        }
        if (w > width) width = w;
    }
    out.node_state_space.resize(S);
    for (std::size_t f = 0; f < S; ++f) {
        const std::size_t nr = rows[f].size();
        std::size_t nc = 0;
        for (std::size_t a = 0; a < nr; ++a) nc = std::max(nc, rows[f][a].size());
        out.node_state_space[f] = Matrix<T>(nr, nc, zero);
        for (std::size_t a = 0; a < nr; ++a)
            for (std::size_t b = 0; b < rows[f][a].size(); ++b)
                out.node_state_space[f](a, b) = rows[f][a][b];
    }
 
    // stateSpace: the local rows side by side, in stateful-node order
    out.state_space = Matrix<T>(space.size(), width, zero);
    for (std::size_t st = 0; st < space.size(); ++st) {
        std::size_t col = 0;
        for (std::size_t f = 0; f < space[st].local.size(); ++f)
            for (std::size_t b = 0; b < space[st].local[f].size(); ++b)
                out.state_space(st, col++) = space[st].local[f][b];
    }
 
    // stateSpaceAggr: the per-station marginal job counts (State.toMarginal)
    out.state_space_aggr = ctmc::ctmc_state_space_aggr(sn, space);
    out.space = std::move(space);
    return out;
}
 
inline std::vector<std::size_t> cutoff_or_closed(const std::vector<std::size_t>& cutoff,
                                                 std::size_t R) {
    if (cutoff.size() == R) return cutoff;
    if (cutoff.empty()) return std::vector<std::size_t>(R, 0);
    if (cutoff.size() == 1) return std::vector<std::size_t>(R, cutoff[0]);
    throw InputError("ctmc_ssg: options.cutoff must hold one entry per class");
}
 
}  // namespace ssg_detail
 
/**
 * Port of `ctmc_ssg`: the FULL state space of the network.
 *
 * @param sn      the refreshed network struct
 * @param options the cutoff of the open classes and the state cap
 * @param fjsync  the fork firing list; a non-empty one is refused, as the
 *                reference refuses a model with `sn.fjsync`
 */
template <class T>
CtmcSsgResult<T> ctmc_ssg(const qn::NetworkStruct<T>& sn,
                          const CtmcSsgOptions& options = CtmcSsgOptions(),
                          const std::vector<qn::FjSync<T>>& fjsync = std::vector<qn::FjSync<T>>()) {
    if (!fjsync.empty())
        throw UnsupportedError(ErrorKind{"Fork"},
            "ctmc_ssg: Fork-join models require reachability-based state space generation "
            "(options.config.state_space_gen='reachable').");
    const std::vector<std::size_t> cutoff =
        ssg_detail::cutoff_or_closed(options.cutoff, sn.nclasses);
    std::vector<qn::NetState<T>> space =
        qn::space_generator(sn, cutoff, options.state_max, options.cutoff_mat);
    return ssg_detail::assemble(sn, std::move(space));
}
 
/**
 * Port of `ctmc_ssg_reachability`: the REACHABLE state space, walked from the
 * model's initial state over the synchronizations `refresh_sync` and
 * `refresh_global_sync` build.
 *
 * @param sn      the refreshed network struct
 * @param options the cutoff of the open classes and the state cap
 * @param fjsync  the fork firing list of a fork-join model, empty otherwise
 */
template <class T>
CtmcSsgResult<T> ctmc_ssg_reachability(
    const qn::NetworkStruct<T>& sn, const CtmcSsgOptions& options = CtmcSsgOptions(),
    const std::vector<qn::FjSync<T>>& fjsync = std::vector<qn::FjSync<T>>()) {
    qn::NetState<T> init;
    if (!ctmc::analyzer_detail::default_init_state(sn, init))
        throw UnsupportedError(ErrorKind{"Model"},
            "ctmc_ssg_reachability: the model's initial marking admits no state; check the Place "
            "populations against the class reference stations");
    const std::vector<std::size_t> cutoff =
        ssg_detail::cutoff_or_closed(options.cutoff, sn.nclasses);
    const std::vector<qn::Sync<T>> sync = qn::refresh_sync(sn);
    const std::vector<qn::GlobalSync<T>> gsync = qn::refresh_global_sync(sn);
    std::vector<qn::NetState<T>> space = ctmc::reachable_space_generator(
        sn, init, sync, gsync, options.state_max, fjsync, cutoff, options.cutoff_mat);
    return ssg_detail::assemble(sn, std::move(space));
}
 
}  // namespace mc
}  // namespace line
 
#endif  // LINE_API_MC_CTMC_SSG_H