global_router.hpp

Go to the documentation of this file.

 
#pragma once
 
#include <algorithm>
#include <cmath>
#include <deque>
#include <limits>
#include <memory>
#include <optional>
#include <recti/generic.hpp>  // for enlarge_with
#include <recti/interval.hpp>
#include <recti/point.hpp>
#include <string>
#include <unordered_map>
#include <vector>
 
namespace recti {
 
    enum class NodeType {
        Steiner,   
        Terminal,  
        Source     
    };
 
    std::string to_string(const NodeType routing_node_type);
 
    template <typename IntPoint> class RoutingNode {
      public:
        std::string id;      
        NodeType node_type;  
        IntPoint pt;         
        std::vector<RoutingNode<IntPoint>*>
            children;  
        RoutingNode<IntPoint>* parent
            = nullptr;             
        double capacitance = 0.0;  
        double delay = 0.0;        
        int path_length = 0;       
 
        RoutingNode(std::string node_id, NodeType node_type, IntPoint node_position)
            : id(std::move(node_id)), node_type(node_type), pt(node_position) {}
 
        void add_child(RoutingNode<IntPoint>* child_node) {
            child_node->parent = this;
            children.emplace_back(child_node);
        }
 
        void remove_child(RoutingNode<IntPoint>* child_node) {
            auto iter = std::find(children.begin(), children.end(), child_node);
            if (iter != children.end()) {
                children.erase(iter);
                child_node->parent = nullptr;
            }
        }
 
        auto get_position() const -> const IntPoint& { return pt; }
 
        auto manhattan_distance(const RoutingNode<IntPoint>* other_node) const -> int {
            return pt.min_dist_with(other_node->pt);
        }
    };
 
    template <typename IntPoint> class GlobalRoutingTree {
      public:
        using Keepout = decltype(std::declval<IntPoint>().enlarge_with(1));
 
      private:
        std::deque<RoutingNode<IntPoint>> _arena;
        int next_steiner_id = 1;   
        int next_terminal_id = 1;  
 
        auto _find_nearest_node(const IntPoint& point, std::optional<std::string> exclude_id
                                                       = std::nullopt) -> RoutingNode<IntPoint>*;
 
        auto _find_nearest_insertion_with_constraints(const IntPoint& pt,
                                                      int allowed_wirelength
                                                      = std::numeric_limits<int>::max(),
                                                      std::optional<std::vector<Keepout>> keepouts
                                                      = std::nullopt)
            -> std::pair<RoutingNode<IntPoint>*, RoutingNode<IntPoint>*>;
 
        auto _insert_terminal_impl(const IntPoint& point,
                                   int allowed_wirelength = std::numeric_limits<int>::max(),
                                   std::optional<std::vector<Keepout>> keepouts = std::nullopt)
            -> void;
 
      public:
        std::unordered_map<std::string, RoutingNode<IntPoint>*>
            nodes;                 
        int worst_wirelength = 0;  
 
        GlobalRoutingTree(IntPoint source_position) {
            _arena.emplace_back("source", NodeType::Source, source_position);
            nodes["source"] = &this->_arena.back();
        }
 
        auto get_source() const -> const RoutingNode<IntPoint>* { return &this->_arena[0]; }
 
        auto get_source() -> RoutingNode<IntPoint>* { return &this->_arena[0]; }
 
        auto insert_steiner_node(const IntPoint& point, std::optional<std::string> parent_id
                                                        = std::nullopt) -> std::string;
 
        auto insert_terminal_node(const IntPoint& point, std::optional<std::string> parent_id
                                                         = std::nullopt) -> std::string;
 
        auto insert_node_on_branch(NodeType new_node_type, const IntPoint& point,
                                   std::string branch_start_id, std::string branch_end_id)
            -> std::string;
 
        auto insert_terminal_with_steiner(const IntPoint& point,
                                          std::optional<std::vector<Keepout>> keepouts
                                          = std::nullopt) -> void {
            _insert_terminal_impl(point, std::numeric_limits<int>::max(), keepouts);
        }
 
        auto insert_terminal_with_constraints(const IntPoint& point, int allowed_wirelength,
                                              std::optional<std::vector<Keepout>> keepouts
                                              = std::nullopt) -> void {
            _insert_terminal_impl(point, allowed_wirelength, keepouts);
        }
 
        auto calculate_total_wirelength() const -> int;
 
        auto calculate_worst_wirelength() const -> int;
 
        auto get_tree_structure(const RoutingNode<IntPoint>* current_node = nullptr,
                                int level = 0) const -> std::string;
 
        auto find_path_to_source(const std::string& node_id) const
            -> std::vector<const RoutingNode<IntPoint>*>;
 
        auto get_all_terminals() const -> std::vector<const RoutingNode<IntPoint>*>;
 
        auto get_all_steiner_nodes() const -> std::vector<const RoutingNode<IntPoint>*>;
 
        void optimize_steiner_points();
 
        void visualize_tree() const;
    };
 
