pas_swap2order.h File Reference

Global placement-order DAG of a closed two-station pass-and-swap tandem. More...

#include <algorithm>
#include <cstddef>
#include <functional>
#include <set>
#include <utility>
#include <vector>
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/matrix.h"

Include dependency graph for pas_swap2order.h:

Go to the source code of this file.

Namespaces
namespace	line
namespace	line::pfqn

Typedefs
template<class T>
using	line::pfqn::PasRateFun = std::function<T(const std::vector<int>&)>
	Total service rate of a queue on an ordered prefix of classes (1-based).

Functions
template<class T>
Matrix< T >	line::pfqn::pas_swap2order (const std::vector< Matrix< T > > &swap, const std::vector< PasRateFun< T > > &listRate, const std::vector< int > &N0=std::vector< int >())
	Placement-order DAG of a two-station pass-and-swap tandem.

Detailed Description

Global placement-order DAG of a closed two-station pass-and-swap tandem.

Templated port of matlab/src/api/pfqn/pas_swap2order.m. With a non-empty swap graph the ordered-state chain is reducible (Comte and Dorsman, 2021, arXiv:2009.12299) and its recurrent class consists of the splits of the orderings that are the linear extensions of a single placement partial order. The port enumerates that recurrent class from the all-in-queue-1 state of the minimal single-job-per-class instance, reads the full ordering c = [l1, reverse(l2)] off every reachable state, and sets H(i, j) = 1 iff i precedes j in EVERY such ordering. The placement order is a class-level property, so the result is valid for any population.

PARTNER FUNCTION. pas_placement takes the H produced here and returns its transitive closure together with the placeable-next test; the two are meant to be used together and are tested against each other.

SERVICE RATES. listRate[m](c) is the total service rate of queue m on the ordered prefix c, and the marginal rate of the p-th customer is the forward difference. The reference guards p == 1 explicitly because some rate handles return a nonzero constant on the empty prefix, and that guard is reproduced: the empty-prefix rate is zero by definition.

ARITHMETIC. Only the rate comparison touches the number type, against the reference's fixed 1e-12 threshold, which is a representable rational. No transcendental function is used and the header is instantiated at Rational. The threshold is NOT relaxed to an exact "> 0" test at exact arithmetic: that would be a different algorithm, admitting transitions the reference prunes.

INDEXING. Classes are 1-based, as in MATLAB, everywhere a class appears in an ordering or in N0. H is (R x R) and 0-based in the C++ sense, so H(a - 1, b - 1) is MATLAB's H(a, b).

Definition in file pas_swap2order.h.