EdgeIndependentSpanningTrees.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/List.h>
#include <ogdf/basic/basic.h>
 
#include <functional>
#include <utility>
#include <vector>
 
namespace ogdf {
 
class OGDF_EXPORT EdgeIndependentSpanningTrees {
public:
    using Solution = EdgeArray<std::pair<unsigned int, unsigned int>>;
 
    EdgeIndependentSpanningTrees() : m_G {nullptr}, m_root {nullptr} { }
 
    EdgeIndependentSpanningTrees(const Graph& G)
        : EdgeIndependentSpanningTrees {G, G.firstNode()} { }
 
    EdgeIndependentSpanningTrees(const Graph& G, node root) : m_G {&G}, m_root {root} { }
 
    ~EdgeIndependentSpanningTrees() = default;
 
    bool findOne(unsigned int k, Solution& f) const;
 
    List<Solution> findAll(unsigned int k) const;
 
    List<Solution> findAllPerm(unsigned int k) const;
 
    const Graph* getGraph() const { return m_G; }
 
    void setGraph(const Graph& G) {
        OGDF_ASSERT(!G.empty());
        m_G = &G;
    }
 
    node getRoot() const { return m_root; }
 
    void setRoot(node root) { m_root = root; }
 
protected:
    void findDo(unsigned int k, std::function<bool(Solution&)> func) const;
 
private:
    const Graph* m_G; 
    node m_root; 
 
    bool checkOnePermUnequal(const Solution& f1, const Solution& f2,
            const std::vector<unsigned int>& perm) const;
 
    bool checkNewTree(const Solution& f1, const Solution& f2, unsigned int k) const;
 
    bool createParentRel(const Solution& f, unsigned int j, NodeArray<adjEntry>& parent) const;
 
    bool checkIndependence(const std::vector<NodeArray<adjEntry>>& parents, unsigned int k) const;
 
    bool checkTwoPathIndependence(const std::vector<NodeArray<adjEntry>>& parents, node v,
            unsigned int p1, unsigned int p2) const;
 
    bool iterate(Solution& f, unsigned int j, unsigned int k) const;
 
    bool isFinished(const Solution& f, unsigned int k) const;
 
    unsigned int createVals(const Solution& f, unsigned int k, std::vector<edge>& tree) const;
 
    void clearTree(Solution& f, unsigned int j) const;
 
    bool nextSpanningTree(unsigned int& t, std::vector<edge>& tree) const;
 
    bool pathExists(const std::vector<edge>& tree, node v1, node v2, unsigned int t) const;
 
    bool isInSubGraph(const std::vector<edge>& sub, const edge& e, unsigned int t) const;
 
    bool createInitialSpanningTrees(Solution& f, unsigned int k) const;
 
    bool insertNewTree(Solution& f, unsigned int t, unsigned int j, std::vector<edge>& tree) const;
 
    bool findAndInsertNextTree(Solution& f, unsigned int& t, unsigned int j,
            std::vector<edge>& tree) const;
};
 
}