MaximumCPlanarSubgraph.h

Go to the documentation of this file.

 /*
 * $Revision: 2299 $
 * 
 * last checkin:
 *   $Author: gutwenger $ 
 *   $Date: 2012-05-07 15:57:08 +0200 (Mon, 07 May 2012) $ 
 ***************************************************************/
 
#ifdef _MSC_VER
#pragma once
#endif

#ifndef OGDF_MAXIMUM_CPLANAR_SUBGRAPH_H
#define OGDF_MAXIMUM_CPLANAR_SUBGRAPH_H

#include <ogdf/basic/Module.h>
#include <ogdf/basic/Timeouter.h>

#include <ogdf/module/CPlanarSubgraphModule.h>
#include <ogdf/cluster/ClusterGraph.h>
#include <ogdf/internal/cluster/MaxCPlanar_Master.h>

#include <ogdf/external/abacus.h>

namespace ogdf {

class OGDF_EXPORT MaximumCPlanarSubgraph : public CPlanarSubgraphModule
{

#ifndef USE_ABACUS
protected:
    ReturnType doCall(const ClusterGraph &G,
            List<edge> &delEdges,
            List<edge> &addedEdges)
    { THROW_NO_ABACUS_EXCEPTION; return retError; }
    
    virtual ReturnType doCall(const ClusterGraph &G,
            List<edge> &delEdges)
    {  THROW_NO_ABACUS_EXCEPTION; return retError; }
};
#else // USE_ABACUS

public:
    MaximumCPlanarSubgraph() : m_heuristicLevel(1), 
                               m_heuristicRuns(1),
                               m_heuristicOEdgeBound(0.4), 
                               m_heuristicNPermLists(5),
                               m_kuratowskiIterations(10),
                               m_subdivisions(10),
                               m_kSupportGraphs(10),
                               m_kuratowskiHigh(0.8),
                               m_kuratowskiLow(0.8),
                               m_perturbation(false),
                               m_branchingGap(0.4),
                               m_time("00:30:00"),
                               m_pricing(true),
                               m_checkCPlanar(false),
                               m_numAddVariables(15),
                               m_strongConstraintViolation(0.3),
                               m_strongVariableViolation(0.3),
                               m_ol(ABA_MASTER::Silent),
                               m_totalTime(-1.0),
                               m_heurTime(-1.0),
                               m_lpTime(-1.0),
                               m_lpSolverTime(-1.0),
                               m_sepTime(-1.0),  
                               m_totalWTime(-1.0),
                               m_numCCons(-1),
                               m_numKCons(-1),
                               m_numLPs(-1),
                               m_numBCs(-1), 
                               m_numSubSelected(-1),
                               m_portaOutput(false) {}
    //destruction
    ~MaximumCPlanarSubgraph() {}

    ReturnType call(const ClusterGraph &G, List<edge> &delEdges,
        List<nodePair> &addedEdges) {
        return doCall(G, delEdges, addedEdges);
    }    
    //setter methods for the  module parameters
    void setHeuristicLevel(int i) {m_heuristicLevel = i;}
    void setHeuristicRuns(int i) {m_heuristicRuns = i;}
    void setHeuristicBound(double d) {m_heuristicOEdgeBound = d;}
    void setNumberOfPermutations(int i) {m_heuristicNPermLists = i;}
    void setNumberOfKuraIterations(int i) {m_kuratowskiIterations = i;}
    void setNumberOfSubDivisions(int i) {m_subdivisions = i;}
    void setNumberOfSupportGraphs(int i) {m_kSupportGraphs = i;}
    void setUpperRounding(double d) {m_kuratowskiHigh = d;}
    void setLowerRounding(double d) {m_kuratowskiLow = d;}
    void setPerturbation(bool b) {m_perturbation = b;}
    void setBranchingGap(double d) {m_branchingGap = d;}
    void setTimeLimit(String s) {m_time = s.cstr();}
    void setOutputLevel(ABA_MASTER::OUTLEVEL o) {m_ol = o;}
    void setPortaOutput(bool b) {m_portaOutput = b;}
    void setPricing(bool b) { m_pricing = b;}
    void setCheckCPlanar(bool b) {m_checkCPlanar = b;}
    void setNumAddVariables(int n) { m_numAddVariables = n;}
    void setStrongConstraintViolation(double d) { m_strongConstraintViolation=d;}
    void setStrongVariableViolation(double d) { m_strongVariableViolation=d;}
    bool & useDefaultCutPool() {return m_defaultCutPool;}
    
