---

pQueue.cpp

/****************************************************
 *  Bachelor Project:                               *
 *  External Memory Minimum Spanning Trees          *
 *  by Dominik Schultes <mail@dominik-schultes.de>  *
 *                                                  *
 *                pQueue.cpp                        *
 *                                                  *
 *  July 22, 2003                                   *
 ****************************************************/


#include "pQueue.h"
#include "../data_structures/duplicatesRemover.h"
#include "../utils/randomizer.h"


void PQueue::initPQueue()
{    
    // create the first external bucket
    _firstExtBucket = new InternalMemoryBucket(_noOfNodesInIntMem,0);

      
    // distribute the edges to the first external bucket and the priority queue
    DS_RANDOMIZE( Randomizer<RandomizerFeistel> randomizer(_graph.noOfNodes()) );
    
    DS_VERBOSE1( std::cout << std::endl
                 << "distribute edges to the first external bucket and the priority queue"
                 << std::endl;
                 Percent percent(_graph.size(), true) );
        
    for (; !_graph.empty(); _graph.pop_back()) {
        DS_DONT_RANDOMIZE( RelabeledEdge edge(_graph.back()) );
        DS_RANDOMIZE( RelabeledEdge edge = randomizer.randomize(_graph.back()) );

        DS_VERBOSE1( percent.printStatus(_graph.size()) );
        DS_VERBOSE2( std::cout << edge << std::endl );
        
        // The source has to be greater than the target.
        if (edge.source() < edge.target()) edge.swap();
        
        // add the current edge to the first external bucket
        // or to the priority queue
        add(edge);
    }

    // delete the input graph
    delete &_graph;

    DS_LOGGING1( logging.events().push_back(
                     LoggingEvent("edges distributed to external buckets")) );
}


void PQueue::reduceNodes()
{
    if ( _pqueue.empty() ) return;
    
    DS_REMOVE_DUPLICATES(
        DuplicatesRemover<PQueue> *duplRem = new DuplicatesRemover<PQueue>(this) );

    // get shortest edge incident to the last node
    RelabeledEdge minWeightEdge( _pqueue.top() );
    _pqueue.pop();
    _result.add( minWeightEdge );

    DS_VERBOSE1( std::cout << std::endl << "reduce nodes" << std::endl;
                 Percent percent( minWeightEdge.source() - _noOfNodesInIntMem );
                 NodeCount processedNodes = 0 );
    
    // Process all edges in the priority queue
    while ( ! _pqueue.empty() ) {
        // get current edge
        RelabeledEdge currentEdge( _pqueue.top() );
        _pqueue.pop();

        // check whether the current edge has the same source vertex as the predecessor
        if ( minWeightEdge.source() == currentEdge.source() ) {
            // throw the old source vertex away
            RelabeledEdgeWithoutSource currentEdgeWithoutSource( currentEdge );
            
            DS_DONT_REMOVE_DUPLICATES(
                // add the relabeled edge to the first external bucket
                // resp. to the priority queue
                add( RelabeledEdge(currentEdgeWithoutSource, minWeightEdge.target()) );
            )
                    
            DS_REMOVE_DUPLICATES(
                // add the edge to the DuplicateRemover
                duplRem->insert( currentEdgeWithoutSource, minWeightEdge.target() );
                
                // clear the DuplicateRemover if this is the last edge incident to the
                // current source vertex
                if ((_pqueue.empty()) ||
                    (_pqueue.top().source() != minWeightEdge.source())) {
                    duplRem->clear( minWeightEdge.target() );
                }
            )
            
        }
        else {
            // the current edge is the shortest one incident to the currently last node
            minWeightEdge = currentEdge;
            _result.add( minWeightEdge );
            
            DS_VERBOSE1( processedNodes++;
                         percent.printStatus(processedNodes) );
        }
    }

    DS_REMOVE_DUPLICATES( delete duplRem );
}

---