FUPSSimple.h

Go to the documentation of this file.

/*
 * $Revision: 2299 $
 * 
 * last checkin:
 *   $Author: gutwenger $ 
 *   $Date: 2012-05-07 15:57:08 +0200 (Mon, 07 May 2012) $ 
 ***************************************************************/
 
#ifdef _MSC_VER
#pragma once
#endif


#ifndef OGDF_FUPS_SIMPLE_H
#define OGDF_FUPS_SIMPLE_H


#include <ogdf/module/FUPSModule.h>


namespace ogdf {


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 adj = 0;
        forall_adj(adj, v) {            
            if (Gamma.rightFace(adj) == f)
                break;
        }

        OGDF_ASSERT(Gamma.rightFace(adj) == f);

        return adj;
    }

protected:  

    virtual Module::ReturnType doCall(UpwardPlanRep &UPR,       
        List<edge> &delEdges);  


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, // copy of the original graph, muss be embedded
                            adjEntry adj_orig, // the adjEntry of the original graph, which right face is the ext. Face and adj->theNode() is the source
                            const List<edge> &del_orig); // deleted edges
};

}
#endif