FaceSinkGraph.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/CombinatorialEmbedding.h>
#include <ogdf/basic/NodeArray.h>
#include <ogdf/basic/FaceArray.h>
#include <ogdf/basic/SList.h>
 
 
namespace ogdf {
 
 
class OGDF_EXPORT FaceSinkGraph : public Graph
{
public:
    FaceSinkGraph(const ConstCombinatorialEmbedding &E, node s);
 
    FaceSinkGraph() : m_pE(nullptr) { }
 
 
    void init(const ConstCombinatorialEmbedding &E, node s);
 
 
    const Graph &originalGraph() const {
        return *m_pE;
    }
 
    const ConstCombinatorialEmbedding  &originalEmbedding() const {
        return *m_pE;
    }
 
    node originalNode(node v) const {
        return m_originalNode[v];
    }
 
    face originalFace(node v) const {
        return m_originalFace[v];
    }
 
    // returns true iff node v in the face-sink graph corresponds to a
    // face in E containing the source
    bool containsSource(node v) const {
        return m_containsSource[v];
    }
 
    node possibleExternalFaces(SList<face> &externalFaces) {
        node v_T = checkForest();
        if (v_T != nullptr)
            gatherExternalFaces(m_T,nullptr,externalFaces);
        return v_T;
    }
 
 
    node faceNodeOf(edge e) {
        return dfsFaceNodeOf(m_T,nullptr,
            m_pE->rightFace(e->adjSource()),m_pE->rightFace(e->adjTarget()));
    }
 
 
    node faceNodeOf(face f) {
        return dfsFaceNodeOf(m_T,nullptr,f,nullptr);
    }
 
 
 
    void stAugmentation(
        node h,                       // node corresponding to external face
        Graph &G,                     // original graph (not const)
        SList<node> &augmentedNodes,  // list of augmented nodes
        SList<edge> &augmentedEdges); // list of augmented edges
 
 
    void stAugmentation(
        node  h,                      // node corresponding to external face
        Graph &G,                     // original graph (not const)
        node  &superSink,             // super sink
        SList<edge> &augmentedEdges); // list of augmented edges
 
    // the ext. face muss be set
    void sinkSwitches(FaceArray< List<adjEntry> > &faceSwitches);
 
private:
    void doInit();
 
    bool dfsCheckForest(
        node v,                   // current node
        node parent,              // its parent in tree
        NodeArray<bool> &visited, // not already visited ?
        // number of internal vertices of G in current tree
        int &nInternalVertices);
 
 
    void gatherExternalFaces(
        node v,                      // current node
        node parent,                 // its parent
        SList<face> &externalFaces); // returns list of possible external faces
 
    node dfsFaceNodeOf(node v, node parent,face f1, face f2);
 
    node dfsStAugmentation(
        node v,                       // current node
        node parent,                  // its parent
        Graph &G,                     // original graph (not const)
        SList<node> &augmentedNodes,  // list of augmented nodes
        SList<edge> &augmentedEdges); // list of augmented edges
 
    node dfsStAugmentation(
        node v,                       // current node
        node parent,                  // its parent
        Graph &G,                     // original graph (not const)
        SList<edge> &augmentedEdges); // list of augmented edges
 
 
    const ConstCombinatorialEmbedding *m_pE;
    node m_source; 
    node m_T;      
 
    NodeArray<node> m_originalNode;   
    NodeArray<face> m_originalFace;   
    NodeArray<bool> m_containsSource; 
 
#if 0
    void dfsFST(node v, //current node
        node parent, //parent of v
        FaceArray< List<adjEntry> > &faceSwitches,
        NodeArray<bool> &visited);
#endif
 
    node checkForest();
};
 
}