util_chains

corsort.util_chains.greedy_chain_decomposition(leq)

Greedy chain decomposition.

Find the longest chain. Then remove its elements from the graph, find the longest chain of the remaining vertices, and so on until exhaustion.

Parameters:

leq (ndarray.) – Matrix of size (n_, n_). Coefficient (i, j) is +1 if we know that item i <= item j, -1 if we know that item i > item j, 0 if we do not know the comparison between them.

Returns:

The chains, from the longest (found first during the algorithm) to the shortest (found last). Each chain is sorted from smallest item to greatest item.

Return type:

list of list

Examples

>>> my_leq = np.array([
...     [ 1,  1,  1,  1,  0,  0],
...     [-1,  1,  1,  0,  0,  0],
...     [-1, -1,  1,  0,  0,  0],
...     [-1,  0,  0,  1,  0,  0],
...     [ 0,  0,  0,  0,  1,  1],
...     [ 0,  0,  0,  0, -1,  1],
... ])
>>> greedy_chain_decomposition(my_leq)
[[0, 1, 2], [4, 5], [3]]

corsort.util_chains.longest_chain(leq)

Longest chain.

Parameters:

leq (ndarray.) – Matrix of size (n_, n_). Coefficient (i, j) is +1 if we know that item i <= item j, -1 if we know that item i > item j, 0 if we do not know the comparison between them.

Returns:

The chain, from smallest to greatest element.

Return type:

list.

Examples

>>> my_leq = np.array([
...     [ 1,  1,  1,  1,  0,  0],
...     [-1,  1,  1,  0,  0,  0],
...     [-1, -1,  1,  0,  0,  0],
...     [-1,  0,  0,  1,  0,  0],
...     [ 0,  0,  0,  0,  1,  1],
...     [ 0,  0,  0,  0, -1,  1],
... ])
>>> longest_chain(my_leq)
[0, 1, 2]

corsort.util_chains.longest_chain_starting_at(leq, start_item)

Longest chain starting at a given item.

Parameters:

• leq (ndarray.) – Matrix of size (n_, n_). Coefficient (i, j) is +1 if we know that item i <= item j, -1 if we know that item i > item j, 0 if we do not know the comparison between them.

• start_item (int) – Item which will be the smallest of the chain.

Returns:

The chain, from smallest to greatest element.

Return type:

list.

Examples

>>> my_leq = np.array([
...     [ 1,  1,  1,  1,  0,  0],
...     [-1,  1,  1,  0,  0,  0],
...     [-1, -1,  1,  0,  0,  0],
...     [-1,  0,  0,  1,  0,  0],
...     [ 0,  0,  0,  0,  1,  1],
...     [ 0,  0,  0,  0, -1,  1],
... ])
>>> longest_chain_starting_at(my_leq, 0)
[0, 1, 2]