PCTree.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/GraphAttributes.h>
#include <ogdf/basic/pctree/PCEnum.h>
#include <ogdf/basic/pctree/PCNode.h>
#include <ogdf/basic/pctree/PCRegistry.h>
#include <ogdf/basic/pctree/PCTreeForest.h>
#include <ogdf/basic/pctree/PCTreeIterators.h>
#include <ogdf/basic/pctree/util/IntrusiveList.h>
 
#include <deque>
#include <list>
#include <sstream>
#include <vector>
 
namespace ogdf::pc_tree {
OGDF_EXPORT bool isTrivialRestriction(int restSize, int leafCount);
 
OGDF_EXPORT int factorial(int n);
 
#ifdef OGDF_DEBUG
 
OGDF_EXPORT extern int PCTREE_DEBUG_CHECK_FREQ;
#endif
 
namespace uid_utils {
OGDF_EXPORT void nodeToID(std::ostream& os, PCNode* n, int pos);
 
OGDF_EXPORT void nodeToPosition(std::ostream& os, PCNode* n, int pos);
 
OGDF_EXPORT void leafToID(std::ostream& os, PCNode* n, int pos);
 
OGDF_EXPORT void leafToPosition(std::ostream& os, PCNode* n, int pos);
 
OGDF_EXPORT bool compareNodesByID(PCNode* a, PCNode* b);
}
 
class OGDF_EXPORT PCTree {
    friend OGDF_EXPORT std::ostream&(operator<<)(std::ostream&, const ogdf::pc_tree::PCTree*);
    friend OGDF_EXPORT std::ostream&(operator<<)(std::ostream&, const ogdf::pc_tree::PCNode*);
 
    friend class PCNode;
    friend class PCTreeRegistry;
    friend class PCTreeForest;
 
public:
    struct Observer; // pre-declaration
 
private:
    // global
    PCTreeForest* m_forest = nullptr;
 
    // needs merge when trees merge
    size_t m_pNodeCount = 0;
    size_t m_cNodeCount = 0;
    IntrusiveList<PCNode> m_leaves;
 
    // needs special merge
    PCNode* m_rootNode = nullptr;
 
    // temp makeConsecutive variables
    size_t m_partialCount = 0;
    size_t m_terminalPathLength = 0;
    PCNode* m_firstPartial = nullptr;
    PCNode* m_lastPartial = nullptr;
    PCNode* m_apexCandidate = nullptr;
    bool m_apexCandidateIsFix = false;
    PCNode* m_apexTPPred2 = nullptr;
 
    // private
    bool m_externalForest = true;
    std::list<Observer*> m_observers;
 
public:
    explicit PCTree() : PCTree(nullptr) {};
 
    explicit PCTree(PCTreeForest* forest) {
        if (forest) {
            m_forest = forest;
            m_externalForest = true;
        } else {
            m_forest = new PCTreeForest();
            m_externalForest = false;
        }
    };
 
    explicit PCTree(int leafNum, std::vector<PCNode*>* added = nullptr,
            PCTreeForest* forest = nullptr);
 
    explicit PCTree(const PCTree& other, PCTreeNodeArray<PCNode*>& nodeMapping,
            bool keep_ids = false, PCTreeForest* forest = nullptr);
 
    explicit PCTree(const std::string& str, bool keep_ids = false, PCTreeForest* forest = nullptr);
 
    virtual ~PCTree();
 
public:
 
    PCNode* newNode(PCNodeType type, PCNode* parent = nullptr, int id = -1);
 
    void destroyNode(PCNode*& node) {
        destroyNode((PCNode* const&)node);
        node = nullptr;
    }
 
    void destroyNode(PCNode* const& node);
 
    void insertLeaves(int count, PCNode* parent, std::vector<PCNode*>* added = nullptr);
 
    void replaceLeaf(int leafCount, PCNode* leaf, std::vector<PCNode*>* added = nullptr);
 
    PCNode* mergeLeaves(const std::vector<PCNode*>& consecutiveLeaves,
            bool assumeConsecutive = false) {
        return mergeLeaves(consecutiveLeaves.begin(), consecutiveLeaves.end(), assumeConsecutive);
    }
 
    template<typename It>
    PCNode* mergeLeaves(It begin, It end, bool assumeConsecutive = false) {
        OGDF_ASSERT(begin != end);
 
        if (!assumeConsecutive && !makeConsecutive(begin, end)) {
            return nullptr;
        }
 
        // Remove all consecutive leaves except the first one.
        It back = prev(end);
        for (auto it = begin; it != back; ++it) {
            destroyLeaf(*it);
        }
 
        OGDF_HEAVY_ASSERT(checkValid());
 
        // Return the remaining leaf.
        return *back;
    }
 
