PlanarSPQRTree.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_SPQR_TREE_H
#define OGDF_PLANAR_SPQR_TREE_H


#include <ogdf/decomposition/SPQRTree.h>


namespace ogdf {

//---------------------------------------------------------
// PlanarSPQRTree
// extension of class SPQRTree for support of embedded graphs
//---------------------------------------------------------


class OGDF_EXPORT PlanarSPQRTree : public virtual SPQRTree
{
public:

    //
    // a) Access operations
    //

    double numberOfEmbeddings() const {
        return numberOfEmbeddings(rootNode());
    }


    double numberOfEmbeddings(node v) const;


    //
    // b) Update operations
    //


    void reverse(node vT);


    void swap(node vT, edge e1, edge e2);


    void swap(node vT, adjEntry adj1, adjEntry adj2);


    void embed(Graph &G);

    void randomEmbed();


    void randomEmbed(Graph &G) {
        randomEmbed();
        embed(G);
    }


protected:
    void init(bool isEmbedded);
    void adoptEmbedding();
    void setPosInEmbedding(
        NodeArray<SListPure<adjEntry> > &adjEdges,
        NodeArray<node> &currentCopy,
        NodeArray<adjEntry> &lastAdj,
        SListPure<node> &current,
        const Skeleton &S,
        adjEntry adj);

    // Embeda original graph according to embeddings of skeletons.
    void expandVirtualEmbed(node vT,
        adjEntry adjVirt,
        SListPure<adjEntry> &adjEdges);
    void createInnerVerticesEmbed(Graph &G, node vT);

}; // class PlanarSPQRTree


} // end namespace ogdf


#endif