NodeColoringHalldorsson.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>
 
namespace ogdf {
template<class E>
class List;
 
class OGDF_EXPORT NodeColoringHalldorsson : public NodeColoringModule {
public:
    NodeColoringHalldorsson() { m_searchProcedure = SearchProcedure::wigdersonSearch; }
 
    inline void setSearchProcedure(SearchProcedure searchProcedure) {
        m_searchProcedure = searchProcedure;
    }
 
    virtual NodeColor call(const Graph& graph, NodeArray<NodeColor>& colors,
            NodeColor start = 0) override;
 
private:
    SearchProcedure m_searchProcedure;
 
    void performHalldorsson(const Graph& graph, List<node>& independentSet);
 
    bool halldorssonRecursive(const Graph& graph, List<node>& independentSet, int k, double alpha);
 
    struct SearchWrapperHalldorsson : public SearchWrapper {
        SearchWrapperHalldorsson(NodeColoringHalldorsson& coloringHalldorsson, const Graph& graph,
                List<node>& independentSet, double alpha)
            : m_coloring(coloringHalldorsson)
            , m_graph(graph)
            , m_independentSet(independentSet)
            , m_alpha(alpha) { }
 
        bool step(int k) override {
            return m_coloring.halldorssonRecursive(m_graph, m_independentSet, k, m_alpha);
        }
 
        NodeColoringHalldorsson& m_coloring;
        const Graph& m_graph;
        List<node>& m_independentSet;
        double m_alpha;
    };
};
}