Colin Champion, 13 Nov 2021/1 Jul 2022

procedure : other evaluations : results : software : index

This page describes an empirical comparison under simulated elections of more than 50 (mostly ordinal) voting methods. Sincere voting, tactical voting and strategic nomination are considered, and two distinct metrics are presented. The results favour minimax or (possibly) Tideman’s (Smith-set) alternative. Minimax is the much the simplest, and therefore the most recommendable.

Elections can be generated under one of three types of model:

There are two metrics for the spatial models. The first is the percentage of elections in which each method elects the rightful winner, defined as the candidate whose mean distance from voters is minimised. The second is mean Euclidean loss. If a voting method elects a candidate whose mean distance from voters is y, and if the minimum mean distance from voters over candidates is x, then the Euclidean loss is y–x. I consider losses to be intrinsically meaningless, but to provide a sounder basis for comparison than percentage correctness. The average distance from a voter to the best candidate in any election is around 1.7, so the differences in performance between competitive methods are very small.

Table 5 (measuring percentage correct for a particular form of tactical voting) is the sole case in which Condorcet+AV (ie. Condorcet/Hare) outperforms minimax, and when we look at the corresponding figures under Euclidean loss the results are reversed: evidently Condorcet/Hare makes fewer but larger mistakes than minimax, and is weaker overall.

The tables apply both metrics to sincere voting, to 4 forms of tactical voting, and to strategic nomination.

The metrics are essentially the same for jury models. The percentage correct is the percentage of elections in which the best candidate is chosen. Valence loss (i.e. loss of merit) is substituted for Euclidean loss.

My program produces some statistics concerning ties. Since these are not included in the main tables I summarise them here for the main condition (sincere voting under a GMM):

In the first 3 types of tactical voting, voters whose sincere first preference is for a certain candidate (c0) place another candidate (c1) at an insincere position in their lists. Type 1 (compromising) moves c1 to the top; type 2 (false cycles) puts him second; and type 3 (burying) puts him at the bottom. The names (‘false cycles’) are for convenience and do not necessarily reflect the mechanism by which subversion takes place.

The fourth form of tactical voting is list voting (which I previously called “exhaustive”). Voters whose sincere first preference is for c0 are sent a preprinted list telling them how to rank the candidates, and vote according to their instructions.

The number of candidates is reduced to 5 for tactical voting. Each of the 20 (c0,c1) pairs corresponds to an attempt at subversion for the first three forms, while there are 5×120 possible subversions to consider for the fourth. A subversion is considered to be successful if the winning candidate is closer to c0, and further from the average voter, than the winner under sincere voting. The result attributed to each method is the worst amongst its sincere result and all successful subversions of the given type.

Notice that the random algorithm seem to gain in accuracy under tactical voting conditions. This is a spuriosity arising from the reduced number of candidates.

I had expected the list condition to provide a sort of composite of the three more specific forms of tactical voting, but it turns out to have quite different properties which I do not understand. In particular Tideman’s Alternative markedly outperforms minimax (even under Euclidean loss) under list strategies, while being weaker under each of the three specific forms. Meanwhile Smith+BordaR, which looked competitive under the specific forms, falls away badly under list voting.

It may be that the list strategies bring in all sorts of artificial behaviour which are unlikely to arise in practice, and that the results corresponding to them should receive little weight. Contrariwise it may be that there are unrecognised but perfectly plausible forms of tactical voting whose effects show through under the list condition. In this case Tideman’s Alternative should be recognised as most resistant to tactical voting and Smith+BordaR as seriously vulnerable.

But either way, the simplicity of minimax and its excellent performance make it a clear preference.

An alternative metric is sometimes used for assessing systems under tactical voting. It asks the question “In what percentage of trials does there exist a group of voters who all prefer another candidate to the sincere winner, and who can cause that candidate to win by changing their votes?” The answer is taken as a measure of strategic vulnerability and its converse is interpreted as ‘robustness to strategy’.

I do not consider this a suitable metric for 3 reasons:

My own metric reports the number of errors under a tactical voting condition. This is the sum of errors which would have happened anyway (a small minority for Condorcet methods) and those induced by tactical voting. Readers should be warned that the two sorts of error might be of unequal importance.

Strategic nomination is modelled by drawing candidates from a distribution which is displaced relative to the voter distribution. The candidates come from a single gaussian whose mean is an exaggerated version of the mean of one of the components of the voter mixture. Draw a line from the origin to the mean of the component; extend it by 0.5; the result is the mean of the candidate distribution.

My evaluation also contains results for a jury model (aka. valence model). Each candidate i has a valence vi, and candidates are ranked by voter j in decreasing order of vi – εi j. The valences are drawn from a standard Gaussian distribution and the noise terms εi j from a zero-mean Gaussian of standard deviation σ. The Borda count does best under this model with Warren D. Smith’s Sinkhorn method coming second.

A jury model has two components, valence and random noise. I don’t doubt that both are present in political preferences but I doubt that spatial models lose anything through their absence.

The addition of a valence component to a spatial model leaves the median voter theorem unaffected, so is unlikely by itself to change anything. It is the random component of a jury model which gives it its characteristic properties, but while I accept that there is a random element to voters’ behaviour, I doubt that it is large enough to have a significant effect when the number of voters is as large as a typical electorate.

Tactical voting is defined slightly differently for a jury model: an attempted subversion is considered to be successful only if it leads to the election of the candidate c0 on whose behalf the tactical voters are acting. AV is pretty much best among methods in dealing with tactical voting under a jury model (Condorcet/AV hybrids may give a marginal improvement, but nothing to justify their added complexity).

The evaluation includes a few methods which aren’t purely ordinal. I have misgivings about their presence given that some degree of distortion is needed to accommodate them. I don’t wish to go much further in the direction of adding cardinal or semi-cardinal methods for fear of generating results which are seriously misleading.

Several other evaluations have been performed under a spatial model. In all cases the voters are drawn from a multivariate Gaussian distribution.

Chamberlin and Cohen (1978). These authors measured the ‘Condorcet efficiencies’ of Coombs, Borda, Hare (=AV) and Plurality (=FPTP). Their most meaningful results are those in Table 5 for medium dispersion and 1000 voters, which are perfectly consistent with those presented here.

Warren D. Smith makes the criticism that Condorcet efficiency is “a measure intentionally contrived to cause Condorcet’s voting system to be best possible, and having, in my opinion, no particular value aside from that” (“Range voting”, 2000.)

I partly disagree. In the circumstances of C&C’s evaluation Condorcet methods should be almost 100% accurate by the Median Voter Theorem, so Condorcet efficiency is almost the same thing as accuracy. ‘Borda efficiency’ would not have the same significance.

It would presumably have been easy for C&C to have published accuracies as well as Condorcet efficiencies. Given their failure to do so we need to bring in our own prior assumptions to interpret their results. This defeats the purpose of an evaluation, which is to confirm or overturn prior beliefs. I therefore accept that it is a severe methodological flaw to have published Condorcet efficiencies without accuracies; but it is not one which prevents us from making use of their figures. If there was a surfeit of trustworthy alternatives, we could afford to disregard C&C’s work; but as things stand it is valuable confirmation of a pattern discernible in some other results.

S. Merrill III (1984). Merrill performed an evaluation under a spatial metric showing the Borda Count to be more accurate than the Condorcet criterion. Smith suspects that “Merrill’s computer program had bugs” and I agree.

Tideman and Plassmann (2012). Completely unbelievable. Table 1 shows AV as 94.41% correct and Copeland 94.45% on effectively infinite voter populations.

Green-Armytage, Tideman and Cosman (2015). Software possibly exhibiting common mode failures with the preceding; shows AV as 94.45% correct and Minimax as 95.19%. Not credible.

Darlington (2016/2018). I believe these evaluations to be sound; however they have significant methodological drawbacks which I shall mention later. Only the earlier evaluation has been formally published.

Quinn (nd). (Unpublished.) This evaluation seems consistent with my own, Darlington’s, and C&C’s, but is rather vaguely presented. Quinn makes the (Python) software for his evaluation available.

My main reservations about Darlington’s evaluations are these:

My conclusion is that the majority of peer-reviewed evaluations are vitiated by software bugs, and that all the sound evaluations are liable to methodological objections. It is with a view to addressing these problems that I performed my own; but it has no formal status, and lacks the authority of the peer-reviewed evaluations listed above.

The position is unfortunate. The topic is important and readers will look to the academic literature for the gold standard in accuracy; and they will be let down. It is hard to see how this can be put right since journals are unlikely to welcome further evaluations.

At the same time, even informal comparisons (such as Darlington’s second) make no attempt to explain the relationship between their results and earlier work (with the praiseworthy exception of Smith). It’s hard to imagine that it didn’t occur to Darlington that the difference between his own figures and Tideman’s needed to be discussed, but academic politeness wins out.

sincere voting : compromising : false cycle : burying : list voting : strategic nomination : jury model

The best result in each table has a solid underline; all other results which are at least as good as minimax have broken underlines, while minimax is indicated by colour. There are various interesting points of detail, but overall the striking feature is the consistently good performance of minimax and Tideman’s alternative. Smith+BordaR, Smith+MinimaxR and Smith+MinimaxF run them close.

For a spatial model:

For a jury model there are 5 candidates and 101 voters. The noise standard deviation is 2.

Some algorithms have more than one name (see below).

 random fptp dblv seq 2rounds nauru bucklin borda sinkhorn mj av coombs
 11.097431.107745.620641.6380 50.680657.198970.910584.213781.906686.0460 53.236090.2217
 clower knockout benhambtr-irv baldwin nanson minimax minisum rp river schulze asm tideman cupper
 93.577093.778593.746793.812393.8127 93.891493.918993.920293.9048 93.904893.769893.827493.787394.2117
condorcet+randomfptpdblv borda av
 93.650993.698393.759693.904993.7495
copeland+ random fptpf fptprdblv bordafbordar avfavr minimaxfminimaxr
 93.802893.801693.834893.828693.904293.9167 93.793393.742893.916793.8823
smith+randomfptpffptprdblv bordafbordar avfavr minimaxfminimaxr
 93.769893.777993.833493.806393.9056 93.964893.7692 93.716893.919193.9191

 randomfptpdblv seq2roundsnaurubucklin bordasinkhornmjav coombs
 55.782420.29178.473210.77487.93935.3135 2.06200.78461.07550.83825.33050.3781
 clower knockout benhambtr-irv baldwin nanson minimax minisum rp river schulze asm tideman cupper
 0.15890.16060.15420.15240.1468 0.14440.14430.14510.1459 0.16240.15220.15600.1325
condorcet+randomfptpdblv bordaav
 0.44710.29260.19190.14530.1721
copeland+randomfptpf fptprdblv bordafbordar avfavrminimaxfminimaxr
 0.15490.15440.15190.15210.14520.1466 0.15460.15900.14460.1483
smith+randomfptpffptpr dblvbordafbordar avfavrminimaxfminimaxr
 0.16240.16020.15410.1561 0.14490.14190.1590 0.16360.14440.1444

 randomfptpdblv seq2roundsnaurubucklin bordasinkhornmjav coombs
 20.063131.908234.063653.0926 38.069941.898950.509345.736753.1890 73.2796
 clower knockout benhambtr-irv baldwin nanson minimax minisum rp river schulze asm tideman cupper
 72.336272.907272.782972.9788 73.111973.246473.261673.181973.1872 70.653172.632073.0107
condorcet+randomfptpdblv bordaav
 67.771872.835968.035473.043172.8854
copeland+randomfptpf fptprdblvbordafbordar avfavrminimaxfminimaxr
 73.271072.885072.834573.047873.1228 73.235772.902172.916473.268773.1097
smith+randomfptpffptpr dblvavfavr bordafbordar minimaxfminimaxr
 70.653172.838172.813368.3018 73.046973.3776 72.885472.8962 73.246473.2464

 randomfptpdblv seq2roundsnaurubucklin bordasinkhornmjav coombs
 49.041431.052611.67829.6541 16.08139.60417.13398.42338.52973.6814
 clower knockout benhambtr-irv baldwin nanson minimax minisum rp river schulze asm tideman cupper
 3.78083.91284.10753.75183.7244 3.59123.59573.6669 3.66164.28133.94743.6594
condorcet+randomfptpdblv bordaav
 7.27474.15884.74683.63644.0384
copeland+randomfptpf fptprdblv bordafbordar avfavr minimaxfminimaxr
 3.68944.00383.97913.7589 3.64263.7467 3.98563.8838 3.59993.7578
smith+randomfptpffptpr dblv bordafbordar avfavr minimaxfminimaxr
 4.28134.11454.05404.6507 3.63663.5629 4.03733.9326 3.59163.5916

 randomfptpdblv seq2roundsnaurubucklin bordasinkhornmjav coombs
 20.063157.423034.063670.1254 60.936741.654954.313950.972664.814857.7650
 clower knockout benhambtr-irv baldwin nanson minimax minisum rp river schulze asm tideman cupper
 55.778061.813551.2456 60.021761.886061.589261.7702 61.317161.265354.9667 53.831265.7327