    template <typename IntPoint> class GlobalRouter {
        IntPoint source_position;                  
        std::vector<IntPoint> terminal_positions;  
        GlobalRoutingTree<IntPoint> tree;          
        int worst_wirelength
            = 0;  
        std::optional<std::vector<typename GlobalRoutingTree<IntPoint>::Keepout>>
            keepouts;  
 
      public:
        using Keepout = decltype(std::declval<IntPoint>().enlarge_with(1));
 
        GlobalRouter(const IntPoint& source_pos, std::vector<IntPoint> terminal_positions,
                     std::optional<std::vector<Keepout>> keepout_regions = std::nullopt);
 
        void route_simple() {
            for (const auto& terminal : this->terminal_positions) {
                this->tree.insert_terminal_node(terminal);
            }
        }
 
        void route_with_steiners() {
            this->tree.worst_wirelength = this->worst_wirelength;  // Store the allowed wirelength
                                                                   // in the tree for reference
            for (const auto& terminal : this->terminal_positions) {
                this->tree.insert_terminal_with_steiner(terminal, this->keepouts);
            }
        }
 
        void route_with_constraints(double multiplier = 1.0) {
            int allowed_wirelength
                = static_cast<int>(std::round(this->worst_wirelength * multiplier));
            this->tree.worst_wirelength = this->worst_wirelength;  // Store the allowed wirelength
                                                                   // in the tree for reference
            for (const auto& terminal : this->terminal_positions) {
                this->tree.insert_terminal_with_constraints(terminal, allowed_wirelength,
                                                            this->keepouts);
            }
        }
 
        auto get_tree() const -> const GlobalRoutingTree<IntPoint>& { return this->tree; }
    };
 
    template <typename IntPoint> extern std::string visualize_routing_tree_svg(
        const GlobalRoutingTree<IntPoint>& tree,
        std::optional<std::vector<typename GlobalRoutingTree<IntPoint>::Keepout>> keepouts
        = std::nullopt,
        const int width = 800, const int height = 600, const int margin = 50);
 
    template <typename IntPoint> extern void save_routing_tree_svg(
        const GlobalRoutingTree<IntPoint>& tree,
        std::optional<std::vector<typename GlobalRoutingTree<IntPoint>::Keepout>> keepouts
        = std::nullopt,
        const std::string& filename = "routing_tree.svg", const int width = 800,
        const int height = 600);
 
    template <typename IntPoint> extern std::string visualize_routing_tree3d_svg(
        const GlobalRoutingTree<IntPoint>& tree,
        std::optional<std::vector<typename GlobalRoutingTree<IntPoint>::Keepout>> keepouts
        = std::nullopt,
        const int scale_z = 100, const int width = 800, const int height = 600,
        const int margin = 50);
 
    template <typename IntPoint> extern void save_routing_tree3d_svg(
        const GlobalRoutingTree<IntPoint>& tree,
        std::optional<std::vector<typename GlobalRoutingTree<IntPoint>::Keepout>> keepouts
        = std::nullopt,
        const int scale_z = 100, const std::string& filename = "routing_tree3d.svg",
        const int width = 800, const int height = 600);
 
}  // namespace recti