CrossingMinimizationModule.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/GraphCopy.h>
#include <ogdf/basic/GraphList.h>
#include <ogdf/basic/Module.h>
#include <ogdf/basic/Timeouter.h>
#include <ogdf/basic/basic.h>
#include <ogdf/basic/memory.h>
 
#include <cstdint>
 
namespace ogdf {
class PlanRep;
 
class OGDF_EXPORT CrossingMinimizationModule : public Module, public Timeouter {
public:
    CrossingMinimizationModule() { }
 
    CrossingMinimizationModule(const CrossingMinimizationModule& cmm) : Timeouter(cmm) { }
 
    virtual ~CrossingMinimizationModule() { }
 
    virtual CrossingMinimizationModule* clone() const = 0;
 
 
    ReturnType call(PlanRep& pr, int cc, int& crossingNumber,
            const EdgeArray<int>* pCostOrig = nullptr,
            const EdgeArray<bool>* pForbiddenOrig = nullptr,
            const EdgeArray<uint32_t>* pEdgeSubGraphs = nullptr) {
        return doCall(pr, cc, pCostOrig, pForbiddenOrig, pEdgeSubGraphs, crossingNumber);
    }
 
 
    ReturnType operator()(PlanRep& pr, int cc, int& crossingNumber,
            const EdgeArray<int>* pCostOrig = nullptr,
            const EdgeArray<bool>* pForbiddenOrig = nullptr,
            const EdgeArray<uint32_t>* pEdgeSubGraphs = nullptr) {
        return call(pr, cc, crossingNumber, pCostOrig, pForbiddenOrig, pEdgeSubGraphs);
    }
 
protected:
 
    virtual ReturnType doCall(PlanRep& pr, int cc, const EdgeArray<int>* pCostOrig,
            const EdgeArray<bool>* pForbiddenOrig, const EdgeArray<uint32_t>* pEdgeSubGraphs,
            int& crossingNumber) = 0;
 
    static int computeCrossingNumber(GraphCopy& graphCopy, const EdgeArray<int>* pCost,
            const EdgeArray<uint32_t>* pEdgeSubGraphs) {
        if (pCost == nullptr) {
            return graphCopy.numberOfNodes() - graphCopy.original().numberOfNodes();
        } else {
            int crossingNumber = 0;
            for (node v : graphCopy.nodes) {
                if (graphCopy.isDummy(v)) {
                    // Dummy node (crossing) found, calculate its cost.
                    edge e1 = graphCopy.original(v->firstAdj()->theEdge());
                    edge e2 = graphCopy.original(v->lastAdj()->theEdge());
                    if (pEdgeSubGraphs != nullptr) {
                        int subgraphCounter = 0;
                        for (int i = 0; i < 32; i++) {
                            if (((*pEdgeSubGraphs)[e1] & (1 << i)) != 0
                                    && ((*pEdgeSubGraphs)[e2] & (1 << i)) != 0) {
                                subgraphCounter++;
                            }
                        }
                        crossingNumber += (subgraphCounter * (*pCost)[e1] * (*pCost)[e2]);
                    } else {
                        crossingNumber += (*pCost)[e1] * (*pCost)[e2];
                    }
                }
            }
            return crossingNumber;
        }
    }
 
    OGDF_MALLOC_NEW_DELETE
};
 
}