BRIAN: Let's dive into Tideman. In this program, your task is going to be to write a program that implements the Tideman Voting System. This voting system is an example of a ranked-preference voting system, which means that every voter, instead of just voting for one candidate, will get to rank their candidates in order of preference.

So a voter, instead of just voting for Alice for example, might instead indicate that Alice is their top choice. But their second choice is Charlie. And their third choice is Bob. And in particular, the Tideman voting method, otherwise known as Ranked Pairs, determines the winner of an election by looking at every possible pair of candidates in that election and determining who would have won a race if the election was just between those two candidates.

Let's take a look at an example of a Ranked Pairs election. Here's an election with three candidates-- Alice, Bob, and Charlie, and five voters. And what we're going to do is consider each pair of candidates, one pair at a time. Let's start just by considering Alice and Bob. Based on these five voters, three of the five voters think that Alice is better than Bob. And two of the five voters think that Bob is better than Alice. So between Alice and Bob, Alice would have won the election if it was just between the two of them.

To represent that, we're going to write Alice and Bob's name and draw an arrow pointing from Alice to Bob to indicate that Alice would have beaten Bob in a head-to-head match-up between the two of them. Let's now consider the other pairs. Let's look at Alice and Charlie, for example.

In this case, judging by these five voters, three voters thought Charlie was better than Alice. And only two voters thought Alice was better than Charlie. So Charlie would have beaten Alice in a head-to-head match up. So we're going to again, draw an arrow, this time pointing from Charlie to Alice, indicating that Charlie is preferred over Alice.

And finally, let's consider the last pair of Charlie and Bob. And in this case, we can see that three of the five voters think that Charlie is better than Bob. Only two think Bob is better than Charlie. So we'll draw one final arrow here, pointing from Charlie to Bob, indicating that Charlie beats Bob in this election.

This structure that we've created is what we call a graph, where we have each of these individual candidates. And we have arrows, otherwise known as edges, pointing from one candidate to another candidate if the first candidate would have beaten the second candidate. And now just using this graph and without looking at the ballots anymore, we can determine who the winner of the election should be.

The winner of the election is the so-called source of the graph, the person who has no arrows pointing at them, but does have arrows pointing at other people. In this case, Charlie has arrows pointing to Alice and Bob. But there are no arrows that are pointing at Charlie, which means nobody beats Charlie. And Charlie therefore, we can conclude, should be the winner of this election.

Now this was a relatively simple election. But there are some times where we might have an election where there is no source of the graph. And we need to figure out how to handle that situation. Let's take a look at an example of that.

Here is an election that has nine voters, again voting for three candidates-- Alice, Bob, and Charlie. And let's consider each of these pairs of candidates one at a time again. Between Alice and Bob, Alice beats Bob, 7 to 2. Seven of these nine voters think that Alice is better than Bob. So we'll draw an arrow from Alice to Bob.

Next we'll take a look at the pair of Bob and Charlie, where we see that Bob beats Charlie 5 to 4. Because five out of the nine voters think that Bob is better than Charlie. So in this case, we'll draw another arrow, this time pointing from Bob to Charlie.

And now let's consider the final pair, Alice and Charlie. And what you'll notice here is that Charlie actually beats Alice 6 to 3. Six of these nine voters think that Charlie is better than Alice. So we'll draw an arrow from Charlie to Alice.

And what you'll notice in this resulting graph is that there is no source of the graph. There's nobody that is undefeated, so to speak. Alice beats Bob, Bob beats Charlie, and Charlie beats Alice in this rock, paper, scissors, reminiscent-style of graph. And so it would be difficult to say who the winner of this election should actually be.

But this is where the ranked pairs idea of Ranked Pairs Voting comes in. Instead of adding all of these edges to the graph all at once, we're going to add the edges one at a time in order, based on the strength of victory for any particular pair. So we'll first take these three pairs-- Alice and Bob, Bob and Charlie, and Charlie and Alice, and put them in order based on the strength of their victory.

The strongest victory is Alice beating Bob-- 7 votes to 2. The next strongest is Charlie beating Alice-- 6 votes to 3. And the least strong margin of victory is Bob beating Charlie, who only won on a 5 to 4 margin.

And now what we're going to do is add edges to this graph in order, based on this strength of victory. But we're not going to add an edge if it would create a cycle, a rock, paper, scissors-style situation, where one candidate points to another which might point to another, which eventually loops back to that original candidate. Because in that sort of situation, we wouldn't know who the winner should be.

So to put this into practice, we would start with Alice beating Bob, the strongest pair, and draw an arrow from Alice to Bob. The next pair is Charlie beating Alice on a 6 to 3 margin. So we would draw an arrow from Charlie to Alice.

