FaceSinkGraph.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_FACE_SINK_GRAPH_H
#define OGDF_FACE_SINK_GRAPH_H


#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(0) { }


    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 != 0)
            gatherExternalFaces(m_T,0,externalFaces);
        return v_T;
    }


    node faceNodeOf(edge e) {
        return dfsFaceNodeOf(m_T,0,
            m_pE->rightFace(e->adjSource()),m_pE->rightFace(e->adjTarget()));
    }


    node faceNodeOf(face f) {
        return dfsFaceNodeOf(m_T,0,f,0);
    }



    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; 

    /*
    void dfsFST(node v, //current node
        node parent, //parent of v
        FaceArray< List<adjEntry> > &faceSwitches, 
        NodeArray<bool> &visited);
        */

    node checkForest();

    
    adjEntry getAdjEntry(node v, face f);

    
}; // class FaceSinkGraph


} // end namespace ogdf


#endif