Election Methods in C

Command Line Utility

countvotes takes url formatted votes, one per line, on the standard input and runs Histogram, VRR, IRNR, IRV, Raw Rating Summation and STV on them, producing HTML results on the standard output.

usage:

countvotes [--dump][--debug][--preindexed]
	[--full-html|--no-full-html|--no-html-head]
	[--disable-all][--enable-all]
	[--enable|--disable hist|irnr|vrr|raw|irv|stv]
	input-file-name|
	--pg "PostgreSQL connect string" --query "SQL;"
--dump
Repeat votes to standard out. Text may not be identical as they are reconstructed from an internal representation.
--debug
Print some additional information as it runs
--preindexed
All choice names must be integers that can be parsed with strtol()
--full-html
Emit a generic <html><head><title></head><body> sequences, and close with </body></html>
this is the default
--no-full-html
--no-html-head
Emit only the vote result HTML which should be included in a full HTML document. These options are synonyms.
--disable-all
Disable all voting methods. You should probably follow this with --enable
--enable-all
Enable all voting methods.
--enable method
Enable a voting method. Can be used multiple times.
--disable method
Disable a voting method. Can be used multiple times.
--pg "PostgreSQL connect string"
Specify PostgreSQL database to connect to. Probably at least "user=foo dbname=bar" should be specified, possibly "host" and "port". See the documentation for PQconnectdb() for details.
--query "SQL;"
The SQL query should return one column which contains strings of url formatted vote data.

Election Method Implementations

Virtual Round Robin (Condorcet)VRR.cVRR.h
Instant Runoff Normalized RatingsIRNR.cIRNR.h
Instant Runoff VotingIRV.cIRV.h
Single Transferrable VoteSTV.cSTV.h
Raw Rating SummationRawRating.cRawRating.h
HistogramHistogram.cHistogram.h

All election methods implement a common interface, taking votes and returning results through functions of the same signature. They are built around an object metaphor, taking a pointer to their struct type as first argument.

The STV functions are shown below for example. In each other implementation replace "STV" with "IRV", "IRNR", etc.

STV* newSTV();

Allocate and initialize an instance.

int STV_voteRating( STV* it, int numVotes, const NameVote* votes );
int STV_voteStoredIndexVoteNode( STV* it, StoredIndexVoteNode* votes );

These two methods equivalently record the vote stored in the passed in arguments. The StoredIndexVoteNode form consumes the argument passed in which should not be referenced after calling this function. The implementation will either free() or store it. The NameVote method does not alter the argument passed in and makes a copy if necessary. Consult the implementation source if malloc() efficiency around stored votes is critical.
Zero is returned on success and some other value on error. Most implementations have no failure mode for voting.

int STV_getWinners( STV* it, int wlen, NameVote** winnersP );

Get election results as sorted name,value pairs. Normally a full ranking will be returned and it is left to display software to recognize and present any special handling for ties. If *winnersP is NULL, store into it a pointer to internally allocated memory with the complete list. If *winnresP is not NULL, copy into it up to as many elements as wlen indicates. It is an error for winnersP to be NULL. Return the number of name,value pairs returned through winnersP. -1 on error.

void STV_htmlSummary( STV* it, FILE* fout );

Print HTML text to fout. Includes an HTML table of winners and any other relevant info (e.g. Virtual Round Robin table or Histograms).

void STV_print( STV* it, FILE* fout );

Print plain text represntation to fout.

void STV_setSharedNameIndex( type* it, NameIndex* ni );

Clobber internal NameIndex (free() as needed) and replace with passed in argument. It's possible for different instances to share one NameIndex, but this replacement should only be done once or free() could be called on the same NameIndex pointer multiple times and corrupt memory.

void clearSTV( STV* it );

Reset internal counters and stored votes. May then use instance for new election count.

deleteSTV( STV* it )

Free everything internally, and then the instance itself.

VirtualVotingSystem* newVirtualSTV()

Create a function pointer based object which can be used runtime interchangeably with other implementations. See NamedVotingSystem.h or the VirtualVotingSystem section below.

STV_deleteVVS( VirtualVotingSystem* vvs )

Clear internals, delete instance. Equivalent to vvs->close( vvs );

Utility Code

NamedVotingSystem.c (.h)

Struct types for passing votes and receiving results

struct NameVoteStruct {
	const char* name;
	float rating;
};
typedef struct NameVoteStruct NameVote;

struct IndexVoteStruct {
	int index;
	float rating;
};
typedef struct IndexVoteStruct IndexVote;

struct StoredIndexVoteNode {
	struct StoredIndexVoteNode* next;
	int numVotes;
	IndexVote vote[];

};
typedef struct StoredIndexVoteNode StoredIndexVoteNode;

StoredIndexVoteNode funcions:

StoredIndexVoteNode* newStoredIndexVoteNode(int count);

Allocates a node big enough to hold count name-index,rating pairs.

StoredIndexVoteNode* dupStoredIndexVoteNode( const StoredIndexVoteNode* );

NameIndex

The "NameIndex" struct is for keeping the string data of candidate names once and storing by integer index elsewhere.

void initNameIndex( NameIndex* ni );

Zero out all the values

void clearNameIndex( NameIndex* ni );

Free any memory, then zero out values.

int nameIndex( NameIndex* ni, const char* name );

Translate a string to integer index. creates new index if first appearance of name.

const char* indexName( NameIndex* ni, int index );

Retrieve name for some index

VirtualVotingSystem

"VirtualVotingSystem" struct contains function pointers for creating runtime typed objects out of the election method implementations.

typedef struct VirtualVotingSystem VirtualVotingSystem;
struct VirtualVotingSystem {
	int (*voteRating)( void* it, int numVotes, const NameVote* votes );
	/*! assumed to retain or free() votes passed in. because it may free(), votes must not be accessed after call.  */
	int (*voteStoredIndexVoteNode)( void* it, StoredIndexVoteNode* votes );
	int (*getWinners)( void* it, int numVotes, NameVote** winnersP );
	void (*htmlSummary)( void* it, FILE* fout );
	void (*print)( void* it, FILE* fout );
	void (*setSharedNameIndex)( void* it, NameIndex* ni );
	void (*close)( VirtualVotingSystem* it );// delete
	
	void* it;
};