FixedEmbeddingUpwardEdgeInserter.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_FIXED_EMBEDDING_UPWARD_EDGE_INSERTER_H
#define OGDF_FIXED_EMBEDDING_UPWARD_EDGE_INSERTER_H



#include <ogdf/module/UpwardEdgeInserterModule.h>
#include <ogdf/basic/CombinatorialEmbedding.h>
#include <ogdf/upward/UpwardPlanarModule.h>




namespace ogdf {



class OGDF_EXPORT FixedEmbeddingUpwardEdgeInserter : public UpwardEdgeInserterModule
{
public:
    FixedEmbeddingUpwardEdgeInserter() {}

    ~FixedEmbeddingUpwardEdgeInserter() { } 
    

private:

    bool isUpwardPlanar(Graph &G) 
    {
        UpwardPlanarModule upMod;
        return upMod.upwardPlanarityTest(G);    
    }

    virtual ReturnType doCall(UpwardPlanRep &UPR,
        const List<edge> &origEdges,        
        const EdgeArray<int>  *costOrig = 0,
        const EdgeArray<bool> *forbiddenEdgeOrig = 0
        ); 


    ReturnType insertAll(UpwardPlanRep &UPR,
                        List<edge> &toInsert,       
                        EdgeArray<int>  &cost);


    void staticLock(UpwardPlanRep &UPR, EdgeArray<bool> &locked, const List<edge> &origEdges, edge e_orig);

    void dynamicLock(UpwardPlanRep &UPR, EdgeArray<bool> &locked, face f, adjEntry e_cur);

    void nextFeasibleEdges(UpwardPlanRep &UPR, List<adjEntry> &nextEdges, face f, adjEntry e_cur, EdgeArray<bool> &locked, bool heuristic); 
    
    void minFIP(UpwardPlanRep &UPR,
                List<edge> &origEdges,
                EdgeArray<int> &cost, 
                edge e_orig,
                SList<adjEntry> &path) { getPath(UPR, origEdges, cost, e_orig, path, false); }



    void constraintFIP(UpwardPlanRep &UPR,
                List<edge> &origEdges,
                EdgeArray<int> &cost, 
                edge e_orig,
                SList<adjEntry> &path) { getPath(UPR, origEdges, cost, e_orig, path, true); }

    void getPath(UpwardPlanRep &UPR,
                List<edge> &origEdges,
                EdgeArray<int> &cost, 
                edge e_orig, 
                SList<adjEntry> &path,
                bool heuristic);


    void markUp(const Graph &G, node v, EdgeArray<bool> &markedEdges);


    void markDown(const Graph &G, node v, EdgeArray<bool> &markedEdges);
    
    void feasibleEdges(UpwardPlanRep &UPR,
                        face f, // current face
                        adjEntry adj, // current adjEntry, right face muss be f
                        EdgeArray<bool> &locked, // we compute the dyn. locked edges on the fly with respect to e
                        List<adjEntry> &feasible, // the list of feasible edges in f with respect to e
                        bool heuristic);

    bool isConstraintFeasible(UpwardPlanRep &UPR,
                            const List<edge> &orig_edges,
                            edge e_orig,
                            adjEntry adjCurrent, 
                            adjEntry adjNext, // the next adjEntry of the current insertion path
                            EdgeArray<adjEntry> &predAdj //Array to reconstruction the insertion path
                            );


    bool isConstraintFeasible(UpwardPlanRep &UPR,
                            List<edge> &origEdges,  
                            edge e_orig,
                            SList<adjEntry> &path); 
    

};

} // end namespace ogdf

#endif