Número de caminos entre nodos de un grafo

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;

9 thoughts on “Número de caminos entre nodos de un grafo”

  1. Pingback: Práctica Algorítmica y Complejidad | Alejandro Morán

  2. 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!

  3. 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!

    1. 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.

      1. 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!

  4. 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

    1. 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 🙂

  5. 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?

    1. 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!.

Leave a Comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.