S'importen les llibreries que utilitzarem per fer el programa.
We'll start by importing all modules needed.
In [1]:
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from matplotlib.patches import Arc, FancyBboxPatch
%matplotlib inline
from IPython.display import display
A continuació es pregunta a l'usuari els paràmetres inicials necessaris per executar l'algoritme principal
Next, user has to input some initial parameters in order to execute the main algorithm.
In [2]:
p1 = input("Tria el número del programa que vols utilitzar: 1-Estudi general; 2-Graf; 3-Matrius i guanyadors ")
p2 = input("Quin mètode de Schulze vols utilitzar: 1-Vots guanyadors; 2-Restes ")
n = input("Quantes opcions o candidats hi ha? ")
if p1 == 2:
p12 = input("Quin tipus de graf vols representar: 1-General; 2-Resaltar camí més fort ")
if p12 == 2:
p121 = raw_input("Indica la opció inicial i final (ex: A-B): ")
else:
p12 = 1
p3 = input("Com insertaràs la matriu de comparació per parelles? 1-Manual; 2-Aleatori ")
if p3 == 2:
p30 = input("Quants votants hi ha? ")
p31 = input("Les butlletes poden estar incomplertes? 1-Sí; 2-No ")
El programa genera la matriu de vots per preferència per parella a partir de valors introduïts manualment (p3 == 1) o bé aleatoriament (p3 == 2).
These lines generate the pairwise preferences matrix based on manually introduced data (p3 == 1) or randomly filled (p3 == 2).
In [3]:
if p3 == 1: #crear una matriu NxN introduint cada valor manualment
mat = []
fila = []
candidats = []
for i in range(n):
candidats.append(chr(65+i))
for j in range(n):
fl = input("{} vs {} ".format(chr(65+i), chr(65+j)))
fila.append(float(fl))
mat.append(fila)
fila = []
matriu = pd.DataFrame(mat, columns=candidats, index=candidats)
if p3 == 2: #crear una matriu NxN amb valors aleatoris
mat = []
fila = []
candidats = []
if p31 ==1:
vrand = 50
else:
vrand = 0
for i in range(n): #crear una matriu NxN plena de zeros
candidats.append(chr(65+i))
for j in range(n):
fila.append(float(0))
mat.append(fila)
fila = []
for i in range(n): #omplir un triangle de la matriu de zeros i despres completar l'altre fent la diferencia
for j in range(n):
if i != j:
mat[i][j] = np.random.randint(0,p30)
mat[i][j] = int(mat[i][j]*float(np.random.randint(100-vrand,101)/100.0))
mat[j][i] = int((p30-mat[i][j])*float(np.random.randint(100-vrand,101)/100.0))
matriu = pd.DataFrame(mat, columns=candidats, index=candidats)
matriu
Out[3]:
Aquí entra en joc l'adaptació de l'algoritme de Floyd-Warshall per trobar la matriu de Schulze. Aquest algoritme troba el camí més curt entre dos punts d'un graf, tot considerant la ponderació de cada camí. En el nostre cas, hem d'afegir que si troba més d'un camí, ha de quedar-se amb el camí que tingui la força mínima més gran. Això ens dona una nova matriu amb el valors minims dels camins trobats.
Here is the Floyd-Warshall algorithm modification to find the Schulze matrix. This algorithm finds the shortest path between two points in a graph, considering the ponderation of each path. The modification consists in what path to choose if there is more than one. The algorithm chooses the path with the highest minimum strenght path. It generates a new matrix with the minimum values of the paths.
In [4]:
P = []
p = []
for i in range(n): #crear una matriu NxN plena de zeros
for j in range(n):
p.append(0)
P.append(p)
p = []
if p2 == 2: #aplicar el metode de restes i fer la diferencia amb la matriu transposada
P = (matriu - matriu.T).as_matrix()
for i in range(n): #omplir la matriu de zeros amb la matriu d'entrada en certes posicions
for j in range(n):
if i != j :
if p2 == 2:
if P[i][j] < 0:
P[i][j] = 0
#si el candidat "i" es mes preferit que el "j" copia el valor de la matriu anterior
if matriu.iloc[i,j] > matriu.iloc[j,i]:
P[i][j] = matriu.iloc[i,j]
#si no, hi posa un zero
else:
P[i][j] = 0
#Algoritme Floyd-Warshall modificat que recorre tota la matriu, valora tots els diferents camins i sobreescriu
#si troba un cami amb un valor mínim més gran que l'actual
for i in range(n):
for j in range(n):
if i != j :
for k in range(n):
if i != k and j != k:
P[j][k] = max(P[j][k], min(P[j][i], P[i][k]))
p = pd.DataFrame(P, columns=candidats, index=candidats)
p
Out[4]:
Una vegada trobada la matriu de Schulze aplicant el mètode anterior, es troba l'ordre de guanyadors tot interpretant aquesta matriu.
Once the Schulze matrix it's created using the previously defined method, it's easy to rank the options just by looking at this matrix.
In [5]:
res = []
re = []
for i in range(n): #crear una matriu NxN plena de zeros
for j in range(n):
re.append(0)
res.append(re)
re = []
for i in range (n): #si el candidat "i" es mes preferit que el "j" suma un punt al candidat "i"
for j in range(n):
if i != j:
if P[i][j] > P[j][i]:
res[i][j] = res[i][j]+1
resultatM = np.matrix(res)
resM = resultatM.T
vect = np.zeros(n)
vectR = np.zeros(n)
for i in range(n): #posar els punts dels candidats en un vector N
vect = np.array(resM[i])
vectR = vectR+vect
llistaG = []
J = -1
for j in range(n): #ordenar els candidats segons la seva puntuacio
for i in range(n):
if n-1-j == vectR[0,i]:
if j == J:
llistaG.append("="+chr(65+i))
else:
if J == -1:
llistaG.append(chr(65+i))
J = j
else:
llistaG.append(">"+chr(65+i))
G = ""
for i in range(n):
G = G+llistaG[i]
G
Out[5]:
A continuació es proposa un nou mètode per poder reconstruir el camí que prèviament s'ha trobat a partir de l'algoritme de Floyd-Warshall. Aquest nou algoritme es basa en tornar a recorre tota la matriu fent les comprovacions que s'han fet prèviament però aquest cop guardant i/o sobreescrivint una seqüència de números que representa el camí. Per exemple, si l'algoritme arriba a una cel·la que representa el camí del candidat "i" al candidat "j" i troba un camí alternatiu que passa per "k", aquesta cel·la és substituida per el valor de la força del nou camí, seguit per una nova seqüència {i,k,j} que substitueix el camí de "i" a "j" per un que fa un altre recorregut des de "i" passant per "k" fins arribar a "j". A mesura que l'algoritme avança, comprova tots els camins directes i hi incorpora un punt interming si ho troba convenient. A partir d'aquí hi ha camins directes i camins amb un punt intermig. El programa continua afegint punts intermitjos als camins que es poden subtituir fins que acaba de recorre la matriu.
Below its a proposal of a new method to reconstruct the path previously found using the Floyd-Warshall algorithm. This new algorithm is based on checking the matrix again but this time recording and/or overwritting a sequence of numbers that represent the path. I. e., if the algorithm gets to a cell that represents the path between the candidate "i" and candidate "j" and it finds an alternative path that pass through "k", this cell is changed for the value of the strenght of the nwe path, followed by a new sequence {i,k,j} that substitute the "i" to "j" path for a "i" to "k" to "j" path. As the algorithm progresses, it checks all the direct paths and it adds an intermediate point if its needed. It keeps adding intermediate points to the paths that can be substituded until it finishes the matrix.
In [6]:
D = []
d = []
for i in range(n): #crear una matriu NxN plena de zeros
for j in range(n):
d.append(0)
D.append(d)
d = []
for i in range(n): #omplir la matriu de zeros amb la força dels camins i els candidats en certes posicions
for j in range(n):
if i != j :
if matriu.iloc[i,j] > matriu.iloc[j,i]:
D[i][j] = [matriu.iloc[i,j], i, j]
else:
D[i][j] = [0, i, j]
for i in range(n): #comprovar si s'ha de canviar el camí i canviar-lo, si cal, afegint punts del nou cami.
for j in range(n):
if i != j :
for k in range(n):
if i != k and j != k:
if D[j][k][0] < min(D[j][i][0], D[i][k][0]):
D[j][k] = [min(D[j][i][0], D[i][k][0])]
for l in range(len(D[j][i])-1):
D[j][k].append(D[j][i][1+l])
for m in range(len(D[i][k])-2):
D[j][k].append(D[i][k][2+m])
mx = D
pn = pd.DataFrame(D, columns=candidats, index=candidats)
pn
Out[6]:
Una vegada obtinguda la matriu de camins, el programa ja té la informació suficient per representar el graf. Primer es defineixen unes variables i despés s'organitza la informació per tal de poder-la utilitzar més còmodament.
Once the path matrix is obtained, the program has the information required to represent the graph. First the variables are defined and then the program organizes the information in order make it easier to use.
In [7]:
IX = -1
JX = -1
f = 10
x = 1*f
y = 5
radi = .5*f
h = 1*0.2
w = 1
h2 = 3.7
w2 = float((n*f-1)/float(n))
estil = ["LArrow", "RArrow", "Round"]
estatFletxes = []
numFletxa = []
for i in range(n): #crea dos vectors que emmagatzemen els numeros i la direció de cada cami
for j in range(n-i):
if matriu.iloc[i, j+i]>matriu.iloc[j+i, i]:
numFletxa.append(int(matriu.iloc[i, j+i]))
estatFletxes.append(1)
else:
if matriu.iloc[i, j+i] != 0:
if matriu.iloc[i, j+i] == matriu.iloc[j+i, i] :
numFletxa.append("X")
estatFletxes.append(2)
else:
numFletxa.append(int(matriu.iloc[j+i, i]))
estatFletxes.append(0)
else:
if i != j+i:
numFletxa.append("X")
estatFletxes.append(2)
display(numFletxa)
display(estatFletxes)
Finalment, es representa el graf utilitzant la llibreria matplotlib i llegint tota la informació recopilada en els passos anteriors.
Finally, the graph is represented using matplotlib library and reading all the information gathered in previous steps.
In [8]:
#definir les dimensions de la figura
plt.figure(figsize=(15,15))
axes = plt.gca()
axes.set_xlim(0, n*f)
axes.set_ylim(0, 6*(n)+2)
axes.set_aspect(1)
#crear el marc principal
box = FancyBboxPatch((.5,1), n*f-1, 6*(n), "square", facecolor="white")
axes.add_patch(box)
axes.set_axis_off()
k=-1
if p12 == 1: #dibuixar totes les arestes negres
for j in range(n-1):
for i in range(n-(j+1)):
arc = Arc((x+i*0.5*f+j*f,y), 2*radi*(i+1), 2*radi*(i+1), 0, 0, 180, color="black")
axes.add_patch(arc)
else:
#dibuixar totes les arestes negres
for j in range(n-1):
for i in range(n-(j+1)):
arc = Arc((x+i*0.5*f+j*f,y), 2*radi*(i+1), 2*radi*(i+1), 0, 0, 180, color="black")
axes.add_patch(arc)
IX = ord(p121[0]) - 65
JX = ord(p121[2]) - 65
#dibuixar les arestes vermelles que indiquen el cami
if mx[IX][JX][0] != 0:
for K in range(len(mx[IX][JX])-2):
Ix = mx[IX][JX][(1+K)]
Jx = mx[IX][JX][(2+K)]
jx = min(Ix,Jx)
ix = np.abs(Ix-Jx)-1
arc = Arc((x+ix*0.5*f+jx*f,y), 2*radi*(ix+1), 2*radi*(ix+1), 0, 0, 180, color="red", linewidth = 3)
axes.add_patch(arc)
for j in range(n-1): #dibuixar totes les fletxes i afegir-hi text
for i in range(n-(j+1)):
k=k+1
fletxa = FancyBboxPatch((x+i*0.5*f+j*f-w-1/1.9+0.2,
y+((1+i)*0.5*f)-h/2-0.3),
1.6*w*1.5, 4*h,
estil[estatFletxes[k]],facecolor="white")
axes.add_patch(fletxa)
if numFletxa[k] > 99999 and numFletxa[k] != "X":
axes.text(x+i*0.5*f+j*f+.1, y+((1+i)*0.5*f-.5),
"{}M".format(np.round(numFletxa[k]/1000000.0, 1)), ha="center", size = 32-2.1*n)
if numFletxa[k] > 999 and numFletxa < 1000000 and numFletxa[k] != "X":
axes.text(x+i*0.5*f+j*f+.1, y+((1+i)*0.5*f-.5),
"{}K".format(numFletxa[k]/1000), ha="center", size = 32-2.1*n)
if numFletxa[k] < 1000 or numFletxa[k] == "X":
axes.text(x+i*0.5*f+j*f+.1, y+((1+i)*0.5*f-.5),
"{}".format(numFletxa[k]), ha="center", size = 32-2.1*n)
for i in range(n): #escriure el nom dels candidats
if i == IX or i == JX:
axes.text(x-0.5*f+i*f, y-2.5, candidats[i], ha="center", size = 40-3*n, color = "red")
else:
axes.text(x-0.5*f+i*f, y-2.5, candidats[i], ha="center", size = 40-3*n, color = "black")
box = FancyBboxPatch((.5+i*w2,1), w2, h2, "square", facecolor="gray", alpha=0.3)
axes.add_patch(box)
#plt.savefig("/home/marti/Documents/Física/TCA/Diagrama{}.pdf".format(10))
plt.show()
Aquí acabaria el programa, però com que les preguntes inicials limiten l'algoritme, es repeteix el codi anterior per poder prepresentar un graf amb el camí des de "E" fins a "C", per exemple.
The program would end here, but due to the fact that the initial questions limit the algorithm, the code is repeated below in order to represent a graph with a path from "E" to "C", i.e..
In [9]:
#redefinim les respostes a les preguntes inicials per tal de poder ensenyar la reconstrucció de cami
p1 = 2
p2 = 1
p12 = 2
p121 = "E-C"
#repetim el codi de la cel·la anterior
#definir les dimensions de la figura
plt.figure(figsize=(15,15))
axes = plt.gca()
axes.set_xlim(0, n*f)
axes.set_ylim(0, 6*(n)+2)
axes.set_aspect(1)
#crear el marc principal
box = FancyBboxPatch((.5,1), n*f-1, 6*(n), "square", facecolor="white")
axes.add_patch(box)
axes.set_axis_off()
k=-1
if p12 == 1: #dibuixar totes les arestes negres
for j in range(n-1):
for i in range(n-(j+1)):
arc = Arc((x+i*0.5*f+j*f,y), 2*radi*(i+1), 2*radi*(i+1), 0, 0, 180, color="black")
axes.add_patch(arc)
else:
#dibuixar totes les arestes negres
for j in range(n-1):
for i in range(n-(j+1)):
arc = Arc((x+i*0.5*f+j*f,y), 2*radi*(i+1), 2*radi*(i+1), 0, 0, 180, color="black")
axes.add_patch(arc)
IX = ord(p121[0]) - 65
JX = ord(p121[2]) - 65
#dibuixar les arestes vermelles que indiquen el cami
if mx[IX][JX][0] != 0:
for K in range(len(mx[IX][JX])-2):
Ix = mx[IX][JX][(1+K)]
Jx = mx[IX][JX][(2+K)]
jx = min(Ix,Jx)
ix = np.abs(Ix-Jx)-1
arc = Arc((x+ix*0.5*f+jx*f,y), 2*radi*(ix+1), 2*radi*(ix+1), 0, 0, 180, color="red", linewidth = 3)
axes.add_patch(arc)
for j in range(n-1): #dibuixar totes les fletxes i afegir-hi text
for i in range(n-(j+1)):
k=k+1
fletxa = FancyBboxPatch((x+i*0.5*f+j*f-w-1/1.9+0.2,
y+((1+i)*0.5*f)-h/2-0.3),
1.6*w*1.5, 4*h,
estil[estatFletxes[k]],facecolor="white")
axes.add_patch(fletxa)
if numFletxa[k] > 99999 and numFletxa[k] != "X":
axes.text(x+i*0.5*f+j*f+.1, y+((1+i)*0.5*f-.5),
"{}M".format(np.round(numFletxa[k]/1000000.0, 1)), ha="center", size = 32-2.1*n)
if numFletxa[k] > 999 and numFletxa < 1000000 and numFletxa[k] != "X":
axes.text(x+i*0.5*f+j*f+.1, y+((1+i)*0.5*f-.5),
"{}K".format(numFletxa[k]/1000), ha="center", size = 32-2.1*n)
if numFletxa[k] < 1000 or numFletxa[k] == "X":
axes.text(x+i*0.5*f+j*f+.1, y+((1+i)*0.5*f-.5),
"{}".format(numFletxa[k]), ha="center", size = 32-2.1*n)
for i in range(n): #escriure el nom dels candidats
if i == IX or i == JX:
axes.text(x-0.5*f+i*f, y-2.5, candidats[i], ha="center", size = 40-3*n, color = "red")
else:
axes.text(x-0.5*f+i*f, y-2.5, candidats[i], ha="center", size = 40-3*n, color = "black")
box = FancyBboxPatch((.5+i*w2,1), w2, h2, "square", facecolor="gray", alpha=0.3)
axes.add_patch(box)
#plt.savefig("/home/marti/Documents/Física/TCA/Diagrama{}.pdf".format(10))
plt.show()