    void destroyLeaf(PCNode* leaf);
 
    PCNode* setRoot(PCNode* newRoot);
 
    PCNode* changeRoot(PCNode* newRoot);
 
    PCNodeType changeNodeType(PCNode* node, PCNodeType newType);
 
    void insertTree(PCNode* at, PCTree* tree);
 
private:
    void unregisterNode(PCNode* node);
 
    void registerNode(PCNode* node);
 
 
public:
 
    bool isTrivialRestriction(int size) const;
 
    bool makeConsecutive(std::initializer_list<PCNode*> consecutiveLeaves) {
        return makeConsecutive(consecutiveLeaves.begin(), consecutiveLeaves.end());
    }
 
    bool makeConsecutive(const std::vector<PCNode*>& consecutiveLeaves) {
        return makeConsecutive(consecutiveLeaves.begin(), consecutiveLeaves.end());
    }
 
    template<typename It>
    bool makeConsecutive(It begin, It end) {
        FullLeafIter iter = [&begin, &end]() { return NextFullLeaf<It>(begin, end); };
        for (auto obs : m_observers) {
            obs->makeConsecutiveCalled(*this, iter);
        }
 
        OGDF_HEAVY_ASSERT(checkValid());
        resetTempData();
 
#ifdef OGDF_DEBUG
        for (auto it = begin; it != end; ++it) {
            PCNode* leaf = *it;
            OGDF_ASSERT(leaf);
            OGDF_ASSERT(leaf->isLeaf());
            OGDF_ASSERT(leaf->m_forest == m_forest);
        }
#endif
        if (isTrivialRestriction(end - begin)) {
            for (auto obs : m_observers) {
                obs->makeConsecutiveDone(*this, Observer::Stage::Trivial, true);
            }
            return true;
        }
 
        // PC_PROFILE_ENTER(1, "label");
        markFull(begin, end);
        // PC_PROFILE_EXIT(1, "label");
 
        return makeFullNodesConsecutive();
    }
 
    void resetTempData() {
        m_forest->m_timestamp++;
        m_firstPartial = m_lastPartial = nullptr;
        m_partialCount = 0;
        m_apexCandidate = nullptr;
        m_apexCandidateIsFix = false;
        m_terminalPathLength = 0;
        m_apexTPPred2 = nullptr;
    }
 
    template<typename It>
    void markLeavesFull(It begin, It end) {
        for (auto it = begin; it != end; ++it) {
            PCNode* leaf = *it;
            OGDF_ASSERT(leaf);
            OGDF_ASSERT(leaf->isLeaf());
            OGDF_ASSERT(leaf->m_forest == m_forest);
            leaf->setLabel(NodeLabel::Full);
        }
    }
 
    template<typename It>
    void markFull(It begin, It end, std::vector<PCNode*>* fullNodeOrder = nullptr) {
        // Attention: This method no longer uses a queue to defer processing of partial/full parents to after
        // all leaves are done, but now directly make parents full if all of their children are full.
        if (fullNodeOrder != nullptr) {
            fullNodeOrder->reserve(m_cNodeCount + m_pNodeCount);
        }
 
        for (auto it = begin; it != end; ++it) {
            PCNode* full_parent = markFull(*it, fullNodeOrder);
            while (full_parent != nullptr) {
                full_parent = markFull(full_parent, fullNodeOrder);
            }
        }
    }
 
    bool makeFullNodesConsecutive();
 
private:
    /* see the paper for more info on how the update works with the following methods */
 
    PCNode* markFull(PCNode* full_node, std::vector<PCNode*>* fullNodeOrder = nullptr);
 
    bool findTerminalPath();
 
    void updateSingletonTerminalPath();
 
    PCNode* createCentralNode();
 
    int updateTerminalPath(PCNode* central, PCNode* tpNeigh);
 
    // labeling / TP finding
 
    void addPartialNode(PCNode* partial);
 
    void removePartialNode(PCNode* partial);
 
    bool checkTPPartialCNode(PCNode* node);
 
    size_t findEndOfFullBlock(PCNode* node, PCNode* pred, PCNode* curr, PCNode*& fullEnd,
            PCNode*& emptyEnd) const;
 
