PlanarModule.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_PLANAR_MODULE_H
#define OGDF_PLANAR_MODULE_H

//=========================================================
// Main functions:
//
// planarityTest(Graph &G)  Tests a graph for planarity.
//
// planarEmbed(Graph &G)  Tests a graph for planarity and returns
//                        a planar embedding if G is planar.
//
//=========================================================

#include <ogdf/basic/EdgeArray.h>
#include <ogdf/basic/NodeArray.h>
#include <ogdf/basic/SList.h>

namespace ogdf {


class OGDF_EXPORT PlanarModule{

public:

    PlanarModule() {};
    ~PlanarModule() {};

    // Returns true, if G is planar, false otherwise.
    bool planarityTest(Graph &G);
    bool planarityTest(const Graph &G);

    // Returns true, if G is planar, false otherwise.
    // If true, G contains a planar embedding.
    bool planarEmbed(Graph &G){return preparation(G,true);}

private:

    // Prepares the planarity test and the planar embedding
    bool preparation(Graph &G,bool embed);

    // Performs a planarity test on a biconnected component
    // of G. numbering contains an st-numbering of the component.
    bool doTest(Graph &G,NodeArray<int> &numbering);

    // Performs a planarity test on a biconnected component
    // of G and embedds it planar. 
    // numbering contains an st-numbering of the component.
    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;



};

}
#endif