[EM] Floyd algorithm?
Markus Schulze
markus.schulze at alumni.tu-berlin.de
Sat Jan 31 06:24:01 PST 2004
Dear Mike,
Floyd has proven that when you consider the possible short-cuts
in that very special order that has been proposed by him then a
single pass through the triple-loop is sufficient to find all
the strongest paths.
When the strength of a pairwise defeat is measured primarily by
p1 (= the absolute number of votes for the winner of this pairwise
defeat) and secondarily by p2 (= the margin of this pairwise
defeat), then a possible implementation to calculate the strengths
of all strongest paths looks as follows:
N is the number of candidates.
Input: d[i,j] with i <> j is the number of voters who strictly
prefer candidate i to candidate j.
Output: "w[i] = true" means that candidate i is a potential
winner. "w[i] = false" means that candidate i is not
a potential winner.
for i : = 1 to N do
for j : = 1 to N do
if ( i <> j ) then
{
p2[i,j] : = d[i,j] - d[j,i] ;
if ( d[i,j] > d[j,i] ) then
p1[i,j] : = d[i,j] ;
if ( d[i,j] <= d[j,i] ) then
p1[i,j] : = 0 ;
}
for i : = 1 to N do
for j : = 1 to N do
if ( i <> j ) then
for k : = 1 to N do
if ( i <> k ) then
if ( j <> k ) then
{
s : = p1[j,i] ;
t : = p2[j,i] ;
if ( ( p1[i,k] < s ) or
( ( p1[i,k] = s ) and ( p2[i,k] < t ) ) ) then
{
s : = p1[i,k] ;
t : = p2[i,k] ;
}
if ( ( p1[j,k] < s ) or
( ( p1[j,k] = s ) and ( p2[j,k] < t ) ) ) then
{
p1[j,k] : = s ;
p2[j,k] : = t ;
}
}
for i : = 1 to N do
w[i] : = true ;
for i : = 1 to N do
for j : = 1 to N do
if ( i <> j ) then
if ( ( p1[j,i] > p1[i,j] ) or
( ( p1[j,i] = p1[i,j] ) and ( p2[j,i] > p2[i,j] ) ) ) then
w[i] : = false ;
*********
You can find the Floyd algorithm (aka Floyd-Warshall algorithm) in many
books on "graph theory", "combinatorial optimization" or "operations
research". In so far as you live in the LA area, I guess that you have
many good public libraries nearby. I suggest that you should go to your
local libraries, search for books on "graph theory", "combinatorial
optimization" or "operations research", and then search in these books
for "Floyd", "Floyd-Warshall", "shortest paths", "maximum capacity
paths" or "semirings".
You wrote that you don't know the Floyd algorithm sufficiently and
therefore you want to keep your "while changing" loop. However, I
suggested that nevertheless you should consider the possible short-cuts
in that very special order that has been proposed by Floyd.
When the strength of a pairwise defeat is measured primarily by
p1 (= the absolute number of votes for the winner of this pairwise
defeat) and secondarily by p2 (= the margin of this pairwise
defeat), then a possible implementation to calculate the strengths
of all strongest paths looks as follows:
N is the number of candidates.
Input: d[i,j] with i <> j is the number of voters who strictly
prefer candidate i to candidate j.
Output: "w[i] = true" means that candidate i is a potential
winner. "w[i] = false" means that candidate i is not
a potential winner.
changing : = true ;
while ( changing = true )
{
changing : = false ;
for i : = 1 to N do
for j : = 1 to N do
if ( i <> j ) then
{
p2[i,j] : = d[i,j] - d[j,i] ;
if ( d[i,j] > d[j,i] ) then
p1[i,j] : = d[i,j] ;
if ( d[i,j] <= d[j,i] ) then
p1[i,j] : = 0 ;
}
for i : = 1 to N do
for j : = 1 to N do
if ( i <> j ) then
for k : = 1 to N do
if ( i <> k ) then
if ( j <> k ) then
{
s : = p1[j,i] ;
t : = p2[j,i] ;
if ( ( p1[i,k] < s ) or
( ( p1[i,k] = s ) and ( p2[i,k] < t ) ) ) then
{
s : = p1[i,k] ;
t : = p2[i,k] ;
}
if ( ( p1[j,k] < s ) or
( ( p1[j,k] = s ) and ( p2[j,k] < t ) ) ) then
{
p1[j,k] : = s ;
p2[j,k] : = t ;
changing : = true ;
}
}
}
for i : = 1 to N do
w[i] : = true ;
for i : = 1 to N do
for j : = 1 to N do
if ( i <> j ) then
if ( ( p1[j,i] > p1[i,j] ) or
( ( p1[j,i] = p1[i,j] ) and ( p2[j,i] > p2[i,j] ) ) ) then
w[i] : = false ;
Mathematicians can live with this implementation since it
is guaranteed that there will never be more than two passes
through the triple-loop. Non-mathematicians can live with this
implementation since the "while changing" loop guarantees that
there will always be a sufficient number of passes through the
triple-loop.
*********
Alternatively, I suggested that you should implement the Dijkstra
algorithm (aka Dykstra algorithm). Also the Dijkstra algorithm has
a runtime of O(N^3). The Dijkstra algorithm is significantly simpler
to understand than the Floyd algorithm. The main reason why I use
the Floyd algorithm and not the Dijkstra algorithm in my paper is
that the source code of the Floyd algorithm is shorter than the
source code of the Dijkstra algorithm.
When the strength of a pairwise defeat is measured primarily by
p1 (= the absolute number of votes for the winner of this pairwise
defeat) and secondarily by p2 (= the margin of this pairwise
defeat), then a possible implementation to calculate the strengths
of all strongest paths looks as follows:
N is the number of candidates.
Input: d[i,j] with i <> j is the number of voters who strictly
prefer candidate i to candidate j.
Output: "w[i] = true" means that candidate i is a potential
winner. "w[i] = false" means that candidate i is not
a potential winner.
for i : = 1 to N do
for j : = 1 to N do
if ( i <> j ) then
{
if ( d[i,j] > d[j,i] ) then
d1[i,j] : = d[i,j] ;
if ( d[i,j] <= d[j,i] ) then
d1[i,j] : = 0 ;
d2[i,j] : = d[i,j] - d[j,i] ;
p1[i,j] : = d1[i,j] ;
p2[i,j] : = d2[i,j] ;
}
for i : = 1 to N do
{
for j : = 1 to N do
unchecked[j] : = true ;
unchecked[i] : = false ;
for j : = 2 to N do
{
v : = - 1 ;
w : = 0 ;
for k : = 1 to N do
if ( unchecked[k] = true ) then
if ( ( p1[i,k] > v ) or
( ( p1[i,k] = v ) and ( p2[i,k] > w ) ) ) then
{
v : = p1[i,k] ;
w : = p2[i,k] ;
x : = k ;
}
unchecked[x] : = false ;
for k : = 1 to N do
if ( unchecked[k] = true ) then
{
s : = p1[i,x] ;
t : = p2[i,x] ;
if ( ( d1[x,k] < s ) or
( ( d1[x,k] = s ) and ( d2[x,k] < t ) ) ) then
{
s : = d1[x,k] ;
t : = d2[x,k] ;
}
if ( ( p1[i,k] < s ) or
( ( p1[i,k] = s ) and ( p2[i,k] < t ) ) ) then
{
p1[i,k] : = s ;
p2[i,k] : = t ;
}
}
}
}
}
for i : = 1 to N do
w[i] : = true ;
for i : = 1 to N do
for j : = 1 to N do
if ( i <> j ) then
if ( ( p1[j,i] > p1[i,j] ) or
( ( p1[j,i] = p1[i,j] ) and ( p2[j,i] > p2[i,j] ) ) ) then
w[i] : = false ;
*********
So there are many efficient algorithms to calculate the strengths
of the strongest paths.
You wrote (31 Jan 2004):
> Apparently there's no way to help Markus to understand that he
> isn't an authority on English grammar.
Apparently there's no way to help Mike to understand that this is a
mailing list on election methods and not a mailing list on English
grammar.
You wrote (31 Jan 2004):
> Markus'd said:
> The problem is: When you refuse to say that you don't call your
> implementation "Floyd algorithm" _anymore_ and when you insult
> those people who mention that you had called your implementation
> "Floyd algorithm", then you make the readers mistakenly believe
> that you claim that you had never called it "Floyd algorithm".
>
> I'd replied:
>
> No, _your_ problem is: ....
No, it's _your_ problem. It is _your_ problem that you don't
understand that you hurt yourself when you describe your favorite
method in such a manner that the readers mistakenly believe that
already for small numbers of candidates a computer is needed to
calculate the winner and that for large numbers of candidates the
runtime to calculate the winner is prohibitive. It is _your_
problem that you don't understand that a discussion about the
merits of the different implementations is _not_ a discussion
about grammar.
You wrote (31 Jan 2004):
> But when you suggested that I inclulde "anymore", that was a
> suggestion about how I should word things.
>
> When, in my most recent message about this, I referred to your
> suggestion about how I should word things, did you believe that
> I referring to your long-ago statement that the Floyd algorithm
> alters the index order? Actually I made it clear what wording
> suggestion I was referrnig to. It was clear that I was referring
> to your suggestion that I should use "anymore".
This is a mailing list on election methods and not on your
grammatical blablabla. When you admit that your comments have
nothing to do with the current discussion about the different
implementations to calculate the strengths of the strongest
paths, then please keep your comments for yourself.
You wrote (31 Jan 2004):
> Markus continued:
>
> However, I haven't made a mistake since when I wrote on
> 15 Dec 2003 that you called your implementation "Floyd algorithm"
> my observation was correct.
>
> I reply:
>
> Can you post a quote in which I said that your first statement
> that I'd called our implementation the Floyd algorithm was
> incorrect?
>
> "I don't call that the Floyd algorithm" doesn't mean that you were
> incorrect a long time ago when you first said that I'd previously
> called it the Floyd algorithm.
On 18 Dec 2003, you wrote: "Wrong. I don't call that the Floyd
algorithm." "Wrong" means "incorrect". Doesn't it?
*********
You wrote (29 Jan 2004):
> If I say "I don't smoke", that doesn't mean "I have never smoked".
I wrote (29 Jan 2004):
> On the other side, when I see you smoking and I ask you for a cigarette
> and you then stub out your cigarette and scream "Wrong. I don't smoke."
> and call me an "idiot" and a "confused wording-Nazi" for saying that I
> have just seen you smoking, then, of course, you make me believe that
> you claim that I erred when I thought that I saw you smoking.
You wrote (31 Jan 2004):
> But long after you first pointed out that the genuine Floyd algorithm
> alters the index order, and long after I'd acknolwdged that the genuine
> Floyd algorithm alters the index order, and that the genuine Floyd
> algorithm is therefore different from our implementation, you continued
> to say that I call our implementation the Floyd algorithm. That's why
> it's true that you're an idiot and a confused wording-Nazi.
On the other side, e.g. in my 22 Dec 2003 mail I wrote 4 times that I
don't claim that you continue to claim that Eppley's algorithm is Floyd's
algorithm. But nevertheless, you continue to claim that I continue to
claim that you continue to claim that Eppley's algorithm is Floyd's
algorithm. You are the idiot and the confused wording-Nazi because you
don't see that you do exactly that thing you insult other people for.
*********
You wrote (29 Jan 2004):
> Look, this mailing list is about voting sytems, and it just isn't the place
> for you to find out about verb grammar. There must be grammatical discussion
> mailing lists. Couldn't you take your questions there instsead of here?
> you're off topic, and people don't appreciate your off-topic spamming about
> your grammatical misundestandings.
I wrote (29 Jan 2004):
> Actually, it is you who spams this mailing list with lessons in English
> grammar. I agree with David Gamble: "One of your rhetorical techniques
> is to mock and highlight unintentional errors of grammar and spelling."
You wrote (31 Jan 2004):
> But you're showing that you need the lessons. But I ask you to go somewhere
> else for them, because here the subject is off-topic. In this case, your
> errors of grammar lead you to endlessly spam the list with incorrect
> statements about another list-member. You're not posting about voting
> systems. You're off-topic. Aside from that, you're incorrect too.
Apparently there's no way to help Mike to understand that a discussion about
the merits of the different implementations to calculate the strengths of the
strongest paths is not a discussion about English grammar. The fact that Mike
calls mails on such implementations "off-topic" questions whether he is really
willing to discuss election methods.
*********
I wrote (29 Jan 2004):
> When I wrote that your use of the term "Floyd algorithm" was
> incorrect, then I didn't point to a _grammatical_ error, I
> pointed to a _mathematical_ error.
You wrote (31 Jan 2004):
> No one said that that statement pointed to a grammatical error. But
> in other statements, when you're telling me that "anymore" is needed
> in order to indicate the present tense, you're making an incorrect
> grammatical claim.
I didn't say that the term "anymore" is needed. I said that it would have
been better if you had used the term "anymore" to stress that you had
corrected your terminology. Do you really believe that whenever someone
makes a suggestion about how you could word things he talks about
grammatical errors?
*********
I wrote (27 Jan 2004):
> The problem is: When you refuse to say that you don't call your
> implementation "Floyd algorithm" _anymore_ and when you insult those
> people who mention that you had called your implementation "Floyd
> algorithm", then you make the readers mistakenly believe that you
> claim that you had never called it "Floyd algorithm".
You wrote (29 Jan 2004):
> Markus the confused wording-Nazi. I've told you that "anymore" is
> optional.
I wrote (29 Jan 2004):
> I guess with your statement you want to say that you prefer terms
> like "confused wording-Nazi" to terms like "anymore".
You wrote (31 Jan 2004):
> "Anymore" was unnecessary in the sentence in which the confused
> wording-Nazi insisted that I should include "anymore".
So you want to say that you have to use insults like "confused
wording-Nazi" because you are unable to use words like "anymore"?
*********
I wrote (29 Jan 2004):
> On the other side, I don't know why you are so upset.
You wrote (31 Jan 2004):
> Though I didn't say I was upset, let me explain why I criticize
> your postings: ...
The large number of annoying and insulting mails from you suggests
that you are upset about the fact that the strengths of the strongest
paths can be calculated in a polynomial runtime. If you are not upset
and you insult other people just for fun, then you shouldn't forget
the smilies ":-)".
You wrote (31 Jan 2004):
> ... Several members of the lst have indicated that they aren't
> interested in this topic that you inisist on pursuing, spamming
> the list with endless repetition of statements that have been
> answered and replies to statements that were never made.
On the other side, several members indicated that they are
interested in efficient algorithms to calculate the strengths
of the strongest paths. If you are not interested then I suggest
that, instead of insulting those who are interested in such
algorithms, you simply shouldn't read those mails.
Markus Schulze
More information about the Election-Methods
mailing list