Riccardo Elitropi
558b590810
- Aggiunta classe di calcolo per ottimizzazione ordine delle lavorazioni - Aggiunti vincoli obbligatori e dipendenze suggerite a ShortestPath.
279 lines
9.8 KiB
C++
279 lines
9.8 KiB
C++
//----------------------------------------------------------------------------
|
|
// EgalTech 2025-2025
|
|
//----------------------------------------------------------------------------
|
|
// File : Dependences.cpp Data : 16.04.25 Versione : 2.7a1
|
|
// Contenuto : Scelta dei nodi in base alle dipenze per ShortestPath ;
|
|
//
|
|
//
|
|
// Modifiche : 16.04.25 RE Creazione modulo.
|
|
//
|
|
//
|
|
//----------------------------------------------------------------------------
|
|
|
|
//--------------------------- Include ----------------------------------------
|
|
#include "stdafx.h"
|
|
#include "DllMain.h"
|
|
#include "ShortestPath.h"
|
|
#include "/EgtDev/Include/EGnStringUtils.h"
|
|
#include <new>
|
|
|
|
using namespace std ;
|
|
|
|
//----------------------------------------------------------------------------
|
|
/* Funzione per impostare i vincoli di precendeza obbligatori */
|
|
bool
|
|
ShortestPath::SetConstraintOrder( int nPrev, int nNext)
|
|
{
|
|
// se ho già delle dipendenze inserite, controllo che non sia già inserita o in conflitto
|
|
for ( auto it = m_vOrderConstr.begin() ; it != m_vOrderConstr.end() ; ++ it) {
|
|
// se dipendenza già presente, non la considero
|
|
if ( ( *it).first == nPrev && ( *it).second == nNext) {
|
|
LOG_INFO( GetENkLogger(), string( "Constraint Dependence already in : " + ToString( nPrev) + ", " + ToString( nNext)).c_str()) ;
|
|
return true ;
|
|
}
|
|
// se conflitto allora ritorno errore
|
|
if ( ( *it).first == nNext && ( *it).second == nPrev) {
|
|
LOG_INFO( GetENkLogger(), string( "Constraint Dependence conflict: " + ToString( nPrev) + ", " + ToString( nNext)).c_str()) ;
|
|
return false ;
|
|
}
|
|
}
|
|
// inserisco la dipendenze
|
|
m_vOrderConstr.emplace_back( make_pair( nPrev, nNext)) ;
|
|
return true ;
|
|
}
|
|
|
|
//----------------------------------------------------------------------------
|
|
/* Funzione per impostare i vincoli di precedenza suggeriti */
|
|
bool
|
|
ShortestPath::SetSuggestedOrder( int nPrev, int nNext)
|
|
{
|
|
// se vettore dipendenze vuoto, lo alloco
|
|
if ( m_vOrderSugg.empty()) {
|
|
m_vOrderSugg.resize( m_nNumPnts * m_nNumPnts, false) ;
|
|
m_vOrderSuggRowMap.resize( m_nNumPnts, false) ;
|
|
}
|
|
// se in conflitto, allora non la inserisco e cancello quella presente
|
|
if ( m_vOrderSugg[ nNext * m_nNumPnts + nPrev]) {
|
|
m_vOrderSugg[ nNext * m_nNumPnts + nPrev] = false ;
|
|
return true ;
|
|
}
|
|
// inserisco la dipendenze
|
|
m_vOrderSugg[ nPrev * m_nNumPnts + nNext] = true ;
|
|
m_vOrderSuggRowMap[ nPrev] = true ;
|
|
return true ;
|
|
}
|
|
|
|
//----------------------------------------------------------------------------
|
|
/* Funzione per verificare se un vincolo è violato o meno */
|
|
bool
|
|
ShortestPath::IsViolatingContraints( int nPrev, int nNext)
|
|
{
|
|
// scorro i vincoli
|
|
for ( const INTINT nC : m_vOrderConstr) {
|
|
// se il vincolo è ( nNext, nPrev) allora non è violato
|
|
if ( nC.first == nNext && nC.second == nPrev)
|
|
return true ;
|
|
}
|
|
return false ;
|
|
}
|
|
|
|
//----------------------------------------------------------------------------
|
|
/* Funzione per verificare se un Path rispetta tutti i vincoli obbligatori */
|
|
bool
|
|
ShortestPath::IsPathRespectingContraints( NODE* pPath)
|
|
{
|
|
// controllo validità del percorso
|
|
if ( pPath == nullptr)
|
|
return false ;
|
|
// controllo se il percorso ricavato, viola un vincolo
|
|
for ( unsigned nC = 0 ; nC < m_vOrderConstr.size() ; ++ nC) {
|
|
// scorro il percorso
|
|
NODE* pCurr = pPath ;
|
|
for ( unsigned i = 0 ; i < m_nNumPnts ; ++ i) {
|
|
if ( pCurr->nPos == m_vOrderConstr[nC].first)
|
|
break ;
|
|
if ( pCurr->nPos == m_vOrderConstr[nC].second)
|
|
return false ;
|
|
pCurr = pCurr->pNext ;
|
|
}
|
|
}
|
|
return true ;
|
|
}
|
|
|
|
//----------------------------------------------------------------------------
|
|
/* Funzione per verificare se una rotazione ciclica di nodi viola dei vincoli */
|
|
bool
|
|
ShortestPath::IsChangingStartPathRespectingConstraints( NODE* pPath, NODE* pFirst)
|
|
{
|
|
// copio il percorso in quello per le dipendenze
|
|
CopyPath( pPath, m_pCheckDep) ;
|
|
NODE* pCurr = m_pCheckDep ;
|
|
for ( unsigned i = 0 ; i < m_nNumPnts ; ++ i) {
|
|
// mi muovo alla posizione succesisva nel percorso di test
|
|
pCurr = pCurr->pNext ;
|
|
// controllo se il nuovo percorso rispetta i vincoli
|
|
if ( IsPathRespectingContraints( pCurr)) {
|
|
pFirst = pFirst->pNext ;
|
|
return true ;
|
|
}
|
|
}
|
|
return false ;
|
|
}
|
|
|
|
//----------------------------------------------------------------------------
|
|
/* Funzione per calcolare il numero di dipendenze SUGGERITE non rispettate da un Path */
|
|
bool
|
|
ShortestPath::IsPathRespectingSuggestedDependences( NODE* pPath, int& nBreak)
|
|
{
|
|
// se non ho dipendenze suggerite, ho finito
|
|
if ( m_vOrderSugg.empty())
|
|
return true ;
|
|
// controllo validità del percorso
|
|
nBreak = 0 ;
|
|
if ( pPath == nullptr)
|
|
return false ;
|
|
// scrorro i nodi coinvolti da dipendenze
|
|
unsigned nDim = m_nNumPnts - ( m_nType == SP_OPEN ? 1 : 0) ;
|
|
for ( unsigned i = 0 ; i < nDim ; ++ i) {
|
|
// controllo se il nodo corrente è legato da dipendenze suggerite
|
|
if ( m_vOrderSuggRowMap[i]) {
|
|
// scorro il percorso
|
|
NODE* pCurr = pPath ;
|
|
for ( unsigned j = 0 ; j < m_nNumPnts ; ++ j) {
|
|
if ( pCurr->nPos != m_nNumPnts - 1) {
|
|
if ( pCurr->nPos == i)
|
|
break ;
|
|
if ( m_vOrderSugg[ i * nDim + pCurr->nPos])
|
|
++ nBreak ;
|
|
}
|
|
pCurr = pCurr->pNext ;
|
|
}
|
|
}
|
|
}
|
|
return ( nBreak == 0) ;
|
|
}
|
|
|
|
//----------------------------------------------------------------------------
|
|
/* Funzione per calcolare il coefficiente di costo per ogni dipedenza suggerita violata */
|
|
unsigned
|
|
ShortestPath::CalcMaxDist( void)
|
|
{
|
|
// scorro gli elementi della matrice delle distanze
|
|
// NB. Si può decidere di calcolarlo diversamente
|
|
if ( m_Dists == nullptr)
|
|
return false ;
|
|
unsigned nMaxDist = 0 ;
|
|
for ( unsigned i = 0 ; i < m_nNumPnts ; ++ i) {
|
|
for ( unsigned j = 0 ; j < m_nNumPnts ; ++ j) {
|
|
if ( i != j && m_Dists[ Index( i, j)] < MAXDIST - 1)
|
|
nMaxDist = max( nMaxDist, m_Dists[ Index( i, j)]) ;
|
|
}
|
|
}
|
|
return nMaxDist ;
|
|
}
|
|
|
|
/* ------------------------------------------------------------------------- */
|
|
bool
|
|
ShortestPath::ChooseFirstNode( unsigned& iFirst)
|
|
{
|
|
// definisco un vettore dei soli nodi che posso inserire
|
|
vector<unsigned> vOkNodes ; vOkNodes.reserve( m_nNumPnts) ;
|
|
// scorro i nodi i-esimi
|
|
for ( unsigned i = 0 ; i < m_nNumPnts ; ++ i) {
|
|
// non deve esistere alcun vincolo del tipo ( j, i)
|
|
bool bOk = true ;
|
|
for ( unsigned nC = 0 ; nC < m_vOrderConstr.size() && bOk ; ++ nC) {
|
|
// recupero il vincolo ( a, b)
|
|
const INTINT& nnDep = m_vOrderConstr[nC] ;
|
|
bOk = nnDep.second != i ;
|
|
}
|
|
if ( bOk)
|
|
vOkNodes.push_back( i) ;
|
|
}
|
|
// se non ho nodi, allora errore
|
|
if ( vOkNodes.empty())
|
|
return false ;
|
|
// scelgo l'ultimo ( per percorsi OPEN)
|
|
iFirst = vOkNodes.back() ;
|
|
return true ;
|
|
}
|
|
|
|
/* ------------------------------------------------------------------------- */
|
|
bool
|
|
ShortestPath::ChooseNextNode( NODE* pPath, unsigned nSize, unsigned& jNext, bool bNearVsFar)
|
|
{
|
|
// recupero i nodi non inseriti nel path
|
|
jNext = -1 ;
|
|
vector<unsigned> vUninstertedNodes ; vUninstertedNodes.reserve( m_nNumPnts) ;
|
|
for ( unsigned nInd = 0 ; nInd < m_nNumPnts ; ++ nInd) {
|
|
bool bIn = false ;
|
|
NODE* pNode = pPath ;
|
|
for ( unsigned nNode = 0 ; nNode < nSize && ! bIn ; ++ nNode) {
|
|
bIn = ( pNode->nPos == nInd) ;
|
|
pNode = pNode->pPrev ;
|
|
}
|
|
if ( ! bIn)
|
|
vUninstertedNodes.push_back( nInd) ;
|
|
}
|
|
// se tutti i nodi sono inseriti, allora non faccio nulla
|
|
if ( vUninstertedNodes.empty())
|
|
return true ;
|
|
// se un solo nodo non inserito, allora non ho altra scelta
|
|
if ( vUninstertedNodes.size() == unsigned( 1)) {
|
|
jNext = vUninstertedNodes[0] ;
|
|
return true ;
|
|
}
|
|
// definisco un vettore dei soli nodi che posso inserire
|
|
vector<unsigned> vOkNodes ; vOkNodes.reserve( m_nNumPnts) ;
|
|
// scorro i nodi che devo ancora posizionare
|
|
for ( unsigned j : vUninstertedNodes) {
|
|
/*
|
|
* l'ultimo nodo inserito è l'i-esimo, e il successivo sarà il j-esimo ( i ---> j)
|
|
* devo controllare che tra i nodi inseriti non ci sia un nodo k tale per cui viene violato
|
|
* il vincolo ( k, j)
|
|
*/
|
|
// controllo che l'arco ( i --> j) sia valido
|
|
if ( ! m_Available[ Index( pPath->nPos, j)])
|
|
continue ;
|
|
// scorro i vincoli
|
|
bool bOk = true ;
|
|
for ( unsigned nC = 0 ; nC < m_vOrderConstr.size() && bOk ; ++ nC) {
|
|
// recupero il vincolo ( a, b)
|
|
const INTINT& nnDep = m_vOrderConstr[nC] ;
|
|
// controllo se esiste un vincolo del tipo ( ?, j)
|
|
if ( nnDep.second == j) {
|
|
// in questo caso controllo se esiste un nodo k != j che viola il vincolo ( k, j)
|
|
for ( unsigned k = 0 ; k < vUninstertedNodes.size() && bOk ; ++ k) {
|
|
if ( vUninstertedNodes[k] != j)
|
|
bOk = ( vUninstertedNodes[k] != nnDep.first) ;
|
|
}
|
|
}
|
|
}
|
|
// se vincolo non violato, allora il nodo j può essere inserito
|
|
if ( bOk)
|
|
vOkNodes.push_back( j) ;
|
|
}
|
|
// se non posso inserire alcun nodo, allora errore
|
|
if ( vOkNodes.empty())
|
|
return false ;
|
|
// se un solo nodo possibile, allora è quello
|
|
if ( vOkNodes.size() == unsigned( 1)) {
|
|
jNext = vOkNodes[0] ;
|
|
return true ;
|
|
}
|
|
// altrimenti seleziono il nodo j-esimo tale per cui l'arco ( i --> j) ha costo minimo/assimo ( bNearVsFar)
|
|
int nRefDist = bNearVsFar ? MAXDIST : -1 ;
|
|
for ( unsigned j : vOkNodes) {
|
|
int nDist = int( ArcCost( pPath->nPos, j)) ;
|
|
bool bUpdate = false ;
|
|
if ( bNearVsFar)
|
|
bUpdate = ( nDist < nRefDist) ;
|
|
else
|
|
bUpdate = ( nDist > nRefDist) ;
|
|
if ( bUpdate) {
|
|
nRefDist = nDist ;
|
|
jNext = j ;
|
|
}
|
|
}
|
|
return true ;
|
|
} |