pas_placement.h File Reference

Placement order of a pass-and-swap (P&S) order-independent network. More...

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

Include dependency graph for pas_placement.h:

Go to the source code of this file.

Classes
struct	line::pfqn::PasPlacement< T >
	Result of pas_placement. More...

Namespaces
namespace	line
namespace	line::pfqn

Functions
template<class T>
PasPlacement< T >	line::pfqn::pas_placement (const Matrix< T > &H)
	Precedence closure of a swap graph.

Detailed Description

Placement order of a pass-and-swap (P&S) order-independent network.

Templated port of matlab/src/api/pfqn/pas_placement.m. An ordering c = (c_1, ..., c_l) is feasible iff class a never precedes class b whenever H(b, a) is nonzero (Comte and Dorsman, 2021, arXiv:2009.12299), so H is read as "row must be placed before column" and its transitive closure P is the full precedence relation. The closure is taken by repeated Boolean squaring against H until it stops growing, which is the reference's own iteration and terminates in at most R steps.

placeable(x) returns the classes that may be placed next given the vector x of remaining per-class counts: class j is placeable iff x(j) > 0 and no still-present class must precede it, sum_i x(i) P(i, j) == 0.

ARITHMETIC. The closure is Boolean and the placeable test is a sum of counts, so nothing here rounds and the header is instantiated at Rational as well as double and Real. P is returned as a 0/1 matrix of T, matching MATLAB's double(P), so it can be multiplied straight into the caller's arithmetic.

EMPTY H. MATLAB returns P = [] and a placeable that admits every present class. Reproduced: an empty H yields an empty P, and placeable then ignores the precedence test.

Definition in file pas_placement.h.