FixedUpwardEmbeddingInserter.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_UPWARD_EMBEDDING_INSERTER_H
#define OGDF_FIXED_UPWARD_EMBEDDING_INSERTER_H



#include <ogdf/basic/Module.h>
#include <ogdf/upward/UpwardPlanarModule.h>
#include <ogdf/basic/GraphCopy.h>
#include <ogdf/upward/UpwardPlanRep.h>


namespace ogdf {


class OGDF_EXPORT FixedUpwardEmbeddingInserter : public Module
{
public:
    // construction
    FixedUpwardEmbeddingInserter();

    // destruction
    ~FixedUpwardEmbeddingInserter(){ }

    // Insert all edges in UPR 
    Module::ReturnType call(UpwardPlanRep &UPR, List<edge> origEdges, EdgeArray<int> &cost);

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

private:
    
    const int infty;
    
    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); 
    
    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 isConstraintFeasible(UpwardPlanRep &UPR,
                            const List<edge> &orig_edges,
                            edge e_orig,
                            adjEntry adj, // the last adjEntry of the 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