network_generators.h

Go to the documentation of this file.

/*
 * Copyright (c) 2012-2026, QORE Lab, Imperial College London
 * All rights reserved.
 */
#ifndef LINE_LANG_QN_NETWORK_GENERATORS_H
#define LINE_LANG_QN_NETWORK_GENERATORS_H
 
/**
 * @file
 * @ingroup line_lang
 * @ingroup line_public
 * The static model factories of MATLAB's `Network`: `tandem*` and `cyclic*`.
 *
 * Ports of `MNetwork.m`'s `tandem`, `tandemPs`, `tandemPsInf`, `tandemFcfs`,
 * `tandemFcfsInf`, `cyclic`, `cyclicPs`, `cyclicPsInf`, `cyclicFcfs` and
 * `cyclicFcfsInf`. They build the SAME model the reference builds, node names
 * and class names included, so a table keyed by name lines up across
 * codebases:
 *
 *   tandem   Source, `Station1..StationM`, Sink, serial routing; class r is an
 *            open class `Class<r>` arriving at rate `lambda[r]` (an exponential
 *            of mean 1/lambda[r]) and served with mean `D(i,r)` at station i.
 *            An INF station is a Delay, any other a Queue under its strategy.
 *   cyclic   `Delay<k>` / `Queue<k>` numbered within their kind, cyclic routing
 *            1 -> 2 -> ... -> M -> 1; class r is a closed class `Class<r>` of
 *            `N[r]` jobs referencing the FIRST station, served with mean
 *            `D(i,r)`; a Queue gets `S[i]` servers.
 *
 * The `*Inf` variants put the rows of Z FIRST as delays and the rows of D after
 * them, which is the reference's `[Z; D]`; the delays of a cyclic model carry
 * an infinite server count in the stacked S vector, as `[Inf*ones(Mz,1); S]`.
 */
 
#include <cmath>
#include <limits>
#include <string>
#include <vector>
 
#include "line/lang/qn/network_builder.h"
#include "line/util/error.h"
#include "line/util/matrix.h"
 
