SubgraphUpwardPlanarizer.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) $ 
 ***************************************************************/
 
#ifndef OGDF_SUBGRAPH_UPWARD_PLANARIZER_H
#define OGDF_SUBGRAPH_UPWARD_PLANARIZER_H


#include <ogdf/basic/ModuleOption.h>
#include <ogdf/module/AcyclicSubgraphModule.h>
#include <ogdf/module/FUPSModule.h>
#include <ogdf/module/UpwardEdgeInserterModule.h>
#include <ogdf/module/UpwardPlanarizerModule.h>
#include <ogdf/upward/UpwardPlanRep.h>
#include <ogdf/upward/FUPSSimple.h>
#include <ogdf/upward/FixedEmbeddingUpwardEdgeInserter.h>
#include <ogdf/decomposition/BCTree.h>
#include <ogdf/module/AcyclicSubgraphModule.h>
#include <ogdf/layered/GreedyCycleRemoval.h>


namespace ogdf
{


class OGDF_EXPORT SubgraphUpwardPlanarizer : public UpwardPlanarizerModule
{       

public:
    SubgraphUpwardPlanarizer()
    {
         m_runs = 1;        
        //set default module
        m_subgraph.set(new FUPSSimple());
        m_inserter.set(new FixedEmbeddingUpwardEdgeInserter());
        m_acyclicMod.set(new GreedyCycleRemoval());
    }

    void setSubgraph(FUPSModule *FUPS) {
        m_subgraph.set(FUPS);
    }

    void setInserter(UpwardEdgeInserterModule *pInserter) {
        m_inserter.set(pInserter);
    }   
    
    void setAcyclicSubgraphModule(AcyclicSubgraphModule *acyclicMod) {
        m_acyclicMod.set(acyclicMod);
    }

    int runs() {return m_runs;}
    void runs(int n) {m_runs = n;}
    
protected:

    virtual ReturnType doCall(UpwardPlanRep &UPR,       
        const EdgeArray<int>  &cost,
        const EdgeArray<bool> &forbid);

    ModuleOption<FUPSModule> m_subgraph; 
    ModuleOption<UpwardEdgeInserterModule> m_inserter; 
    ModuleOption<AcyclicSubgraphModule> m_acyclicMod; 
    int m_runs; 

private:
    
    void constructComponentGraphs(BCTree &BC, NodeArray<GraphCopy> &biComps);   
    
    void dfsMerge(const GraphCopy &GC,
             BCTree &BC, 
             NodeArray<GraphCopy> &biComps,                                     
             NodeArray<UpwardPlanRep> &uprs, 
             UpwardPlanRep &UPR_res,
             node parent_BC,
             node current_BC,
             NodeArray<bool> &nodesDone); 
    

    void merge(const GraphCopy &GC,      
         UpwardPlanRep &UPR_res,
         const GraphCopy &block,
         UpwardPlanRep &UPR             
         ); 
};

}

#endif