condorcet+randomfptpdblv avborda
 58.455850.502163.330464.3305 61.8784
copeland+randomfptpf fptprdblvavfavr bordafbordarminimaxfminimaxr
 59.399058.355855.514461.1771 64.673261.6829 63.890962.1660 62.343662.8676
smith+randomfptpffptpr dblvavfavrbordaf bordarminimaxfminimaxr
 54.966750.498248.311363.3401 64.325959.9502 61.873860.7576 61.452761.4527

 randomfptpdblv seq2roundsnaurubucklin bordasinkhornmjav coombs
 49.04149.721711.67824.0857 5.07009.00194.55295.5646 4.46154.3572
 clower knockout benhambtr-irv baldwin nanson minimax minisum rp river schulze asm tideman cupper
 6.51443.93525.83323.8516 3.33833.36273.27953.42443.4302 7.00055.61563.8071
condorcet+randomfptpdblv avborda
 9.64177.83194.46473.91443.0194
copeland+randomfptpf fptprdblv bordafbordar avfavr minimaxfminimaxr
 4.94274.24304.59764.5346 2.95093.4203 3.37953.7330 3.19403.2085
smith+randomfptpffptpr dblvbordafbordar avfavrminimaxfminimaxr
 7.00057.24967.51724.4576 3.01983.4904 3.91604.1564 3.37613.3761

 randomfptpdblv seq2roundsnaurubucklin bordasinkhornmjav coombs
 20.063157.423045.739470.1254 54.970850.945334.648031.450966.691656.6180
 clower knockout benhambtr-irv baldwin nanson minimax minisum rp river schulze asm tideman cupper
 58.996062.673356.186459.4640 56.9688 63.654962.685061.455861.477261.9809 54.995466.8414
condorcet+randomfptpdblv bordaav
 61.912658.766257.258053.842463.3369
copeland+randomfptpf fptprdblv bordafbordar avfavrminimaxfminimaxr
 54.556253.060947.517055.719952.399750.2573 52.692148.793460.793050.6185
smith+randomfptpffptpr dblvbordafbordar avfavrminimaxfminimaxr
 61.980959.359154.040857.2633 53.852461.779963.343661.153863.6587 63.6587

 randomfptpdblv seq2roundsnaurubucklin bordasinkhornmjav coombs
 49.04149.72177.41084.0857 5.78105.81228.38719.45254.14154.5322
 clower knockout benhambtr-irv baldwin nanson minimax minisum rp river schulze asm tideman cupper
 5.00583.39144.27233.46403.7874 2.79762.92363.01023.04194.92674.67213.2297
condorcet+randomfptpdblv bordaav
 7.50694.72334.61014.57913.3330
copeland+randomfptpf fptprdblv bordafbordar avfavrminimaxfminimaxr
 5.40685.21515.91644.81124.8760 5.41325.02795.73203.28755.3695
smith+randomfptpffptpr dblvbordafavfavr bordarminimaxfminimaxr
 4.92674.24774.90314.60514.57513.3257 3.32933.61012.79622.7962

 randomfptpdblv seq2roundsnaurubucklin bordasinkhornmjav coombs
 20.063131.908234.063653.0926 26.985040.155914.3073
 clower knockout benhambtr-irv baldwin nanson minimax minisum rp river schulze asm tideman cupper
 52.109955.539445.219154.0403 50.618356.450054.607755.254055.0637 50.915647.757163.7136
condorcet+randomfptpdblv bordaav
 52.587741.633048.254537.625355.5332
copeland+randomfptpf fptprdblv bordafbordar avfavr minimaxfminimaxr
 45.785642.504841.332545.428636.7202 45.840245.683345.185050.921847.4136
smith+randomfptpffptpr dblv bordafbordar avfavr minimaxfminimaxr
 50.915642.533739.993348.0025 37.649445.354655.530654.543356.381556.3815

 randomfptpdblv seq2roundsnaurubucklin bordasinkhornmjav coombs
 49.041431.052612.85289.6545 22.365210.323219.4402
 clower knockout benhambtr-irv baldwin nanson minimax minisum rp river schulze asm tideman cupper
 8.93017.665611.50258.2011 8.11016.65976.78966.97937.212111.0265 8.85525.4897
condorcet+randomfptpdblv bordaav
 15.054918.96398.890911.31797.6755
copeland+randomfptpf fptprdblv bordafbordar avfavr minimaxfminimaxr
 9.765410.434210.55449.1426 10.90308.71549.17039.31647.60778.5760
smith+randomfptpffptpr dblv bordafbordar avfavr minimaxfminimaxr
 11.026515.047915.38818.925811.2508 8.88337.67707.90026.62196.6219

 randomfptpdblv seq2roundsnaurubucklin bordasinkhornmjav coombs
 11.121358.807869.511966.110073.7896 71.330782.807675.010167.0930-74.548393.1396
 clower knockout benhambtr-irv baldwin nanson minimax minisum rp river schulze asm tideman cupper
 95.364895.436095.426795.452895.4457 95.472495.481095.481295.477195.4774 95.435895.437995.425895.5870
condorcet+randomfptpdblv bordaav
 95.389595.441495.452295.442195.4262
copeland+randomfptpf fptprdblv bordafbordar avfavr minimaxfminimaxr
 95.444695.461195.452095.4632 95.445795.4851 95.443395.4205 95.480095.4720
smith+randomfptpffptpr dblv bordafbordar avfavr minimaxfminimaxr
 95.435895.457295.451395.4594 95.442995.4957 95.433495.4099 95.481095.4810

 randomfptpdblv seq2roundsnaurubucklin bordasinkhornmjav coombs
 66.46527.21293.02234.30602.8958 2.79150.82732.60474.5235-2.18100.2310
 clower knockout benhambtr-irv baldwin nanson minimax minisum rp river schulze asm tideman cupper
 0.09730.09810.09590.09590.0943 0.09380.09380.09400.09400.09740.09660.09770.0903
condorcet+randomfptpdblv bordaav
 0.19350.10680.09770.09690.1009
copeland+randomfptpf fptprdblv bordafbordar avfavr minimaxfminimaxr
 0.09630.09500.09570.09480.0964 0.09770.09630.09380.09390.0944
smith+randomfptpffptpr dblv bordafbordar avfavr minimaxfminimaxr
 0.09740.09560.09610.0952 0.09660.0931 0.09770.0991 0.09380.0938

 randomfptpdblv seq2roundsnaurubucklin bordasinkhornmjav coombs
 20.031982.885983.776370.823784.404385.1145 83.880985.891285.857884.490484.450284.4901
 clower knockout benhambtr-irv baldwin nanson minimax minisum rp river schulze asm tideman cupper
 84.050484.534084.556784.650984.5717 84.698984.692384.698484.685184.684084.5192 84.638784.568885.5751
condorcet+randomfptpdblv bordaav
 84.354384.664684.688984.808684.5576
copeland+randomfptpf fptprdblv bordafbordar avfavr minimaxfminimaxr
 84.559484.680884.645884.6977 84.697784.7189 84.575684.5656 84.699884.6729
smith+randomfptpffptpr dblv bordafbordar avfavr minimaxfminimaxr
 84.519284.668784.658084.6892 84.808584.7609 84.557684.5568 84.692784.6927

 randomfptpdblv seq2roundsnaurubucklin bordasinkhornmjav coombs
 116.25284.25583.776112.96523.5017 3.17243.72622.83782.85003.44903.47423.4563
 clower knockout benhambtr-irv baldwin nanson minimax minisum rp river schulze asm tideman cupper
 3.44513.42113.37543.4092 3.34953.35073.34803.35503.35593.4537 3.37553.41723.1143
condorcet+randomfptpdblv bordaav
 4.03783.36913.35393.29473.4204
copeland+randomfptpf fptprdblv bordafbordar avfavr minimaxfminimaxr
 3.42333.35753.37613.3485 3.29583.3394 3.40883.4134 3.34703.3609
smith+randomfptpffptpr dblv bordafbordar avfavr minimaxfminimaxr
 3.45373.36563.37113.3535 3.29483.3181 3.42043.4199 3.35033.3503