    bool setApexCandidate(PCNode* ac, bool fix = false);
 
    // update
 
    void replaceTPNeigh(PCNode* central, PCNode* oldTPNeigh, PCNode* newTPNeigh,
            PCNode* newFullNeigh, PCNode* otherEndOfFullBlock);
 
    PCNode* splitOffFullPNode(PCNode* node, bool skip_parent);
 
 
public:
 
    bool intersect(PCTree& other, PCTreeNodeArray<PCNode*>& mapping);
 
private:
    bool findNodeRestrictions(PCTree& applyTo, PCTreeNodeArray<PCNode*>& mapping,
            PCTreeNodeArray<std::vector<PCNode*>>& blockNodes,
            PCTreeNodeArray<std::vector<PCNode*>>& subtreeNodes,
            PCTreeNodeArray<PCNode*>& leafPartner, PCTreeNodeArray<bool>& isFront);
 
    void restoreSubtrees(PCTreeNodeArray<std::vector<PCNode*>>& blockNodes,
            PCTreeNodeArray<std::vector<PCNode*>>& subtreeNodes,
            PCTreeNodeArray<PCNode*>& leafPartner, PCTreeNodeArray<bool>& isFront);
 
 
public:
    operator const PCTreeRegistry&() const { return m_forest->m_nodeArrayRegistry; }
 
    [[nodiscard]] PCTreeForest* getForest() const { return m_forest; }
 
    [[nodiscard]] bool isTrivial() const;
 
    [[nodiscard]] const IntrusiveList<PCNode>& getLeaves() const { return m_leaves; }
 
    [[nodiscard]] size_t getLeafCount() const { return m_leaves.size(); };
 
    [[nodiscard]] size_t getPNodeCount() const { return m_pNodeCount; }
 
    [[nodiscard]] size_t getCNodeCount() const { return m_cNodeCount; }
 
    [[nodiscard]] PCNode* getRootNode() const { return m_rootNode; }
 
    int getTerminalPathLength() const { return m_terminalPathLength; }
 
    FilteringPCTreeDFS allNodes() const { return FilteringPCTreeDFS(*this, m_rootNode); }
 
    FilteringPCTreeDFS innerNodes() const {
        return FilteringPCTreeDFS(*this, m_rootNode, [](PCNode* node) { return !node->isLeaf(); });
    }
 
    template<typename Container>
    void currentLeafOrder(Container& container) const {
        for (PCNode* leaf : FilteringPCTreeDFS(*this, m_rootNode)) {
            if (leaf->isLeaf()) {
                container.push_back(leaf);
            }
        }
        OGDF_ASSERT(container.size() == m_leaves.size());
    }
 
    std::vector<PCNode*> currentLeafOrder() const {
        std::vector<PCNode*> container;
        currentLeafOrder(container);
        return container;
    }
 
    bool checkValid(bool allow_small_deg = true) const;
 
    bool isValidOrder(const std::vector<PCNode*>& order) const;
 
    void getTree(ogdf::Graph& tree, ogdf::GraphAttributes* g_a,
            PCTreeNodeArray<ogdf::node>& pc_repr, ogdf::NodeArray<PCNode*>* g_repr = nullptr,
            bool mark_full = false, bool show_sibs = false) const;
 
    void getRestrictions(std::vector<std::vector<PCNode*>>& restrictions,
            PCNode* fixedLeaf = nullptr) const;
 
    template<typename R>
    R possibleOrders() const {
        R orders(1);
        for (PCNode* node : innerNodes()) {
            if (node->getNodeType() == PCNodeType::CNode) {
                orders *= 2;
            } else {
                R children(node->getChildCount());
                if (node == m_rootNode) {
                    children -= 1; // don't count circular shifts
                }
                orders *= factorial(children);
            }
        }
        return orders;
    }
 
    std::ostream& uniqueID(std::ostream& os,
            const std::function<void(std::ostream& os, PCNode*, int)>& printNode = uid_utils::nodeToID,
            const std::function<bool(PCNode*, PCNode*)>& compareNodes = uid_utils::compareNodesByID);
 
    std::string uniqueID(
            const std::function<void(std::ostream& os, PCNode*, int)>& printNode = uid_utils::nodeToID,
            [[maybe_unused]] const std::function<bool(PCNode*, PCNode*)>& compareNodes =
                    uid_utils::compareNodesByID) {
        std::stringstream sb;
        uniqueID(sb, printNode, compareNodes);
        return sb.str();
    }
 
 
public:
    template<typename It>
    struct NextFullLeaf {
        It m_it;
        It m_end;
 
