From 50f2130f18e86055892c870c14af5101feb568ff Mon Sep 17 00:00:00 2001 From: "Zancanaro; Carlo" Date: Wed, 21 Nov 2012 01:43:43 +1100 Subject: Implementation stuff. --- clang/lib/Analysis/MCFSimplex.cpp | 68 +++++++++++++++++++++++---------------- 1 file changed, 40 insertions(+), 28 deletions(-) (limited to 'clang/lib/Analysis/MCFSimplex.cpp') diff --git a/clang/lib/Analysis/MCFSimplex.cpp b/clang/lib/Analysis/MCFSimplex.cpp index 4b1b75a..3da685d 100644 --- a/clang/lib/Analysis/MCFSimplex.cpp +++ b/clang/lib/Analysis/MCFSimplex.cpp @@ -30,7 +30,7 @@ /*------------------------------ INCLUDES ----------------------------------*/ /*--------------------------------------------------------------------------*/ -#include "MCFSimplex.h" +#include "clang/Analysis/Analyses/IntervalSolver/MCFSimplex.h" #include #include @@ -116,9 +116,10 @@ using namespace MCFClass_di_unipi_it; optimize the update of the potential. Unfortunately this doesn't work well: for this reason it is set to 0. */ - +#ifndef throw // QUICK HACK #define throw(x) assert(false); +#endif /*--------------------------------------------------------------------------*/ /*--------------------------- FUNCTIONS ------------------------------------*/ @@ -410,7 +411,7 @@ void MCFSimplex::SetAlg( bool UsPrml , char WhchPrc ) MemDeAlloc(false); if( Senstv && ( status != kUnSolved ) ) { nodePType *node = dummyRootP; - for( int i = 0 ; i < n ; i++ ) + for( unsigned int i = 0 ; i < n ; i++ ) node = node->nextInT; node->nextInT = NULL; @@ -483,7 +484,7 @@ void MCFSimplex::SetAlg( bool UsPrml , char WhchPrc ) CreateAdditionalDualStructures(); MemDeAlloc(true); nodeDType *node = dummyRootD; - for( int i = 0 ; i < n ; i++ ) + for( unsigned int i = 0 ; i < n ; i++ ) node = node->nextInT; node->nextInT = NULL; @@ -513,11 +514,12 @@ void MCFSimplex::SetAlg( bool UsPrml , char WhchPrc ) //#endif } #endif - if( newPricingRule == kFirstEligibleArc ) + if( newPricingRule == kFirstEligibleArc ) { if( newUsePrimalSimplex ) arcToStartP = arcsP; else arcToStartD = arcsD; + } if( ( nmax && mmax ) && ( newPricingRule == kCandidateListPivot ) ) MemAllocCandidateList(); @@ -941,13 +943,13 @@ void MCFSimplex::ChgCosts( cCRow NCost , cIndex_Set nms , for( arcDType *arc = arcsD + strt ; arc < (arcsD + stp) ; arc++ ) arc->cost = *(NCost++); - if( Senstv && ( status != kUnSolved ) ) + if( Senstv && ( status != kUnSolved ) ) { if( usePrimalSimplex ) ComputePotential( dummyRootP ); else { #if( QUADRATICCOST == 0 ) for( arcDType *arc = arcsD ; arc != stopArcsD ; arc++ ) - if( arc->ident > BASIC ) + if( arc->ident > BASIC ) { if( GTZ( ReductCost( arc ) , EpsCst ) ) { arc->flow = 0; arc->ident = AT_LOWER; @@ -956,13 +958,15 @@ void MCFSimplex::ChgCosts( cCRow NCost , cIndex_Set nms , arc->flow = arc->upper; arc->ident = AT_UPPER; } + } CreateInitialDModifiedBalanceVector(); PostDVisit( dummyRootD ); #endif } - else + } else { status = kUnSolved; + } } // end( MCFSimplex::ChgCosts ) @@ -993,8 +997,8 @@ void MCFSimplex::ChgCost( Index arc , cCNumber NCost ) node = ( arcsD + arc )->head; ComputePotential( dummyRootD ); - for( arcDType *a = arcsD ; a != stopArcsD ; a++) - if( a->ident > BASIC ) + for( arcDType *a = arcsD ; a != stopArcsD ; a++) + if( a->ident > BASIC ) { if( GTZ( ReductCost( a ) , EpsCst ) ) { a->flow = 0; a->ident = AT_LOWER; @@ -1003,6 +1007,7 @@ void MCFSimplex::ChgCost( Index arc , cCNumber NCost ) a->flow = a->upper; a->ident = AT_UPPER; } + } CreateInitialDModifiedBalanceVector(); PostDVisit( dummyRootD ); @@ -1016,8 +1021,8 @@ void MCFSimplex::ChgCost( Index arc , cCNumber NCost ) /*-------------------------------------------------------------------------*/ -void MCFSimplex::ChgQCoef( cCRow NQCoef , cIndex_Set nms , - cIndex strt , Index stp ) +void MCFSimplex::ChgQCoef( cCRow NQCoef , cIndex_Set , + cIndex , Index stp ) { if( stp > m ) stp = m; @@ -1057,7 +1062,7 @@ void MCFSimplex::ChgQCoef( cCRow NQCoef , cIndex_Set nms , /*-------------------------------------------------------------------------*/ -void MCFSimplex::ChgQCoef( Index arc , cCNumber NQCoef ) +void MCFSimplex::ChgQCoef( Index , cCNumber NQCoef ) { #if( QUADRATICCOST ) if( arc >= m ) @@ -1362,7 +1367,7 @@ void MCFSimplex::CloseArc( cIndex name ) ComputePotential( dummyRootD ); for( arcDType *a = arcsD ; a != stopArcsD ; a++ ) - if( a->ident > BASIC ) + if( a->ident > BASIC ) { if( GTZ( ReductCost( a ) , EpsCst ) ) { a->flow = 0; a->ident = AT_LOWER; @@ -1371,6 +1376,7 @@ void MCFSimplex::CloseArc( cIndex name ) a->flow = a->upper; a->ident = AT_UPPER; } + } } CreateInitialDModifiedBalanceVector(); @@ -2564,11 +2570,12 @@ void MCFSimplex::DualSimplex( void ) while( fine == false ) { /* If node is the root of subtree T2, Dual Simplex jumps to the node (if exists) which follows the last node of T2 */ - if( node == h2 ) + if( node == h2 ) { if( lastNodeOfT2->nextInT ) node = lastNodeOfT2->nextInT; else break; + } // Search arc in the Backward Star of nodes of T1 arcDType *arc = node->firstBs; @@ -2760,7 +2767,6 @@ void MCFSimplex::DualSimplex( void ) theta = leavingArc->flow - leavingArc->upper; // Initial value of theta is the infeasibility of the leaving arc - FNumber t; nodeDType *k1; nodeDType *k2; /* if entering arc is in U, Dual Simplex pushs flow in the cycle @@ -2905,7 +2911,7 @@ void MCFSimplex::DualSimplex( void ) /*--------------------------------------------------------------------------*/ template -void MCFSimplex::UpdateT( A *h , A *k , N *h1 , N *h2 , N *k1 , N *k2 ) +void MCFSimplex::UpdateT( A * , A *k , N * , N *h2 , N *k1 , N *k2 ) { /* In subtree T2 there is a path from node h2 (deepest node of the leaving arc h and root of T2) to node k2 (deepest node of the leaving arc h and @@ -3421,7 +3427,7 @@ MCFSimplex::arcDType* MCFSimplex::RuleDualCandidateListPivot( void ) // Search other arcs to fill the list do { nodeDType *node = nodesD + groupPos; - for( node ; node < stopNodesD ; node += numGroup ) { + for( ; node < stopNodesD ; node += numGroup ) { arcDType *arc = node->enteringTArc; cFNumber flow = arc->flow; if( LTZ( flow , EpsFlw ) ) { @@ -3598,18 +3604,19 @@ void MCFSimplex::PostPVisit( nodePType *r ) // The method controls if "r" is a leaf in T bool rLeaf = false; int i = r - nodesP; - if( r->nextInT ) + if( r->nextInT ) { if( ( r->nextInT )->subTreeLevel <= r->subTreeLevel ) rLeaf = true; else rLeaf = true; + } - if( rLeaf ) // If "r" is a leaf + if( rLeaf ) { // If "r" is a leaf if( ( r->enteringTArc)->head == r ) // If enteringTArc of "r" goes in "r" ( r->enteringTArc )->flow = modifiedBalance[ i ]; else // If enteringTArc of "r" goes out "r" ( r->enteringTArc )->flow = - modifiedBalance[ i ]; - else { // If "r" isn't a leaf + } else { // If "r" isn't a leaf nodePType *desc = r->nextInT; // Call PostPVisit for every child of "r" while( ( desc ) && ( desc->subTreeLevel > r->subTreeLevel ) ) { @@ -3624,12 +3631,13 @@ void MCFSimplex::PostPVisit( nodePType *r ) desc = desc->nextInT; } - if( r != dummyRootP ) + if( r != dummyRootP ) { if( ( r->enteringTArc )->head == r ) // If enteringTArc of "r" goes in "r" ( r->enteringTArc )->flow = modifiedBalance[ i ]; else // If enteringTArc of "r" goes out "r" ( r->enteringTArc )->flow = - modifiedBalance[ i ]; } + } } /*--------------------------------------------------------------------------*/ @@ -3650,11 +3658,12 @@ void MCFSimplex::BalanceFlow( nodePType *r ) else { // The method controls if "r" is a leaf in T bool rLeaf = false; - if( r->nextInT ) + if( r->nextInT ) { if( ( r->nextInT )->subTreeLevel <= r->subTreeLevel ) rLeaf = true; else rLeaf = true; + } if( rLeaf ) // If "r" is a leaf AdjustFlow( r ); // The method controls if entering basic arc in "r" is @@ -3680,7 +3689,7 @@ void MCFSimplex::BalanceFlow( nodePType *r ) void MCFSimplex::AdjustFlow( nodePType *r ) { arcPType *arc = r->enteringTArc; - if( arc >= dummyArcsP ) // If entering arc of "r" is a dummy arc + if( arc >= dummyArcsP ) { // If entering arc of "r" is a dummy arc if( LTZ( arc->flow , EpsFlw ) ) { // If this dummy arc has flow < 0, the algorithm overturns the arc nodePType *temp = arc->tail; @@ -3749,6 +3758,7 @@ void MCFSimplex::AdjustFlow( nodePType *r ) } } } + } /*--------------------------------------------------------------------------*/ @@ -3792,11 +3802,12 @@ void MCFSimplex::PostDVisit( nodeDType *r ) // The method controls if "r" is a leaf in T bool rLeaf = false; int i = r - nodesD; - if( r->nextInT ) + if( r->nextInT ) { if( ( r->nextInT )->subTreeLevel <= r->subTreeLevel ) rLeaf = true; else rLeaf = true; + } if( rLeaf ) // If "r" is a leaf if( ( r->enteringTArc)->head == r ) // If enteringTArc of "r" goes in "r" @@ -3819,12 +3830,13 @@ void MCFSimplex::PostDVisit( nodeDType *r ) desc = desc->nextInT; } - if( r != dummyRootD ) + if( r != dummyRootD ) { if( ( r->enteringTArc )->head == r ) // If enteringTArc of "r" goes in "r" ( r->enteringTArc )->flow = modifiedBalance[ i ]; else // If enteringTArc of "r" goes out "r" ( r->enteringTArc )->flow = - modifiedBalance[ i ]; } + } #endif } @@ -3961,7 +3973,7 @@ void MCFSimplex::PrintDArc( arcDType *arc ) MCFSimplex::nodePType* MCFSimplex::RecoverPNode( Index ind ) { - if( ( ind < 0 ) || ( ind > n ) ) + if( ( ind > n ) ) return( NULL ); if( ind ) return( nodesP + ind - 1 ); @@ -3993,7 +4005,7 @@ MCFSimplex::arcPType* MCFSimplex::RecoverPArc( nodePType *tail , MCFSimplex::nodeDType* MCFSimplex::RecoverDNode( Index ind ) { - if( ( ind < 0 ) || ( ind > n ) ) + if( ( ind > n ) ) return( NULL ); if( ind ) -- cgit v1.2.3