FaceSinkGraph.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/CombinatorialEmbedding.h>
#include <ogdf/basic/FaceArray.h>
#include <ogdf/basic/NodeArray.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();
};
 
}