NodeColoringBergerRompel.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/basic.h>
#include <ogdf/graphalg/NodeColoringJohnson.h>
#include <ogdf/graphalg/NodeColoringModule.h>
#include <ogdf/graphalg/NodeColoringSequential.h>
#include <ogdf/graphalg/NodeColoringSimple.h>
#include <ogdf/graphalg/NodeColoringWigderson.h>
 
namespace ogdf {
 
class OGDF_EXPORT NodeColoringBergerRompel : public NodeColoringModule {
public:
    enum class BruteForceProcedure {
        trivialColoring, 
        sequentialColoringSimple, 
        sequentialColoringDegree, 
        johnsonColoring, 
        wigdersonColoring, 
        pooled, 
    };
 
    NodeColoringBergerRompel()
        : m_simpleColoring()
        , m_sequentialColoring()
        , m_johnsonColoring()
        , m_wigdersonColoring()
        , m_searchProcedure(SearchProcedure::wigdersonSearch)
        , m_bruteForceProcedure(BruteForceProcedure::pooled)
        , m_alpha(0.4) { }
 
    inline void setSearchProcedure(SearchProcedure searchProcedure) {
        m_searchProcedure = searchProcedure;
    }
 
    inline void setBruteForceProcedure(BruteForceProcedure bruteForceProcedure) {
        m_bruteForceProcedure = bruteForceProcedure;
    }
 
    inline void setAlpha(double alpha) {
        OGDF_ASSERT(alpha > 0.1);
        m_alpha = alpha;
    }
 
    virtual NodeColor call(const Graph& graph, NodeArray<NodeColor>& colors,
            NodeColor start = 0) override;
 
private:
    NodeColoringSimple m_simpleColoring;
    NodeColoringSequential m_sequentialColoring;
    NodeColoringJohnson m_johnsonColoring;
    NodeColoringWigderson m_wigdersonColoring;
    SearchProcedure m_searchProcedure;
    BruteForceProcedure m_bruteForceProcedure;
    double m_alpha;
 
    bool bergerRompelParameterized(const Graph& graph, NodeArray<NodeColor>& colors,
            NodeColor& color, int k, double alpha);
 
    struct SearchWrapperBergerRompel : public SearchWrapper {
        SearchWrapperBergerRompel(NodeColoringBergerRompel& coloringBergerRompel,
                const Graph& graph, NodeArray<NodeColor>& colors, double alpha)
            : m_coloring(coloringBergerRompel), m_graph(graph), m_colors(colors), m_alpha(alpha) { }
 
        bool step(int k) override {
            NodeColor start = NodeColor(1);
            return m_coloring.bergerRompelParameterized(m_graph, m_colors, start, k, m_alpha);
        }
 
        NodeColoringBergerRompel& m_coloring;
        const Graph& m_graph;
        NodeArray<NodeColor>& m_colors;
        double m_alpha;
    };
};
}