        NextFullLeaf(It it, It an_end) : m_it(it), m_end(an_end) { }
 
        PCNode* operator()() {
            if (m_it == m_end) {
                return nullptr;
            }
            PCNode* n = *m_it;
            ++m_it;
            return n;
        }
    };
 
    using FullLeafIter = std::function<std::function<PCNode*()>()>;
 
    struct Observer {
        enum class Stage { Trivial, NoPartials, InvalidTP, SingletonTP, Done };
 
        virtual void onNodeCreate([[maybe_unused]] PCNode* node) {};
 
        virtual void makeConsecutiveCalled([[maybe_unused]] PCTree& tree,
                [[maybe_unused]] FullLeafIter consecutiveLeaves) {};
 
        virtual void labelsAssigned([[maybe_unused]] PCTree& tree,
                [[maybe_unused]] PCNode* firstPartial, [[maybe_unused]] PCNode* lastPartial,
                [[maybe_unused]] int partialCount) {};
 
        virtual void terminalPathFound([[maybe_unused]] PCTree& tree, [[maybe_unused]] PCNode* apex,
                [[maybe_unused]] PCNode* apexTPPred2, [[maybe_unused]] int terminalPathLength) {};
 
        virtual void centralCreated([[maybe_unused]] PCTree& tree,
                [[maybe_unused]] PCNode* central) {};
 
        virtual void beforeMerge([[maybe_unused]] PCTree& tree, [[maybe_unused]] int count,
                [[maybe_unused]] PCNode* tpNeigh) {};
 
        virtual void afterMerge([[maybe_unused]] PCTree& tree, [[maybe_unused]] PCNode* successor,
                [[maybe_unused]] PCNode* mergedNode) {};
 
        virtual void whenPNodeMerged([[maybe_unused]] PCTree& tree, [[maybe_unused]] PCNode* tpNeigh,
                [[maybe_unused]] PCNode* tpPred, [[maybe_unused]] PCNode* fullNeigh) {};
 
        virtual void whenCNodeMerged([[maybe_unused]] PCTree& tree,
                [[maybe_unused]] PCNode* tpNeigh, [[maybe_unused]] bool tpNeighSiblingsFlipped,
                [[maybe_unused]] PCNode* fullNeigh, [[maybe_unused]] PCNode* fullOuterChild) {};
 
        virtual void fullNodeSplit([[maybe_unused]] PCTree& tree,
                [[maybe_unused]] PCNode* fullNode) {};
 
        virtual void makeConsecutiveDone([[maybe_unused]] PCTree& tree,
                [[maybe_unused]] Stage stage, [[maybe_unused]] bool success) {};
 
        virtual void onApexMoved([[maybe_unused]] PCTree& tree,
                [[maybe_unused]] PCNode* apexCandidate, [[maybe_unused]] PCNode* central,
                [[maybe_unused]] PCNode* parent) {};
 
        virtual void nodeDeleted([[maybe_unused]] PCTree& tree,
                [[maybe_unused]] PCNode* toBeDeleted) {};
        virtual void nodeReplaced([[maybe_unused]] PCTree& tree, [[maybe_unused]] PCNode* replaced,
                [[maybe_unused]] PCNode* replacement) {};
    };
 
    struct LoggingObserver : public Observer {
        void makeConsecutiveCalled(PCTree& tree, FullLeafIter consecutiveLeaves) override;
 
        void labelsAssigned(PCTree& tree, PCNode* firstPartial, PCNode* lastPartial,
                int partialCount) override;
 
        void terminalPathFound(PCTree& tree, PCNode* apex, PCNode* apexTPPred2,
                int terminalPathLength) override;
 
        void centralCreated(PCTree& tree, PCNode* central) override;
 
        void beforeMerge(PCTree& tree, int count, PCNode* tpNeigh) override;
 
        void makeConsecutiveDone(PCTree& tree, Stage stage, bool success) override;
    };
 
    std::list<Observer*>::const_iterator addObserver(Observer* observer) {
        m_observers.push_back(observer);
        return --m_observers.end();
    }
 
    void removeObserver(std::list<Observer*>::const_iterator it) { m_observers.erase(it); }
 
    void removeObserver(Observer* observer) { m_observers.remove(observer); }
 
};
 
int PCTreeRegistry::keyToIndex(PCNode* key) { return key->index(); }
 
}