PlanarSubgraphModule.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/GraphCopy.h>
#include <ogdf/basic/List.h>
#include <ogdf/basic/Module.h>
#include <ogdf/basic/Thread.h>
#include <ogdf/basic/Timeouter.h>
#include <ogdf/basic/basic.h>
#include <ogdf/basic/memory.h>
 
#include <algorithm>
 
namespace ogdf {
 
template<typename TCost>
class PlanarSubgraphModule : public Module, public Timeouter {
    unsigned int m_maxThreads; 
 
public:
    PlanarSubgraphModule() {
#ifdef OGDF_MEMORY_POOL_NTS
        m_maxThreads = 1;
#else
        m_maxThreads = max(1u, Thread::hardware_concurrency());
#endif
    }
 
    ReturnType call(const Graph& G, const EdgeArray<TCost>& cost, const List<edge>& preferredEdges,
            List<edge>& delEdges, bool preferredImplyPlanar = false) {
        return doCall(G, preferredEdges, delEdges, &cost, preferredImplyPlanar);
    }
 
    ReturnType call(const Graph& G, const List<edge>& preferredEdges, List<edge>& delEdges,
            bool preferredImplyPlanar = false) {
        return doCall(G, preferredEdges, delEdges, nullptr, preferredImplyPlanar);
    }
 
    ReturnType call(const Graph& G, const EdgeArray<TCost>& cost, List<edge>& delEdges) {
        List<edge> preferredEdges;
        return doCall(G, preferredEdges, delEdges, &cost);
    }
 
    ReturnType call(const Graph& G, List<edge>& delEdges) {
        List<edge> preferredEdges;
        return doCall(G, preferredEdges, delEdges);
    }
 
    ReturnType operator()(const Graph& G, const List<edge>& preferredEdges, List<edge>& delEdges,
            bool preferredImplyPlanar = false) {
        return call(G, preferredEdges, delEdges, preferredImplyPlanar);
    }
 
    ReturnType operator()(const Graph& G, List<edge>& delEdges) { return call(G, delEdges); }
 
    ReturnType callAndDelete(GraphCopy& GC, const List<edge>& preferredEdges,
            List<edge>& delOrigEdges, bool preferredImplyPlanar = false) {
        List<edge> delEdges;
        ReturnType retValue = call(GC, preferredEdges, delEdges, preferredImplyPlanar);
        if (isSolution(retValue)) {
            for (edge eCopy : delEdges) {
                delOrigEdges.pushBack(GC.original(eCopy));
                GC.delEdge(eCopy);
            }
        }
        return retValue;
    }
 
    ReturnType callAndDelete(GraphCopy& GC, List<edge>& delOrigEdges) {
        List<edge> preferredEdges;
        return callAndDelete(GC, preferredEdges, delOrigEdges);
    }
 
    virtual PlanarSubgraphModule* clone() const = 0;
 
    unsigned int maxThreads() const { return m_maxThreads; }
 
    void maxThreads(unsigned int n) {
#ifndef OGDF_MEMORY_POOL_NTS
        m_maxThreads = n;
#endif
    }
 
protected:
    // computes set of edges delEdges, which have to be deleted
    // in order to get a planar subgraph; edges in preferredEdges
    // should be contained in planar subgraph
    // must be implemented by derived classes!
    virtual ReturnType doCall(const Graph& G, const List<edge>& preferredEdges, List<edge>& delEdges,
            const EdgeArray<TCost>* pCost = nullptr, bool preferredImplyPlanar = false) = 0;
 
    OGDF_MALLOC_NEW_DELETE
};
 
}