EgtNumKernel :

- piccole migliorie.

Dijkstra.cpp

@@ -0,0 +1,151 @@
+//----------------------------------------------------------------------------
+//  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 ;
+}

Dijkstra.h

@@ -0,0 +1,38 @@
+//----------------------------------------------------------------------------
+//  EgalTech 2015-2015
+//----------------------------------------------------------------------------
+// File : Dijkstra.h          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.
+//
+//
+//----------------------------------------------------------------------------
+
+#pragma once
+
+#include "/EgtDev/Include/ENkDijkstra.h"
+
+//----------------------------------------------------------------------------
+#define MAXDIST         1073741823U    // 2^30 - 1 per evitare overflow
+
+//----------------------------------------------------------------------------
+
+//----------------------------------------------------------------------------
+class Dijkstra : public IDijkstra
+{
+   public :
+      ~Dijkstra( void) override ;
+      bool SetGraph( DBLMATRIX AdjMatrix, int nDestInd = -1) override ;
+      bool GetPath( INTVECTOR& vNodePath) override ;
+
+   public :
+      Dijkstra( void) ;
+
+   private :
+      int m_nDest ;
+      DBLMATRIX m_AdjMatrix ;
+      bool m_bValid ;
+} ;
+

EgtNumKernel.vcxproj

@@ -207,6 +207,7 @@ copy $(TargetPath) \EgtProg\Dll64</Command>
     </ResourceCompile>
   </ItemDefinitionGroup>
   <ItemGroup>
+    <ClCompile Include="Dijkstra.cpp" />
     <ClCompile Include="ENkDllMain.cpp" />
     <ClCompile Include="Fn.cpp" />
     <ClCompile Include="Hybrid.cpp" />
@@ -236,6 +237,7 @@ copy $(TargetPath) \EgtProg\Dll64</Command>
     <ClInclude Include="..\Include\ENkDllMain.h" />
     <ClInclude Include="..\Include\ENkPolynomial.h" />
     <ClInclude Include="..\Include\ENkPolynomialRoots.h" />
+    <ClInclude Include="Dijkstra.h" />
     <ClInclude Include="DllMain.h" />
     <ClInclude Include="JenkinsTraub.h" />
     <ClInclude Include="MaximumFiller.h" />

EgtNumKernel.vcxproj.filters

@@ -22,6 +22,9 @@
     <Filter Include="File di origine\MaximumFilling">
       <UniqueIdentifier>{205f239f-c48e-4049-bac5-74708a6c530c}</UniqueIdentifier>
     </Filter>
+    <Filter Include="File di origine\Dijkstra">
+      <UniqueIdentifier>{54a2fd6b-2491-42af-932a-eaa6f62f1ae2}</UniqueIdentifier>
+    </Filter>
   </ItemGroup>
   <ItemGroup>
     <ClCompile Include="ENkDllMain.cpp">
@@ -66,6 +69,9 @@
     <ClCompile Include="MaximumFiller.cpp">
       <Filter>File di origine\MaximumFilling</Filter>
     </ClCompile>
+    <ClCompile Include="Dijkstra.cpp">
+      <Filter>File di origine\Dijkstra</Filter>
+    </ClCompile>
   </ItemGroup>
   <ItemGroup>
     <ClInclude Include="stdafx.h">
@@ -110,6 +116,9 @@
     <ClInclude Include="MaximumFiller.h">
       <Filter>File di intestazione</Filter>
     </ClInclude>
+    <ClInclude Include="Dijkstra.h">
+      <Filter>File di intestazione</Filter>
+    </ClInclude>
   </ItemGroup>
   <ItemGroup>
     <ResourceCompile Include="EgtNumKernel.rc">