EgtNumKernel/Dijkstra.cpp

//----------------------------------------------------------------------------
//  EgalTech 2015-2015
//----------------------------------------------------------------------------
// File : Dijkstra.cpp        Data : 08.02.24        Versione : 2.6b1
// Contenuto : Classe per calcolo del percorso a peso minimo su un grafo orientato.
//
//
// Modifiche : 02.02.2024 RE Creazione modulo.
//
//
//----------------------------------------------------------------------------

//--------------------------- Include ----------------------------------------
#include "stdafx.h"
#include "DllMain.h"
#include "Dijkstra.h"
#include "/EgtDev/Include/EGnStringUtils.h"
#include "/EgtDev/Include/EgtILogger.h"
#include "set"
#include <new>

using namespace std ;

//----------------------------------------------------------------------------
IDijkstra*
CreateDijkstra( void)
{
   return static_cast<IDijkstra*> ( new(nothrow) Dijkstra) ;
}

//----------------------------------------------------------------------------
Dijkstra::Dijkstra( void)
{
   m_AdjMatrix = { } ;
   m_nDest = -1 ;
   m_bValid = false ;
}

//----------------------------------------------------------------------------
Dijkstra::~Dijkstra( void)
{
}

//----------------------------------------------------------------------------
bool
Dijkstra::SetGraph( DBLMATRIX AdjMatrix, int nDestInd) {

  // se vuota, errore
   if ( AdjMatrix.empty())
      return false ;

  // controllo che la matrice sia quadrata
   int nRows = static_cast<int>( AdjMatrix.size()) ;
   for ( int i = 0 ; i < nRows ; ++ i)
      if ( static_cast<int>( AdjMatrix[i].size()) != nRows)
         return false ;

  // i pesi non devono essere negativi
   for ( int i = 0 ; i < nRows ; ++ i)
      for ( int j = 0 ; j < int( AdjMatrix[i].size()) ; ++ j)
         if ( AdjMatrix[i][j] < 0)
            return false ;

  // assegno la matrice delle adiancenze e la destinazione
   m_AdjMatrix = AdjMatrix ;
   m_nDest = nDestInd ;

  // per sicurezza assegno agli elementi sulla diagonale la massima distanza
   for ( int i = 0 ; i < nRows ; ++ i)
      m_AdjMatrix[i][i] = WEIGHT_NO_ADJ ;

  // il grafo è valido
   m_bValid = true ;

   return true ;
}

//----------------------------------------------------------------------------
bool
Dijkstra::GetPath( INTVECTOR& vNodePath)
{
  // se il grafo non è valido, allora esco
   if ( ! m_bValid)
      return false ;

  // dimensione dei nodi
   const int DIM = static_cast<int>( m_AdjMatrix.size()) ;

  // ridimensiono il percorso
   vNodePath.resize( DIM) ;

  // definisco il vettore delle distanze
   vector<double> vDists ; vDists.resize( DIM) ;

  // definisco l'insieme dei nodi visitati
   set<int> sNode_toCheck ;

  // inizializzo l'insieme dei nodi da visitare, le distanze ( ad infinito) e gli indici dei nodi
  // precedenti ( tutti a -1)
   for ( int i = 0 ; i < DIM ; ++ i) {
      sNode_toCheck.insert( i) ;
      vNodePath[i] = -1 ;
      vDists[i] = WEIGHT_NO_ADJ ;
   }
  // il nodo sorgente ( in posizione zero) ha distanza nulla
   vDists[0] = 0. ;

  // finchè non ho controllato tutti i nodi...
   while ( ! sNode_toCheck.empty()) {
     // cerco il nodo ( tra quelli non ancora visitati) a cui è associata la distanza minima
     // ( alla prima iterazione il nodo è lo 0)
      int nMinInd = -1 ;
      double dDistRef = WEIGHT_NO_ADJ - 1 ;
      for ( int i = 0 ; i < DIM ; ++ i) {
        // cerco un nodo i disponibile
         set<int>::iterator iter = sNode_toCheck.find( i) ;
         if ( iter == sNode_toCheck.end())
            continue ;
        // se la distanza e minore del riferimento, aggiorno
         if ( vDists[i] < dDistRef) {
            dDistRef = vDists[i] ;
            nMinInd = i ;
         }
      }
     // se nodo non trovato o coincidente alla destinazione ( se presente), allora il percorso è terminato
      if ( nMinInd == -1  ||  nMinInd == m_nDest)
         break ;

     // escludo il nodo i-esimo trovato
      sNode_toCheck.erase( nMinInd) ;

     // cerco i nodi ad esso adiacenti
      for ( int i = 0 ; i < DIM ; ++ i) {
         if ( m_AdjMatrix[nMinInd][i] < MAXDIST) {
           // la distanza per raggiungere il nodo i dal nodo nMinInd è pari alla somma dei contributi
           // associati alle lunghezza trovate
            double myDist = vDists[nMinInd] + m_AdjMatrix[nMinInd][i] ;
           // se inferiore...
            if ( myDist < vDists[i]) {
              // aggiorno la distanza per raggiungere il nodo i
               vDists[i] = myDist ;
              // aggiorno l'indice per raggiungere il nodo i
               vNodePath[i] = nMinInd ;
            }
         }
      }

   }

   return true ;
}