UpwardPlanarSubgraphSimple.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/basic.h>
#include <ogdf/upward/UpwardPlanarSubgraphModule.h>
 
namespace ogdf {
class GraphCopy;
class GraphCopySimple;
template<class E1, class E2>
class Tuple2;
template<class E>
class List;
template<class E>
class SList;
template<class E>
class SListPure;
 
class OGDF_EXPORT UpwardPlanarSubgraphSimple : public UpwardPlanarSubgraphModule {
public:
    // construction
    UpwardPlanarSubgraphSimple() { }
 
    // destruction
    ~UpwardPlanarSubgraphSimple() { }
 
    // computes set of edges delEdges, which have to be deleted
    // in order to get a planar subgraph; edges in preferedEdges
    // should be contained in planar subgraph
    virtual void call(const Graph& G, List<edge>& delEdges) override;
 
    void call(GraphCopy& GC, List<edge>& delEdges);
 
 
private:
    bool checkAcyclic(GraphCopySimple& graphAcyclicTest, SList<Tuple2<node, node>>& tmpAugmented);
 
    void dfsBuildSpanningTree(node v, SListPure<edge>& treeEdges, NodeArray<bool>& visited);
};
 
}