sn_zero_capacity.h

Go to the documentation of this file.

/*
 * Copyright (c) 2012-2026, QORE Lab, Imperial College London
 * All rights reserved.
 */
#ifndef LINE_API_SN_SN_ZERO_CAPACITY_H
#define LINE_API_SN_SN_ZERO_CAPACITY_H
 
/**
 * @file
 * @ingroup api_sn
 * Port of matlab/src/api/sn/sn_zero_capacity.m: the closed chains trapped at a
 * zero-capacity station.
 *
 * A station with zero servers never completes a job, nor does one that serves
 * a class at rate zero (an infinite mean service time, which is how a layer
 * above a zero-capacity LQN element sees it). A closed chain that visits one
 * therefore ends, in steady state, with its whole population parked there:
 * zero throughput everywhere, an infinite response time at that station, and
 * no load on any other. The remaining chains are unaffected, since a trapped
 * job holds no other resource, so a model with such chains is solved as the
 * model without them. A rate-zero class at a finite-server station shared with
 * a live chain would hold servers forever, so that case is refused.
 *
 * RATE ZERO IS READ ON AN ENABLED PAIR ONLY. The reference's `sn.rates` holds
 * NaN where a class has no service; this port holds 0 there with the parallel
 * `disabled` flag set, so a bare `rates == 0` would read every unvisited pair
 * as stalled. Only a visited pair can trap a chain, so the outcome is the same.
 *
 * ARITHMETIC: field. Comparisons only.
 */
 
#include <cmath>
#include <cstddef>
#include <string>
#include <vector>
 
#include "line/lang/qn/network_struct.h"
#include "line/num/number.h"
 
namespace line {
namespace api {
 
/** What `sn_zero_capacity` reports. */
struct ZeroCapacity {
    /** (nchains) the 1-based zero-capacity station trapping chain c, 0 if none. */
    std::vector<std::size_t> deadstat;
    /**
     * Non-empty when the model has no steady state of this form: an open class
     * reaches a zero-capacity station, a chain visits two of them, or a rate-zero
     * finite-server station is shared with a live chain.
     */
    std::string reason;
    /** True when some chain is trapped. */
    bool any() const {
        for (std::size_t s : deadstat)
            if (s > 0) return true;
        return false;
    }
};
 
template <class T>
ZeroCapacity sn_zero_capacity(const qn::NetworkStruct<T>& sn) {
    ZeroCapacity out;
    const std::size_t M = sn.nstations, K = sn.nclasses;
    out.deadstat.assign(sn.nchains, 0);
    // stalled(i, r): station i completes no class-r job
    std::vector<std::vector<bool>> stalled(M, std::vector<bool>(K, false));
    bool anystalled = false;
    for (std::size_t i = 0; i < M; ++i)
        for (std::size_t r = 0; r < K; ++r) {
            const bool zr = !sn.disabled[i][r] &&
                            num_traits<T>::to_double(sn.rates(i, r)) == 0.0;
            stalled[i][r] = zr || sn.stations[i].nservers == 0.0;
            anystalled = anystalled || stalled[i][r];
        }
    if (!anystalled) return out;
 
    const std::vector<double> st2sf = sn.station_to_stateful();
    const std::vector<double> njobs = sn.njobs();
    // visited(c, i, r): chain c visits station i in class r
    auto visited = [&](std::size_t c, std::size_t i, std::size_t r) {
        const double sf = st2sf[i];
        if (std::isnan(sf) || c >= sn.visits.size()) return false;
        const std::size_t row = static_cast<std::size_t>(sf) - 1;
        if (row >= sn.visits[c].rows() || r >= sn.visits[c].cols()) return false;
        return num_traits<T>::to_double(sn.visits[c](row, r)) > 0.0;
    };
    for (std::size_t c = 0; c < sn.nchains; ++c) {
        std::vector<std::size_t> hit;
        bool open = false;
        for (std::size_t r = 0; r < K; ++r)
            if (sn.chains[c][r] && std::isinf(njobs[r])) open = true;
        for (std::size_t i = 0; i < M; ++i) {
            bool h = false;
            for (std::size_t r = 0; r < K && !h; ++r)
                h = sn.chains[c][r] && stalled[i][r] && visited(c, i, r);
            if (h) hit.push_back(i);
        }
        if (hit.empty()) continue;
        if (open) {
            out.reason = "Station " + sn.stations[hit[0]].name +
                         " has zero capacity and is visited by an open class, which accumulates "
                         "there without bound: the model has no steady state.";
            return out;
        }
        if (hit.size() > 1) {
            std::string names;
            for (std::size_t k = 0; k < hit.size(); ++k)
                names += (k ? ", " : "") + sn.stations[hit[k]].name;
            out.reason = "Chain " + std::to_string(c + 1) + " visits " +
                         std::to_string(hit.size()) + " stations with zero capacity (" + names +
                         "): its jobs are trapped at all of them and how they divide depends on "
                         "the initial state.";
            return out;
        }
        out.deadstat[c] = hit[0] + 1;
    }
    for (std::size_t i = 0; i < M; ++i) {
        bool dead = false;
        for (std::size_t s : out.deadstat) dead = dead || s == i + 1;
        const double ns = sn.stations[i].nservers;
        if (!dead || ns == 0.0 || std::isinf(ns)) continue;
        for (std::size_t c = 0; c < sn.nchains; ++c) {
            if (out.deadstat[c] == i + 1) continue;
            for (std::size_t r = 0; r < K; ++r)
                if (sn.chains[c][r] && visited(c, i, r)) {
                    out.reason = "Station " + sn.stations[i].name +
                                 " serves a class at rate zero and is shared with a chain that "
                                 "is not trapped there: the stalled jobs would hold its servers "
                                 "forever.";
                    return out;
                }
        }
    }
    return out;
}
 
}  // namespace api
}  // namespace line
 
#endif  // LINE_API_SN_SN_ZERO_CAPACITY_H