     //getter methods for results
     double getTotalTime() {return m_totalTime;}
     double getHeurTime() {return m_heurTime;}
     double getLPTime() {return m_lpTime;}
     double getLPSolverTime() {return m_lpSolverTime;}
     double getSeparationTime() {return m_sepTime;}
     double getTotalWTime() {return m_totalWTime;}
     int    getNumCCons() {return m_numCCons;}
     int    getNumKCons() {return m_numKCons;}
     int    getNumLPs()   {return m_numLPs;}
     int    getNumBCs()   {return m_numBCs;}
     int    getNumSubSelected() {return m_numSubSelected;}
     int    getNumVars() {return m_numVars;}
     
     void writeFeasible(const String &filename, Master &master, 
        ABA_MASTER::STATUS &status);
#ifdef OGDF_DEBUG
    bool getSolByHeuristic(){return m_solByHeuristic;}
#endif
        
    
protected:
    virtual ReturnType doCall(const ClusterGraph &G,
            List<edge> &delEdges)
    {
        List<nodePair> addEdges;
        return doCall(G, delEdges, addEdges);
    }
    
    //as above, also returns the set of edges that were
    //added to construct a completely connected planar
    //graph that contains the computed c-planar subgraph
    virtual ReturnType doCall(const ClusterGraph &G,
            List<edge> &delEdges,
            List<nodePair> &addedEdges);
    
    double getDoubleTime(const ABA_TIMER &act)
    {
        long tempo = act.centiSeconds()+100*act.seconds()+6000*act.minutes()+360000*act.hours();
        return  ((double) tempo)/ 100.0;
    }//getdoubletime
    
    void getBottomUpClusterList(const cluster c, List< cluster > & theList);
    
private:
    //Abacus Master class settings in order of appearance
    int m_heuristicLevel, m_heuristicRuns;
    double m_heuristicOEdgeBound;
    int m_heuristicNPermLists, m_kuratowskiIterations;
    int m_subdivisions, m_kSupportGraphs;
    double m_kuratowskiHigh, m_kuratowskiLow;
    bool m_perturbation;
    double m_branchingGap;
    const char *m_time;
    bool m_pricing;//<! Decides if pricing is used
    bool m_checkCPlanar;//<! If set to true, only c-planarity is checked
    int m_numAddVariables;
    double m_strongConstraintViolation;
    double m_strongVariableViolation;
    
    ABA_MASTER::OUTLEVEL m_ol;
    
    const char* getPortaFileName()
    {
        return "porta.poi";
    }
    const char* getIeqFileName()
    {
        return "porta.ieq";
    }
    const int maxConLength()
    {
        return 1024;
    }
    void outputCons(ofstream &os, 
    ABA_STANDARDPOOL<ABA_CONSTRAINT, ABA_VARIABLE> *connCon, 
    ABA_STANDARDPOOL<ABA_VARIABLE, ABA_CONSTRAINT> *stdVar);
    
    //results
    double m_totalTime;  //<! Total computation time, returned from abacus
    double m_heurTime;   //<! Time spent in heuristic, returned from abacus
    double m_lpTime;     //<! Cpu time spent in members of the LP-interface, returned from abacus
    double m_lpSolverTime; //<! Cpu time required by the LP solver, returned from abacus
    double m_sepTime;  //<! Cpu time spent in the separation of cutting planes, returned from abacus
    double m_totalWTime; //<! Total wall clock time, returned from abacus
    int    m_numCCons;   //<! Number of added connectivity constraints
    int    m_numKCons;   //<! Number of added kuratowski constraints
    int    m_numLPs;     //<! The number of optimized linear programs (LP-relax.).
    int    m_numBCs;     //<! The number of generated subproblems.
    int    m_numSubSelected; //<! The number of subproblems selected by ABACUS.
    int    m_numVars;    //<! The number of global variables.
    bool   m_portaOutput; //<! If set to true, output for PORTA in ieq format is generated.
    bool   m_defaultCutPool; //<! Passed through to master
#ifdef OGDF_DEBUG
    bool m_solByHeuristic;
#endif 

};

#endif // USE_ABACUS

} //end namespace ogdf


#endif // OGDF_MAXIMUM_CPLANAR_SUBGRAPH_H