The Tideman voting method (Ranked Pairs) determines the winner of an election based on ranked preferences from voters. Instead of just picking a candidate with the most votes, Tideman compares every pair of candidates head-to-head, locks in the strongest wins, and avoids cycles to ensure the winner is the most broadly preferred.
Project Requirements
- Implement the Tideman (ranked pairs) voting system
- Handle voter preferences and candidate data
- Record pairwise preferences between candidates
- Create pairs of candidates (winner vs loser)
- Sort pairs by strength of victory
- Lock pairs without creating cycles in the graph
- Find the source of the graph (candidate with no incoming edges) and print the election winner
vote()
Records a voter's preference for a candidate at a specific rank.
record_preferences()
Updates the preferences matrix based on a voter's ranked choices.
add_pairs()
Creates pairs of candidates with one preferred over the other.
sort_pairs()
Sorts pairs by the strength of victory (difference in preferences).
lock_pairs()
Locks pairs into the graph without creating cycles.
print_winner()
Finds and prints the source candidate (with no incoming edges).
Step 1: The vote Function
This function takes the rank, candidate name, and ranks array. It stores the voter's preference and returns true
if the candidate is found.
bool vote(int rank, string name, int ranks[])
{
for (int i = 0; i < candidate_count; i++)
{
if (strcmp(candidates[i], name) == 0)
{
ranks[rank] = i;
return true;
}
}
return false;
}
Step 2: Recording Preferences
This function updates the preferences
2D array to count how many voters prefer candidate i
over j
.
// preferences[i][j] is number of voters who prefer i over j
int preferences[MAX][MAX];
// Update preferences given one voter's ranks
void record_preferences(int ranks[])
{
for (int i = 0 ; i < candidate_count; i++)
{
for (int j = i + 1; j < candidate_count; j++)
{
preferences[ranks[i]][ranks[j]]++;
}
}
return;
}
Step 3: Adding Pairs
This function creates all possible pairs of candidates and determines the winner and loser for each pair based on preferences.
// Each pair has a winner, loser
typedef struct
{
int winner;
int loser;
} pair;
// Array of candidates
string candidates[MAX];
pair pairs[MAX * (MAX - 1) / 2];
// Record pairs of candidates where one is preferred over the other
void add_pairs(void)
{
for (int i = 0; i < candidate_count; i++)
{
for (int j = i + 1; j < candidate_count; j++)
{
if (preferences[i][j] > preferences[j][i])
{
pairs[pair_count].winner = i;
pairs[pair_count].loser = j;
pair_count++;
}
else if (preferences[i][j] < preferences[j][i])
{
pairs[pair_count].winner = j;
pairs[pair_count].loser = i;
pair_count++;
}
}
}
return;
}
Step 4: Sorting Pairs
This function sorts the pairs in decreasing order by the strength of victory using bubble sort.
// Sort pairs in decreasing order by strength of victory
void sort_pairs(void)
{
int swap = 1;
while (swap != 0)
{
swap = 0;
for (int i = 0; i < pair_count - 1; i++)
{
int diff1 = preferences[pairs[i].winner][pairs[i].loser] -
preferences[pairs[i].loser][pairs[i].winner];
int diff2 = preferences[pairs[i+1].winner][pairs[i+1].loser] -
preferences[pairs[i+1].loser][pairs[i+1].winner];
if (diff1 < diff2)
{
pair temp = pairs[i];
pairs[i] = pairs[i+1];
pairs[i+1] = temp;
swap++;
}
}
}
return;
}
Step 5: Locking Pairs Without Cycles
This function locks pairs into the candidate graph in order, without creating cycles. The helper function creates_cycle
checks for cycles.
// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
for (int i = 0; i < pair_count; i++)
{
int winner = pairs[i].winner;
int loser = pairs[i].loser;
if (!creates_cycle(winner, loser))
{
locked[winner][loser] = true;
}
}
return;
}
// Check if locking would create a cycle
bool creates_cycle(int winner, int loser)
{
if (locked[loser][winner] == true)
{
return true;
}
for (int i = 0; i < candidate_count; i++)
{
if (locked[i][winner] == true)
{
if (creates_cycle(i, loser))
{
return true;
}
}
}
return false;
}
Step 6: Printing the Winner
This function finds and prints the winner: the candidate who does not have any arrow pointing to them in the locked array.
// Print the winner of the election
void print_winner(void)
{
for (int i = 0; i < candidate_count; i++)
{
bool i_win = true;
for (int j = 0; j < candidate_count; j++)
{
if (locked[j][i])
{
i_win = false;
break;
}
}
if (i_win)
{
printf("%s\n", candidates[i]);
return;
}
}
}
Full Implementation
The complete Tideman voting system implementation with all functions and main logic:
#include "cs50.h"
#include <stdio.h>
#include <string.h>
// Max number of candidates
#define MAX 9
// preferences[i][j] is number of voters who prefer i over j
int preferences[MAX][MAX];
// locked[i][j] means i is locked in over j
bool locked[MAX][MAX];
// Each pair has a winner, loser
typedef struct
{
int winner;
int loser;
} pair;
// Array of candidates
string candidates[MAX];
pair pairs[MAX * (MAX - 1) / 2];
int pair_count;
int candidate_count;
// Function prototypes
bool vote(int rank, string name, int ranks[]);
void record_preferences(int ranks[]);
void add_pairs(void);
void sort_pairs(void);
void lock_pairs(void);
bool creates_cycle(int winner, int loser);
void print_winner(void);
int main(int argc, string argv[])
{
// Check for invalid usage
if (argc < 2)
{
printf("Usage: tideman [candidate ...]\n");
return 1;
}
// Populate array of candidates
candidate_count = argc - 1;
if (candidate_count > MAX)
{
printf("Maximum number of candidates is %i\n", MAX);
return 2;
}
for (int i = 0; i < candidate_count; i++)
{
candidates[i] = argv[i + 1];
}
// Clear graph of locked in pairs
for (int i = 0; i < candidate_count; i++)
{
for (int j = 0; j < candidate_count; j++)
{
locked[i][j] = false;
}
}
pair_count = 0;
int voter_count = get_int("Number of voters: ");
// Query for votes
for (int i = 0; i < voter_count; i++)
{
// ranks[i] is voter's ith preference
int ranks[candidate_count];
// Query for each rank
for (int j = 0; j < candidate_count; j++)
{
string name = get_string("Rank %i: ", j + 1);
if (!vote(j, name, ranks))
{
printf("Invalid vote.\n");
return 3;
}
}
record_preferences(ranks);
printf("\n");
}
add_pairs();
sort_pairs();
lock_pairs();
print_winner();
return 0;
}
// Update ranks given a new vote
bool vote(int rank, string name, int ranks[])
{
for (int i = 0; i < candidate_count; i++)
{
if (strcmp(candidates[i], name) == 0)
{
ranks[rank] = i;
return true;
}
}
return false;
}
// Update preferences given one voter's ranks
void record_preferences(int ranks[])
{
for (int i = 0; i < candidate_count; i++)
{
for (int j = i + 1; j < candidate_count; j++)
{
preferences[ranks[i]][ranks[j]]++;
}
}
return;
}
// Record pairs of candidates where one is preferred over the other
void add_pairs(void)
{
for (int i = 0; i < candidate_count; i++)
{
for (int j = i + 1; j < candidate_count; j++)
{
if (preferences[i][j] > preferences[j][i])
{
pairs[pair_count].winner = i;
pairs[pair_count].loser = j;
pair_count++;
}
else if (preferences[i][j] < preferences[j][i])
{
pairs[pair_count].winner = j;
pairs[pair_count].loser = i;
pair_count++;
}
}
}
return;
}
// Sort pairs in decreasing order by strength of victory
void sort_pairs(void)
{
int swap = 1;
while (swap != 0)
{
swap = 0;
for (int i = 0; i < pair_count - 1; i++)
{
int diff1 = preferences[pairs[i].winner][pairs[i].loser] -
preferences[pairs[i].loser][pairs[i].winner];
int diff2 = preferences[pairs[i+1].winner][pairs[i+1].loser] -
preferences[pairs[i+1].loser][pairs[i+1].winner];
if (diff1 < diff2)
{
pair temp = pairs[i];
pairs[i] = pairs[i+1];
pairs[i+1] = temp;
swap++;
}
}
}
return;
}
// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
for (int i = 0; i < pair_count; i++)
{
int winner = pairs[i].winner;
int loser = pairs[i].loser;
if (!creates_cycle(winner, loser))
{
locked[winner][loser] = true;
}
}
return;
}
// Check if locking would create a cycle
bool creates_cycle(int winner, int loser)
{
if (locked[loser][winner] == true)
{
return true;
}
for (int i = 0; i < candidate_count; i++)
{
if (locked[i][winner] == true)
{
if (creates_cycle(i, loser))
{
return true;
}
}
}
return false;
}
// Print the winner of the election
void print_winner(void)
{
for (int i = 0; i < candidate_count; i++)
{
bool i_win = true;
for (int j = 0; j < candidate_count; j++)
{
if (locked[j][i])
{
i_win = false;
break;
}
}
if (i_win)
{
printf("%s\n", candidates[i]);
return;
}
}
}
Key Considerations
- Cycle Detection: Recursive function to prevent cycles in the graph
- Pair Sorting: Sorting by strength of victory ensures strongest preferences are locked first
- Graph Representation: Using a locked matrix to represent edges between candidates
- Source Detection: Finding the candidate with no incoming edges to determine the winner
- Input Validation: Ensuring votes are for valid candidates
Example Execution
Candidates: Alice, Bob, Charlie
Voter Preferences:
- Voter 1: Alice > Bob > Charlie
- Voter 2: Bob > Charlie > Alice
- Voter 3: Charlie > Alice > Bob
Result: Alice wins according to Tideman method