FUPSSimple.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/CombinatorialEmbedding.h>
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/GraphList.h>
#include <ogdf/basic/Module.h>
#include <ogdf/basic/basic.h>
#include <ogdf/upward/FUPSModule.h>
 
namespace ogdf {
class GraphCopy;
class UpwardPlanRep;
template<class E>
class List;
 
class OGDF_EXPORT FUPSSimple : public FUPSModule {
public:
    FUPSSimple() : m_nRuns(0) { }
 
    // destructor
    ~FUPSSimple() { }
 
    // options
 
    void runs(int nRuns) { m_nRuns = nRuns; }
 
    int runs() const { return m_nRuns; }
 
    adjEntry getAdjEntry(const CombinatorialEmbedding& Gamma, node v, face f) {
        adjEntry adjFound = nullptr;
        for (adjEntry adj : v->adjEntries) {
            if (Gamma.rightFace(adj) == f) {
                adjFound = adj;
                break;
            }
        }
 
        OGDF_ASSERT(Gamma.rightFace(adjFound) == f);
 
        return adjFound;
    }
 
protected:
    virtual Module::ReturnType doCall(UpwardPlanRep& UPR, List<edge>& delEdges) override;
 
 
private:
    int m_nRuns; 
 
    void computeFUPS(UpwardPlanRep& UPR, List<edge>& delEdges);
 
    /*
     * @param GC The Copy of the input graph G.
     * @param &delEdges The deleted edges (edges of G).
     * @param random compute a random span tree
     * @multisource true, if the original graph got multisources. In this case, the incident edges of
     *  the source are allways included in the span tree
     */
    void getSpanTree(GraphCopy& GC, List<edge>& delEdges, bool random);
 
    /*
     * Function use by geSpannTree to compute the spannig tree.
     */
    void dfs_visit(const Graph& G, edge e, NodeArray<bool>& visited, EdgeArray<bool>& treeEdges,
            bool random);
 
    // construct a merge graph with repsect to gamma and its test acyclicity
    bool constructMergeGraph(GraphCopy& M, adjEntry adj_orig, const List<edge>& del_orig);
};
 
}