NodeColoringWigderson.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/basic.h>
#include <ogdf/graphalg/NodeColoringModule.h>
#include <ogdf/graphalg/NodeColoringSequential.h>
#include <ogdf/graphalg/NodeColoringSimple.h>
 
#include <cmath>
 
namespace ogdf {
template<class E>
class List;
 
class OGDF_EXPORT NodeColoringWigderson : public NodeColoringModule {
public:
    enum class MaxDegreeProcedure {
        smallestIndex, 
        minDegreeRecursion, 
        maxDegreeRecursion, 
        minDegreeOriginal, 
        maxDegreeOriginal, 
        minDegreeNeighbors, 
        maxDegreeNeighbors, 
    };
 
    enum class RecursionAnchorProcedure {
        trivialColoring, 
        sequentialColoringSimple, 
        sequentialColoringDegree, 
        pooled, 
    };
 
    enum class BruteForceProcedure {
        sequentialColoringSimple, 
        sequentialColoringDegree, 
        pooled, 
    };
 
    NodeColoringWigderson()
        : m_coloringSimple()
        , m_sequentialColoring()
        , m_searchProcedure(SearchProcedure::wigdersonSearch)
        , m_maxDegreeProcedure(MaxDegreeProcedure::smallestIndex)
        , m_recursionAnchorProcedure(RecursionAnchorProcedure::pooled)
        , m_bruteForceProcedure(BruteForceProcedure::pooled) { }
 
    inline void setSearchProcedure(SearchProcedure searchProcedure) {
        m_searchProcedure = searchProcedure;
    }
 
    inline void setMaxDegreeProcedure(MaxDegreeProcedure maxDegreeProcedure) {
        m_maxDegreeProcedure = maxDegreeProcedure;
    }
 
    inline void setRecursionAnchorProcedure(RecursionAnchorProcedure recursionAnchorProcedure) {
        m_recursionAnchorProcedure = recursionAnchorProcedure;
    }
 
    inline void setBruteForceProcedure(BruteForceProcedure bruteForceProcedure) {
        m_bruteForceProcedure = bruteForceProcedure;
    }
 
    virtual NodeColor call(const Graph& graph, NodeArray<NodeColor>& colors,
            NodeColor start = 0) override;
 
private:
    NodeColoringSimple m_coloringSimple;
    NodeColoringSequential m_sequentialColoring;
    SearchProcedure m_searchProcedure;
    MaxDegreeProcedure m_maxDegreeProcedure;
    RecursionAnchorProcedure m_recursionAnchorProcedure;
    BruteForceProcedure m_bruteForceProcedure;
 
    inline int wigdersonFunction(int n, int k) const {
        OGDF_ASSERT(n >= 0);
        OGDF_ASSERT(k >= 1);
        return std::ceil(std::pow(n, 1.0 - (1.0 / (static_cast<double>(k) - 1.0))));
    }
 
    bool wigdersonCaller(const Graph& graph, NodeArray<NodeColor>& colors, NodeColor& color, int k);
 
    bool wigdersonRecursive(const Graph& graph, NodeArray<NodeColor>& colors, NodeColor& color,
            int k, NodeArray<int>& degreesOriginal, List<node>& nodesToBeColored);
 
    struct SearchWrapperWigderson : public SearchWrapper {
        SearchWrapperWigderson(NodeColoringWigderson& coloringWigderson, const Graph& graph,
                NodeArray<NodeColor>& colors)
            : m_coloring(coloringWigderson), m_graph(graph), m_colors(colors) { }
 
        bool step(int k) override {
            NodeColor start = NodeColor(1);
            return m_coloring.wigdersonCaller(m_graph, m_colors, start, k);
        }
 
        NodeColoringWigderson& m_coloring;
        const Graph& m_graph;
        NodeArray<NodeColor>& m_colors;
    };
};
}