NodeColoringModule.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/NodeSet.h>
#include <ogdf/basic/simple_graph_alg.h>
 
namespace ogdf {
 
class OGDF_EXPORT NodeColoringModule {
public:
    using NodeColor = unsigned int;
 
    enum class SearchProcedure {
        linearSearch, 
        binarySearch, 
        wigdersonSearch 
    };
 
    enum class RamseyProcedure {
        smallestIndex, 
        smallestDegree, 
        largestDegree, 
        extremalDegree, 
    };
 
    NodeColoringModule() : m_ramseyProcedure(RamseyProcedure::smallestIndex) { }
 
    virtual NodeColor call(const Graph& graph, NodeArray<NodeColor>& colors, NodeColor start = 0) = 0;
 
    virtual ~NodeColoringModule() { }
 
    virtual bool checkColoring(const Graph& graph, const NodeArray<NodeColor>& colors) const;
 
    virtual void preprocessGraph(Graph& graph) const { makeSimpleUndirected(graph); }
 
protected:
    RamseyProcedure m_ramseyProcedure;
 
    struct SubsetIterator {
        using Index = int;
 
        Array<node>& m_set;
        Array<Index> m_indices;
        Index m_numElements;
 
        SubsetIterator(Array<node>& set, Index subsetSize)
            : m_set(set), m_indices(subsetSize), m_numElements(subsetSize) {
            OGDF_ASSERT(subsetSize <= set.size());
            for (Index i = 0; i < m_numElements; i++) {
                m_indices[i] = i;
            }
        }
 
        bool isOk() {
            for (Index i = 0; i < m_numElements; i++) {
                if (m_indices[i] > (m_set.size() - m_numElements + i)) {
                    return false;
                }
            }
            return true;
        }
 
        List<node> currentSubset() {
            List<node> result;
            for (Index i = 0; i < m_numElements; i++) {
                result.emplaceBack(m_set[m_indices[i]]);
            }
            return result;
        }
 
        bool advance() {
            for (Index i = m_numElements - 1; i >= 0; i--) {
                m_indices[i]++;
                if (m_indices[i] <= (m_set.size() + i - m_numElements)) {
                    for (int j = i + 1; j < m_numElements; j++) {
                        m_indices[j] = m_indices[i] + j - i;
                    }
                    return true;
                }
            }
            return false;
        }
    };
 
    struct SearchWrapper {
        virtual bool step(int k) = 0;
    };
 
    template<class CONTAINER>
    bool checkIndependentSet(const Graph& graph, const CONTAINER& nodes) const {
        NodeSet<false> nodeSet(graph);
        for (node v : nodes) {
            nodeSet.insert(v);
        }
        for (node v : nodes) {
            for (adjEntry adj : v->adjEntries) {
                if (nodeSet.isMember(adj->twinNode()) && adj->twinNode() != v) {
                    return false;
                }
            }
        }
        return true;
    }
 
    virtual void createBuckets(const Graph& graph, int size, Array<Array<node>>& buckets) const;
 
    template<class LISTITERATOR>
    void getNeighbors(const Graph& graph, LISTITERATOR nodes, List<node>& neighbors) const {
        neighbors.clear();
        NodeArray<bool> isInserted(graph, false);
 
        for (LISTITERATOR its = nodes; its.valid(); its++) {
            node v = (*its);
            OGDF_ASSERT(v != nullptr);
            OGDF_ASSERT(v->graphOf() == &graph);
 
            for (adjEntry adj : v->adjEntries) {
                node twin = adj->twinNode();
                if (!isInserted[twin]) {
                    neighbors.emplaceBack(twin);
                    isInserted[twin] = true;
                }
            }
        }
    }
 
    int getNeighborDegrees(const node& v) const;
 
    template<class LISTITERATOR>
    void getNeighborsComplement(const Graph& graph, LISTITERATOR nodes,
            List<node>& complementNeighbors) const {
        // Preparations step
        complementNeighbors.clear();
        NodeArray<bool> isComplement(graph, true);
 
        // Mark all given nodes as false
        for (LISTITERATOR its = nodes; its.valid(); its++) {
            node v = (*its);
            OGDF_ASSERT(v != nullptr);
            OGDF_ASSERT(v->graphOf() == &graph);
            isComplement[v] = false;
        }
 
        // Mark all neighbors of the given nodes as false
        List<node> neighbors;
        getNeighbors<LISTITERATOR>(graph, nodes, neighbors);
        for (node& v : neighbors) {
            isComplement[v] = false;
        }
 
        // Store all nodes which are part of the complement
        for (node v : graph.nodes) {
            if (isComplement[v]) {
                complementNeighbors.emplaceBack(v);
            }
        }
    }
 
    template<class LISTITERATOR>
    void mergeNodeLists(const Graph& graph, LISTITERATOR firstList, LISTITERATOR secondList,
            List<node>& mergedList) const {
        mergedList.clear();
        NodeArray<bool> isInserted(graph, false);
        List<LISTITERATOR> iterators = {firstList, secondList};
        for (auto& iterator : iterators) {
            for (LISTITERATOR its = iterator; its.valid(); its++) {
                node v = (*its);
                OGDF_ASSERT(v != nullptr);
                OGDF_ASSERT(v->graphOf() == &graph);
                if (!isInserted[v]) {
                    mergedList.emplaceBack(v);
                    isInserted[v] = true;
                }
            }
        }
    }
 
    virtual int getMaximumDegreeNode(const Graph& graph, node& maxDegreeNode) const;
 
    virtual int getMaximumDegreeNodes(const Graph& graph, List<node>& maxDegreeNodes) const;
 
    virtual int getMinimumDegreeNode(const Graph& graph, node& minDegreeNode) const;
 
    virtual int getMinimumDegreeNodes(const Graph& graph, List<node>& minDegreeNodes) const;
 
    virtual NodeColor getMaximumNodeColor(NodeArray<NodeColor>& colors);
 
    virtual void reverseNodeTable(const Graph& graphOrig, const Graph& graphNew,
            const NodeArray<node>& orig2New, NodeArray<node>& new2Orig) const;
 
    virtual void ramseyAlgorithm(const Graph& graph, List<node>& clique,
            List<node>& independentSet) const;
 
    virtual void cliqueRemoval(const Graph& graph, List<node>& independentSet) const;
 
    int searchLinear(SearchWrapper* searchWrapper, int start, int end) const;
 
    int searchBinary(SearchWrapper* searchWrapper, int start, int end) const;
 
    int searchWigderson(SearchWrapper* searchWrapper) const;
};
}