PlanarSubgraphPQTree.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_SUBGRAPH_PQTREE_H
#define OGDF_PLANAR_SUBGRAPH_PQTREE_H



#include <ogdf/internal/planarity/PQTree.h>
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/SList.h>
#include <ogdf/internal/planarity/PlanarLeafKey.h>
#include <ogdf/internal/planarity/MaxSequencePQTree.h>

namespace ogdf {

// Overriding the function doDestruction (see basic.h)
// Allows deallocation of lists of PlanarLeafKey<whaInfo*>
// and PQLeafKey<edge,indInfo*,bool> in constant time using OREAS
// memory management.


typedef PQLeafKey<edge,whaInfo*,bool> *PtrPQLeafKeyEWB;

template<>
inline bool doDestruction<PtrPQLeafKeyEWB>(const PtrPQLeafKeyEWB*) { return false; }

typedef PlanarLeafKey<whaInfo*> *PtrPlanarLeafKeyW;

template<>
inline bool doDestruction<PtrPlanarLeafKeyW>(const PtrPlanarLeafKeyW*) { return false; }



class PlanarSubgraphPQTree: public MaxSequencePQTree<edge,bool> {

public:

    PlanarSubgraphPQTree() : MaxSequencePQTree<edge,bool>() {};

    virtual ~PlanarSubgraphPQTree() {};

    // Initializes a new PQ-tree with a set of leaves.
    virtual int Initialize(SListPure<PlanarLeafKey<whaInfo*>*> &leafKeys);
        
    // Replaces the pertinent subtree by a set of new leaves.
    void ReplaceRoot(SListPure<PlanarLeafKey<whaInfo*>*> &leafKeys);

    // Reduces a set of leaves.
    virtual bool Reduction(SListPure<PlanarLeafKey<whaInfo*>*> &leafKeys,
                           SList<PQLeafKey<edge,whaInfo*,bool>*> &eliminatedKeys);
private:

    // Replaces a pertinet subtree by a set of new leaves if the root 
    // is full.
    void ReplaceFullRoot(SListPure<PlanarLeafKey<whaInfo*>*> &leafKeys);

    // Replaces a pertinet subtree by a set of new leaves if the root 
    // is partial.
    void ReplacePartialRoot(SListPure<PlanarLeafKey<whaInfo*>*> &leafKeys);

    // Removes the leaves that have been marked for elimination from the PQ-tree.
    void removeEliminatedLeaves(SList<PQLeafKey<edge,whaInfo*,bool>*> &eliminatedKeys);

};  

}

#endif