ChainAndY
- class corsort.ChainAndY(a, b, c, d)[source]
A poset consisting of a chain and a Y-shape.
Use
draw()to visualize an example.- Parameters:
- property average_height
Average height.
- Returns:
Size c. Average height for each node.
- Return type:
Examples
>>> ChainAndY(2, 1, 7, 3).average_height array([Fraction(14, 3), Fraction(28, 3), Fraction(7, 6), Fraction(133, 48), Fraction(35, 8), Fraction(287, 48), Fraction(91, 12), Fraction(147, 16), Fraction(259, 24), Fraction(595, 48), Fraction(35, 8), Fraction(91, 12), Fraction(259, 24)], dtype=object)
- property average_normalized_height
Average normalized height.
- Returns:
Size c. Average normalized height for each node.
- Return type:
Examples
>>> ChainAndY(2, 1, 7, 3).average_normalized_height array([Fraction(1, 3), Fraction(2, 3), Fraction(1, 12), Fraction(19, 96), Fraction(5, 16), Fraction(41, 96), Fraction(13, 24), Fraction(21, 32), Fraction(37, 48), Fraction(85, 96), Fraction(5, 16), Fraction(13, 24), Fraction(37, 48)], dtype=object)
- property delta
Estimator of position “delta” for each node.
It is the number of descendants, minus the number of ancestors. Up to an affine transformation, it is the average between the worst and the best possible positions of the node in the sorted list.
- Returns:
Size a + b + c + d. Estimator delta for each node.
- Return type:
Examples
>>> ChainAndY(10, 4, 5, 7).delta array([ -9, -7, -5, -3, -1, 1, 3, 5, 7, 9, -15, -13, -11, -9, 0, 2, 4, 6, 8, -2, 0, 2, 4, 6, 8, 10])
- draw(with_labels=False, alpha_labels=False)[source]
Draw the poset.
- Parameters:
Examples
>>> ChainAndY(10, 4, 5, 7).draw()
>>> ChainAndY(10, 4, 5, 7).draw(alpha_labels=True)
- property graph
The poset as a networkx graph.
The main purpose of the property is to be used by
draw().- Returns:
class – The graph.
- Return type:
~networkx.DiGraph
Examples
>>> print(ChainAndY(10, 4, 5, 7).graph) DiGraph with 26 nodes and 24 edges
- kemeny_score(order)[source]
Kemeny score of an order over the candidates.
- Parameters:
order (
list) – An order over the candidates.- Returns:
The Kemeny score (average kendall-tau distance with a linear extension of the poset).
- Return type:
Examples
>>> poset = ChainAndY(2, 2, 1, 3) >>> poset.kemeny_score([0, 4, 7, 2, 6, 3, 5, 1]) 13.5
- property median_height
Median height.
- Returns:
Size a + b + c + d. Median height for each node in the linear extensions.
- Return type:
Examples
>>> ChainAndY(2, 1, 7, 3).median_height array([ 3., 9., 0., 2., 3., 5., 7., 8., 10., 12., 3., 7., 10.])
- property n_nodes
Number of nodes
- Returns:
Number of nodes
- Return type:
Examples
>>> ChainAndY(2, 1, 1, 2).n_nodes 6
- property nb_ancestors
Number of ancestors for each node.
- Returns:
Size a + b + c + d. Number of ancestors for each node.
- Return type:
Examples
>>> ChainAndY(10, 4, 5, 7).nb_ancestors array([10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 16, 15, 14, 13, 5, 4, 3, 2, 1, 7, 6, 5, 4, 3, 2, 1])
- property nb_descendants
Number of ancestors for each node.
- Returns:
Size a + b + c + d. Number of descendants for each node.
- Return type:
Examples
>>> ChainAndY(10, 4, 5, 7).nb_descendants array([ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 5, 6, 7, 8, 9, 10, 11])
- property nb_linear_extensions
Number of linear extensions.
- Returns:
Number of linear extensions of the poset.
- Return type:
Examples
>>> ChainAndY(10, 4, 5, 7).nb_linear_extensions 4206894120
- property order_average_height
Order of the nodes, according to average height.
- Returns:
Estimated order of the nodes.
- Return type:
Examples
>>> ChainAndY(2, 2, 1, 3).order_average_height array([2, 3, 0, 5, 4, 6, 1, 7]...)
- property order_delta
Order of the nodes, according to estimator delta.
- Returns:
Estimated order of the nodes.
- Return type:
Examples
>>> ChainAndY(2, 2, 1, 3).order_delta array([2, 3, 0, 5, 1, 4, 6, 7]...)
- property order_kemeny
Kemeny order of the nodes in the profile of linear extensions.
- Returns:
The candidates, in their Kemeny order.
- Return type:
Examples
>>> ChainAndY(0, 1, 2, 7).order_kemeny array([0, 3, 4, 1, 5, 6, 7, 2, 8, 9])
- property order_median_height
Order of the nodes, according to median height.
- Returns:
Estimated order of the nodes.
- Return type:
Examples
>>> ChainAndY(2, 2, 1, 3).order_median_height array([2, 3, 0, 5, 1, 4, 6, 7]...)
- property order_rho
Order of the nodes, according to estimator rho.
- Returns:
Estimated order of the nodes.
- Return type:
Examples
>>> ChainAndY(2, 2, 1, 3).order_rho array([2, 3, 0, 5, 1, 6, 4, 7]...)
- property order_spearman_optimal
Order of the nodes optimizing the expected Spearman distance.
- Returns:
The candidates, in their optimal order for expected Spearman distance.
- Return type:
Examples
>>> ChainAndY(0, 1, 2, 7).order_spearman_optimal array([0, 3, 4, 1, 5, 6, 7, 2, 8, 9]...)
- property positions_counts_in_extensions
Positions counts in linear extensions for the elements of the poset.
- Returns:
Size a + b + c + d * a + b + c + d. Coefficient (i, r) represents the number of linear extensions of the poset where node i is in rank r (note that items and ranks are numbered from 0, Python-style).
- Return type:
Examples
>>> ChainAndY(2, 1, 7, 3).positions_counts_in_extensions array([[1440, 1320, 1200, 1080, 960, 840, 720, 600, 480, 360, 240, 120, 0], [ 0, 120, 240, 360, 480, 600, 720, 840, 960, 1080, 1200, 1320, 1440], [7920, 1320, 120, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [ 0, 4620, 2940, 1260, 420, 105, 15, 0, 0, 0, 0, 0, 0], [ 0, 0, 2520, 3024, 2184, 1134, 414, 84, 0, 0, 0, 0, 0], [ 0, 0, 0, 1260, 2380, 2555, 1905, 980, 280, 0, 0, 0, 0], [ 0, 0, 0, 0, 560, 1540, 2340, 2440, 1760, 720, 0, 0, 0], [ 0, 0, 0, 0, 0, 210, 810, 1710, 2490, 2565, 1575, 0, 0], [ 0, 0, 0, 0, 0, 0, 60, 320, 940, 1950, 3010, 3080, 0], [ 0, 0, 0, 0, 0, 0, 0, 10, 74, 309, 959, 2464, 5544], [ 0, 1980, 1980, 1620, 1260, 945, 675, 450, 270, 135, 45, 0, 0], [ 0, 0, 360, 720, 1000, 1190, 1290, 1300, 1220, 1050, 790, 440, 0], [ 0, 0, 0, 36, 116, 241, 411, 626, 886, 1191, 1541, 1936, 2376]]...)
- property profile_linear_extensions
Profile consisting of all linear extensions.
- Returns:
One row for each linear extension, a + b + c + d columns. Each coefficient is the label of a node.
- Return type:
Examples
>>> ChainAndY(1, 2, 1, 2).profile_linear_extensions array([[0, 1, 2, 3, 4, 5], [1, 0, 2, 3, 4, 5], [1, 2, 0, 3, 4, 5], [1, 2, 3, 0, 4, 5], [1, 2, 3, 4, 0, 5], [1, 2, 3, 4, 5, 0], [0, 1, 2, 4, 3, 5], [1, 0, 2, 4, 3, 5], [1, 2, 0, 4, 3, 5], [1, 2, 4, 0, 3, 5], [1, 2, 4, 3, 0, 5], [1, 2, 4, 3, 5, 0], [0, 1, 2, 4, 5, 3], [1, 0, 2, 4, 5, 3], [1, 2, 0, 4, 5, 3], [1, 2, 4, 0, 5, 3], [1, 2, 4, 5, 0, 3], [1, 2, 4, 5, 3, 0]])
- property profile_linear_extensions_svvamp
Profile consisting of all linear extensions, as a svvamp profile.
- Returns:
Each voter represents a linear extension of the poset.
- Return type:
Profile
Examples
The attribute preferences_rk of the svvamp profile is equal to the attribute
profile_linear_extensions()of the poset:>>> ChainAndY(1, 2, 1, 2).profile_linear_extensions_svvamp.preferences_rk array([[0, 1, 2, 3, 4, 5], [1, 0, 2, 3, 4, 5], [1, 2, 0, 3, 4, 5], [1, 2, 3, 0, 4, 5], [1, 2, 3, 4, 0, 5], [1, 2, 3, 4, 5, 0], [0, 1, 2, 4, 3, 5], [1, 0, 2, 4, 3, 5], [1, 2, 0, 4, 3, 5], [1, 2, 4, 0, 3, 5], [1, 2, 4, 3, 0, 5], [1, 2, 4, 3, 5, 0], [0, 1, 2, 4, 5, 3], [1, 0, 2, 4, 5, 3], [1, 2, 0, 4, 5, 3], [1, 2, 4, 0, 5, 3], [1, 2, 4, 5, 0, 3], [1, 2, 4, 5, 3, 0]])
- property rho
Estimator of position “rho” for each node.
It is de / (de + an), where de denotes the number of descendants and an the number of ancestors. Up to an affine transformation, it would be the average position of the node if its descendants and ancestors were forming a chain and if no information was known about the other elements.
- Returns:
Size a + b + c + d. Estimator rho for each node.
- Return type:
Examples
>>> ChainAndY(10, 4, 5, 7).rho array([Fraction(1, 11), Fraction(2, 11), Fraction(3, 11), Fraction(4, 11), Fraction(5, 11), Fraction(6, 11), Fraction(7, 11), Fraction(8, 11), Fraction(9, 11), Fraction(10, 11), Fraction(1, 17), Fraction(2, 17), Fraction(3, 17), Fraction(4, 17), Fraction(1, 2), Fraction(3, 5), Fraction(7, 10), Fraction(4, 5), Fraction(9, 10), Fraction(5, 12), Fraction(1, 2), Fraction(7, 12), Fraction(2, 3), Fraction(3, 4), Fraction(5, 6), Fraction(11, 12)], dtype=object)
- property spearman_costs
Spearman costs.
- Returns:
Size a + b + c + d * a + b + c + d. Coefficient (i, r) represents the contribution of item i to the Spearman distance if it is placed in position r in the estimate ranking.
- Return type:
Examples
>>> ChainAndY(2, 1, 7, 3).spearman_costs array([[ 34320, 27840, 24000, 22560, 23280, 25920, 30240, 36000, 42960, 50880, 59520, 68640, 78000], [ 78000, 68640, 59520, 50880, 42960, 36000, 30240, 25920, 23280, 22560, 24000, 27840, 34320], [ 1560, 8040, 17160, 26520, 35880, 45240, 54600, 63960, 73320, 82680, 92040, 101400, 110760], [ 16575, 7215, 7095, 12855, 21135, 30255, 39585, 48945, 58305, 67665, 77025, 86385, 95745], [ 31590, 22230, 12870, 8550, 10278, 16374, 24738, 33930, 43290, 52650, 62010, 71370, 80730], [ 46605, 37245, 27885, 18525, 11685, 9605, 12635, 19475, 28275, 37635, 46995, 56355, 65715], [ 61620, 52260, 42900, 33540, 24180, 15940, 10780, 10300, 14700, 22620, 31980, 41340, 50700], [ 76635, 67275, 57915, 48555, 39195, 29835, 20895, 13575, 9675, 10755, 16965, 26325, 35685], [ 91650, 82290, 72930, 63570, 54210, 44850, 35490, 26250, 17650, 10930, 8110, 11310, 20670], [106665, 97305, 87945, 78585, 69225, 59865, 50505, 41145, 31805, 22613, 14039, 7383, 5655], [ 31590, 22230, 16830, 15390, 17190, 21510, 27720, 35280, 43740, 52740, 62010, 71370, 80730], [ 61620, 52260, 42900, 34260, 27060, 21860, 19040, 18800, 21160, 25960, 32860, 41340, 50700], [ 91650, 82290, 72930, 63570, 54282, 45226, 36652, 28900, 22400, 17672, 15326, 16062, 20670]]...)
- spearman_score(order)[source]
Spearman score of an order over the candidates.
- Parameters:
order (
list) – An order over the candidates.- Returns:
The Spearman score (average Spearman distance with a linear extension of the poset).
- Return type:
Examples
>>> poset = ChainAndY(2, 2, 1, 3) >>> poset.spearman_score([0, 4, 7, 2, 6, 3, 5, 1]) 22.142857142857142
- corsort.linear_extensions(chain_1, chain_2)[source]
Linear extensions for two independent chains (separate connected components).
- Parameters:
chain_1 (class:list)
chain_2 (class:list)
- Yields:
extension (class:list) – A linear extension of the poset consisting of the two given chains.
Examples
>>> for linear_extension in linear_extensions([1, 2, 3], [42, 52]): ... print(linear_extension) [ 1 2 3 42 52] [ 1 2 42 3 52] [ 1 2 42 52 3] [ 1 42 2 3 52] [ 1 42 2 52 3] [ 1 42 52 2 3] [42 1 2 3 52] [42 1 2 52 3] [42 1 52 2 3] [42 52 1 2 3]
>>> for linear_extension in linear_extensions([1, 2, 3], []): ... print(linear_extension) [1 2 3]