And next, Bob beats Charlie 5 to 4. So we would have drawn an arrow from Bob to Charlie, but we shouldn't yet. Because we should first notice that if we were to draw an arrow from Bob to Charlie, that would create a cycle, where Bob goes to Charlie, who goes to Alice, who goes back to Bob.

Any time we would be adding an edge that creates a cycle, we're just going to skip that edge and declare that now, in this case, since we've made it through all of the pairs, we're done. And we're going to look at this result graph to determine who the winner of the election should be. And in this case, the winner of the election is again, the source of the graph, who in this case, is Charlie.

So in summary, the Tideman Voting Method works as follows-- we start by tallying up the votes. Once all of the voters have indicated their preferences, we're going to look at each pair of candidates and determine who the winner of the election would be for just that particular pair. After we have all of those pairs, the next step is going to be to sort those pairs we're going to sort the pairs of candidates in decreasing strength of victory, where the strongest or widest margin of victory is first. And we go down to the smallest margin of victory at the end.

After we have the sorted pairs, the next step is to lock those pairs in one at a time. Starting with the strongest pair, we're going to lock in each pair. That is to say add an edge to that graph, as long as adding that edge isn't going to create a cycle. If it would create a cycle, we're going to skip that edge and just move on to the next pair. And after we have that resulting graph, we can determine the winner of the election by just checking to see who the source of the graph is-- in other words, who has no arrows pointing at them.

So in order to implement this idea in C, we're going to need to use some data structures and variables. So let's take a look at the data structures that you're going to be using in this program. The first that you're going to have access to is an array of candidates. Candidates is an array of strings that is just an array of all of the candidates names. So if there are three candidates-- Alice, Bob, and Charlie, you might have Alice as candidate number 0, Bob as candidate number 1, and Charlie as candidate number 2, for example.

You're also going to have access to a variable called preferences. And preferences is a two-dimensional array of integers interpreted as follows-- preferences [i][j] is the number of voters who prefer a candidate i over candidate j. Let's take a look at an example to see what that actually means in context.

Here's an example of an election with three candidates-- Alice, Bob, and Charlie, And four voters. And based on these four ballots, you might fill in the preferences' two-dimensional array as follows-- this first row preference, of 0, represents preferences for Alice, who's candidate number 0 in the candidates array. That first cell, also with 0, means that 0 people think that Alice is better than Alice, which makes sense.

The next cell in this row 3, means that three voters think that Alice is better than Bob. And the final cell here means that three voters think Alice is better than Charlie. The second row, meanwhile, preferences square bracket 1, that represents preferences for Bob. One voter thinks Bob is better than Alice. Nobody thinks Bob is better than Bob. And one voter thinks Bob is better than Charlie.

And finally, this last row in the preferences two-dimensional array represents preferences for Charlie. One voter thinks Charlie is better than Alice. Three voters think Charlie is better than Bob. And nobody thinks Charlie is better than Charlie.

This two-dimensional array now captures all of the data we need about individual voter preferences to determine what the pairs are and who is the winner of each pair in the election. So we need now, some way to represent pairs.

And to do that, we've defined a struct for you. This struct has two fields-- winner and loser-- each of which is an integer representing the candidate index in that candidate's array, who is the winner or the loser for this particular pair, respectively. Those pairs are going to be added to pairs, which is going to be an array of all of the pairs where one candidate is preferred above another. In other words, if there's a pair where the two candidates tie and no one person is favored over the other, we're not going to bother adding that pair to the pairs array.

You're then going to use that pairs array to generate a graph. This graph is called locked. And this is going to be a two-dimensional Boolean array, representing the candidate graph. And the way to interpret this two-dimensional array is that if locked [i][j] is true, that means we have locked in the edge or the arrow pointing from candidate i to candidate j.

So at first, all of the values in this two-dimensional Boolean array are going to be false, because we have no arrows pointing anywhere at the beginning of our algorithm. But every time you want to add an arrow or an edge pointing from one candidate to another candidate, you're going to change the value of locked [i][j] to true, for some candidates i and j.

So let's take a look at the functions that you'll actually need to write in order to implement Tideman. You're going to implement six functions-- vote, record_preferences, add_pairs, sort_pairs, lock_pairs, and print_winner, where after you've completed all of these functions, you'll have implemented the entire voting system. So let's take a look at these functions one at a time, beginning with the vote function.

The vote function is going to be called every time a voter indicates that some candidate has some rank in their preferences. The vote function takes in three inputs-- the rank itself, the name of the candidate, as well as an array of all of that particular voter's ranks. So what you're going to do in this function is you're going to look through the candidate's array for a candidate that has the same name. And if you're able to find a candidate with the same name, you're going to update the ranks array for that particular voter, and your function should return true.

