BoothLueker.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/List.h>
#include <ogdf/basic/SList.h>
#include <ogdf/basic/basic.h>
#include <ogdf/planarity/PlanarityModule.h>
 
namespace ogdf {
 
 
class OGDF_EXPORT BoothLueker : public PlanarityModule {
public:
    BoothLueker() { }
 
    ~BoothLueker() { }
 
    virtual bool isPlanarDestructive(Graph& G) override;
 
    virtual bool isPlanar(const Graph& G) override;
 
    virtual bool planarEmbed(Graph& G) override { return preparation(G, true); }
 
 
    virtual bool planarEmbedPlanarGraph(Graph& G) override { return preparation(G, true); }
 
private:
    bool preparation(Graph& G, bool embed);
 
    bool doTest(Graph& G, NodeArray<int>& numbering);
 
    bool doEmbed(Graph& G, NodeArray<int>& numbering, EdgeArray<edge>& backTableEdges,
            EdgeArray<edge>& forwardTableEdges);
 
    // Used by doEmbed. Computes an entire embedding from an
    // upward embedding.
    void entireEmbed(Graph& G, NodeArray<SListPure<adjEntry>>& entireEmbedding,
            NodeArray<SListIterator<adjEntry>>& adjMarker, NodeArray<bool>& mark, node v);
 
    void prepareParallelEdges(Graph& G);
 
 
    //private Members for handling parallel edges
    EdgeArray<ListPure<edge>> m_parallelEdges;
    EdgeArray<bool> m_isParallel;
    int m_parallelCount;
};
 
}