Algebra

Exercicis d'ordinador d'Àlgebra

Informació general

• Tots els programaris estan pensats per a ser compilats amb gcc i executats en Linux.
• Tots els programaris donen ajuda si s'executen sense paràmetres.

Exercicis 1 i 2

• Descarregar el fitxer alg1.zip
• descomprimir el zip

unzip alg1.zip

• compilar

make

• executar

# Executa el binari sense arguments. Si ho feu imprimeix per pantalla les opcions disponibles.
bin/ex1
# Executa el binari sense arguments. Si ho feu imprimeix per pantalla les opcions disponibles.
bin/ex2
# Exemple de com executar correctament ex1
bin/ex1 matriu_binaria.txt noms2.txt
# Exemple de com executar correctament ex2
bin/ex2 matriu_binaria.txt noms2.txt

Descripció dels exercicis

• ex1: És un programa demostratiu que llegeix un fitxer que conté la matriu d'adjacència del graf, en calcula el grau de cadascun dels vèrtexs i ho imprimeix en pantalla. No cal implementar res, només s'ha de compilar, executar, i veure la sortida per pantalla (veure explicació més amunt). És important entendre el codi, perquè servirà per fer el segon exercici (ex2).
• ex2: En aquest exercici es demana modificar el codi font (que ja té tota la part de entrada/sortida programada per nosaltres) de forma que imprimeixi per pantalla la llista de veïns de cadascun dels vèrtexs del graf.

Formats d'arxius

Matriu d'adjacència (format 1)

A continuació indicarem els formats dels arxius que farem servir per a representar grafs. Ho farem per al graf de la figura que es mostra a continuació.

Bàsicament hi han dos fitxers que s'han d'especificar: la matriu d'adjacències (que a l'exemple anterior correspon al fitxer matriu_binaria.txt) i una llista dels noms (o etiquetes) assignats als vèrtex (fitxer noms2.txt).

La matriu d'adjacències per l'exemple considerat aquí és aquesta:

Fig. 1: Graf d'exemple en format matriu

8 8
0 1 1 0 0 0 1 0
1 0 1 1 1 0 0 0
1 1 0 1 0 0 1 0
0 1 1 0 1 1 1 0
0 1 0 1 0 1 0 1
0 0 0 1 1 0 1 1
1 0 1 1 0 1 0 1
0 0 0 0 1 1 1 0

Observeu que la primera línia del fitxer s’utilitza per indicar el nombre de columnes i files de la matriu d’adjacències. En aquest exemple són 8 files i 8 columnes (la matriu d'adjacències és quadrada, i per tant el nombre de files és igual al nombre de columnes). La resta de valors indiquen, tal i com s'ha comentat a classe, l'adjacència de dos vèrtex del graf.

A més del fitxer amb la matriu d’adjacències, en un altre fitxer hi haurà una llista amb els noms de cada vèrtex, cada nom a una línia diferent. Vegeu a continuació un exemple de fitxer de noms (en aquest exemple correspon al fitxer noms2.txt) que es pot fer servir pel graf de la figura de la dreta.

A
B
C
D
E
F
G
Z

Llista d'adjacencies

El format de fitxer per a les llistes d'adjacències és el següent (al exemple es diu: graf_adj.txt): 4 8 2 1 2 2 0 2 3 0 1 3 1 2 Aquest fitxer representa el graf dibuixat a la figura 2. La primera línia del fitxer s'utilitza per a indicar el nombre de vèrtexs i branques respectivament. Després, cada vèrtex es representa amb dues línies, la primera indica el nombre de veïns, i la segona indica els índexs dels veïns, separats per un espai buit.

El fixter amb els noms dels nodes té el mateix format que en el cas anterior.

Fig. 2: Graf d'exemple en format llista

Matriu d'adjacència (fomat 2)

Aquest format es fa servir per a grafs amb branques ponderades. El format es sembla molt al anterior, amb la diferencia que quan dos nodes no estan connectats, es posa infinit a la entrada corresponent de la matriu. Nosaltres representarem el número infinit amb un número enter molt gran (2147483647). Per simplicitat, teniu definit un macro INF que representa aquest número. Es troba definit al fitxer utils.h que us hem donat.

8 8
2147483647 30 20 2147483647 2147483647 2147483647 10 2147483647
30 2147483647 20 10 10 2147483647 2147483647 2147483647
20 20 2147483647 20 2147483647 2147483647 30 2147483647
2147483647 10 20 2147483647 10 5 5 2147483647
2147483647 10 2147483647 10 2147483647 5 2147483647 10
2147483647 2147483647 2147483647 5 5 2147483647 10 30
10 2147483647 30 5 2147483647 10 2147483647 20
2147483647 2147483647 2147483647 2147483647 10 30 20 2147483647

Fig. 3: Graf d'exemple com matriu d'adjacència (format 2)

Dibuixar grafs

Per generar la imatge del graf de la dreta hem seguit aquests passos:

# generem un fitxer graf.dot amb l'especificació del graf
bin/test_dot matriu_binaria.txt noms2.txt > graf.dot
# generem una imatge amb el .dot
dot graf.dot -Tpng -o graf.png
#despleguem l'imatge
display graf.png

Descripció del codi

Tot el codi necessari es troba a la llibreria libgrafs. Si voleu veure com s'han està implementat podeu descarregar el codi font des de aquí: També es troba disponible la documentació de les estructures de dades i les funcions aquí: [1]

Dijkstra's Algorithm

To run it

bin/dijsktra data/matriu_dijkstra_1.txt data/noms_dijkstra_1.txt Z A tmp/cami_dijkstra_1.txt
bin/dibuixa_cami data/matriu_dijkstra_1.txt data/noms_dijkstra_1.txt tmp/cami_dijkstra_1.txt > dibuixos/cami_dijkstra_1.dot
dot -Tpng dibuixos/cami_dijkstra_1.dot -o dibuixos/cami_dijkstra_1.png
display dibuixos/cami_dijkstra_1.png

Test the resulting path

> bin/test_path data/matriu_dijkstra_1.txt data/noms_dijkstra_1.txt Z A tmp/cami_dijkstra_1.txt 
optimal path:
n: 3
given cost: 30
actual cost: 30
test passed!