Tideman Election Code :- C Programming (CS50 Project 3)
Tideman Election Code in C
-- CS50: Introduction to Computer Science Project 3 Implementation
Project 3:-
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 and print the election winner
Step 1: The vote Function
This function takes the rank means whom voter choose for rank 1st, 2nd, 3rd .. nth, with each rank this function take input candidate name and ranks array this 1-D array made for each voter which store ranked wise candidates index for present voter.
Index 0 store voters 1st preference and Index 1 store voters 2nd preference ..
Example 1: If Candidates array look like [Alice, Bob, Charlie] then ranks array for voter 1(see in example 2) [1, 0, 2]
It stores the voter's preference and returns true if the candidate is found. In tideman election method each voter give there preference to each candidate.
Example 2: There are 3 candidate in election- Alice, Bob, Charlie
Then voter give rank to each candidate according to his point of view.
Voter 1 - i) Bob
ii) Alice
iii) Charlie
Voter 2 - i) Charlie
ii) Bob
iii) Alice
Voter 3 - i) Alice
ii) Bob
iii) Charlie
See how arguments for this function will pass-
example.c
// 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)) // Calling Vote function if candidate name given by voter present in candidate list then store preference and return true
{
printf("Invalid vote.\n");
return 3;
}
}
record_preferences(ranks); // If given vote by voter is valid then add this voter's preferences in array
printf("\n");
}
tideman.c
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.
Example 3: Preference array look like on the basis of Example 2
i 🠊 Alice Bob Charlie
j
🠋
Alice 0 2 1
Bob 1 0 1
Charlie 2 2 0
tideman.c
// 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 candidate have pair with every other candidate and each pair have one winner and one loser.
tideman.c
// Each pair has a winner, loser
typedef struct
{
int winner; // int because we did't track candidates name, we use candidates index
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.
In above step we made pair now we sort pair according to which pair have high diff of votes.
tideman.c
// 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.
Example: In pairs array we have first pair b/w Alice and Bob and winner is Bob(acc to eg 3)
Cycle means or locked means Bob -> Alice
For second pair Alice and Charlie and winner is Alice
Alice -> Charlie
3rd pair Bob and Charlie winner is Bob
cycle will look like Bob -> Charlie
Alice
⬈ ⬊
Bob ➡ Charlie
In this case Bob is winner because he has no arrow towards himself by any other candidate means not lose to any other candidate. If 3rd pair have Charlie winner and we lock or make arrow Charlie -> Bob , we skip this lock and run winner fn and then also Bob win.
Alice Alice
⬈ ⬊ →→ ⬈ ⬊
Bob ⬅ Charlie Bob Charlie
it is wrong because this make a complete cycle, so if anywhere forming a cycle then we need to avoid that pair because if we locked that pair then no one will become winner. Winner will be that candidate which have no arrow towards himself.
tideman.c
// 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.
tideman.c
// 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:
tideman.c
#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
Interactive Tideman Election Simulator
Enter up to 9 candidate names, add voter preferences, and calculate the winner using the Tideman algorithm (Ranked Pairs).
Step 1: Enter Candidates
Candidates: None
Step 2: Add Voter Preferences
Election Result
Winner: -