The way to interpret the ranks is that ranks [i] represents the voter's ith preference. So rank 0 is the candidate's top preference. Ranks 1 is the candidate's next preference, so on and so forth. And if no candidate is found that matches the name that's provided as input to the function, you shouldn't update any ranks at all. And instead, your function should just return false.

Ultimately, you're going to use this ranks in another function as the input to the record_preferences function. This function is going to be called once for each voter. And it takes as input, that users ranks. All of their rankings for all of the candidates. And what you're going to do in the record_preferences function is update the preferences two-dimensional array based on this current voter is ranks. And this function again, is going to be called for each of the voters.

Let's take a look at an example for one particular voter. Here's an example of one voter's ranks, where in this case, candidate number 3 is this voters top choice. Candidate 0 is their second choice. Candidate 4 is their third choice, so on and so forth. And based on this ranks array, you're going to need to determine which candidates are preferred over other candidates.

And in this case, based on this particular array, we might notice that candidate 3, the top choice, is preferred over all of the other candidates-- candidate 0, 4, 1, and 2. Meanwhile, candidate 0 is preferred over candidates 4, 1, and 2. Candidate 4 is preferred over candidates 1 and 2. Candidate 1 is preferred over candidate 2. And candidate 2 is not preferred over anyone.

So for this particular ranks array, we were able to determine which candidates are preferred over others. And we would have to update our preferences array accordingly. After we have a representation of all of the voters preferences, the next step is going to be to look at each pair of candidates, determine who the winner or the loser, if any, are for that particular pair, and add them to the pairs array in the add_pairs function. What the add_pairs function is going to do is it's going to add each pair of candidates to the pairs array, as long as one of the candidates is actually preferred over the other candidate-- in other words, as long as there's actually a winner and a loser for that particular pair.

This function should also update the global variable pair account to represent the total number of pairs that you added to the pairs array. So for example, if we had a two-dimensional array of preferences as shown here, there are two pairs of candidates that have a winner and a loser. There is this pair of 0 and 1 where candidate 0 is preferred over candidate 1. And we know that because looking at the preferences array, we can see that there are three voters that think that candidate 0 is better than candidate 1. But there's only one voter who thinks the candidate 1 is better than candidate 0.

The other pair that we could add to the pairs array is the pair of candidates 2 and 0, where candidate 2 is the winner, and 0 is the loser. And again, we know that by looking at the preferences array. We can see that there are three voters that think that candidate 2 is better than candidate 0. And there's only one voter who thinks that candidate 0 is better than candidate 2.

The next step after we've added all of the pairs to the pairs array is to sort all of those pairs. And we're going to do that in the sort_pairs function. What this function is going to do is it is going to sort the pairs in order by decreasing strength of victory. And you can measure the strength of a victory by looking at how many people preferred the winner of that pair over the loser of the pair. If more people prefer the winner, it's a stronger victory.

You can use any sorting algorithm you'd like in order to sort those pairs. But at the end of the sort_pairs function, the pairs array should be sorted in order from strongest victory to weakest victory. Ultimately, we're going to use that sort of array in the next function-- lock_pairs-- which is going to go through those pairs one at a time and lock them into the graph. In particular, the lock_pairs function is responsible for updating the locked two-dimensional Boolean array in order to create the locked graph by adding all of the edges in decreasing order of victory strength, as long as adding that edge won't create a cycle.

If adding a particular edge between one candidate and another would ultimately create a cycle inside of the candidate graph, you shouldn't add that edge. And you should skip and move on to the next one. So you'll need some mechanism inside of your lock_pairs function to detect whether or not adding an edge is going to lead to a cycle where you could follow some path to get back to that original candidate.

To take a look at an example, here on the left, you can see an example of a locked graph. And on the right is the graphical representation of the same thing. Notice that every time a true appears inside of the locked two-dimensional array, that represents an arrow pointing from one candidate to another. So because locked 0, 1 is true, that means there is an arrow pointing from Alice to Bob. Because locked 2, 0 is true, that means there's an arrow pointing from Charlie to Alice. And because locked 2, 1 is also true, that means there's also an arrow pointing from Charlie to Bob.

After you've generated this locked graph, the final step is to print out the winner of the election. Recall again that the winner of the election is just going to be whichever candidate is the source of the graph. And you can assume for the purposes of this program, that there will not be more than one source. So there's only going to be one winner for the election.

And recall again, that the source of the graph is just whichever candidate doesn't have any arrows or edges pointing at them. And so you might want to look at this graph to figure out which of the candidates has no arrow that's pointed at them. Once you've implemented these six functions-- vote, record_preferences, add_pairs, sort_pairs, lock_pairs, and print_winner, you'll have implemented all that you need in order to simulate an election using the Tideman Voting System. My name is Brian, and this was Tideman.