namespace line {
namespace qn {
 
namespace gen_detail {
 
/** `[Z; D]`: the rows of Z stacked on top of the rows of D. */
template <class T>
Matrix<T> stack_rows(const Matrix<T>& Z, const Matrix<T>& D) {
    if (Z.rows() == 0) return D;
    if (Z.cols() != D.cols())
        throw InputError("Network generator: Z and D must have one column per class");
    Matrix<T> out(Z.rows() + D.rows(), D.cols(), num_traits<T>::from_int(0));
    for (std::size_t i = 0; i < Z.rows(); ++i)
        for (std::size_t r = 0; r < Z.cols(); ++r) out(i, r) = Z(i, r);
    for (std::size_t i = 0; i < D.rows(); ++i)
        for (std::size_t r = 0; r < D.cols(); ++r) out(Z.rows() + i, r) = D(i, r);
    return out;
}
 
/** Mz INF strategies, then M of `sched`. */
inline std::vector<SchedStrategy> inf_then(std::size_t Mz, std::size_t M, SchedStrategy sched) {
    std::vector<SchedStrategy> st(Mz, SchedStrategy::INF);
    st.insert(st.end(), M, sched);
    return st;
}
 
}  // namespace gen_detail
 
/**
 * `Network.tandem(lambda, D, strategy)`: an open tandem line.
 *
 * @param lambda   arrival rate per class
 * @param D        D(i,r), mean service time of class r at station i
 * @param strategy scheduling strategy of each station
 */
template <class T>
Network<T> tandem(const std::vector<T>& lambda, const Matrix<T>& D,
                  const std::vector<SchedStrategy>& strategy) {
    const std::size_t M = D.rows(), R = D.cols();
    if (lambda.size() != R)
        throw InputError("Network.tandem: lambda must have one entry per column of D");
    if (strategy.size() != M)
        throw InputError("Network.tandem: strategy must have one entry per row of D");
    Network<T> model("Model");
    std::vector<std::size_t> node;
    node.push_back(model.add_source("Source"));
    for (std::size_t i = 0; i < M; ++i) {
        const std::string nm = "Station" + std::to_string(i + 1);
        node.push_back(strategy[i] == SchedStrategy::INF ? model.add_delay(nm)
                                                          : model.add_queue(nm, strategy[i]));
    }
    node.push_back(model.add_sink("Sink"));
    RoutingMatrix<T> P;
    std::vector<std::size_t> cls(R);
    for (std::size_t r = 0; r < R; ++r) {
        cls[r] = model.add_open_class("Class" + std::to_string(r + 1), 0);
        for (std::size_t k = 0; k + 1 < node.size(); ++k)
            P.set(cls[r], cls[r], node[k], node[k + 1], num_traits<T>::from_int(1));
    }
    const T one = num_traits<T>::from_int(1);
    for (std::size_t r = 0; r < R; ++r) {
        model.set_arrival(node[0], cls[r], Distrib<T>::exp_mean(T(one / lambda[r])));
        for (std::size_t i = 0; i < M; ++i)
            model.set_service(node[1 + i], cls[r], Distrib<T>::exp_mean(D(i, r)));
    }
    model.link(P);
    return model;
}
 
/** `Network.tandemPsInf(lambda, D, Z)`: delays for the rows of Z, then PS queues for D. */
template <class T>
Network<T> tandem_ps_inf(const std::vector<T>& lambda, const Matrix<T>& D, const Matrix<T>& Z) {
    return tandem(lambda, gen_detail::stack_rows(Z, D),
                  gen_detail::inf_then(Z.rows(), D.rows(), SchedStrategy::PS));
}
 
/** `Network.tandemPs(lambda, D)`: PS queues only. */
template <class T>
Network<T> tandem_ps(const std::vector<T>& lambda, const Matrix<T>& D) {
    return tandem_ps_inf(lambda, D, Matrix<T>(0, D.cols(), num_traits<T>::from_int(0)));
}
 
/** `Network.tandemFcfsInf(lambda, D, Z)`: delays for the rows of Z, then FCFS queues for D. */
template <class T>
Network<T> tandem_fcfs_inf(const std::vector<T>& lambda, const Matrix<T>& D, const Matrix<T>& Z) {
    return tandem(lambda, gen_detail::stack_rows(Z, D),
                  gen_detail::inf_then(Z.rows(), D.rows(), SchedStrategy::FCFS));
}
 
/** `Network.tandemFcfs(lambda, D)`: FCFS queues only. */
template <class T>
Network<T> tandem_fcfs(const std::vector<T>& lambda, const Matrix<T>& D) {
    return tandem_fcfs_inf(lambda, D, Matrix<T>(0, D.cols(), num_traits<T>::from_int(0)));
}
 
/**
 * `Network.cyclic(N, D, strategy, S)`: a closed cyclic network.
 *
 * @param N        population per class
 * @param D        D(i,r), mean service time of class r at station i
 * @param strategy scheduling strategy of each station
 * @param S        number of servers of each station (read at the Queues only)
 */
template <class T>
Network<T> cyclic(const std::vector<double>& N, const Matrix<T>& D,
                  const std::vector<SchedStrategy>& strategy, const std::vector<double>& S) {
    const std::size_t M = D.rows(), R = D.cols();
    if (N.size() != R)
        throw InputError("Network.cyclic: N must have one entry per column of D");
    if (strategy.size() != M || S.size() != M)
        throw InputError("Network.cyclic: strategy and S must have one entry per row of D");
    Network<T> model("Model");
    std::vector<std::size_t> node(M);
    std::size_t nQ = 0, nD = 0;
    for (std::size_t i = 0; i < M; ++i) {
        if (strategy[i] == SchedStrategy::INF) {
            node[i] = model.add_delay("Delay" + std::to_string(++nD));
        } else {
            node[i] = model.add_queue("Queue" + std::to_string(++nQ), strategy[i]);
            model.set_number_of_servers(node[i], S[i]);
        }
    }
    RoutingMatrix<T> P;
    std::vector<std::size_t> cls(R);
    for (std::size_t r = 0; r < R; ++r) {
        cls[r] = model.add_closed_class("Class" + std::to_string(r + 1), N[r], node[0], 0);
        // circul(M): i -> i+1, M -> 1; a single station loops on itself
        for (std::size_t i = 0; i < M; ++i)
            P.set(cls[r], cls[r], node[i], node[(i + 1) % M], num_traits<T>::from_int(1));
    }
    for (std::size_t i = 0; i < M; ++i)
        for (std::size_t r = 0; r < R; ++r)
            model.set_service(node[i], cls[r], Distrib<T>::exp_mean(D(i, r)));
    model.link(P);
    return model;
}
 
/**
 * `Network.cyclicPsInf(N, D, Z, S)`: delays for the rows of Z, then PS queues
 * for the rows of D with `S` servers each (one server each when S is empty).
 */
template <class T>
Network<T> cyclic_ps_inf(const std::vector<double>& N, const Matrix<T>& D, const Matrix<T>& Z,
                         std::vector<double> S = std::vector<double>()) {
    if (S.empty()) S.assign(D.rows(), 1.0);
    std::vector<double> Sall(Z.rows(), std::numeric_limits<double>::infinity());
    Sall.insert(Sall.end(), S.begin(), S.end());
    return cyclic(N, gen_detail::stack_rows(Z, D),
                  gen_detail::inf_then(Z.rows(), D.rows(), SchedStrategy::PS), Sall);
}
 
/** `Network.cyclicPs(N, D, S)`: PS queues only. */
template <class T>
Network<T> cyclic_ps(const std::vector<double>& N, const Matrix<T>& D,
                     const std::vector<double>& S = std::vector<double>()) {
    return cyclic_ps_inf(N, D, Matrix<T>(0, D.cols(), num_traits<T>::from_int(0)), S);
}
 
/** `Network.cyclicFcfsInf(N, D, Z, S)`: delays for Z, then FCFS queues for D. */
template <class T>
Network<T> cyclic_fcfs_inf(const std::vector<double>& N, const Matrix<T>& D, const Matrix<T>& Z,
                           std::vector<double> S = std::vector<double>()) {
    if (S.empty()) S.assign(D.rows(), 1.0);
    std::vector<double> Sall(Z.rows(), std::numeric_limits<double>::infinity());
    Sall.insert(Sall.end(), S.begin(), S.end());
    return cyclic(N, gen_detail::stack_rows(Z, D),
                  gen_detail::inf_then(Z.rows(), D.rows(), SchedStrategy::FCFS), Sall);
}
 
/** `Network.cyclicFcfs(N, D, S)`: FCFS queues only. */
template <class T>
Network<T> cyclic_fcfs(const std::vector<double>& N, const Matrix<T>& D,
                       const std::vector<double>& S = std::vector<double>()) {
    return cyclic_fcfs_inf(N, D, Matrix<T>(0, D.cols(), num_traits<T>::from_int(0)), S);
}
 
}  // namespace qn
}  // namespace line
 
#endif  // LINE_LANG_QN_NETWORK_GENERATORS_H