trees.h

/*
 * vim: ts=4 sw=4 et tw=0 wm=0
 *
 * libdialect - A library for computing DiAlEcT layouts:
 *                 D = Decompose/Distribute
 *                 A = Arrange
 *                 E = Expand/Emend
 *                 T = Transform
 *
 * Copyright (C) 2018  Monash University
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 * See the file LICENSE.LGPL distributed with the library.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 *
 * Author(s):   Steve Kieffer   <http://skieffer.info>
*/

#ifndef DIALECT_TREES_H
#define DIALECT_TREES_H

#include <set>
#include <map>
#include <vector>
#include <string>

#include "libavoid/geomtypes.h"

#include "libdialect/graphs.h"
#include "libdialect/commontypes.h"
#include "libdialect/ortho.h"
#include "libdialect/opts.h"
#include "libdialect/util.h"
#include "libdialect/routing.h"

namespace dialect {

class Tree {
public:

    Tree(Graph_SP G, Node_SP root);

    void symmetricLayout(CardinalDir growthDir, double nodeSep, double rankSep,
                         bool convexOrdering = true);

    void flip(void);

    void translate(Avoid::Point vect);

    void rotate(CardinalDir dg);

    void rotateGrowthDirCW(unsigned quarterTurns);

    Graph_SP underlyingGraph(void) const { return m_graph; }

    Node_SP getRootNode(void) const { return m_root; }

    std::string repr(void) const;

    id_type getRootNodeID(void) const { return m_root->id(); }

    bool isSymmetrical(void) const { return m_isSymmetric; }

    Node_SP buildRootlessBox(CardinalDir growthDir) const;

    size_t size(void) const { return m_nodes.size(); }

    void addNetworkToRoutingAdapter(RoutingAdapter &ra, TreeRoutingType trt, Graph_SP core = nullptr);

    void addNetwork(Graph &G, NodesById &treeNodes, EdgesById &treeEdges);

    void addConstraints(Graph &G, bool alignRoot);

    void addBufferNodesAndConstraints(Graph &G, NodesById &bufferNodes);

private:

    void clearRankBounds(void);
    std::vector<double> getBounds(unsigned rank, double nodeSep) const;
    Trees getCTrees(void) const;
    std::string computeIsomString(void) const;

    // the underlying Graph
    Graph_SP m_graph;
    // the root Node
    Node_SP m_root;
    // Depth of the tree (number of ranks)
    unsigned m_depth;
    // Breadth of the tree (width of widest rank)
    unsigned m_breadth;
    // Is the layout symmetric?
    bool m_isSymmetric;
    // All nodes lying at or below the root.
    // This can differ from the set of nodes in the underlying Graph m_graph when we are working
    // with C-trees, a special type of subtree used in the symmetric layout process.
    NodesById m_nodes;
    // IDs of those nodes that are leaves
    std::set<unsigned> m_leafIDs;
    // map rank numbers (0-based) to the Nodes belonging to that rank
    std::vector<Nodes> m_nodesByRank;
    // We also want the Nodes of each rank partitioned according to whether they are leaves.
    std::vector<Nodes> m_leavesByRank;
    std::vector<Nodes> m_nonleavesByRank;
    // map Node IDs to the ranks to which those Nodes belong
    std::map<id_type, unsigned> m_rankByNodeID;
    // map ID of child to parent Node
    NodesById m_parents;
    // For layout, we keep track of a pair <lb, ub>, i.e.
    // the lower and upper bounds on the lateral coordinates
    // of the tree, for each rank (e.g. for NORTH growth direction the
    // bounds are on x-coordinates).
    std::vector<std::vector<double>> m_boundsByRank;
    // We also keep global lower and upper bounds on rank coords.
    double m_lb;
    double m_ub;
    /* 
     * If the boundary is tight then the bounds for each rank cover just the
     * nodes on that rank plus half nodeSep on each end; else the bounds for
     * every rank are equal to the tight bounds for the widest rank.
     */
    bool m_boundaryTight;
    // Growth direction
    CardinalDir m_growthDir;
};

} // namespace dialect

#endif // DIALECT_TREES_H