ILPClusterPlanarity.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/List.h>
#include <ogdf/basic/Stopwatch.h>
#include <ogdf/basic/basic.h>
#include <ogdf/cluster/ClusterGraph.h>
#include <ogdf/cluster/ClusterPlanarityModule.h>
#include <ogdf/cluster/internal/CP_MasterBase.h>
#include <ogdf/cluster/internal/CPlanarityMaster.h>
 
#include <ogdf/external/abacus.h>
 
#include <cstdint>
#include <iosfwd>
#include <string>
 
namespace abacus {
template<class BaseType, class CoType>
class StandardPool;
} // namespace abacus
 
namespace ogdf {
 
 
class OGDF_EXPORT ILPClusterPlanarity : public ClusterPlanarityModule {
public:
    using NodePairs = List<NodePair>;
    using CP_MasterBase = cluster_planarity::CP_MasterBase;
 
    enum class solmeth { Fallback, New };
 
    ILPClusterPlanarity()
        : 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:20:00")
        , m_pricing(false)
        , m_numAddVariables(15)
        , m_strongConstraintViolation(0.3)
        , m_strongVariableViolation(0.3)
        , m_solmeth(solmeth::New)
        , m_optStatus(abacus::Master::STATUS::Unprocessed)
        , 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_numVars(-1)
        , m_portaOutput(false)
        , m_defaultCutPool(true)
#ifdef OGDF_DEBUG
        , m_solByHeuristic(false)
#endif
    {
    }
 
    //destruction
    ~ILPClusterPlanarity() { }
 
    bool isClusterPlanar(const ClusterGraph& CG, NodePairs& addedEdges);
 
    bool isClusterPlanar(const ClusterGraph& CG) override;
 
    bool isClusterPlanarDestructive(ClusterGraph& CG, Graph& G) override {
        return isClusterPlanar(CG);
    }
 
    bool clusterPlanarEmbedClusterPlanarGraph(ClusterGraph& CG, Graph& G) override;
 
    //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.c_str(); }
 
    void setPortaOutput(bool b) { m_portaOutput = b; }
 
    void setPricing(bool b) { m_pricing = 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
    abacus::Master::STATUS getOptStatus() { return m_optStatus; }
 
    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 char* filename, CP_MasterBase& master, abacus::Master::STATUS& status);
#ifdef OGDF_DEBUG
    bool getSolByHeuristic() { return m_solByHeuristic; }
#endif
 
    solmeth& solutionMethod() { return m_solmeth; }
 
protected:
    // Performs a c-planarity test on CG.
    bool doTest(const ClusterGraph& CG);
 
    //as above, on success also returns the set of edges that were
    //added to construct a completely connected planar graph.
    bool doTest(const ClusterGraph& G, NodePairs& addedEdges);
 
    // Performs a c-planarity test using only a reduced set
    // of allowed extension edges, returns c-planarity status
#if 0
    virtual bool doFastTest(const ClusterGraph &G);
#endif
 
    double getDoubleTime(const Stopwatch& act) {
        int64_t tempo = act.centiSeconds() + 100 * act.seconds() + 6000 * act.minutes()
                + 360000 * act.hours();
        return ((double)tempo) / 100.0;
    }
 
    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;
    string m_time;
    bool m_pricing; //<! Decides if pricing is used
    int m_numAddVariables;
    double m_strongConstraintViolation;
    double m_strongVariableViolation;
 
    solmeth m_solmeth; 
 
    const char* getPortaFileName() { return "porta.poi"; }
 
    const char* getIeqFileName() { return "porta.ieq"; }
 
    int maxConLength() { return 1024; }
 
    void outputCons(std::ofstream& os,
            abacus::StandardPool<abacus::Constraint, abacus::Variable>* connCon,
            abacus::StandardPool<abacus::Variable, abacus::Constraint>* stdVar);
 
    //results
    abacus::Master::STATUS m_optStatus; //<! Status of optimization, returned from abacus
    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
};
 
}