varseq

Module summary

Implements weighted variable sequences data structure.

Mostly mirrors the corresponding key methods of BDD.BDD class.

Tests coverage: varseq_test

(In the implementation details below, click on class/function names for additional documentation and links to the source code.)

❖❖❖

Implements classes:

VarSeq(layer_vars, layer_sizes)

Implements weighted variable sequence data structure.

Implements functions (outside the classes above):

non_dominated(e, A, B)

Checks if the element "e" is non-dominated.

❖❖❖

Implementation details

❖❖❖

VarSeq

class varseq.VarSeq(layer_vars, layer_sizes)

Implements weighted variable sequence data structure.

Public Methods:

__init__(layer_vars, layer_sizes)	Class constructor.
generate_weights(N)	Generates a random valid sequence of N weights.
random([vars, N])	Generates a random variable sequence.
size()	Returns the total sequence size (sum of element weights).
var_size(var)	Returns the element weight (given its label var).
S(a, j)	Returns cost of sliding element a (label) to position j.
slide(a, j[, inplace])	Performs a sift of element a (label) to position j.
__str__()	Converts the object to a string (used to print a sequence).
__len__()	Returns a sequence length (number of elements)
count_inversions_to(to_what)	Counts inversions with another list (or VarSeq).
greedy_sort([to_what])	Revises the VarSeq to a given order of labels to_what.
align_to([to_what])	Revises the varseq to given variable order in \(O(N)\) time.
OA_bruteforce(with_what)	Enumerates all possible alignments with another sequence.
is_aligned(to_what)	Helper function: checks if varseq is aligned with to_what.

---

OA_bruteforce(with_what)

Enumerates all possible alignments with another sequence.

Parameters

with_what (VarSeq) – target ordering.

Returns

[<no. of optima>, <list of A-aligned>, <list of B-aligned>]

Return type

list

Example

Having the returned object res, res[0] gives the number of optima. Then, assuming it is at least 3, res[1][2] gives A-aligned in the third optimum, res[2][2] gives B-aligned in the third optimum.

S(a, j)

Returns cost of sliding element a (label) to position j.

align_to(to_what=None)

Revises the varseq to given variable order in \(O(N)\) time.

Parameters

• to_what – a list/tuple/np.darray of target var names,

• sequence (or a variable) –

Returns

a revised variable sequence

Return type

VarSeq

Note

The original sequence in unchanged (the operation is NOT in-place!)

count_inversions_to(to_what)

Counts inversions with another list (or VarSeq).

classmethod generate_weights(N)

Generates a random valid sequence of N weights.

That is, respects the requirement: \(n_{i+1} \leq 2n_i\).

greedy_sort(to_what=None)

Revises the VarSeq to a given order of labels to_what.

Parameters

to_what (list / VarSeq) – target order of variables (or a varseq where it can be extracted from.)

Note

A naive implementation / cross-check, “sift-align” procedure, \(O(N^2)\).

is_aligned(to_what)

Helper function: checks if varseq is aligned with to_what.

classmethod random(vars=None, N=7)

Generates a random variable sequence.

Returns

an object representing a weighted variable sequence with N variables and random element weights. If no variable labels are given (in vars), uses a random permutation of integer labels 1,…,N.

Return type

VarSeq

size()

Returns the total sequence size (sum of element weights).

slide(a, j, inplace=False)

Performs a sift of element a (label) to position j.

Returns

a revised copy of a variable sequence or a self-pointer (if inplace = True)

Return type

VarSeq

var_size(var)

Returns the element weight (given its label var).

❖❖❖

Functions

varseq.non_dominated(e, A, B)

Checks if the element “e” is non-dominated.

Considering e as a candidate for the last position in the target alignment of VarSeq -s A and B, check if it is non-dominated.

Returns

True = non-dominated, False = dominated.