FixedEmbeddingUpwardEdgeInserter.h

Go to the documentation of this file.

/*
 * $Revision: 2524 $
 *
 * last checkin:
 *   $Author: gutwenger $
 *   $Date: 2012-07-03 09:54:22 +0200 (Tue, 03 Jul 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