1#ifndef JNGEN_INCLUDE_TREE_INL_H2#error File "tree_inl.h" must not be included directly.3#include "../tree.h" // for completion emgine4#endif56void Tree::addEdge(int u, int v, const Weight& w) {7    extend(std::max(u, v) + 1);89    u = vertexByLabel(u);10    v = vertexByLabel(v);1112    int ret = dsu_.unite(u, v);13    ensure(ret, "A cycle appeared in the tree");1415    addEdgeUnsafe(u, v);1617    if (!w.empty()) {18        setEdgeWeight(m() - 1, w);19    }20}2122bool Tree::canAddEdge(int u, int v) {23    u = vertexByLabel(u);24    v = vertexByLabel(v);25    return dsu_.getRoot(u) != dsu_.getRoot(v);26}2728Array Tree::parents(int root) const {29    ensure(isConnected(), "Tree::parents(int): Tree is not connected");30    root = vertexByLabel(root);3132    Array parents(n());33    parents[root] = -1;34    std::vector<int> used(n());35    std::vector<int> queue{root};36    for (size_t i = 0; i < queue.size(); ++i) {37        int v = queue[i];38        used[v] = true;39        for (auto to: internalEdges(v)) {40            if (!used[to]) {41                parents[to] = v;42                queue.push_back(to);43            }44        }45    }4647    for (auto& x: parents) {48        if (x != -1) {49            x = vertexLabel(x);50        }51    }5253    return parents;54}5556Tree& Tree::shuffle() {57    doShuffle();58    return *this;59}6061Tree Tree::shuffled() const {62    Tree t = *this;63    return t.shuffle();64}6566Tree& Tree::shuffleAllBut(const Array& except) {67    doShuffleAllBut(except);68    return *this;69}7071Tree Tree::shuffledAllBut(const Array& except) const {72    Tree g(*this);73    return g.shuffleAllBut(except);74}7576Tree Tree::link(int vInThis, const Tree& other, int vInOther) {77    ensure(vInThis < n(), "Cannot link a nonexistent vertex");78    ensure(vInOther < other.n(), "Cannot link to a nonexistent vertex");7980    Tree t(*this);8182    for (const auto& e: other.edges()) {83        t.addEdge(e.first + n(), e.second + n());84    }8586    t.addEdge(vInThis, vInOther + n());8788    return t;89}9091Tree Tree::glue(int vInThis, const Tree& other, int vInOther) {92    ensure(vInThis < n(), "Cannot glue a nonexistent vertex");93    ensure(vInOther < other.n(), "Cannot glue to a nonexistent vertex");9495    auto newLabel = [vInThis, vInOther, &other, this] (int v) {96        if (v < vInOther) {97            return n() + v;98        } else if (v == vInOther) {99            return vInThis;100        } else {101            return n() + v - 1;102        }103    };104105    Tree t(*this);106107    for (const auto& e: other.edges()) {108        t.addEdge(newLabel(e.first), newLabel(e.second));109    }110111    ensure(t.n() == n() + other.n() - 1);112113    return t;114}115116// Tree generators go here117118Tree Tree::bamboo(int size) {119    ensure(size > 0, "Number of vertices in the tree must be positive");120    checkLargeParameter(size);121    Tree t;122    for (int i = 0; i + 1 < size; ++i) {123        t.addEdge(i, i+1);124    }125    t.normalizeEdges();126    return t;127}128129Tree Tree::random(int size) {130    ensure(size > 0, "Number of vertices in the tree must be positive");131    checkLargeParameter(size);132    if (size == 1) {133        return Tree();134    }135    return fromPruferSequence(Array::random(size - 2, size));136}137138Tree Tree::randomPrim(int size, int elongation) {139    ensure(size > 0, "Number of vertices in the tree must be positive");140    checkLargeParameter(size);141    Tree t;142    for (int v = 1; v < size; ++v) {143        int parent = rnd.wnext(v, elongation);144        t.addEdge(parent, v);145    }146    t.normalizeEdges();147    return t;148}149150Tree Tree::randomKruskal(int size) {151    ensure(size > 0, "Number of vertices in the tree must be positive");152    checkLargeParameter(size);153    Tree t;154    t.extend(size);155    while (!t.isConnected()) {156        auto e = rnd.nextp(size, dpair);157        if (t.canAddEdge(e.first, e.second)) {158            t.addEdge(e.first, e.second);159        }160    }161    return t;162}163164Tree Tree::star(int size) {165    ensure(size > 0, "Number of vertices in the tree must be positive");166    checkLargeParameter(size);167    Tree t;168    for (int i = 1; i < size; ++i) {169        t.addEdge(0, i);170    }171    t.normalizeEdges();172    return t;173}174175Tree Tree::caterpillar(int size, int length) {176    ensure(size > 0, "Number of vertices in the tree must be positive");177    ensure(length > 0, "Length of the caterpillar must be positive");178    checkLargeParameter(size);179    ensure(length <= size);180    Tree t = Tree::bamboo(length);181    for (int i = length; i < size; ++i) {182        t.addEdge(rnd.next(length), i);183    }184    t.normalizeEdges();185    return t;186}187188Tree Tree::binary(int size) {189    return kary(size, 2);190}191192Tree Tree::kary(int size, int k) {193    ensure(size > 0, "Number of vertices in the tree must be positive");194    checkLargeParameter(size);195196    Tree t;197    for (int i = 1; i < size; ++i) {198        t.addEdge((i - 1) / k, i);199    }200    t.normalizeEdges();201    return t;202}203204Tree Tree::fromPruferSequence(const Array& code) {205    std::vector<int> degree(code.size() + 2, 1);206    for (int v: code) {207        ++degree[v];208    }209210    std::set<int> leaves;211    for (size_t v = 0; v != degree.size(); ++v) {212        if (degree[v] == 1) {213            leaves.insert(v);214        }215    }216217    Tree t;218    for (int v: code) {219        ENSURE(!leaves.empty());220        int to = *leaves.begin();221        leaves.erase(leaves.begin());222        if (--degree[v] == 1) {223            leaves.insert(v);224        }225226        t.addEdge(v, to);227    }228229    ENSURE(leaves.size() == 2u);230    t.addEdge(*leaves.begin(), *leaves.rbegin());231    t.normalizeEdges();232    return t;233234}235236void Tree::doPrintParents(std::ostream& out, const OutputModifier& mod) const {237    int root = mod.printParents;238    if (root == -1) {239        root = 0;240    }241242    auto parents = this->parents(root);243    if (mod.printParents == -1) {244        parents.erase(parents.begin());245    }246247    if (mod.printN) {248        out << n() << "\n";249    }250251    // TODO: avoid copy-paste from doPrintEdges252    if (mod.printWeights && vertexWeights_.hasNonEmpty()) {253        auto vertexWeights = prepareWeightArray(vertexWeights_, n());254        for (int i = 0; i < n(); ++i) {255            if (i > 0) {256                out << " ";257            }258            JNGEN_PRINT_NO_MOD(vertexWeights[vertexByLabel(i)]);259        }260        out << "\n";261    }262263    auto t(mod);264    {265        auto mod(t);266        mod.printN = false;267268        if (mod.printWeights && edgeWeights_.hasNonEmpty()) {269            ensure(false, "Printing parents and edge weights is not supported");270            ensure(271                mod.printParents == -1,272                "Root must not be set to any exact value when printing a tree "273                "with edge weights. To fix it, either set printParents() "274                "or printWeights(false)");275            ENSURE(root == 0);276            // TODO: some code to be here277        } else {278            JNGEN_PRINT(parents);279        }280    }281}282