---

main.cpp

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

#include <iostream>


#include "config.h"
#include "data_structures/mst.h"
#include "data_structures/edgeVector.cpp"
#include "utils/logging.h"
#include "utils/utils.h"

DS_LOGGING1( Logging logging("log.txt") );

#include "buckets/buckets.cpp"
#include "priority_queue/pQueue.cpp"
#include "utils/generate.cpp"
#include "utils/importExport.cpp"
#include "base_case/kruskal.cpp"
#include "utils/parameters.h"


void abortAfterNodeReducing(std::string filename, InternalMemoryBucket *reducedGraph)
{
    if (filename != "") {
        // write reduced graph to the given file
        std::ofstream outFile(filename.c_str());
        // dummy EdgeVector in order to avoid a compiler error:
        // An instance of EdgeVector<RelabeledEdge> is needed to provide
        // a suitable output operator for intMemBucket.
        EdgeVector<RelabeledEdge> dummy(0,0); 
        outFile << 'r' << std::endl << *reducedGraph;
        DS_LOGGING1( logging.events().push_back(
                         LoggingEvent("reduced graph written to file")) );
    }
    std::cout << std::endl << "abort after the 'node reducing'-phase" << std::endl;    
}


int main(int argc, char *argv[])
{
    DS_LOGGING1( logging.events().push_back(LoggingEvent("begin")) );
    
    Parameters param(argc, argv); // parse the command-line arguments

    DS_USE_BUCKETS(
        typedef Buckets<DS_EXT_BUCKET_SIZE> MyBuckets;
        // compute the number of buckets that are needed to store the edges of all nodes
        MyBuckets::BucketID noOfBuckets =
            MyBuckets::noOfExtBuckets(param.noOfNodes(),
                                      param.noOfNodesInInternalMemory());
        
        DS_VERBOSE1( std::cout << "number of external buckets = "
                               << noOfBuckets << std::endl;
                     memoryUsageForecast(param.noOfNodes(),
                                         param.noOfNodesInInternalMemory(),
                                         noOfBuckets) );
    )

    // INPUT
    EdgeVector<> * inputGraph;

    if (param.randomGraph()) {
        // generate random graph
        inputGraph = generateRandomGraph(param.randomGraphNoOfNodes(),
                                         param.randomGraphNoOfEdges());

        DS_LOGGING1( logging.setProblemInstance(
                        new LoggingRandomGraph(param.randomGraphNoOfNodes(),
                                               param.randomGraphNoOfEdges(),
                                               param.noOfNodesInInternalMemory())) );   
    }
    if (param.gridGraph()) {
        // generate grid graph
        inputGraph = generateGridGraph(param.gridGraphNoOfNodesX(),
                                       param.gridGraphNoOfNodesY());
        
        DS_LOGGING1( logging.setProblemInstance(
                        new LoggingGridGraph(param.gridGraphNoOfNodesX(),
                                             param.gridGraphNoOfNodesY(),
                                             param.noOfNodesInInternalMemory())) );
    }
    if (param.geometricGraph()) {
        // generate geometric graph
        inputGraph = generateGeometricGraph(param.geometricGraphNoOfNodes(),
                                            param.geometricGraphNoOfNeighbours());
        
        DS_LOGGING1( logging.setProblemInstance(
                        new LoggingGeometricGraph(param.geometricGraphNoOfNodes(),
                                                  param.geometricGraphNoOfNeighbours(),
                                                  inputGraph->noOfEdges(),
                                                  param.noOfNodesInInternalMemory())) );
    }
    if (param.importInputFilename() != "") {
        // import graph from file
        DS_VERBOSE1( std::cout << std::endl << "import graph" << std::endl );
        inputGraph = importEdgeVector( param.importInputFilename() );

        DS_LOGGING1( logging.setProblemInstance(
                        new LoggingImportedGraph(inputGraph->noOfNodes(),
                                                 inputGraph->noOfEdges(),
                                                 param.noOfNodesInInternalMemory(),
                                                 param.importInputFilename())) );
    }
    
    // export input graph
    if (param.exportInputFilename() != "") {
        DS_VERBOSE1( std::cout << std::endl << "export graph" << std::endl );
        
        if ( param.exportInputFormatAdjacencyList() ) {
            // export format: adjacency lists
            std::ofstream outFile(param.exportInputFilename().c_str());
            exportEdgeVectorAdjList(outFile, *inputGraph);
        }
        else {
            if ( param.exportInputFormatCompressed() ) {
                // export format: compressed
                exportEdgeVectorCompressed(param.exportInputFilename(), *inputGraph);   
            }
            else {
                // export format: list of edges
                std::ofstream outFile(param.exportInputFilename().c_str());
                outFile << *inputGraph; 
            }
        }
        if ( param.quitAfterExporting() ) {
            // quit after exporting
            std::cout << std::endl
                      << "quit after exporting the input graph." << std::endl;
            exit(0);
        }
    }
    
    DS_LOGGING1( logging.events().push_back(LoggingEvent("graph generated/imported")) );


    
    MST result; // the resulting MST
    
    // PROCESSING
    if ( param.noOfNodes() <= param.noOfNodesInInternalMemory() ) {
        // all nodes fit in internal memory
        // ==> Kruskal's algorithm can by applied immediately
        Kruskal<Edge> *kruskal = new Kruskal<Edge>(*inputGraph,result);
        delete kruskal;
    }
    else {
        // node reduction phase is required
        DS_LOGGING1( logMemoryUsage("before buckets") );

        
        // perform node reduction
        
        DS_USE_BUCKETS(
            // buckets implementation
            MyBuckets *buckets = new MyBuckets(*inputGraph, result,
                                               noOfBuckets,
                                               param.noOfNodesInInternalMemory());
            InternalMemoryBucket *intMemBucket = buckets->getIntMemBucket();
            delete buckets;
        )

        DS_USE_PQUEUE(
            // priority queue implementation
            PQueue *pqueue = new PQueue(*inputGraph, result,
                                        param.noOfNodesInInternalMemory());
            InternalMemoryBucket *intMemBucket = pqueue->getIntMemBucket();
            delete pqueue;
        )
            
        // end of 'node reduction'

            
        DS_LOGGING1( logMemoryUsage("after buckets") );

        DS_LOGGING1( logging.events().push_back(LoggingEvent("nodes reduced")) );
        
        if ( param.abortAfterNodeReducing() ) {
            // abort processing after the node reduction phase
            abortAfterNodeReducing( param.reducedGraphFilename(), intMemBucket );
        }
        else {
            // apply Kruskal's algorithm to the reduced graph
            Kruskal<RelabeledEdge> *kruskal =
                new Kruskal<RelabeledEdge>(*intMemBucket,result);
            delete kruskal;
        }
    }
    
    
        
    // OUTPUT
    DS_LOGGING1( logging.setResult(new LoggingResult(result.noOfEdges(),
                                                     result.totalWeight())) );
    DS_LOGGING1( logging.events().push_back(LoggingEvent("end")) );
    DS_LOGGING1( logging.printLog() );

    if (param.outputFilename() != "") {
        // write the computed mst to the given file
        std::ofstream outFile(param.outputFilename().c_str());
        outFile << result;
    }
    
    DS_VERBOSE1( std::cout << std::endl << "finished." << std::endl );
    
    return 0;
}

---