dblv: The `double vote' (Nanson, 1882). A candidate’s score is the sum of his first and second preference votes.

sequential voting: A series of rounds, in each of which the candidates are split randomly into two sets and voters choose between them, voting for whichever set contains their preferred candidate.

clower, cupper: These are the lower and upper bounds of Condorcet methods, both of which elect the Condorcet winner when one exists, while clower is telepathically wrong in remaining cases and cupper is telepathically right.

Llull’s knockout: Voters choose between A and B head to head, then between the winner and C, and so forth.

minisum: Suppose that 10 more voters prefer A to B than prefer B to A. Then B has a defeat margin of 10 to A, and A has no defeat margin at all (or a defeat margin of 0) to B. Elect the candidate whose sum of defeat margins is least. This is Tideman’s ‘Simplified Dodgson Rule’ (‘Collective Decisions and Voting’, 2006).

q&dc: “Count the basic scores of the candidates, which for a given candidate is the number of ballots on which it is ranked above at least one other candidate. Determine the Smith candidate X having the lowest basic score. Elect from among the candidates not pairwise defeated by X, the one with the highest basic score.” [Forest Simmons.]

tiebreaks: If Copeland’s method has a full Borda tiebreak, then a Borda ranking is computed on the entire field, and the winner is the Copeland winner who comes highest in it. A restricted Borda tiebreak is computed by applying the Borda count to the Copeland tie set – that is, ballots are compressed by squeezing out candidates not belonging to the set, and Borda’s method applied. DBLV can only be full.

X+Yf is sometimes written ‘X,Y’ and X+Yr ‘X//Y’.

fptp = plurality
av = irv = rcv = hare = ware
condorcet+av = condorcet/hare
condorcet+borda = black
copeland+borda = Dasgupta/Maskin (not clear whether this is bordar or bordaf)
smith+avf = woodall
smith+avr = smith/irv
X+Yf = X,Y and X+Yr = X//Y

condorcet.c : simplemethods.c : rankedpairs.c : ranf.c : condorcet.h : memory.h

Clicking on the following link will download the software as a tar file. Put it in a safe directory and extract the files (tar -xf condorcet.tar). The software is free to use and modify under GPL 3.0.

condorcet.c simplemethods.c rankedpairs.c ranf.c condorcet.h memory.h

Compile under g++:

g++ -O -g -o condorcet condorcet.c simplemethods.c rankedpairs.c ranf.c

This creates an executable ‘condorcet’.

The main program condorcet.c, the subroutines simplemethods.c and rankedpairs.c, and the header condorcet.h are the code I wrote specially; ranf.c and memory.h are a couple of my standard library files.

The call is:

    condorcet ncandidates nvoters ntrials options

where the options are character strings separated by ‘+’ signs. The legal options are:

The following is a fairly maximal call:

condorcet 5 30001 300000 cyc+av+coombs+diag:av

condorcet is written as an extensible program allowing you to add voting methods without changing any existing code. You provide a C/C++ function to apply the method and notify its existence through a standard call; you compile your new method in with the existing code base; and then you run condorcet as before.

Your code for a voting method receives the ballots (and possibly additional information) as input and should return the winning candidate. The normal prototype is one of the following:

int newmethod(int **bal,int *count,int nbal,int m) ;
int newmethod(int **bal,int *count,int nbal,int m,int **r) ;
int newmethod(int m,int **r) ;

coombs is an example of the first, benham of the second, and minisum of the third.

The matrix of counts can take either of two values:

The matrix of margins will be supplied unless your method is notified with a ‘p’ flag, in which case it receives the matrix of poscounts.

You should not assume that the ballots come in any particular order except that the first ballot will be random (to allow for the random ballot required by Ranked Pairs); nor should you assume that a ballot is listed only once in bal. You can easily compute r for yourself, but to avoid duplication you’re urged to use the extra parameter if you use victory margins (or their signums).

If a method determines its result from the victory margins without needing to refer to the ballots, the third call (in which the first three arguments of the second are omitted) provides a neater interface.

You do not need to worry about tied preferences since the ballots are strict orderings.

Extended prototypes pass an additional integer array:

int newmethod(int **bal,int *count,int nbal,int m,int *a) ;
int newmethod(int **bal,int *count,int nbal,int m,int **r,int *a) ;
int newmethod(int m,int **r,int *a) ;

The array a can have one of several different meanings:

Finally there is a prototype for methods which make use of the Smith set:

int newmethod(int **bal,int *count,int nbal,int m,int **r,int *a,int na) ;

Here a is the Smith set and na its size. Methods using the Smith set are implemented alongside Smith tiebreaks.

You notify condorcet by calling the function ‘notify’ with 3 arguments, which are the function implementing the voting method, its name, and a string of character flags which tell condorcet how to use it.

The notification needs to take place before main() is invoked. You achieve this by assigning the return value of ‘notify’ to a top-level static variable as shown in the example.

The header file condorcet.h should be included in your program to define the notification functions. It also defines a routine to find the Smith set and a few static utilities: factorial, compress, decompress, and euclid. See the source for details.

Suppose we want to evaluate Forest Simmons’s ‘Quick and Dirty Condorcet’ (“Count the basic scores of the candidates, which for a given candidate is the number of ballots on which it is ranked above at least one other candidate. Determine the Smith candidate X having the lowest basic score. Elect from among the candidates not pairwise defeated by X, the one with the highest basic score.”). We can write a function to implement it as follows:

#include "memory.h"
#include "condorcet.h"

int qdc(int **bal,int *count,int nbal,int m,int **rmat,int *set,int nset)
{ if(nset==1) return set[0] ; 
  int i,imax,balno,c,*basicscore=ivector(nset) ; 
  // Count the basic scores of the candidates, which for a given candidate is  
  // the no. of ballots on which it is ranked above at least one other candidate
  for(i=0;i<nset;i++) for(c=set[i],balno=0;balno<nbal;balno++) 
    if(bal[balno][m-1]!=c) basicscore[i] += count[balno] ;
  // Determine the Smith candidate c having the lowest basic score.
  for(c=i=0;i<nset;i++) if(basicscore[i]<basicscore[c]) c = i ; 
  // Elect from among the candidates not pairwise defeated by c, the one with
  // the highest basic score.
  for(imax=-1,i=0;i<nset;i++) if(rmat[c][i]<=0) 
    if(imax<0||basicscore[i]>basicscore[imax]) imax = i ; 
  free(basicscore) ; 
  return set[imax] ; 
}
static int unused = notify(qdc,"q&dc","c") ;

You now need to recompile condorcet with an extended command:

g++ -O -g -o condorcet condorcet.c simplemethods.c rankedpairs.c ranf.c qdc.c

When you run condorcet, q&dc results will be included among the output; eg.

    smith+ random  fptpf   fptpr    dblv   bordaf  bordar   avf     avr   minimaxfminimaxrtideman   q&dc
           0.0911  0.0911  0.0911  0.0911  0.0911  0.0911  0.0911  0.0911  0.0911  0.0911  0.0911  0.0911 

The various methods have been implemented following the descriptions I found most helpful. They are meant to be usable for reference but I cannot guarantee that all are exactly correct. If you think your favourite algorithm receives short shrift, you may want to validate the software. (It is also possible that I may have messed up copying and pasting, so simply running a small number of trials may bring the error to light.)

My implementation of Ranked Pairs follows Tideman’s original paper literally whereas my River may be simplistic.

Ties (other than those that receive special treatment: Copeland, Smith and Ranked Pairs) are resolved by taking the lexically first tied winner. There would be no advantage in randomly permuting the candidates because they’re random in the first place. If you want to make use of my code but want a genuinely random tiebreak, then you should either randomly permute the candidates in advance or modify the code.

After computing the Smith set I sort it lexically because the algorithm for finding it returns elements in decreasing order of Copeland score, which would violate the intended randomness of tie-breaking.

Almost all the code in condorcet except the individual methods is highly generic, so it would be hard for it to disadvantage a particular algorithm. MJ is special-cased throughout so it is something of an exception.

• euclid     • radixsort     • method     • exec     • line     • print     • getnalg     • getalg     • notify     • genmargins     • genposcounts     • llullset     • smithset     • genpt     • election     • battery     • votetactically     • main

#include "memory.h"
#include <math.h>
#include "condorcet.h"

static double euclid(xy A,xy B) 
{ return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y)) ; }
double ranf(),gaussv() ; // in ranf.c
int rani(int) ; 
void ranset(int) ;
int condorcet(int m,int **r) ;

static void radixsort(unsigned int *x,int n) // sort ascending 
{ unsigned int *a=x,*b=(unsigned int *) ivector(n),*c,f,k ; 
  int nb=sizeof(int),i,bytepos,count[256],offs[256] ;
  for(k=~0,f=i=0;i<n;i++) { k &= x[i] ; f |= x[i] ; }
  f ^= k ; 

  for(bytepos=0;bytepos<8*nb;bytepos+=8) if((f>>bytepos)&255)
  { for(i=0;i<256;i++) count[i] = 0 ; 
    for(i=0;i<n;i++) count[(a[i]>>bytepos)&255] += 1 ; 
    for(offs[0]=0,i=1;i<256;i++) offs[i] = offs[i-1] + count[i-1] ;
    for(i=0;i<n;i++) { k = (a[i]>>bytepos)&255 ; b[offs[k]++] = a[i] ; }
    c = b ; b = a ; a = c ; 
  }
  if(a==x) free(b) ; else { for(i=0;i<n;i++) x[i] = a[i] ; free(a) ; } 
}

struct method // structure defining a voting method
{ void *f ; 
  char *name,pflag,cflag,Cflag,aflag,bflag,rflag,fflag,xflag,active,argtype ; 
  int res,len ; 
  method(void *p1,char *p2,char *p3,int p4)
  { f = p1 ; name = p2 ; argtype = p4 ; 
    len = strlen(name) ; 
    if(strchr(p3,'o')) active = 0 ; else active = 1 ;
    if(strchr(p3,'p')) pflag = 1 ; else pflag = 0 ;
    if(strchr(p3,'c')) cflag = 1 ; else cflag = 0 ;
    if(strchr(p3,'C')) Cflag = 1 ; else Cflag = 0 ;
    if(strchr(p3,'a')) aflag = 1 ; else aflag = 0 ;
    if(strchr(p3,'b')) bflag = 1 ; else bflag = 0 ;
    if(strchr(p3,'r')) rflag = 1 ; else rflag = 0 ;
    if(strchr(p3,'f')) fflag = 1 ; else fflag = 0 ;
    if(strchr(p3,'x')) xflag = 1 ; else xflag = 0 ;
  }
  int exec(int **b,int *c,int nb,int m,int **r,int **p,int *s,int ns)
  { int **mat=pflag?p:r ; 
    if(argtype==0) return ((int (*)(int **,int *,int,int)) f)(b,c,nb,m) ; 
    else if(argtype==1) 
      return ((int (*)(int **,int *,int,int,int **)) f)(b,c,nb,m,mat) ; 
    else if(argtype==2) 
      return ((int (*)(int **,int *,int,int,int *)) f)(b,c,nb,m,s) ; 
    else if(argtype==3) 
      return ((int (*)(int **,int *,int,int,int **,int *)) f)(b,c,nb,m,mat,s) ; 
    else if(argtype==4) 
      return ((int (*)(int **,int *,int,int,int **,int *,int)) f)
              (b,c,nb,m,mat,s,ns) ; 
    else if(argtype==11) return ((int (*)(int,int **)) f)(m,mat) ; 
    else if(argtype==13) return ((int (*)(int,int **,int *)) f)(m,mat,s) ; 
    throw up("can\'t process arg type %d",argtype) ; 
  }
  int line(int l) // says how often a method occurs on line l of output
  { if(l==0) return !cflag ; 
    else if(l==1) return cflag&&argtype!=4 ; 
    else if(l==2) return Cflag ; 
    else if(l==3) return rflag + fflag ;
    else return rflag + fflag + (argtype==4) ;
  }
  int print(int sp,char opt)
  { char buf[30] ; 
    int l=(opt?len+1:len),i=(2*sp+16-l)/2-4,j ;
    for(j=0;j<i;j++) buf[j] = ' ' ; 
    strcpy(buf+i,name) ; 
    if(opt) { buf[i+len] = opt ; buf[i+len+1] = 0 ; }
    printf("%s",buf) ; 
    return 12-l-(16-l)/2 ; 
  }
} ;
static int nmethod=0,methodlen=0 ; 
static method *mlist=0 ; 

static int getnalg()
{ int i,j,n ;
  for(n=i=0;i<nmethod;i++) for(j=0;j<5;j++) n += mlist[i].line(j) ;
  return n ; 
}
static int getalg(char *name)
{ int i,algno ;
  for(algno=i=0;i<nmethod;i++) if(mlist[i].line(0))
  { if(!strcmp(mlist[i].name,name)) return algno ; algno += 1 ; }
  for(i=0;i<nmethod;i++) if(mlist[i].line(1))
  { if(!strcmp(mlist[i].name,name)) return algno ; algno += 1 ; }
  for(i=0;i<nmethod;i++) algno += mlist[i].line(2) + mlist[i].line(3) ;
  for(i=0;i<nmethod;i++) if(mlist[i].line(4))
  { if(!strcmp(mlist[i].name,name)) return algno ; algno += 1 ; }
  return -1 ; 
}
int notify(void *func,char *n,char *t,int a)
{ int i ; 
  for(i=0;i<nmethod;i++) if(!strcmp(mlist[i].name,n))
    throw up("%s has already been notified",n) ;
  if((strchr(t,'a')||strchr(t,'b'))&&a!=2&&a!=3&&a!=13) 
    throw up("%s does not have a suitable arg for type %s",n,t) ; 
  if(a==0||a==1) // standard args + possibly results matrix
  { if(strchr(t,'f')||a==4) 
      throw up("%s does not have enough args for type %s",n,t) ; 
  }
  if(strchr(t,'a')||strchr(t,'b')||strchr(t,'f')) if(a!=2&&a!=3&&a!=13)
    throw up("%s has type %s which needs an array argument",n,t) ; 
  if(!strchr(t,'a')&&!strchr(t,'b')&&!strchr(t,'f')) if(a==2||a==3||a==13)
    throw up("%s has type %s which does not have an array argument",n,t) ; 
  if(nmethod==methodlen)
  { methodlen += 60 ; 
    mlist = (method *) cjcrealloc(mlist,methodlen*sizeof(method)) ; 
  }
  mlist[nmethod++] = method(func,n,t,a) ;
  return 0 ; 
}
int notify(int (*f)(int **,int *,int,int),char *name,char *opts)
{ return notify((void *)f,name,opts,0) ; }
int notify(int (*f)(int **,int *,int,int,int **),char *name,char *opts)
{ return notify((void *)f,name,opts,1) ; }
int notify(int (*f)(int,int **),char *name,char *opts)
{ return notify((void *)f,name,opts,11) ; }
int notify(int (*f)(int **,int *,int,int,int *),char *name,char *opts)
{ return notify((void *)f,name,opts,2) ; }
int notify(int (*f)(int **,int *,int,int,int **,int *),char *name,char *opts)
{ return notify((void *)f,name,opts,3) ; }
int notify(int (*f)(int,int **,int *),char *name,char *opts)
{ return notify((void *)f,name,opts,13) ; }
int notify(int (*f)(int **,int *,int,int,int **,int *,int),char *n,char *o)
{ return notify((void *)f,n,o,4) ; }

int simplenotifier() ; // in simplemethods
static int unusedvariable = simplenotifier() ; 

int **genmargins(int **bal,int *count,int nbal,int m) // rmat[i][j] contains i's
{ int i,j,v,balno,*b,**rmat=imatrix(m,m) ;      // signed victory margin over j 
  for(balno=0;balno<nbal;balno++) for(v=count[balno],b=bal[balno],i=0;i<m-1;i++)
    for(j=i+1;j<m;j++) rmat[b[i]][b[j]] += v ; 
  for(i=0;i<m-1;i++) for(j=i+1;j<m;j++) 
  { v = rmat[i][j] - rmat[j][i] ; rmat[i][j] = v ; rmat[j][i] = -v ; }
  return rmat ;
}
int **genposcounts(int **bal,int *count,int nbal,int m)
{ int i,v,balno,*b,**pmat=imatrix(m,m) ;  
  for(balno=0;balno<nbal;balno++) for(v=count[balno],b=bal[balno],i=0;i<m;i++)
    pmat[b[i]][i] += v ; 
  return pmat ;
}
/* -------------------------------- llullset -------------------------------- */

int llullset(int m,int **r,int *llullscore,int *set)
{ int i,j,t,imax,rsgn ; 
  for(i=0;i<m;i++) for(llullscore[i]=j=0;j<m;j++) 
  { if(r[i][j]>0) rsgn = 1 ; else if(r[i][j]<0) rsgn = -1 ; else rsgn = 0 ; 
    llullscore[i] += rsgn ; 
  }
  for(i=0;i<m;i++) if(i==0||llullscore[i]>imax) imax = llullscore[i] ;  
  for(t=i=0;i<m;i++) if(llullscore[i]==imax) set[t++] = i ; 
  return t ; 
}
/* -------------------------------- smithset -------------------------------- */

int smithset(int m,int **r,int *llullscore,int *set)
{ int i,j,row,col,lhs,rhs,ind[25] ;
  xi* pref = xivector(m) ; 
  for(i=0;i<m;i++) pref[i] = xi(llullscore[i],i) ; 
  xisortdown(pref,m) ; 
  for(i=0;i<m;i++) ind[i] = pref[i].i ; 
  free(pref) ;   

  for(rhs=1,lhs=0;lhs<rhs;lhs=rhs,rhs=row+1)
  { for(;rhs<m&&llullscore[ind[rhs]]==llullscore[ind[rhs-1]];rhs++) ; 
    for(col=rhs,row=m;col==rhs&&row>=rhs;row--) 
      for(col=lhs;col<rhs&&r[ind[row-1]][ind[col]]<0;col++) ; 
  }
  for(i=0;i<lhs;i++) set[i] = ind[i] ; 
  return lhs ; 
}

/* -------------------------------- election -------------------------------- */

xy genpt(xy *offs,double qscl)
{ int i=rani(3) ; 
  xy U = xy(gaussv()+offs[i].x,gaussv()+offs[i].y) ;
  if(qscl>=0) U.y *= qscl ; 
  return U ; 
}
// generate a random election under the model

int election(int m,int n,int **bal,int *count,double *dist,double **d2,
             int opt,int *mj,double qsd,double qscl)
{ double q,r,**judg ;
  int i,j,t,*vote=ivector(m),*x=ivector(n),nbal,rind ;
  xy V,offs[3],*C=xyvector(m) ;
  xi *pref=xivector(m) ;
  if(mj) judg = matrix(m,n) ; 
  for(i=0;i<m;i++) dist[i] = 0 ; 

  // generate voter distributions and candidates
  if(qsd>0) for(j=0;j<m;j++) C[j] = gaussv() ; // jury model
  else if(qscl>=0)                           // single gaussian
  { for(i=0;i<3;i++) offs[i] = xy() ;
    for(j=0;j<m;j++) C[j] = genpt(offs,qscl) ; 
    if(opt) for(j=0;j<m;j++) C[j].x += 1 ;     // offset
  }
  else                                         // mixture of 3 gaussians
  { for(i=0;i<3;i++) offs[i] = xy(gaussv(),gaussv()) ; 
    if(opt) for(q=euclid(offs[0],xy()),r=1+1/(2*q),j=0;j<m;j++) // offset
      C[j] = xy(gaussv()+r*offs[0].x,gaussv()+r*offs[0].y) ; 
    else for(j=0;j<m;j++) C[j] = genpt(offs,-1) ; 
  }

  // generate voters
  for(j=0;j<n;j++) 
  { if(qsd<=0) V = genpt(offs,qscl) ; 
    for(i=0;i<m;i++) 
    { if(qsd>0) q = qsd*gaussv() - C[i].x ;       // v's estimate of c's badness
      else dist[i] += q = euclid(C[i],V) ;        // distance
      pref[i] = xi(q,i) ; 
      if(mj) judg[i][j] = q ; 
    }
    xisort(pref,m) ;                              // sort the distances to cands
    for(i=0;i<m;i++) vote[i] = pref[i].i ;        // thus find voter's ranking
    x[j] = compress(vote,m) ;                     // compress ranking to an int
  }

  // compute the array of candidate losses
  if(qsd>0) 
  { for(q=i=0;i<m;i++) if(i==0||C[i].x>q) q = C[i].x ; 
    for(i=0;i<m;i++) dist[i] = q - C[i].x ; 
  }
  else for(i=0;i<m;i++) dist[i] /= n ;            // convert sum of dists to avg

  // sort the compressed rankings to dedupe them; then store them decompressed
  // in bal together with counts in count
  rind = x[0] ;
  radixsort((unsigned int *)x,n) ;
  for(t=-1,nbal=i=0;i<n;i=j)
  { for(j=i+1;j<n&&x[j]==x[i];j++) ; 
    if(x[i]==rind) t = nbal ; 
    decompress(x[i],bal[nbal],m) ; 
    count[nbal++] = (j-i) ; 
  }

  // put a random ballot first
  if(t<0) throw up("logic error in random ballots") ; 
  for(i=0;i<m;i++) swap(bal[t][i],bal[0][i]) ;
  swap(count[t],count[0]) ; 

  if(d2&&qsd<=0) for(i=0;i<m-1;i++) for(j=i+1;j<m;j++)
    d2[i][j] = d2[j][i] = euclid(C[i],C[j]) ; 
  else if(d2) for(i=0;i<m;i++) for(j=0;j<m;j++) d2[i][j] = (i!=j) ; 
  if(mj) for(q=mj[0]=i=0;i<m;i++) // have to find mj winner here
  { realsort(judg[i],n) ; 
    if(i==0||judg[i][n/2]<q) { mj[0] = i ; q = judg[i][n/2] ; }
  }
  if(mj) freematrix(judg) ; 
  free(vote,x,pref,C) ; 
  return nbal ;
}
/* -------------------------------- battery --------------------------------- */

// battery of voting methods; first standalone, then llull and smith tiebreaks
// minimax tells us whether we have a condorcet cycle, and if not we short cut
// the condorcet methods, assigning the condorcet winner to each 

void battery(int **bal,int *count,int nbal,int m,int *res,int *tie)
{ int i,j,k,minx,nset,*llullscore,**rmat,*set,ntb=9,nalg=getnalg() ; 
  int **score=imatrix(nmethod,m),*buf,*red,*ccount,**cbal,**rdash,*p ; 
  int **pmat,**pdash,nn,mi,ai,bi,r,iter,balno,algno,cond ; 

  rmat = genmargins(bal,count,nbal,m) ;
  pmat = genposcounts(bal,count,nbal,m) ;
  for(bi=ai=mi=-1,i=0;i<nmethod;i++) 
    if(!strcmp(mlist[i].name,"minimax")) mi = i ; 
    else if(!strcmp(mlist[i].name,"irv")||!strcmp(mlist[i].name,"av")) ai = i ; 
    else if(!strcmp(mlist[i].name,"borda")) bi = i ; 
  if(mi<0) throw up("minimax not provided as a method") ; 
  if(ai<0) throw up("av/irv not provided as a method") ; 
  if(bi<0) throw up("borda not provided as a method") ; 
  cond = condorcet(m,rmat) ; 

  // now do non-Condorcet methods
  for(algno=i=0;i<nmethod;i++) if(!mlist[i].cflag)
  { if(mlist[i].active||(cond<0&&mlist[i].Cflag))
    { if(!mlist[i].f) r = -(1+i) ; 
      else r = mlist[i].exec(bal,count,nbal,m,rmat,pmat,score[i],0) ; 
      mlist[i].res = res[algno] = r ;
    }
    algno += 1 ; 
  }

  if(cond>=0) for(;algno<nalg;algno++) res[algno] = cond ; // no cycle
  else                                                     // condorcet cycle 
  { // do the standalone condorcet methods
    for(i=0;i<nmethod;i++) if(mlist[i].cflag&&mlist[i].argtype!=4)
    { if(!mlist[i].f) res[algno] = -(1+i) ; 
     else if(mlist[i].aflag)       // av follow-on
        res[algno] = mlist[i].exec(bal,count,nbal,m,rmat,pmat,score[ai],0) ; 
      else if(mlist[i].bflag)       // borda follow-on
        res[algno] = mlist[i].exec(bal,count,nbal,m,rmat,pmat,score[bi],0) ; 
      else if(mlist[i].fflag||!strcmp(mlist[i].name,"minimax")) // full tiebreak 
        res[algno] = mlist[i].exec(bal,count,nbal,m,rmat,pmat,score[i],0) ; 
      else res[algno] = mlist[i].exec(bal,count,nbal,m,rmat,pmat,0,0) ; 
      if(!strcmp(mlist[i].name,"minimax")) minx = res[algno] ;
      algno += 1 ; 
    }

    if(tie) 
    { tie[0] += 1 ;                                 // condorcet cycle
      for(i=0;i<m;i++) if(i!=minx&&score[mi][minx]==score[mi][i]) break ;
      if(i<m) tie[3] += 1 ;                         // minimax tie
    }

    // do the condorcet completions
    for(i=0;i<nmethod;i++) if(mlist[i].Cflag) res[algno++] = mlist[i].res ; 

    // no do the tiebreaks for each of the set-valued methods
    llullscore = ivector(m) ; 
    set = ivector(m) ; 
    buf = ivector(m) ; 
    red = ivector(m) ; 
    for(iter=0;iter<2;iter++)
    { if(iter==0) nset = llullset(m,rmat,llullscore,set) ;
      else nset = smithset(m,rmat,llullscore,set) ;
      if(tie&&iter==0)
      { for(i=0;i<nset&&(set[i]!=minx);i++) ; 
        if(i==nset) tie[7] += 1 ; // count of minimax winners outside llull set
      }
      isortup(set,nset) ; // so that the smith set is listed in 'random' order
      if(tie) tie[4+iter] += nset ; 
      if(tie&&nset>1) tie[1+iter] += 1 ;           // non-singleton set

      nn = factorial(nset) ;
      ccount = ivector(nn) ; 
      cbal = imatrix(nn,nset) ;

      // compact the ballots
      for(i=0;i<m;i++) buf[i] = -1 ; 
      for(i=0;i<nset;i++) buf[set[i]] = i ;
      for(balno=0;balno<nbal;balno++)
      { for(j=i=0;i<m;i++) if((k=buf[bal[balno][i]])>=0) red[j++] = k ; 
        if(j!=nset) throw up("j=%d, nset=%d",j,nset) ; 
        k = compress(red,nset) ; 
        ccount[k] += count[balno] ; 
      }
      for(i=0;i<nn;i++) decompress(i,cbal[i],nset) ;
      rdash = genmargins(cbal,ccount,nn,nset) ; 
      pdash = genposcounts(cbal,ccount,nn,nset) ; 

      for(i=0;i<nmethod;i++) 
      { if(mlist[i].fflag)
        { for(r=j=0;j<nset;j++) if(j==0||score[i][set[j]]>score[i][r]) 
            r = set[j] ; 
          res[algno++] = r ; 
        }
        if(mlist[i].rflag)
        { if(mlist[i].fflag) p = red ; // work array
          else if(mlist[i].aflag) p = score[ai] ; 
          else if(mlist[i].bflag) p = score[bi] ; 
          else p = 0 ; 
          j = mlist[i].exec(cbal,ccount,nn,nset,rdash,pdash,p,0) ;
          res[algno++] = set[j&0xffffff] ; // because minimax includes a flag
        }
        if(iter&&mlist[i].argtype==4) // tideman's alternative
          res[algno++] = mlist[i].exec(bal,count,nbal,m,rmat,pmat,set,nset) ;
      }
      free(ccount) ; freeimatrix(cbal,rdash,pdash) ; 
    }
    free(llullscore,set,buf,red) ; 
  }
  freeimatrix(rmat,pmat,score) ; 
}
/* ----------------------------- votetactically ----------------------------- */

void votetactically(int *ibal,int *obal,int m,int c0,int c1,int opt) 
{ int j,k ; 
  for(j=0;j<m;j++) obal[j] = ibal[j] ; 
  if(ibal[0]==c0&&opt==4) decompress(c1,obal,m) ; 
  else if(ibal[0]==c0)
  { if(opt==1) { obal[0] = c1 ; obal[1] = c0 ; }
    else if(opt==2) { if(ibal[1]==c1) return ; obal[1] = c1 ; }
    else { if(ibal[m-1]==c1) return ; obal[m-1] = c1 ; }
    for(k=(opt==3?1:2),j=1;j<m;j++) 
      if(ibal[j]!=c1) obal[k++] = ibal[j] ; 
    if((opt==3&&k!=m-1)||(opt<3&&k!=m)) throw up("logic error") ; 
  }
}
/* ---------------------------------- main ---------------------------------- */

int main(int argc,char **argv)
{ int m = argc<2?9:atoi(argv[1]) , n = argc<3?10001:atoi(argv[2]) ;
  int ntests = argc<4?100000:atoi(argv[3]) , opt=0,mji,diag=-1,metric ; 
  int nalg=getnalg(),i,j,k,l,t,nbal,rightful,testno,c0,c1,mj,mno,offset=0,clim ;
  int *res=ivector(nalg) , **cbal=imatrix(n,m) , *cres=ivector(nalg) ;
  int *rbal = ivector(2*m) , *active = ivector(nalg) , resdiag,ndiag,sp,resno ; 
  int **bal=imatrix(n,m),*win=ivector(nalg),*tie=ivector(8),*count=ivector(n) ;
  double q,tbal,qdist,qsd=-1,qscale=-1, *qlos = vector(nalg) ;
  double *qres = vector(nalg) , *dist = vector(m) , **d2 = matrix(m,m) ; 
  char *tok , buf[50] ;
  if(m>12) throw up("too many candidates (%d): max is 12",m) ; 

  /* -------------------------- extract parameters -------------------------- */

  if(argc>=5) for(tok=strtok(argv[4],"+-, ");tok;tok=strtok(0,"+-, "))
  { for(k=i=0;i<nmethod;i++) 
      if(!strcmp(tok,mlist[i].name)&&mlist[i].active==0)
        k = mlist[i].active = 1 ; 
    if(k) ; // don't reuse option
    else if(!strcmp(tok,"offset")) offset = 1 ; 
    else if(buf[8]=0,strncpy(buf,tok,8),!strcmp(buf,"gaussian")) 
    { if(strlen(tok)>9&&tok[8]==':') qscale = atof(tok+9) ; else qscale = 1 ; }
    else if(buf[4]=0,strncpy(buf,tok,4),!strcmp(buf,"jury")) 
    { if(tok[4]==':') qsd = atof(tok+5) ; else qsd = 1 ; 
      if(qsd<=0) throw up("%.1e not a legal noise level for jury model") ; 
    }
    else if(buf[3]=0,strncpy(buf,tok,3),!strcmp(buf,"com")) opt = 1 ; 
    else if(!strcmp(buf,"cyc")) opt = 2 ; 
    else if(!strcmp(buf,"bur")) opt = 3 ; 
    else if(!strcmp(buf,"exh")) opt = 4 ; 
    else if(buf[5]=0,strncpy(buf,tok,5),!strcmp(buf,"diag:"))
    { diag = getalg(tok+5) ; 
      if(diag<0||diag>=nalg) throw up("%s - method not present",tok) ;
    }
    else throw up("%s is an unrecognised option",tok) ;
  }
  /* --------------------- set up mji and activity array -------------------- */

  if(qsd>0) for(i=0;i<nmethod;i++) mlist[i].active = 1 ; 
  if(opt) for(i=0;i<nmethod;i++) if(mlist[i].xflag) mlist[i].active = 0 ; 
  for(i=0;i<nalg;i++) active[i] = 1 ; 
  for(resno=k=0;k<2;k++) for(i=0;i<nmethod;i++) if(mlist[i].line(k))
  { if(!strcmp(mlist[i].name,"mj")) mji = resno ; 
    if(mlist[i].active==0) active[resno] = 0 ; 
    resno += 1 ; 
  }
  if(opt&&active[mji]) throw up("can\'t do tactical voting for mj") ; 
  if((offset||qscale)&&qsd>0) throw up("illegal options for jury model") ; 

  /* --------------------------- loop over tests ---------------------------- */

  for(qdist=ndiag=tbal=testno=0;testno<ntests;testno++)
  { tbal += nbal = election(m,n,bal,count,dist,d2,offset,
                   active[mji]?&mj:0,qsd,qscale) ; 
    for(q=t=0;t<m;t++) if(t==0||dist[t]<q) { rightful = t ; q = dist[t] ; }
    qdist += q ; // add mean dist of rightful winner from voters 
    battery(bal,count,nbal,m,res,tie) ;
    for(i=0;i<nalg;i++) if(res[i]<0)
    { mno = -(1+res[i]) ; 
      if(!strcmp(mlist[mno].name,"mj")) res[i] = mj ; 
      else if(!strcmp(mlist[mno].name,"clower")) res[i] = -1 ; 
      else if(!strcmp(mlist[mno].name,"cupper")) res[i] = rightful ; 
    }
    if(opt>0) // if we're doing tactical voting
    { if(diag>=0) resdiag = res[diag] ; 
      // loop over candidate pairs to find most damaging successful subversion
      for(k=-1,c0=0;c0<m;c0++) // supporters of c0 will vote tactically
        for(clim=(opt==4?factorial(m):m),c1=0;c1<clim;c1++) 
          if(opt==4||c0!=c1) 
      { for(i=0;i<nbal;i++) votetactically(bal[i],cbal[i],m,c0,c1,opt) ; 
        battery(cbal,count,nbal,m,cres,0) ;
        for(i=0;i<nalg;i++) if(active[i]&&cres[i]!=res[i]) 
          if(dist[cres[i]]>dist[res[i]]&&d2[c0][cres[i]]<d2[c0][res[i]])
        { res[i] = cres[i] ; if(i==diag) k = c0 | (c1<<6) | (res[i]<<26) ; }
      } // " %s %c\n"
      if(k>=0&&ndiag<100) // print diagnostics if requested
      { printf("%c -> %c: supporters of %c ",
          resdiag+'a',(k>>26)+'a',(k&0x3f)+'a') ; 
        if(opt==4) printf("submit a fixed ballot\n") ; 
        else if(opt==3) printf("demote %c\n",(k>>6)&0xfffff) ;
        else printf("promote %c\n",(k>>6)&0xfff) ;
        for(i=0;i<nbal;i++) 
        { votetactically(bal[i],cbal[i],m,k&0x3f,(k>>6)&0xfffff,opt) ; 
          for(j=0;j<m;j++) printf("%c",bal[i][j]+'a') ; 
          printf(" -> ") ;
          for(j=0;j<m;j++) printf("%c",cbal[i][j]+'a') ; 
          printf(" | %d   votes\n",count[i]) ;
        }
        printf("\n") ; 
        ndiag += 1 ; 
      }
    }

    for(i=0;i<nalg;i++) if(active[i]&&res[i]>=0) 
    { qlos[i] += dist[res[i]] ; if(res[i]==rightful) win[i] += 1 ; }
  }   
  /* ---------------------------- print results ----------------------------- */

  printf("%d tests (%d:%d->%.1f)\n----------\n",
         ntests,m,n,tbal/(double)ntests) ; 
  if(opt==0)
  { printf("number of Condorcet cycles = %d = %.2f%%\n",
           tie[0],tie[0]*100.0/ntests) ; 
    printf("average size of copeland/smith set when there is a Condorcet "
           "cycle = %.2f/%.2f\n",
           tie[4]/(double)tie[0],tie[5]/(double)tie[0]) ; 
    printf("number of copeland/smith/minimax ties =  %d/%d/%d = "
           "%.2f%%/%.2f%%/%.2f%%\n",tie[1],tie[2],tie[3], 
           tie[1]*100.0/ntests,tie[2]*100.0/ntests,tie[3]*100.0/ntests) ; 
    printf("number of minimax winners who are not in the Copeland set = %d\n",
           tie[7]) ; 
  }
  if(diag>=0) for(i=0;i<nalg;i++) if(i!=diag) active[i] = 0 ; 

  for(metric=0;metric<2;metric++) // loop over %age/euclidean loss
  { printf("%s",metric==0?"percentages:\n":"\nmean losses x100:\n") ; 
    if(metric==0) for(k=0;k<nalg;k++) qres[k] = win[k] * 100.0/ntests ; 
    else for(k=0;k<nalg;k++) qres[k] = (qlos[k]-qdist) * 100.0/ntests ; 
    
    for(resno=t=0;t<5;t++)      // loop over the 5 lines of output
    { for(l=resno,i=0;i<nmethod;i++) if((k=mlist[i].line(t)))
      { if(active[l]) break ; if(k==2&&active[l+1]) break ; l += k ; }
      if(i==nmethod) { resno = l ; continue ; } // skip inactive line

      if(t<2) sp = 10 ; 
      else if(t==2) { printf("condorcet+") ; sp = 0 ; }
      else if(t==3) { printf(" copeland+") ; sp = 0 ; }
      else { printf("    smith+") ; sp = 0 ; }

      for(i=0;i<nmethod;i++) if((k=mlist[i].line(t)))
      { if(k==1) sp = mlist[i].print(sp,0) ; 
        else { sp = mlist[i].print(sp,'f') ; sp = mlist[i].print(sp,'r') ; }
      }
      printf("\n          ") ; 
      for(i=0;i<nmethod;i++) if((k=mlist[i].line(t)))
      { if( active[resno]==0
        || (!strcmp(mlist[i].name,"clower")&&(metric>0||opt>0)) ) 
       { printf("   -    ") ; resno += 1 ; }
       else for(j=0;j<k;j++) { printf("%7.4f ",qres[resno]) ; resno += 1 ; }
      }
      printf("\n") ; 
    }
    if(resno!=nalg) throw up("logic error: %d %d",resno,nalg) ; 
  } // end loop over metric (print type)
}
/* -------------------------------------------------------------------------- */

• randomcandidate     • fptp     • dblv     • bucklin     • borda     • nauru     • tworounds     • seq     • condorcet     • minimax     • minisum     • knockout     • btrav     • av     • btr     • benham     • coombs     • nansonbaldwin     • nanson     • baldwin     • approvalsm     • sinkhorn     • schulze     • simplenotifier

#include <math.h>
#include "memory.h"
#include "condorcet.h"

/* --------------------------- positional methods --------------------------- */

int randomcandidate(int m,int **r) { return 0 ; }

int fptp(int m,int **p,int *score) 
{ int i,imax,v,s ; 
  for(i=0;i<m;i++) 
  { s = score[i] = p[i][0] ; if(i==0||s>v) { imax = i ; v = s ; } }
  return imax ; 
}
int dblv(int m,int **p,int *score) 
{ int i,imax,v,s ; 
  for(i=0;i<m;i++) 
  { s = score[i] = p[i][0] + p[i][1] ; if(i==0||s>v) { imax = i ; v = s ; } }
  return imax ; 
}
int bucklin(int m,int **p)
{ int imax,v,i,k,*score=ivector(m),n ; 
  for(n=i=0;i<m;i++) n += p[0][i] ; 
  for(v=k=0;2*v<n;k++)
  { for(i=0;i<m;i++) score[i] += p[i][k] ; 
    for(v=imax=i=0;i<m;i++) if(i==0||score[i]>v) { imax = i ; v = score[i] ; }
  }
  free(score) ; 
  return imax ; 
}
int borda(int m,int **p,int *iscore)
{ int i,j,imax,v ; 
  for(i=0;i<m;i++) for(iscore[i]=j=0;j<m;j++) iscore[i] += ((m-1)-j)*p[i][j] ;
  for(v=imax=i=0;i<m;i++) if(i==0||iscore[i]>v) { imax = i ; v = iscore[i] ; }
  return imax ;   
}
int nauru(int m,int **p)
{ int i,j,imax ; 
  double q,v ; 
  for(i=0;i<m;i++) 
  { for(q=j=0;j<m;j++) q += p[i][j]/(1.0+j) ;
    if(i==0||q>v) { imax = i ; v = q ; } 
  }
  return imax ;   
}
/* -------------------------- other crude methods --------------------------- */

int tworounds(int **bal,int *count,int nbal,int m,int **p)
{ int i,j,c0,c1,amax ; 
  for(i=0;i<m;i++) if(i==0||p[i][0]>amax) { c0 = i ; amax = p[i][0] ; }
  for(c1=-1,i=0;i<m;i++) if(i!=c0&&(c1<0||p[i][0]>amax)) 
  { c1 = i ; amax = p[i][0] ; }
  for(amax=i=0;i<nbal;i++)
  { for(j=0;j<m;j++) 
      if(bal[i][j]==c0) { amax += count[i] ; break ; }
      else if(bal[i][j]==c1) { amax -= count[i] ; break ; }
  }
  return amax>=0?c0:c1 ;
}
int seq(int **bal,int *count,int nbal,int m)
{ int lo,mid,hi,i,j,nlo,nhi ;
  for(lo=0,hi=m;hi>lo+1;)
  { mid = (lo+hi)/2 ; 
    for(nlo=nhi=i=0;i<nbal;i++)
    { for(j=0;j<m&&(bal[i][j]<lo||bal[i][j]>=hi);j++) ; 
      if(bal[i][j]<mid) nlo += count[i] ; else nhi += count[i] ; 
    }
    if(nlo>=nhi) hi = mid ; else lo = mid ; 
  }
  return lo ; 
}
/* ------------------------- simple margin methods -------------------------- */

int condorcet(int m,int **r)
{ int i,j ; 
  for(i=0;i<m;i++) 
  { for(j=0;j<m&&(j==i||r[i][j]>0);j++) ; if(j==m) return i ; }
  return -1 ;
}
int minimax(int m,int **r,int *iscore)
{ int i,j,imax,v,flag ; 
  for(i=0;i<m;i++) for(flag=j=0;j<m;j++) 
    if(i!=j&&(flag==0||r[i][j]<iscore[i])) { iscore[i] = r[i][j] ; flag = 1 ; }
  for(v=imax=i=0;i<m;i++) if(i==0||iscore[i]>v) { imax = i ; v = iscore[i] ; }
  return imax ;  
}
int minisum(int m,int **r)
{ int i,j,imax,v,*iscore=ivector(m) ; 
  for(i=0;i<m;i++) for(iscore[i]=0,j=0;j<m;j++) 
    if(i!=j&&r[i][j]<0) iscore[i] += r[i][j] ; 
  for(v=imax=i=0;i<m;i++) if(i==0||iscore[i]>v) { imax = i ; v = iscore[i] ; }
  free(iscore) ; 
  return imax ;
}
int knockout(int m,int **r)
{ int i,winner ; 
  for(winner=0,i=1;i<m;i++) if(r[i][winner]>0) winner = i ; 
  return winner ;
}
/* --------------------------------- btr/av --------------------------------- */

int btrav(int **bal,int *count,int nbal,int m,int **r,int *avscr,int opt)
{ int t,tau,balno,winner,loser,lose2,mleft,**b=imatrix(nbal,m),i,j ;
  int v,*iscore=ivector(m) ; 
  for(balno=0;balno<nbal;balno++) for(t=0;t<m;t++) b[balno][t] = bal[balno][t] ;
  for(mleft=m;mleft>1;mleft--) // mleft is the number of remaining candidates
  { if(opt==2)                 // benham
    { for(i=0;i<mleft;i++)     // is b[0][i] a condorcet winner among remainers?
      { for(t=j=0;j<mleft;j++) if(j!=i&&r[b[0][i]][b[0][j]]>0) t += 1 ; 
        if(t==mleft-1) break ; // if this is satisfied then b[0][i] is winner 
      }
      if(i<mleft) { b[0][0] = b[0][i] ; break ; }
    }
    for(balno=0;balno<m;balno++) iscore[balno] = 0 ; 
    for(balno=0;balno<nbal;balno++) iscore[b[balno][0]] += count[balno] ;
    for(v=loser=t=0;t<mleft;t++) if(t==0||iscore[b[0][t]]<v) 
    { loser = b[0][t] ; v = iscore[loser] ; }
    if(opt==1)
    { for(v=lose2=-1,t=0;t<mleft;t++) if(b[0][t]!=loser) 
        if(v<0||iscore[b[0][t]]<v) { lose2 = b[0][t] ; v = iscore[lose2] ; }
      if(r[loser][lose2]>0) loser = lose2 ; 
    }
    if(avscr) avscr[loser] = m-mleft ; 
    for(balno=0;balno<nbal;balno++) for(tau=t=0;t<mleft;t++) 
      if(b[balno][t]!=loser) b[balno][tau++] = b[balno][t] ;
  }
  winner = b[0][0] ;
  if(avscr) avscr[winner] = m-1 ; 
  free(iscore) ; 
  freeimatrix(b) ; 
  return winner ;
}
int av(int **bal,int *count,int nbal,int m,int *avscr) 
{ return btrav(bal,count,nbal,m,0,avscr,0) ; }
int btr(int **bal,int *count,int nbal,int m,int **r) 
{ return btrav(bal,count,nbal,m,r,0,1) ; }
int benham(int **bal,int *count,int nbal,int m,int **r) 
{ return btrav(bal,count,nbal,m,r,0,2) ; }

/* --------------------------------- coombs --------------------------------- */

int coombs(int **bal,int *count,int nbal,int m)
{ int i,v,tau,n,balno,winner,loser,mleft,**b=imatrix(nbal,m),*score=ivector(m) ;
  for(n=balno=0;balno<nbal;balno++) 
  { for(i=0;i<m;i++) b[balno][i] = bal[balno][i] ; n += count[balno] ; }

  for(mleft=m;mleft>0;mleft--) // mleft is the number of remaining candidates
  { for(balno=0;balno<m;balno++) score[balno] = 0 ; 
    for(balno=0;balno<nbal;balno++) score[b[balno][0]] += count[balno] ;
    for(v=winner=i=0;i<mleft;i++) if(i==0||score[b[0][i]]>v) 
    { winner = b[0][i] ; v = score[winner] ; }
    if(2*v>n) break ; 
    for(balno=0;balno<m;balno++) score[balno] = 0 ; 
    for(balno=0;balno<nbal;balno++) score[b[balno][mleft-1]] += count[balno] ;
    for(v=loser=i=0;i<mleft;i++) if(i==0||score[b[0][i]]>v) 
    { loser = b[0][i] ; v = score[loser] ; }
    for(balno=0;balno<nbal;balno++) for(tau=i=0;i<mleft;i++) 
      if(b[balno][i]!=loser) b[balno][tau++] = b[balno][i] ;
    winner = b[0][0] ;
  }
  free(score) ; freeimatrix(b) ; 
  return winner ;
}
/* --------------------------------- nansen --------------------------------- */

int nansonbaldwin(int **bal,int *count,int nbal,int m,int *bordascore,int flag)
{ int i,v,k,balno,mleft,**b=imatrix(nbal,m),*score=ivector(m) ;
  int *ind=ivector(m),*set=ivector(m),nset,**pmat ;
  for(i=0;i<m;i++) { score[i] = bordascore[i] ; set[i] = i ; }

  for(mleft=m;;mleft=nset) // mleft is the number of remaining candidates in set
  { if(flag) // baldwin
    { for(v=i=0;i<mleft;i++) if(i==0||score[i]<v) { k = i ; v = score[i] ; }
      for(nset=i=0;i<mleft;i++) if(i!=k) ind[nset++]= set[i] ; 
    }
    else // nanson
    { for(v=i=0;i<mleft;i++) v += score[i] ;
      for(nset=i=0;i<mleft;i++) if(score[i]*mleft>v) ind[nset++] = set[i] ;
      if(nset==0) { ind[0] = set[0] ; nset = 1 ; } // all borda scores equal
    }
    for(i=0;i<nset;i++) set[i] = ind[i] ; 
    if(nset==mleft||nset==1) { k = set[0] ; break ; }
    for(i=0;i<m;i++) ind[i] = -1 ; // ind gives the indices of candidates in set
    for(k=i=0;i<nset;i++) ind[set[i]] = k++ ; 
    for(balno=0;balno<nbal;balno++) for(k=i=0;i<m;i++) // squeeze out defeated..
    { v = ind[bal[balno][i]] ; if(v>=0) b[balno][k++] = v ; } // ... candidates
    pmat = genposcounts(b,count,nbal,nset) ; 
    borda(nset,pmat,score) ; 
    freeimatrix(pmat) ; 
  }
  free(score,set,ind) ; freeimatrix(b) ; 
  return k ;
}
int nanson(int **bal,int *count,int nbal,int m,int *bordascore)
{ return nansonbaldwin(bal,count,nbal,m,bordascore,0) ; }
int baldwin(int **bal,int *count,int nbal,int m,int *bordascore)
{ return nansonbaldwin(bal,count,nbal,m,bordascore,1) ; }

/* ----------------------------------- asm ---------------------------------- */

int approvalsm(int **bal,int *count,int nbal,int m,int **A)
{ int i,j,iter,balno,v,*b,imax,D,*T=ivector(m),*r=ivector(m) ;
  xi *pref=xivector(m) ;  
  for(balno=0;balno<nbal;balno++) 
    for(b=bal[balno],v=count[balno],i=0;i<m/2;i++) T[b[i]] += v ; 
  for(i=0;i<m;i++) pref[i] = xi(T[i],i) ; 
  xisortdown(pref,m) ; 
  for(i=0;i<m;i++) r[i] = pref[i].i ;
  for(iter=0;;iter++)
  { for(v=imax=-1,i=0;i<m-1;i++) if(A[r[i]][r[i+1]]<0)
    { D = T[r[i]] - T[r[i+1]] ; if(imax<0||D<v) { imax = i ; v = D ; } }
    if(imax>=0) swap(r[imax],r[imax+1]) ; else break ; 
  }
  imax = r[0] ; 
  free(T,r,pref) ; 
  return imax ; 
}
/* --------------------------------- sinkhorn ------------------------------- */

// this depends on the margins plus the total number of voters

int sinkhorn(int **bal,int *count,int nbal,int m,int **margin)
{ int i,j,iter,i0,i1,nv ;
  double q,rho,orho,**u=matrix(m,m),*r=vector(m),*c=vector(m),*s=vector(m) ; 

  for(nv=i=0;i<nbal;i++) nv += count[i] ; 
  for(i=0;i<m;i++) for(j=0;j<m;j++) u[i][j] = (margin[i][j]+nv)/2.0 + 1 ; 
  for(i=0;i<m;i++) r[i] = c[i] = 1 ; 

  for(iter=0;iter<10||fabs((rho/orho)-1)>fabs(rho-1)*1e-6;orho=rho,iter++) 
  { // balance the rows
    for(i=0;i<m;i++) { for(s[i]=j=0;j<m;j++) s[i] += u[i][j] ; s[i] = 1/s[i] ; }
    for(i=0;i<m;i++) { r[i] *= s[i] ; for(j=0;j<m;j++) u[i][j] *= s[i] ; }
    // balance the cols
    for(j=0;j<m;j++) { for(s[j]=i=0;i<m;i++) s[j] += u[i][j] ; s[j] = 1/s[j] ; }
    for(j=0;j<m;j++) { c[j] *= s[j] ; for(i=0;i<m;i++) u[i][j] *= s[j] ; }
    // compute the scores and find the best two candidates
    for(i1=i0=-1,i=0;i<m;i++) 
    { s[i] = c[i] / r[i] ;
      if(i0<0||s[i]>s[i0]) { i1 = i0 ; i0 = i ; }
      else if(i1<0||s[i]>s[i1]) i1 = i ; 
    }
    rho = s[i0]/s[i1] ; // will terminate when rho is barely moving
  }

  freematrix(u) ; free(r,c,s) ; 
  return i0 ; 
}
/* --------------------------------- schulze -------------------------------- */

/* Based on Warren D. Smith's code at https://rangevoting.org/IEVS/IEVS.c
   m = number of candidates, margin = matrix of victory margins
   winner = X st. beatpath strength over rivals Y exceeds strength from Y 
*/
int schulze(int m,int **margin)
{ int i,j,k,**strength=imatrix(m,m) ;
  for(i=0;i<m;i++) for(j=0;j<m;j++) strength[i][j] = margin[i][j] ;
  for(i=0;i<m;i++) for(j=0;j<m;j++) if(i!=j) for(k=0;k<m;k++) if(k!=i&&k!=j)
    strength[j][k] = max(strength[j][k],min(strength[j][i],strength[i][k])) ;

  // if there's no (j,i) stronger than (i,j) then i is the winner
  for(i=0;i<m;i++) { for(j=0;j<m&&strength[i][j]>=0;j++) ; if(j==m) break ; }
  if(i==m) throw up("logic error in schulze: no winner found") ; 
  freeimatrix(strength) ; 
  return i ;
}
/* ------------------------------ simplenotifier ---------------------------- */

int rankedpairs(int **bal,int *count,int nbal,int m,int **margin) ;
int river(int m,int **r) ;
int tideman(int **bal,int *count,int nbal,int m,int **rmat,int *set,int nset) ;

int simplenotifier()
{ notify(randomcandidate,"random","rCp") ; 
  notify(fptp,"fptp","frCp") ; 
  notify(dblv,"dblv","fCp") ; 
  notify(seq,"seq","x") ; 
  notify(tworounds,"2rounds","p") ; 
  notify(nauru,"nauru","p") ; 
  notify(bucklin,"bucklin","p") ; 
  notify(borda,"borda","Cfrp") ; 
  notify(sinkhorn,"sinkhorn","o") ; 
  notify((void *)0,"mj","ox",-1) ;
  notify(av,"av","oCrf") ; 
  notify(coombs,"coombs","o") ; 

  notify((void *)0,"clower","cx",-1) ;
  notify(knockout,"knockout","c") ; 
  notify(benham,"benham","c") ; 
  notify(btr,"btr","c") ; 
  notify(baldwin,"baldwin","cb") ; 
  notify(nanson,"nanson","cb") ; 
  notify(minimax,"minimax","cfr") ;
  notify(minisum,"minisum","c") ;
  notify(rankedpairs,"rp","c") ; 
  notify(river,"river","c") ;   
  notify(schulze,"schulze","c") ; 
  notify(approvalsm,"asm","c") ; 
  notify((void *)0,"cupper","cx",-1) ;
  notify(tideman,"tideman","c") ; 
  return 0 ; 
}
/* -------------------------------------------------------------------------- */

• tideman     • setdom     • rprec     • rankedpairs     • river

#include "memory.h"
#include "condorcet.h"

/* --------------------------- tideman's alternative ------------------------ */

int tideman(int **bal,int *count,int nbal,int m,int **rmat,int *set,int nset)
{ if(nset==1) return set[0] ; 
  int i,j,balno,ns=nset,imin ;
  int *s=ivector(nset),*score=ivector(m),*map=ivector(m),**r ;
  if(nset>2) r = imatrix(nset,nset) ;
  for(i=0;i<ns;i++) s[i] = set[i] ; 

  while(ns>1) 
  { for(i=0;i<m;i++) score[i] = map[i] = 0 ; 
    for(i=0;i<ns;i++) map[s[i]] = 1 ; 
    for(balno=0;balno<nbal;balno++)
    { for(j=0;j<ns&&map[bal[balno][j]]==0;j++) ; score[bal[balno][j]] += 1 ; }
    for(i=0;i<ns;i++) if(i==0||score[s[i]]<score[s[imin]]) imin = i ; 
    for(j=i=0;i<ns;i++) if(i!=imin) s[j++] = s[i] ; 
    ns -= 1 ; 
    if(ns==1) break ; 
    // now we have to recompute the smith set - first compute the margins
    for(i=0;i<ns;i++) for(score[i]=j=0;j<ns;j++) 
    { r[i][j] = rmat[s[i]][s[j]] ; if(r[i][j]>0) score[i] += 1 ; }
    ns = smithset(ns,r,score,map) ; // map gets the smith set of the reduced fld
    for(i=0;i<ns;i++) score[i] = s[map[i]] ; // find the elts of the smith set
    for(i=0;i<ns;i++) s[i] = score[i] ;      // and put them in s
    isortup(s,ns) ;                          // keep them in random order
  }
  i = s[0] ;
  if(nset>2) freeimatrix(r) ;
  free(s,score,map) ;
  return i ; 
}
/* -------------------------------- ranked pairs ---------------------------- */

#define setdom(a,b,c) { a[b][c] = 1 ; a[c][b] = -1 ; }

int rprec(xi *maj,int m,int npair,int level,int fixed,int **idom)
{ int i,j,k,hi,lo,mi,mx,n,*set,*ind,res,**dom=imatrix(m,m) ; 
  if(idom) for(i=0;i<m;i++) for(j=0;j<m;j++) dom[i][j] = idom[i][j] ; 
  for(k=level;k<npair;k++)   
  { mx = maj[k].x ; 
    mi = maj[k].i ;
    if(k<fixed||k==npair-1||maj[k+1].x<mx) // easy case  
    { hi = mi >> 8 ; 
      lo = mi & 0xff ; 
      if(dom[hi][lo]==0) 
      { setdom(dom,hi,lo) ; 
        for(i=0;i<m;i++) 
        { if(dom[i][hi]>0) setdom(dom,i,lo) ; 
          if(dom[lo][i]>0) setdom(dom,hi,i) ; 
        }
      }
    }
    else // several equal majorities - need to recurse over possible orders
    { set = ivector(npair-k) ;
      ind = ivector(npair-k) ;
      for(set[0]=mi,n=1;k+n<npair&&maj[k+n].x==mx;n++) set[n] = maj[k+n].i ; 
      if(n>12) throw up("too many tied majorities (%d) in rankedpairs",n) ;
      for(res=0,i=factorial(n)-1;i>=0;i--)
      { decompress(i,ind,n) ; 
        for(j=0;j<n;j++) maj[k+j].i = set[ind[j]] ; 
        res |= rprec(maj,m,npair,k,k+n,dom) ; 
      }
      free(ind,set) ;
      break ;
    }
  }
  if(k==npair) for(res=i=0;i<m;i++) // reached a leaf - find possible winners
  { for(j=0;j<m&&dom[j][i]<=0;j++) ; if(j==m) res |= 1<<i ; }
  freeimatrix(dom) ; 
  return res ; 
}
int rankedpairs(int **bal,int *count,int nbal,int m,int **margin)
{ int i,j,k,npair,res ;
  xi *maj = xivector((m*(m-1))/2) ; 
  for(npair=i=0;i<m-1;i++) for (j=i+1;j<m;j++)
    if(margin[i][j]>0) maj[npair++] = xi(margin[i][j],(i<<8)|j) ; 
    else if(margin[i][j]<0) maj[npair++] = xi(-margin[i][j],(j<<8)|i) ; 
  xisortdown(maj,npair) ; 
  res = rprec(maj,m,npair,0,0,0) ;
  free(maj) ; 
  for(k=-1,i=0;k<0&&i<m;i++) { j = bal[0][i] ; if(res&(1<<j)) k = j ; }
  return k ; 
}
/* ----------------------------------- river -------------------------------- */

int river(int m,int **r)
{ int i,j,k,npair,res,**dom=imatrix(m,m),hi,lo,mi,iter ;
  xi *maj = xivector((m*(m-1))/2) ; 
  for(npair=i=0;i<m;i++) 
  { for(k=npair,j=0;j<m;j++) 
      if(r[i][j]<0) maj[npair++] = xi(-r[i][j],(j<<8)|i) ; 
    if(npair>k) { xisortdown(maj+k,npair-k) ; npair = min(npair,k+2) ; }
  }
  xisortdown(maj,npair) ; 

  for(i=0;i<npair;i++)   
  { mi = maj[i].i ;
    lo = mi >> 8 ; 
    hi = mi & 0xff ; 
    if(dom[hi][lo]==0) 
    { setdom(dom,hi,lo) ; 
      for(j=0;j<m;j++) 
      { if(dom[j][hi]>0) setdom(dom,j,lo) ; 
        if(dom[lo][j]>0) setdom(dom,hi,j) ; 
      }
    }
  }
  for(k=-1,i=0;k<0&&i<m;i++) for(j=0;k<0&&j<m;j++) if(dom[i][j]>0) k = j ; 
  for(iter=i=0;i>=0&&iter<=m;iter++) 
  { for(i=-1,j=0;i<0&&j<m;j++) if(dom[k][j]>0) i = k = j ; }
  if(iter==m) throw up("infinite loop in river") ; 
  free(maj) ; freeimatrix(dom) ; 
  return k ; 
}

Header file for voting methods.

• factorial     • compress     • decompress

int notify(void *func,char *n,char *t,int a) ;
int notify(int (*f)(int **,int *,int,int),char *name,char *opts) ;
int notify(int (*f)(int **,int *,int,int,int **),char *name,char *opts) ;
int notify(int (*f)(int **,int *,int,int,int *),char *name,char *opts) ;
int notify(int (*f)(int **,int *,int,int,int **,int *),char *name,char *opts) ;
int notify(int (*f)(int **,int *,int,int,int **,int *,int),char *n,char *o) ;
int notify(int (*f)(int,int **),char *name,char *opts) ; // 11
int notify(int (*f)(int,int **,int *),char *name,char *opts) ; // 13

int smithset(int m,int **r,int *llullscore,int *set) ;
int **genposcounts(int **bal,int *count,int nbal,int m) ;
int **genmargins(int **bal,int *count,int nbal,int m) ;

// note the general restriction that the number of candidates must be small 
// enough for its factorial to be stored in an int
static int factorial(int m) 
{ int i,t ; for(t=i=1;i<=m;i++) t *= i ; return t ; }

// compress maps a ballot onto an integer from 0 to m!-1
static int compress(int *x,int m) 
{ int i,j,t,buf[50] ; 
  for(i=0;i<m;i++) { buf[i] = x[i] ; buf[m+i] = i ; }
  for(i=1;i<m;i++) 
  { for(j=x[i-1]+1;j<m;j++) buf[m+j] -= 1 ; buf[i] = buf[m+x[i]] ; }
  for(t=buf[0],i=1;i<m-1;i++) t = (m-i)*t + buf[i] ;
  return t ; 
}
#ifndef  _STDLIB_H
#include <stdlib.h>
#endif
static void decompress(int r,int *x,int m) // inverse of compress
{ int i,j,k,buf[25] ;
  div_t res ; 
  buf[0] = x[m-1] = 0 ;
  for(i=1;i<m;i++) 
  { res = div(r,i+1) ; r = res.quot ; x[m-i-1] = res.rem ; buf[i] = i ; }
  for(i=0;i<m;i++) 
  { k = buf[x[i]] ; for(j=x[i];j<m-i-1;j++) buf[j] = buf[j+1] ; x[i] = k ; }
}

This is a reimplementation of the Numerical Recipes random number generator.

• step     • ranf     • ranset     • gaussv     • rani

#include <math.h>

#define IA 16807
#define IM 2147483647
#define IQ 127773
#define IR 2836
#define NDIV (1+(IM-1)/32)

static long tabx=0,tab[32],state=123467 ; 

static long step()
{ long k = state / IQ ; 
  state = IA * (state-k*IQ) - IR*k ;
  return state<0?state+IM:state ; 
} 
double ranf()
{ int i ; 
  if(tabx==0) { for(i=63;i>=0;i--) tab[i&31] = step() ; tabx = tab[0] ; }
  i = tabx / NDIV ; 
  tabx = tab[i] ; 
  tab[i] = step() ; 
  return tabx / (double) IM; 
} 
void ranset(int seed) 
{ if(seed>0) state = 2*seed ; else state = 1 - 2*seed ; 
  if(state>=IM) state = 1 + state%(IM-1) ; 
  tabx = 0 ; 
}
double gaussv()
{ static int toggle = 1 ; 
  static double u1,u2,pi=3.141592653589793 ; 

  if((toggle=1-toggle)) return u1 * sin(u2) ; 
  for(u1=0;u1==0;u1=ranf()) ; 
  u1 = sqrt(-2*log(u1)) ; 
  u2 = 2*pi*ranf() ; 
  return u1 * cos(u2) ; 
}
int rani(int n) { return (int)(n*ranf()) ; }

This is my standard header file; you don’t need to look at it (and much of it is unused in my evaluation). Vector and matrix allocators zeroise the memory they allocate. A xi and an xy are a (double,int) and a (double,double) ordered pair respectively.

• max     • min     • cjcup     • cjcuplog     • cjcformat     • cjcprint2     • cjcprint1     • complex     • print     • xy     • print     • xi     • settable     • unset     • double     • print     • free     • cjcupalloc     • cjcuprealloc     • swap     • freename     • charvector     • xivector     • isortup     • realsort     • xysort     • xisort     • xisortdown     • fupopenread     • fupopenwrite     • freadline     • readline

#ifndef MEMORY_H
#define MEMORY_H

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>

static double max(double a,double b) { if(a>b) return a ; else return b ; }
static double min(double a,double b) { if(a<b) return a ; else return b ; }
static double max(double a,int b) { if(a>b) return a ; else return b ; }
static double min(double a,int b) { if(a<b) return a ; else return b ; }
static double max(int a,double b) { if(a>b) return a ; else return b ; }
static double min(int a,double b) { if(a<b) return a ; else return b ; }
static int max(int a,int b) { if(a>b) return a ; else return b ; }
static int min(int a,int b) { if(a<b) return a ; else return b ; }
#define abnormal(x) (!!((x)-(x))) // x-x forced to boolean

/* ---------------------------- define throwing up -------------------------- */

static int cjcupline=-1,cjcperror=0 ;
static const char *cjcupfile="",*cjcupfunc="" ;

static int cjcup(const char *m,...) 
{ va_list vl ; 
  fprintf(stderr,"*** Error at line %d of %s [function %s]:\n",
                 cjcupline,cjcupfile,cjcupfunc) ;
  if(cjcperror) perror(0) ; 
  va_start(vl,m) ; 
  vfprintf(stderr,m,vl) ; 
  va_end(vl) ; 
  fprintf(stderr,"\n") ; 
  fflush(0) ; 
  return 0 ; 
} ;
static void cjcuplog(const char *f,int l,const char *ff) 
{ cjcupfile = f ; cjcupline = l ; cjcupfunc = ff ; } 

#define up (cjcuplog(__FILE__,__LINE__,__PRETTY_FUNCTION__),cjcup)

/* -------------------------- simple ordered pairs -------------------------- */

static char cjcbuf[600]={0} ;
static int cjcind = 40 , cjcint = 0 ; 
static void cjcformat(char *fmt)
{ int i ; 
  if(strlen(fmt)>18) throw up("overlong cjcprint format %s") ;
  strcpy(cjcbuf,fmt) ; 
  for(i=0;fmt[i]&&fmt[i]!='%';i++) ;
  for(;fmt[i]&&(fmt[i]=='l'||(fmt[i]<'a'||fmt[i]>'z'));i++) ;
  cjcint = (fmt[i]=='d') ;
}
static char *cjcprint2(double x,double y)
{ if(cjcbuf[0]==0) cjcformat("%.1f") ; 
  char *ptr = cjcbuf + cjcind ; 
  cjcbuf[cjcind] = '(' ;
  if(cjcint) cjcind += 2 + sprintf(cjcbuf+cjcind+1,cjcbuf,(int)x) ; 
  else cjcind += 2 + sprintf(cjcbuf+cjcind+1,cjcbuf,x) ; 
  cjcbuf[cjcind-1] = ',' ;
  if(cjcint) cjcind += 2 + sprintf(cjcbuf+cjcind,cjcbuf,(int)y) ; 
  else cjcind += 2 + sprintf(cjcbuf+cjcind,cjcbuf,y) ; 
  cjcbuf[cjcind-2] = ')' ;
  cjcbuf[cjcind-1] = 0 ;
  if(cjcind>600) throw up("data overflow on printing an ordered pair") ; 
  if(cjcind>500) cjcind = 40 ;
  return ptr ; 
}
static char *cjcprint2(char *fmt,double x,double y)
{ cjcformat(fmt) ; return cjcprint2(x,y) ; }

static char *cjcprint1(double x)
{ if(cjcbuf[0]==0) cjcformat("%.1f") ; 
  char *ptr = cjcbuf + cjcind ; 
  if(cjcint) cjcind += 1 + sprintf(cjcbuf+cjcind,cjcbuf,(int)x) ; 
  else cjcind += 1 + sprintf(cjcbuf+cjcind,cjcbuf,x) ; 
  if(cjcind>600) throw up("data overflow on printing") ; 
  if(cjcind>500) cjcind = 40 ;
  return ptr ; 
}
static char *cjcprint1(char *fmt,double x)
{ cjcformat(fmt) ; return cjcprint1(x) ; }

struct complex
{ double re,im ; 
  complex() { re = im = 0 ; } 
  complex(double x) { re = x ; im = 0 ; } 
  complex(double x,double y) { re = x ; im = y ; } 
  complex &operator=(double x) { re = x ; im = 0 ; return *this ; }
  char *print(char *fmt) { return cjcprint2(fmt,re,im) ; }
  char *print() { return cjcprint2(re,im) ; }
} ;
struct xy 
{ double x,y ; 
  xy() { x = y = 0 ; } 
  xy(double xx) { x = xx ; y = 0 ; } 
  xy(double xx,double yy) { x = xx ; y = yy ; } 
  xy(double xx,double(*f)(double)) { x = xx ; y = f(x) ; } 
  xy &operator=(double xx) { x = xx ; y = 0 ; return *this ; }
  char *print(char *fmt) { return cjcprint2(fmt,x,y) ; }
  char *print() { return cjcprint2(x,y) ; }
} ;
inline bool operator==(xy a,xy b) { return a.x==b.x&&a.y==b.y ; } 
struct xi 
{ double x ; int i ; 
  xi() { x = i = 0 ; } 
  xi(double a,int b) { x = a ; i = b ; } 
} ;
/* --------------------------------- settables ------------------------------ */

struct settable
{ private: double x ;
  public:
    bool set ; 
    settable() { set = 0 ; }
    settable(double y) 
    { if(abnormal(y)) throw up("setting a settable to %.1e",y) ; 
      set = 1 ; 
      x = y ; 
    }
    settable unset() { return this[0] = settable() ; }
    operator double() 
    { if(!set) throw up("accessing an unset settable") ; return x ; }
    settable &operator=(double y) 
    { if(abnormal(y)) throw up("assigning %.1e to a settable",y) ;
      set = 1 ; 
      x = y ; 
      return *this ; 
    }
    char *print() 
    { if(set) return cjcprint1(x) ;
      char *ptr=cjcbuf+cjcind ;
      strcpy(ptr,"undef") ; 
      cjcind += 6 ; 
      if(cjcind>500) cjcind = 40 ; 
      return ptr ; 
    }
    char *print(char *fmt) { cjcformat(fmt) ; return print() ; }
} ;
inline bool operator==(settable x,settable y) 
{ return (x.set==0&&y.set==0)||((double)x)==(double(y)) ; } 
inline bool operator==(settable x,double y) 
{ return x.set && y==(double)x ; } 
inline bool operator==(double x,settable y) { return (y==x) ; }
inline bool operator!=(settable x,settable y) { return !(x==y) ; } 

inline settable operator+=(settable &x,double y) 
{ if(!x.set) throw up("incrementing an unset settable") ; 
  return x = settable(x+y) ; 
}
inline settable operator-=(settable &x,double y) 
{ if(!x.set) throw up("decrementing an unset settable") ; 
  return x = settable(x-y) ; 
}
inline settable operator*=(settable &x,double y) 
{ if(y==0) return x = settable(0) ; 
  if(!x.set) throw up("*= applied to an unset settable") ; 
  return x = settable(x*y) ; 
}
inline settable operator/=(settable &x,double y) 
{ if(y==0) throw up("settable divided by 0") ; 
  if(!x.set) throw up("/= applied to an unset settable") ; 
  return x = settable(x/y) ; 
}

inline settable max(settable a,settable b) 
{ if(a.set&&(!b.set||a>b)) return a ; else return b ; }
inline settable min(settable a,settable b) 
{ if(a.set&&(!b.set||a<b)) return a ; else return b ; }

inline settable max(settable a,double b) 
{ if(a.set&&a>b) return a ; else return b ; }
inline settable min(settable a,double b) 
{ if(a.set&&a<b) return a ; else return b ; }
inline settable max(double a,settable b) 
{ if(b.set&&b>a) return b ; else return a ; }
inline settable min(double a,settable b) 
{ if(b.set&&b<a) return b ; else return a ; }

inline settable max(settable a,int b) 
{ if(a.set&&a>b) return a ; else return b ; }
inline settable min(settable a,int b) 
{ if(a.set&&a<b) return a ; else return b ; }
inline settable max(int a,settable b) 
{ if(b.set&&b>a) return b ; else return a ; }
inline settable min(int a,settable b) 
{ if(b.set&&b<a) return b ; else return a ; }

/* ------------------------------ variadic free() --------------------------- */

static void free(void *a,void *b) { free(a) ; free(b) ; } 
static void free(void *a,void *b,void *c) 
{ free(a) ; free(b) ; free(c) ; } 
static void free(void *a,void *b,void *c,void *d) 
{ free(a) ; free(b) ; free(c) ; free(d) ; } 
static void free(void *a,void *b,void *c,void *d,void *e) 
{ free(a) ; free(b) ; free(c) ; free(d) ; free(e) ; } 
static void free(void *a,void *b,void *c,void *d,void *e,void *f) 
{ free(a) ; free(b) ; free(c) ; free(d) ; free(e) ; free(f) ; } 
static void free(void *a,void *b,void *c,void *d,void *e,void *f,void *g) 
{ free(a) ; free(b) ; free(c) ; free(d) ; free(e) ; free(f) ; free(g) ; } 
static void free(void *a,void *b,void *c,void *d,
                 void *e,void *f,void *g,void *h) 
{ free(a) ; free(b) ; free(c) ; free(d) ; 
  free(e) ; free(f) ; free(g) ; free(h) ; 
} 
/* ------------------------- robust allocs ---------------------------- */

static void *cjcupalloc(int a,int b)
{ if(a<0||b<0) throw cjcup("negative length %d requested from cjcalloc.",a*b) ; 
  void *p=calloc(a,b) ; 
  if(p==0) throw cjcup("cjcalloc unable to allocate %d bytes of memory.",b) ; 
  memset(p,0,a*b) ; 
  return p ; 
} 
static void *cjcuprealloc(void *a,int b)
{ if(b<0) throw cjcup("negative length %d requested from cjcrealloc.",b) ; 
  if(a==0&&b==0) return 0 ; 
  void *p=realloc(a,b) ; 
  if(b>0&&p==0) 
    throw cjcup("cjcrealloc unable to reallocate %x to %d bytes.",a,b) ;
  return p ; 
} 
#define cjcalloc (cjcuplog(__FILE__,__LINE__,__PRETTY_FUNCTION__),cjcupalloc)
#define cjcrealloc (cjcuplog(__FILE__,__LINE__,__PRETTY_FUNCTION__),cjcuprealloc)

/* ---------------------------- generic matrix ------------------------------ */

#define genvector(type,vecname)                         \
static type *vecname(int n)                             \
{ return (type*) cjcalloc(n,sizeof(type)) ; }           \
static type *vecname(type *x,int n)                     \
{ return (type *) cjcrealloc(x,n*sizeof(type)) ; }      \
static void swap(type &a,type &b) { type c=b ; b = a ; a = c ; }

#define genmatrix(type,vecname,name,freename)           \
static type *vecname(int n)                             \
{ return (type*) cjcalloc(n,sizeof(type)) ; }           \
static type *vecname(type *x,int n)                     \
{ return (type *) cjcrealloc(x,n*sizeof(type)) ; }      \
static type **name(int m,int n)                         \
{ type **a = (type **) cjcalloc(m,sizeof(type *)) ;     \
  a[0] = vecname(m*n) ;                                 \
  for(int i=1;i<m;i++) a[i] = a[i-1] + n ;              \
  return a ;                                            \
}                                                       \
static type ***name(int m,int n,int l)                  \
{ int i ;                                               \
  type ***a = (type ***) cjcalloc(m,sizeof(type **)) ;  \
  a[0] = (type **) cjcalloc(m*n,sizeof(type *)) ;       \
  for(i=1;i<m;i++) a[i] = a[i-1] + n ;                  \
  a[0][0] = vecname(m*n*l) ;                            \
  for(i=1;i<m*n;i++) a[0][i] = a[0][i-1] + l ;          \
  return a ;                                            \
}                                                       \
static void freename(type **a) { if(a) free(a[0],a) ; } \
static void freename(type **a,type **b)                 \
{ freename(a) ; freename(b) ; }                         \
static void freename(type **a,type **b,type **c)        \
{ freename(a) ; freename(b) ; freename(c) ; }           \
static void freename(type **a,type **b,type **c,type **d)   \
{ freename(a) ; freename(b) ; freename(c) ; freename(d) ; } \
static void freename(type **a,type **b,type **c,type **d,   \
                     type **e)                              \
{ freename(a) ; freename(b) ; freename(c) ; freename(d) ;   \
  freename(e) ; }                                           \
static void freename(type **a,type **b,type **c,type **d,   \
                     type **e,type **f)                     \
{ freename(a) ; freename(b) ; freename(c) ; freename(d) ;   \
  freename(e) ; freename(f) ; }                             \
static void freename(type ***a) { if(a) free(a[0][0],a[0],a) ; } \
static void swap(type &a,type &b) { type c=b ; b = a ; a = c ; } 

/* --------------------------- matrix instances ----------------------------- */

genmatrix(double,vector,matrix,freematrix) ; 
genmatrix(int,ivector,imatrix,freeimatrix) ; 
genmatrix(xi,xivector,ximatrix,freeximatrix) ; 
genmatrix(xy,xyvector,xymatrix,freexymatrix) ; 
genmatrix(char,charvector,charmatrix,freecharmatrix) ; 
genmatrix(char*,strvector,strmatrix,freestrmatrix) ; 
genmatrix(short,shortvector,shortmatrix,freeshortmatrix) ; 
genmatrix(complex,cvector,cmatrix,freecmatrix) ; 
genmatrix(settable,setvector,setmatrix,freesetmatrix) ; 

// a couple of specials
static char *charvector(char *c) 
{ char *ret=charvector(1+strlen(c)) ; strcpy(ret,c) ; return ret ; } 
static xi *xivector(double *x,int n)
{ xi *y=xivector(n) ; 
  for(int i=0;i<n;i++) y[i] = xi(x[i],i) ; 
  return y ; 
}
/* ----------------------------- generic sorts ------------------------------ */

#define shellsortup(x,n,type,field)                                    \
{ int i,j,inc ; type y ;                                               \
  for(inc=1;1+3*inc<(n);inc=1+3*inc) ;                                 \
  for(;inc>0;inc/=3) for(i=inc;i<(n);i++)                              \
  { for(y=x[i],j=i;j>=inc;j-=inc)                                      \
    { if(y.field<x[j-inc].field) x[j] = x[j-inc] ; else break ; }      \
    x[j] = y ;                                                         \
  }                                                                    \
}
#define shellsortdown(x,n,type,field)                                  \
{ int i,j,inc ; type y ;                                               \
  for(inc=1;1+3*inc<(n);inc=1+3*inc) ;                                 \
  for(;inc>0;inc/=3) for(i=inc;i<(n);i++)                              \
  { for(y=x[i],j=i;j>=inc;j-=inc)                                      \
    { if(y.field>x[j-inc].field) x[j] = x[j-inc] ; else break ; }      \
    x[j] = y ;                                                         \
  }                                                                    \
}
#define shsortup(x,n,type)                                             \
{ int i,j,inc ; type y ;                                               \
  for(inc=1;1+3*inc<(n);inc=1+3*inc) ;                                 \
  for(;inc>0;inc/=3) for(i=inc;i<(n);i++)                              \
  { for(y=x[i],j=i;j>=inc;j-=inc)                                      \
    { if(y<x[j-inc]) x[j] = x[j-inc] ; else break ; }                  \
    x[j] = y ;                                                         \
  }                                                                    \
}
#define shsortdown(x,n,type)                                           \
{ int i,j,inc ; type y ;                                               \
  for(inc=1;1+3*inc<(n);inc=1+3*inc) ;                                 \
  for(;inc>0;inc/=3) for(i=inc;i<(n);i++)                              \
  { for(y=x[i],j=i;j>=inc;j-=inc)                                      \
    { if(y>x[j-inc]) x[j] = x[j-inc] ; else break ; }                  \
    x[j] = y ;                                                         \
  }                                                                    \
}
/* ----------------------------- sundry sorts ------------------------------- */

static void isortup(int *u,int n) { shsortup(u,n,int) ; }
static void realsort(double *u,int n) { shsortup(u,n,double) ; }
static void xysort(xy *u,int n) { shellsortup(u,n,xy,x) ; }
static void xisort(xi *u,int n) { shellsortup(u,n,xi,x) ; }
static void xisortdown(xi *u,int n) { shellsortdown(u,n,xi,x) ; } 

/* -------------------------- define robust fopens -------------------------- */

static FILE *fupopenread(char *name)
{ FILE *f ; 
  if(name[0]=='-'&&name[1]=='-'&&name[2]==0) f = stdin ; 
  else f = fopen(name,"r") ; 
  if(f==0) 
  { cjcperror = 1 ; 
    throw cjcup("Your input file %s could not be found.",name) ; 
  }
  return f ; 
} 
static FILE *fupopenwrite(char *name)
{ FILE *f ; 
  if(name[0]=='-'&&name[1]=='-'&&name[2]==0) f = stdout ; 
  else f = fopen(name,"w") ; 
  if(f==0) 
  { cjcperror = 1 ; 
    throw cjcup("Unable to write to your file %s.",name) ; 
  }
  return f ; 
} 
#define fopenread (cjcuplog(__FILE__,__LINE__,__PRETTY_FUNCTION__),fupopenread)
#define fopenwrite (cjcuplog(__FILE__,__LINE__,__PRETTY_FUNCTION__),fupopenwrite)
static char *freadline(FILE *ifl)
{ char *s=0 ; 
  int slen,ns,c,i ; 
  for(slen=ns=0;;)
  { c = fgetc(ifl) ; 
    if(c==EOF||c=='\n') 
    { if(slen>ns+1||(ns==0&&c=='\n')) s = charvector(s,ns+1) ; return s ; }
    if(ns>=slen-1)
    { slen += 20 + slen/2 ; 
      s = charvector(s,slen) ; 
      for(i=ns;i<slen;i++) s[i] = 0 ; 
    }
    s[ns++] = (char) c ; 
  }
}
static char *readline() { return freadline(stdin) ; } 
#endif