Con el fin de ayudar a los compañeros que han acudido a mi blog solicitando ayuda para la práctica he invertido unas cuantas horas en resolver el problema añadido de este año “Obtener el número de caminos entre nodos de un grafo conexo”.
Comienzo con una breve explicación del método que he empleado:
Este problema puede ser resuelto mediante una búsqueda en profundidad en el grafo, el algoritmo es bastante rápido y sirve para cualquier tamaño de grafo (mi solución es recursiva y, para un grafo de tamaño n siendo n muy grande produciría un desbordamiento de pila, aunque ese problema no se nos presentará en esta practica ya que n es menor que 100).
Dejo un link a la práctica entera, esta vez es mi solución con el apartado 1 actualizado, respecto al apartado 2 recomiendo usar el de nuestro compañero David ubicado en el post: http://alejandromoran.com/practica-algoritmica-y-complejidad/
Link al fichero .adb: Fichero .adb comprimido
Y a continuación dejo el código de la práctica para verlo en esta entrada del blog:
with Ada.Text_IO,Ada.Integer_Text_IO, Ada.Command_Line, Text_IO;
use Ada.Text_IO,Ada.Integer_Text_IO,Ada.Command_Line, Text_IO;
procedure practica is
file,file2,file3 : File_Type;
fila,columna,valor : Natural;
lineasLeidas : Natural := 0;
totalNodos : Natural := 100;
package Int_IO is new Text_IO.Integer_IO (Integer);
type filaMatriz is array (1..101) of integer;
type matrizAdyacencia is array (1..101) of filaMatriz;
matriz: matrizAdyacencia;
type ArrayNodos is array (1..totalNodos) of integer;
-- SOLUCIÓN APARTADO 1: Cuello de botella y número de caminos entre nodos
-- Solucionar este problema mediante el uso de listas reduciría la dificultad
visitados : ArrayNodos := (others=>0);
arrayVisitados : ArrayNodos := (others=>0);
nodoOrigen : Natural := 0;
nodoDestino : Natural := 0;
minBottleneck : Natural := Integer'Last;
-- '
maximoAnchoDeBanda : Natural := 0;
caminos : Natural := 0;
function Adyacentes (vertice : in Natural) return ArrayNodos is
adyacentes : ArrayNodos := (others=>0);
contadorAdyacentes : Natural := 1;
begin
-- Devolvemos los adyacentes a un vertice
for i in 1..totalNodos loop
if matriz(vertice)(i) > 0 then
adyacentes(contadorAdyacentes) := i;
contadorAdyacentes := contadorAdyacentes + 1;
end if;
end loop;
return adyacentes;
end Adyacentes;
function UltimoVisitado (visitados : ArrayNodos) return Natural is
contador : Natural := 1;
begin
while visitados(contador) /= 0 loop
contador := contador + 1;
end loop;
return visitados(contador-1);
end UltimoVisitado;
function HaSidoVisitado (visitados : ArrayNodos; nodo : Natural) return Boolean is
contador : Natural := 1;
visitado : Boolean := false;
begin
while visitados(contador) /= 0 and Not visitado loop
if(visitados(contador) = nodo) then
visitado := true;
end if;
contador := contador + 1;
end loop;
return visitado;
end HaSidoVisitado;
function VisitarNodo (nodosVisitados : ArrayNodos; nodo : Natural) return ArrayNodos is
contador : Natural := 1;
visitados : ArrayNodos := nodosVisitados;
begin
while visitados(contador) /= 0 loop
contador := contador + 1;
end loop;
visitados(contador) := nodo;
return visitados;
end VisitarNodo;
function EliminarUltimoVisitado (nodosVisitados : ArrayNodos) return ArrayNodos is
contador : Natural := 1;
visitados : ArrayNodos := nodosVisitados;
begin
while visitados(contador) /= 0 loop
contador := contador + 1;
end loop;
visitados(contador-1) := 0;
return visitados;
end EliminarUltimoVisitado;
procedure Apartado1 (matriz : matrizAdyacencia; nodosVisitados : ArrayNodos; bottleneck : Natural ) is
nodos : ArrayNodos;
visitados : ArrayNodos := nodosVisitados;
cuelloBotella : Natural := 0;
begin
nodos := Adyacentes(UltimoVisitado(visitados));
for i in nodos'Range loop
-- '
if Not (HaSidoVisitado(visitados, nodos(i))) then
if (nodos(i) = nodoDestino) then
cuelloBotella := Matriz(UltimoVisitado(visitados))(nodos(i));
if Not (cuelloBotella < bottleneck) then
cuelloBotella := bottleneck;
end if;
visitados := VisitarNodo(visitados, nodos(i));
caminos := caminos + 1;
if(cuelloBotella > maximoAnchoDeBanda) then
maximoAnchoDeBanda := cuelloBotella;
end if;
visitados := EliminarUltimoVisitado(visitados);
exit;
end if;
end if;
end loop;
for i in nodos'Range loop
-- '
if (nodos(i) = 0) then
exit;
end if;
if Not (HaSidoVisitado(visitados, nodos(i)) or nodos(i) = nodoDestino) then
cuelloBotella := matriz(UltimoVisitado(visitados))(nodos(i));
if Not (cuelloBotella /= 0 and cuelloBotella < bottleneck) then
cuelloBotella := bottleneck;
end if;
visitados := VisitarNodo(visitados, nodos(i));
Apartado1(matriz, visitados, cuelloBotella);
visitados := EliminarUltimoVisitado(visitados);
end if;
end loop;
end Apartado1;
-- FIN DE LA SOLUCIÓN AL APARTADO 1
-- SOLUCIÓN AL APARTADO 2: Se entiende aunque se puede mejorar bastante
-- Función para saber si todos los nodos han sido visitados
function TodosVisitados (nodos : ArrayNodos) return boolean is
begin
for i in nodos'Range loop
-- '
if visitados(i) = 0 then
return false;
end if;
end loop;
return true;
end TodosVisitados;
-- Función para saber si un nodo en concreto ha sido visitado
function Visitado(nodos : ArrayNodos; vertice : Natural) return boolean is
begin
if nodos(vertice) > 0 then
return true;
end if;
return false;
end Visitado;
-- Procedimiento para marcar un nodo como visitado
procedure Visitar(vertice, valor : Natural) is
begin
visitados(vertice) := valor;
end Visitar;
function GetMaximoFila(nodos : ArrayNodos; fila : Natural; checkVisitado : Boolean := true) return integer is
valor : Natural := 0;
nodo : Natural := 0;
begin
for i in 1..totalNodos loop
if matriz(fila)(i) > valor and Not Visitado(nodos,i) = checkVisitado then
valor := matriz(fila)(i);
nodo := i;
end if;
end loop;
return nodo;
end GetMaximoFila;
function GetValorElemento(fila, indice : Natural) return integer is
begin
return matriz(fila)(indice);
end GetValorElemento;
visitadosArbol : ArrayNodos := (others=>0);
procedure VisitarArbol(vertice, valor : Natural) is
begin
visitadosArbol(vertice) := valor;
end VisitarArbol;
function GetPadre(nodos : ArrayNodos; fila : Natural) return integer is
valor : Natural := 0;
nodo : Natural := 0;
begin
for i in 1..totalNodos loop
if matriz(fila)(i) > valor and Visitado(nodos,i) then
valor := matriz(fila)(i);
nodo := i;
end if;
end loop;
return nodo;
end GetPadre;
type FilaArbolExpansion is array (1..3) of integer;
type ArrayArbolExpansion is array (1..totalNodos) of FilaArbolExpansion;
function ArbolExpansionMaximo return ArrayArbolExpansion is
nodoSiguiente : Natural := 1;
valorAux : Natural := 0;
nodosAnterioresArbol : array (1..totalNodos) of integer := (others=>0);
nodosAnterioresPadre : array (1..totalNodos) of integer := (others=>0);
valorMaximoArbol : Natural := 1;
nodoMaximoArbol : natural := 0;
visitaAnterior : boolean := false;
count : Natural := 0;
solucionArbol : ArrayArbolExpansion;
nodoAnterior : Natural := 0;
begin
valorAux := nodoSiguiente;
while Not TodosVisitados (visitadosArbol) loop
VisitarArbol(nodosiguiente, valorMaximoArbol);
nodosAnterioresArbol(nodoSiguiente) := 0;
nodoMaximoArbol := GetMaximoFila(visitadosArbol,nodoSiguiente);
if GetMaximoFila(visitadosArbol,nodoSiguiente) = 0 then
valorMaximoArbol := 0;
else
valorMaximoArbol := GetValorElemento(nodoSiguiente, GetMaximoFila(visitadosArbol, nodoSiguiente));
end if;
if nodosAnterioresArbol'Length > 0 then
for i in nodosAnterioresArbol'Range loop
if nodosAnterioresArbol(i) > valorMaximoArbol then
nodoMaximoArbol := i;
valorMaximoArbol := nodosAnterioresArbol(i);
valorAux := GetPadre(visitadosarbol, i);
nodoSiguiente := nodoMaximoArbol;
visitaAnterior := true;
end if;
end loop;
end if;
for i in 1..totalNodos loop
if Not Visitado(visitadosArbol,i) and matriz(nodoSiguiente)(i) /= 0 then
if (matriz(nodoSiguiente)(i) > nodosAnterioresArbol(i)) then
nodosAnterioresArbol(i) := matriz(nodoSiguiente)(i);
end if;
end if;
end loop;
if GetMaximoFila(visitadosArbol, nodoSiguiente) = 0 then
for i in 1..totalNodos loop
if Not Visitado(visitadosArbol,i) then
nodoSiguiente := GetMaximoFila(visitadosArbol,i,false);
end if;
end loop;
end if;
if Not visitaAnterior then
valorAux := nodoSiguiente;
end if;
visitaAnterior := false;
nodoSiguiente := nodoMaximoArbol;
if nodoSiguiente = 0 then
exit;
end if;
count := count + 1;
solucionArbol(count) := (valorAux, nodoSiguiente, valorMaximoArbol);
end loop;
return solucionArbol;
end ArbolExpansionMaximo;
-- FIN DE LA SOLUCIÓN AL APARTADO 2
function EscribirFichero return natural is
begin
return 1;
end EscribirFichero;
arbolExpansion : ArrayArbolExpansion;
begin
-- OPERACIONES DE LECTURA
Open(File => file,
Mode => In_File,
Name => Argument (1),
Form => "");
while not Text_IO.End_Of_File (file) loop
if lineasLeidas = 0 then
Int_IO.Get (File => file, Item => totalNodos);
lineasLeidas := lineasLeidas + 1;
else
Int_IO.Get (File => file,
Item => fila);
Int_IO.Get (File => file,
Item => columna);
Int_IO.Get (File => file,
Item => valor);
matriz(fila)(columna) := valor;
matriz(columna)(fila) := valor;
lineasLeidas := lineasLeidas + 1;
end if;
end loop;
Close(File => file);
-- FIN OPERACIONES DE LECTURA
-- OPERACIONES DE ESCRITURA
Create (file3, Out_File, "apartado1.txt");
for i in 1..totalNodos loop
for j in 1..totalNodos loop
Int_IO.Put (File => file3,
Item => i);
Int_IO.Put (File => file3,
Item => j);
nodoOrigen := i;
nodoDestino := j;
arrayVisitados := visitarNodo(arrayVisitados, nodoOrigen);
Apartado1(matriz, arrayVisitados, minBottleneck);
Int_IO.Put (File => file3,
Item => maximoAnchoDeBanda);
Int_IO.Put (File => file3,
Item => caminos);
-- Reiniciamos los contadores
minBottleneck := Integer'Last;
maximoAnchoDeBanda := 0;
caminos := 0;
arrayVisitados := (others=>0);
Text_IO.New_Line(file3);
end loop;
end loop;
Close(File => file3);
arbolExpansion := ArbolExpansionMaximo;
Create (file2, Out_File, "apartado2.txt");
Int_IO.Put (File => file2,
Item => totalNodos);
Text_IO.New_Line(file2);
for i in 1..totalNodos-1 loop
Int_IO.Put (File => file2,
Item => arbolExpansion(i)(1));
Int_IO.Put (File => file2,
Item => arbolExpansion(i)(2));
Int_IO.Put (File => file2,
Item => arbolExpansion(i)(3));
Text_IO.New_Line(file2);
end loop;
Close(File => file2);
-- FIN DE LAS OPERACIONES DE ESCRITURA
end practica;
Pingback: Práctica Algorítmica y Complejidad | Alejandro Morán
Muchas gracias Alejandro por el esfuerzo de ayudarnos.
Esta todo bien de la practica salvo por el apartado 2 =O
Dado que el resultado que se escribe en el fichero salida2.txt
no corresponde con los que ponen en la practica.
Aun así muchísimas gracias por tu tiempo de verdad.
Un saludo!
Se me había olvidado ponerte lo que surge en el apartado 2:
Lo que hay en el fichero entrada.txt
5
1 2 2
1 3 2
1 4 3
2 5 1
3 5 4
4 5 1
Lo que se obtiene el fichero apartado2.txt:
5
1 4 3
1 2 2
1 3 2
3 5 4
En vez de esto que es lo que se supone que tendría que salir:
5
1 2 2
1 3 2
1 4 3
3 5 4
Gracias de nuevo!
Buenas Mario, el año pasado ya me enfrenté yo a eso que preguntas, en realidad está bien salvo que la ejecución del algoritmo mío ha tomado un camino distinto al de la solución propuesta, pregúntale a tu profesor si existe algún problema, en mi caso el año pasado no lo hubo, y no debería de haberlo ya que es un camino igualmente válido, mi algoritmo se basa en el de PRIM, pero tomando caminos de valor máximo, un saludo.
A vale,mientras que sea un árbol recubridor mínimo no pasa nada por el algoritmo de Prim!
Una vez mas gracias por todo!
Un saludo!
Hola Alejandro, primero de todo, agradecerte por el trabajo que haces y ayudarnos a todos.
Mi pregunta es que si lo que hay en esta página está todo bien y optimizado, o es mejor hacer un “mix” con un apartado de aquí y el que hizo tu compañero David. Si es así que me recomendarías?
Un saludo y gracias
Buenas Daniel, perdona por tardar en responder, ya sabes que en las últimas semanas se acumula mucho trabajo 🙂 mi recomendación es hacer un buen “mix” de las dos prácticas pq según dicen este año tienen “anticopia” (que lo dudo un poco) y aún así me consta que mucha gente se ha basado en estas prácticas para entregar la suya propia así que lo mejor que puedes hacer es una buena mezcla de las dos, un saludo 🙂
Alejandro hay alguna forma de hacer el apartado 1 con el numero de caminos entre los nodos de un grafo ,con la forma de hacerlo de David?
El algoritmo desarrollado en la práctica de David es el “Algoritmo de Floyd-Warshall”, únicamente sirve para encontrar el camino mínimo entre dos nodos en grafos ponderados. Si quieres hacer ese apartado, te recomiendo realizar una búsqueda por internet, el que yo hice está basado en un algoritmo conocido muy fácil de implementar, no recuerdo el nombre, solamente que lo encontré en Java y lo adapté a mi código, un saludo!.