text: /************************************************************************
   * This file introduces a class to model a Routing Resource Graph (RRGraph or RRG) 
   * which is widely used by placers, routers, analyzers etc.
   *
   * Overview
   * ========
   * RRGraph aims to describe in a general way how routing resources are connected
   * in a FPGA fabric.
   * It includes device-level information for routing resources, 
   * such as the physical location of nodes, 
   * routing segment information of each routing resource 
   * switch information of each routing resource.
   * 
   * A Routing Resource Graph (RRGraph or RRG) is a directed graph (has many cycles),
   * which consists of a number of nodes and edges.
   *
   * Node
   * ----
   * Each node represents a routing resource, which could be 
   * 1. a routing track in X-direction or Y-direction (CHANX or CHANY) 
   * 2. an input or an output of a logic block (IPIN or OPIN) 
   * 3. a virtual source or sink node (SOURCE or SINK), which are starting/ending points of routing trees.
   *
   * Edge
   * ----
   * Each edge represents a switch between routing resources, which could be
   * 1. a multiplexer
   * 2. a tri-state buffer
   * 3. a pass gate
   * 4. a non-configurable (can not be turned off) buffer
   * 5. a short (metal connection that can not be turned off
   *
   * Note: Multiplexers are the most common type
   *
   * The switch information are categorized in the rr_switch_inf of RRGraph class.
   * rr_switch_inf is created to minimize memory footprint of RRGraph classs
   * While the RRG could contain millions (even much larger) of edges, there are only
   * a limited number of types of switches.
   * Hence, we use a flyweight pattern to store switch-related information that differs
   * only for types of switches (switch type, drive strength, R, C, etc.).
   * Each edge stores the ids of the switch that implements it so this additional information
   * can be easily looked up.
   *
   * Note: All the switch-related information, such as R, C, should be placed in rr_switch_inf
   * but NOT directly in the edge-related data of RRGraph. 
   * If you wish to create a new data structure to represent switches between routing resources,
   * please follow the flyweight pattern by linking your switch ids to edges only!
   *
   * Guidlines on using the RRGraph data structure 
   * =============================================
   *
   * For those want to access data from RRGraph
   * ------------------------------------------
   * Some examples for most frequent data query:
   * 
   *     // Strongly suggest to use a read-only rr_graph object
   *     const RRGraph& rr_graph;
   *
   *     // Access type of a node with a given node id
   *     // Get the unique node id that you may get 
   *     // from other data structures or functions 
   *     RRNodeId node_id;                                    
   *     t_rr_type node_type = rr_graph.node_type(node_id);
   *
   *     // Access all the fan-out edges from a given node  
   *     for (const RREdgeId& out_edge_id : rr_graph.node_out_edges(node_id)) {
   *       // Do something with out_edge
   *     }
   *     // If you only want to learn the number of fan-out edges
   *     size_t num_out_edges = rr_graph.node_fan_out(node_id);
   *
   *     // Access all the switches connected to a given node  
   *     for (const RREdgeId& in_edge_id : rr_graph.node_in_edges(node_id)) {
   *       RRSwitchId edge_switch_id = rr_graph.edge_switch(in_edge_id);
   *       // Do something with the switch
   *     }
   *
   * Please refer to the detailed comments on each public accessors
   *
   * For those want to build/modify a RRGraph
   * -----------------------------------------
   * Do NOT add a builder to this data structure!
   * Builders should be kept as free functions that use the public mutators
   * We suggest developers to create builders in separated C/C++ source files
   * outside the rr_graph header and source files
   *
   * After build/modify a RRGraph, please do run a fundamental check, a public accessor.
   * to ensure that your RRGraph does not include invalid nodes/edges/switches/segements 
   * as well as connections.
   * The validate() function gurantees the consistency between internal data structures, 
   * such as the id cross-reference between nodes and edges etc.,
   * so failing it indicates a fatal bug!
   * This is a must-do check! 
   *
   * Example: 
   *    RRGraph rr_graph;
   *    ... // Building RRGraph
   *    rr_graph.validate(); 
   *
   * Optionally, we strongly recommend developers to run an advance check in check_rr_graph()  
   * This guarantees legal and routable RRGraph for VPR routers.
   *
   * This checks for connectivity or other information in the RRGraph that is unexpected 
   * or unusual in an FPGA, and likely indicates a problem in your graph generation. 
   * However, if you are intentionally creating an RRGraph with this unusual, 
   * buts still technically legal, behaviour, you can write your own check_rr_graph() with weaker assumptions. 
   *
   * Note: Do NOT modify the coordinate system for nodes, they are designed for downstream drawers and routers
   *
   * For those want to extend RRGraph data structure
   * --------------------------------------------------------------------------
   * Please avoid modifying any existing public/private accessors/mutators
   * in order to keep a stable RRGraph object in the framework
   * Developers may add more internal data to RRGraph as well as associate accessors/mutators
   * Please update and comment on the added features properly to keep this data structure friendly to be extended.
   *
   * Try to keep your extension within only graph-related internal data to RRGraph.
   * In other words, extension is necessary when the new node/edge attributes are needed.
   * RRGraph should NOT include other data which are shared by other data structures outside.
   * The rr-graph is the single largest data structure in VPR,
   * so avoid adding unnecessary information per node or per edge to it, as it will impact memory footprint.
   * Instead, using indices to point to the outside data source instead of embedding to RRGraph
   * For example: 
   *   For any placement/routing cost related information, try to extend t_rr_indexed_data, but not RRGraph
   *   For any placement/routing results, try to extend PlaceContext and RoutingContext, but not RRGraph
   * 
   * For those want to develop placers or routers
   * --------------------------------------------------------------------------
   * The RRGraph is designed to be a read-only database/graph, once created.
   * Placement and routing should NOT change any attributes of RRGraph.
   * Any placement and routing results should be stored in other data structures, such as PlaceContext and RoutingContext. 
   *
   * Tracing Cross-Reference 
   * =======================
   * RRGraph is designed to a self-contained data structure as much as possible.
   * It includes the switch information (rr_switch) and segment_information (rr_segment)
   * which are necessary to build-up any external data structures.
   *
   * Internal cross-reference
   * ------------------------
   *
   *  +--------+                  +--------+
   *  |        |  node_in_edges   |        |
   *  |        |  node_out_edges  |        |
   *  |  Node  |----------------->|  Edge  |--+
   *  |        |<-----------------|        |  |
   *  |        |  edge_src_node   |        |  |
   *  +--------+  edge_sink_node  +--------+  |edge_switch
   *      |                                   |
   *      | node_segment                      |
   *      v                                   v
   *  +------------+                     +----------+
   *  |            |                     |          |
   *  |            |                     |          |
   *  |  Segments  |                     |  Switch  |
   *  |            |                     |          |
   *  |            |                     |          |
   *  +------------+                     +----------+
   *
   *
   * External cross-reference
   * ------------------------
   * The only cross-reference to outside data structures is the cost_index
   * corresponding to the data structure t_rr_index_data
   * Details can be found in the definition of t_rr_index_data
   * This allows rapid look up by the router of additional information it needs for this node, using a flyweight pattern.
   *
   * +---------+  cost_index   +------------------------------+
   * | RRGraph |-------------->| cost_index_data[cost_index] | 
   * +---------+               +------------------------------+
   *
   * Note: if you wish to use a customized routing-cost data structure, 
   * please use the flyweigth pattern as we do for t_rr_index_data!
   *
   * Access to a node/edge/switch/segment, please use the StrongId created
   * ---------------------------------------------------------------------
   *    For node, use RRNodeId
   *    For edge, use RREdgeId
   *    For switch, use RRSwitchId
   *    For segment, use RRSegmentId
   *
   *    These are the unique identifier for each data type.
   *    To check if your id is valid or not, use the INVALID() function of StrongId class.
   *    Example:
   *       if (node_id == RRNodeId::INVALID()) {
   *       }  
   *
   ***********************************************************************/
  #ifndef RR_GRAPH_OBJ_H
  #define RR_GRAPH_OBJ_H
  
  /*
   * Notes in include header files in a head file 
   * Only include the neccessary header files 
   * that is required by the data types in the function/class declarations!
   */
  /* Header files should be included in a sequence */
  /* Standard header files required go first */
  #include <limits>
  #include <vector>
  
  /* EXTERNAL library header files go second*/
  #include "vtr_vector.h"
  #include "vtr_range.h"
  #include "vtr_geometry.h"
  #include "arch_types.h"
  
  /* VPR header files go third */
  #include "vpr_types.h"
  #include "rr_graph_fwd.h"
  
  class RRGraph {
    public: /* Types */
      /* Iterators used to create iterator-based loop for nodes/edges/switches/segments */
      typedef vtr::vector<RRNodeId, RRNodeId>::const_iterator node_iterator;
      typedef vtr::vector<RREdgeId, RREdgeId>::const_iterator edge_iterator;
      typedef vtr::vector<RRSwitchId, RRSwitchId>::const_iterator switch_iterator;
      typedef vtr::vector<RRSegmentId, RRSegmentId>::const_iterator segment_iterator;
  
      /* Ranges used to create range-based loop for nodes/edges/switches/segments */
      typedef vtr::Range<node_iterator> node_range;
      typedef vtr::Range<edge_iterator> edge_range;
      typedef vtr::Range<switch_iterator> switch_range;
      typedef vtr::Range<segment_iterator> segment_range;
  
    public: /* Accessors */
      /* Aggregates: create range-based loops for nodes/edges/switches/segments
       * To iterate over the nodes/edges/switches/segments in a RRGraph, 
       *    using a range-based loop is suggested.
       *  -----------------------------------------------------------------
       *    Example: iterate over all the nodes
       *      // Strongly suggest to use a read-only rr_graph object
       *      const RRGraph& rr_graph;
       *      for (const RRNodeId& node : rr_graph.nodes()) {
       *        // Do something with each node
       *      }
       *
       *      for (const RREdgeId& edge : rr_graph.edges()) {
       *        // Do something with each edge
       *      }
       *
       *      for (const RRSwitchId& switch : rr_graph.switches()) {
       *        // Do something with each switch
       *      }
       *
       *      for (const RRSegmentId& segment : rr_graph.segments()) {
       *        // Do something with each segment
       *      }
       */
      node_range nodes() const;
      edge_range edges() const;
      switch_range switches() const;
      segment_range segments() const;
  
      /* Node-level attributes */
      size_t node_index(const RRNodeId& node) const; /* TODO: deprecate this accessor as outside functions should use RRNodeId */
  
      /* get the type of a RRGraph node : types of each node, can be channel wires (CHANX or CHANY) or 
       *                                  logic block pins(OPIN or IPIN) or virtual nodes (SOURCE or SINK)
       *                                  see t_rr_type definition for more details
       */
      t_rr_type node_type(const RRNodeId& node) const;
  
      /* Get coordinate of a node. (xlow, xhigh, ylow, yhigh):
       *   For OPIN/IPIN/SOURCE/SINK, xlow = xhigh and ylow = yhigh
       *   This is still the case when a logic block has a height > 1
       *   For CHANX/CHANY, (xlow, ylow) and (xhigh, yhigh) represent
       *   where the routing segment starts and ends.
       *   Note that our convention alway keeps
       *   xlow <= xhigh and ylow <= yhigh
       *   Therefore, (xlow, ylow) is a starting point for a CHANX/CHANY in Direction::INC
       *   (xhigh, yhigh) is a starting point for a CHANX/CHANY in Direction::DEC
       *
       *   Note: there is only a single drive point for each routing segment (track)
       *   in the context of uni-directional wires
       *                           
       *   Example :
       *   CHANX in Direction::INC  
       *   (xlow, ylow)                (xhigh, yhigh)
       *        |                           |
       *       \|/                         \|/
       *        ---------------------------->
       *
       *   CHANX in Direction::DEC  
       *   (xlow, ylow)                (xhigh, yhigh)
       *        |                           |
       *       \|/                         \|/
       *        <----------------------------
       *
       *   CHANY in Direction::INC
       *       
       *      /|\ <-------(xhigh, yhigh)
       *       |
       *       |  <-------(xlow, ylow)
       *
       *   CHANY in Direction::DEC
       *       
       *       |  <-------(xhigh, yhigh)
       *       |
       *      \|/ <-------(xlow, ylow)
       */
      short node_xlow(const RRNodeId& node) const;
      short node_ylow(const RRNodeId& node) const;
      short node_xhigh(const RRNodeId& node) const;
      short node_yhigh(const RRNodeId& node) const;
  
      /* Get the length of a routing track. 
       * Note that it is ONLY meaningful for CHANX and CHANY, which represents the number of logic blocks that a routing track spans
       * For nodes that are OPIN/IPIN/SOURCE/SINK, the length is supposed to be always 0
       */
      short node_length(const RRNodeId& node) const;
  
      /* A short-cut function to get coordinates of a node,
       * where xmin of vtr::Rect = xlow, 
       *       ymin of vtr::Rect = ylow,
       *       xmax of vtr::Rect = xhigh, 
       *       ymax of vtr::Rect = yhigh. 
       */
      vtr::Rect<short> node_bounding_box(const RRNodeId& node) const;
  
      /* Get node starting and ending points in routing channels. 
       * See details in the figures for node_xlow(), node_ylow(), node_xhigh() and node_yhigh()
       * For routing tracks in Direction::INC:
       * node_start_coordinate() returns (xlow, ylow) as the starting point 
       * node_end_coordinate() returns (xhigh, yhigh) as the ending point 
       *
       * For routing tracks in Direction::DEC:
       * node_start_coordinate() returns (xhigh, yhigh) as the starting point 
       * node_end_coordinate() returns (xlow, ylow) as the ending point 
       *
       * For routing tracks in Direction::BIDIR:
       * node_start_coordinate() returns (xlow, ylow) as the starting point 
       * node_end_coordinate() returns (xhigh, yhigh) as the ending point 
       *
       * Applicable to routing track nodes only!!! 
       * This function will requires the types of node to be either CHANX or CHANY
       */
      vtr::Point<short> node_start_coordinate(const RRNodeId& node) const;
      vtr::Point<short> node_end_coordinate(const RRNodeId& node) const;
  
      /* Get the capacity of a node. 
       * Literally, how many nets can be mapped to the node. 
       * Typically, each node has a capacity of 1 but special nodes (SOURCE and SINK) will have a 
       * large number due to logic equivalent pins
       * See Vaughn Betz's book for more details
       */
      short node_capacity(const RRNodeId& node) const;
  
      /* Get the number of edges that drives a given node
       * Note that each edge is typically driven by a node
       * (true in VPR RRG that is currently supported, may not be true in customized RRG)
       * This can also represent the number of drive nodes 
       * An example where fan-in of a node C is 2
       *      
       *                edge A
       *        node A -------->+
       *                        |
       *                        |-->node C 
       *                 edgeB  |
       *        node B -------->+
       *  
       */
      short node_fan_in(const RRNodeId& node) const;
  
      /* Get the number of edges that are driven a given node
       * Note that each edge typically drives by a node 
       * (true in VPR RRG that is currently supported, may not be true in customized RRG)
       * This can also represent the number of fan-out nodes 
       * An example where fan-out of a node A is 2
       *      
       *                  edge A
       *        node A -+--------> node B
       *                |
       *                |     
       *                | edgeB  
       *                +--------> node C
       *  
       */
      short node_fan_out(const RRNodeId& node) const;
  
      /* Get the ptc_num of a node
       * The ptc (pin, track, or class) number is an integer 
       * that allows you to differentiate between wires, pins or sources/sinks with overlapping x,y coordinates or extent. 
       * This is useful for drawing rr-graphs nicely. 
       * For example, all the CHANX rr_nodes that have the same y coordinate and x-coordinates 
       * that overlap will have different ptc numbers, by convention starting at 0. 
       * This allows them to be drawn without overlapping, as the ptc num can be used as a track identifier. 
       * The main routing code does not care about ptc num.
       *
       * The ptc_num carries different meanings for different node types
       * (true in VPR RRG that is currently supported, may not be true in customized RRG)
       * CHANX or CHANY: the track id in routing channels
       * OPIN or IPIN: the index of pins in the logic block data structure
       * SOURCE and SINK: the class id of a pin (indicating logic equivalence of pins) in the logic block data structure
       *  
       * To ease the access to ptc_num for different types of nodes:
       * node_pin_num() is designed for logic blocks, which are IPIN and OPIN nodes
       * node_track_num() is designed for routing tracks, which are CHANX and CHANY nodes
       * node_class_num() is designed for routing source and sinks, which are SOURCE and SINK nodes
       *
       * Due to a useful identifier, ptc_num is used in building fast look-up 
       */
      short node_ptc_num(const RRNodeId& node) const;
      short node_pin_num(const RRNodeId& node) const;
      short node_track_num(const RRNodeId& node) const;
      short node_class_num(const RRNodeId& node) const;
  
      /* Get the index of cost data in the list of cost_indexed_data data structure
       * It contains the routing cost for different nodes in the RRGraph
       * when used in evaluate different routing paths
       * See cross-reference section in this header file for more details
       */
      short node_cost_index(const RRNodeId& node) const;
  
      /* Get the directionality of a node
       * see node coordinate for details 
       * only matters the routing track nodes (CHANX and CHANY) 
       */
      Direction node_direction(const RRNodeId& node) const;
  
      /* Get the side where the node physically locates on a logic block. 
       * Mainly applicable to IPIN and OPIN nodes, which locates on the perimeter of logic block 
       * The side should be consistent to <pinlocation> definition in architecture XML
       *
       *             TOP
       *        +-----------+
       *        |           |
       *  LEFT  |   Logic   | RIGHT
       *        |   Block   |
       *        |           |
       *        +-----------+
       *            BOTTOM
       *
       */
      e_side node_side(const RRNodeId& node) const;
  
      /* Get resistance of a node, used to built RC tree for timing analysis */
      float node_R(const RRNodeId& node) const;
  
      /* Get capacitance of a node, used to built RC tree for timing analysis */
      float node_C(const RRNodeId& node) const;
  
      /* Get segment id of a node, containing the information of the routing
       * segment that the node represents. See more details in the data structure t_segment_inf
       */
      RRSegmentId node_segment(const RRNodeId& node) const;
  
      /* Get the number of non-configurable incoming edges to a node */
      short node_num_configurable_in_edges(const RRNodeId& node) const;
  
      /* Get the number of non-configurable outgoing edges from a node */
      short node_num_non_configurable_in_edges(const RRNodeId& node) const;
  
      /* Get the number of configurable output edges of a node */
      short node_num_configurable_out_edges(const RRNodeId& node) const;
  
      /* Get the number of non-configurable output edges of a node */
      short node_num_non_configurable_out_edges(const RRNodeId& node) const;
  
      /* Get the range (list) of edges related to a given node */
      edge_range node_configurable_in_edges(const RRNodeId& node) const;
      edge_range node_non_configurable_in_edges(const RRNodeId& node) const;
      edge_range node_configurable_out_edges(const RRNodeId& node) const;
      edge_range node_non_configurable_out_edges(const RRNodeId& node) const;
  
      /* Get a list of edge ids, which are incoming edges to a node */
      edge_range node_in_edges(const RRNodeId& node) const;
  
      /* Get a list of edge ids, which are outgoing edges from a node */
      edge_range node_out_edges(const RRNodeId& node) const;
  
      /* Edge-related attributes 
       * An example to explain the terminology used in RRGraph
       *          edgeA
       *  nodeA --------> nodeB
       *        | edgeB
       *        +-------> nodeC
       *
       *  +----------+----------------+----------------+
       *  |  Edge Id |  edge_src_node | edge_sink_node |
       *  +----------+----------------+----------------+
       *  |   edgeA  |     nodeA      |      nodeB     |
       *  +----------+----------------+----------------+
       *  |   edgeB  |     nodeA      |      nodeC     |
       *  +----------+----------------+----------------+
       *
       */
      size_t edge_index(const RREdgeId& edge) const; /* TODO: deprecate this accessor as outside functions should use RREdgeId */
      /* Get the source node which drives a edge */
      RRNodeId edge_src_node(const RREdgeId& edge) const;
      /* Get the sink node which a edge ends to */
      RRNodeId edge_sink_node(const RREdgeId& edge) const;
      /* Get the switch id which a edge represents
       * using switch id, timing and other information can be found
       * for any node-to-node connection
       */
      RRSwitchId edge_switch(const RREdgeId& edge) const;
      /* Judge if a edge is configurable or not. 
       * A configurable edge is controlled by a programmable memory bit
       * while a non-configurable edge is typically a hard-wired connection
       */
      bool edge_is_configurable(const RREdgeId& edge) const;
      bool edge_is_non_configurable(const RREdgeId& edge) const;
  
      /* Switch Info */
      size_t switch_index(const RRSwitchId& switch_id) const; /* TODO: deprecate this accessor as outside functions should use RRSwitchId */
      /* Get the switch info of a switch used in this RRGraph */
      const t_rr_switch_inf& get_switch(const RRSwitchId& switch_id) const;
  
      /* Segment Info */
      size_t segment_index(const RRSegmentId& segment_id) const; /* TODO: deprecate this accessor as outside functions should use RRSegmentId */
      /* Get the segment info of a routing segment used in this RRGraph */
      const t_segment_inf& get_segment(const RRSegmentId& segment_id) const;
  
      /* Utilities */
      /* Find the edges connecting two nodes */
      std::vector<RREdgeId> find_edges(const RRNodeId& src_node, const RRNodeId& sink_node) const;
      /* Find a node with given features from internal fast look-up */
      RRNodeId find_node(const short& x, const short& y, const t_rr_type& type, const int& ptc, const e_side& side = NUM_SIDES) const;
      /* Find the number of routing tracks in a routing channel with a given coordinate */
      short chan_num_tracks(const short& x, const short& y, const t_rr_type& type) const;
  
      /* This flag is raised when the RRgraph contains invalid nodes/edges etc. 
       * Invalid nodes/edges exist when users remove nodes/edges from RRGraph
       * RRGraph object will not immediately remove the nodes and edges but
       * will mark them with invalid ids.
       * Afterwards the is_dirty flag is raised as an indicator, to tell users
       * that a clean-up process (invoked by compress() function)is required.
       * After executing compress(), the is_dirty will be reset to false
       *
       * Example:
       *   RRGraph rr_graph;
       *   RRNodeId node_id; // Node id to be removed
       *   rr_graph.remove_node(node_id); 
       *   // RRGraph is now dirty (rr_graph.is_dirty() == true)
       *   ...
       *   // During this period, when you perform data query,
       *   // You may encounter invalid nodes and edges
       *   // It may happen that 
       *   // 1. their ids are invalid 
       *   // 2. the cross-reference between nodes and edge, i.e.,
       *   //    node_in_edges(), node_out_edges() 
       *   // 3. invalid node returned from find_node(), which use fast look-up
       *   ... 
       *   rr_graph.compress(); 
       *   // RRGraph is now clean (rr_graph.is_dirty() == false)
       */
      bool is_dirty() const;
  
    public:                                        /* Echos */
      void print_node(const RRNodeId& node) const; /* Print the detailed information of a node */
  
    public: /* Public Validators */
      /* Check data structure for internal consistency
       * This function will 
       * 1. re-build fast look-up for nodes
       * 2. check all the edges and nodes are connected
       *    Literally, no invalid ids in fan-in/fan-out of edges/nodes
       * 3. check that all the nodes representing routing tracks have valid id linked to its segment-related data structure
       * 4. check that all the edges have valid id linked to its switch-related data structure 
       *
       * Any valid and non-dirty RRGraph should pass this check
       * It is highly recommended to run this function after building any RRGraph object
       */
      bool validate() const;
  
      /* Validate is the node id does exist in the RRGraph */
      bool valid_node_id(const RRNodeId& node) const;
  
      /* Validate is the edge id does exist in the RRGraph */
      bool valid_edge_id(const RREdgeId& edge) const;
  
    public: /* Mutators */
      /* Reserve the lists of nodes, edges, switches etc. to be memory efficient. 
       * This function is mainly used to reserve memory space inside RRGraph,
       * when adding a large number of nodes/edge/switches/segments,
       * in order to avoid memory fragements
       * For example: 
       *    RRGraph rr_graph;
       *    // Add 1000 CHANX nodes to the RRGraph object
       *    rr_graph.reserve_nodes(1000);
       *    for (size_t i = 0; i < 1000; ++i) {
       *      rr_graph.create_node(CHANX);
       *    }
       */
      void reserve_nodes(const int& num_nodes);
      void reserve_edges(const int& num_edges);
      void reserve_switches(const int& num_switches);
      void reserve_segments(const int& num_segments);
  
      /* Add new elements (node, edge, switch, etc.) to RRGraph */
      /* Add a node to the RRGraph with a deposited type 
       * Detailed node-level information should be added using the set_node_* functions
       * For example: 
       *   RRNodeId node = create_node();
       *   set_node_xlow(node, 0);
       */
      RRNodeId create_node(const t_rr_type& type);
      /* Add a edge to the RRGraph, by providing the source and sink node 
       * This function will automatically create a node and
       * configure the nodes and edges in connection   
       */
      RREdgeId create_edge(const RRNodeId& source, const RRNodeId& sink, const RRSwitchId& switch_id);
      RRSwitchId create_switch(const t_rr_switch_inf& switch_info);
      RRSegmentId create_segment(const t_segment_inf& segment_info);
  
      /* Remove elements from RRGraph
       * This function just turn the nodes and edges to an invalid id without deletion
       * This will cause the RRGraph to be marked as dirty (is_dirty(): false => true)
       * To thoroughly remove the edges and nodes as well as clear the dirty flag,
       * use compress() after the remove functions
       * Example: 
       *   RRGraph rr_graph;
       *   rr_graph.remove_node()
       *   .. // remove more nodes 
       *   rr_graph.remove_edge()
       *   .. // remove more nodes 
       *   // rr_graph.is_dirty() == true
       *   // If you want to access any node or edge
       *   // Check codes for ids should be intensively used
       *   // Such as, 
       *   // for (const RREdgeId& in_edge : rr_graph.node_in_edges()) {
       *   //   if (RREdgeId::INVALID() != in_edge) {
       *   //     ...
       *   //   }
       *   // }
       *   rr_graph.compress()
       *   // rr_graph.is_dirty() == false
       */
      void remove_node(const RRNodeId& node);
      void remove_edge(const RREdgeId& edge);
  
      /* Set node-level information */
      void set_node_xlow(const RRNodeId& node, const short& xlow);
      void set_node_ylow(const RRNodeId& node, const short& ylow);
      void set_node_xhigh(const RRNodeId& node, const short& xhigh);
      void set_node_yhigh(const RRNodeId& node, const short& yhigh);
  
      /* This is a short-cut function, set xlow/xhigh/ylow/yhigh for a node
       * Please respect the following to configure the bb object:
       * bb.xmin = xlow, bb.ymin = ylow; bb.xmax = xhigh, bb.ymax = yhigh;
       */
      void set_node_bounding_box(const RRNodeId& node, const vtr::Rect<short>& bb);
  
      void set_node_capacity(const RRNodeId& node, const short& capacity);
  
      /* A generic function to set the ptc_num for a node */
      void set_node_ptc_num(const RRNodeId& node, const short& ptc);
  
      /* Only applicable to IPIN and OPIN, set the ptc_num for a node, which is the pin id in a logic block,
       * See definition in t_type_descriptor data structure   
       */
      void set_node_pin_num(const RRNodeId& node, const short& pin_id);
  
      /* Only applicable to CHANX and CHANY, set the ptc_num for a node, which is the track id in a routing channel,
       * Routing channel is a group of routing tracks, each of which has a unique index
       * An example 
       *       Routing Channel 
       *    +------------------+
       *    |                  |
       * ---|----------------->|----> track_id: 0
       *    |                  |
       *   ...   More tracks  ...
       *    |                  |
       * ---|----------------->|----> track_id: 1
       *    |                  |
       *    +------------------+
       */
      void set_node_track_num(const RRNodeId& node, const short& track_id);
  
      /* Only applicable to SOURCE and SINK, set the ptc_num for a node, which is the class number in a logic block,
       * See definition in t_type_descriptor data structure   
       */
      void set_node_class_num(const RRNodeId& node, const short& class_id);
  
      /* Set the routing cost index for node, see node_cost_index() for details */
      /* TODO: the cost index should be changed to a StrongId!!! */
      void set_node_cost_index(const RRNodeId& node, const short& cost_index);
  
      /* Set the directionality for a node, only applicable to CHANX and CHANY */
      void set_node_direction(const RRNodeId& node, const Direction& direction);
  
      /* Set the side for a node, only applicable to OPIN and IPIN */
      void set_node_side(const RRNodeId& node, const e_side& side);
  
      /* Set the RC information for a node */
      void set_node_R(const RRNodeId& node, const float& R);
      void set_node_C(const RRNodeId& node, const float& C);
  
      /* Set the routing segment linked to a node, only applicable to CHANX and CHANY */
      void set_node_segment(const RRNodeId& node, const RRSegmentId& segment_index);
  
      /* Edge partitioning is performed for efficiency, 
       * so we can store configurable and non-configurable edge lists for a node in one vector, 
       * and efficiently iterate over all edges, or only the configurable or non-configurable subsets.
       * This function will re-organize the incoming and outgoing edges of each node, 
       * i.e., node_in_edges() and node_out_edges():
       * 1. configurable edges (1st part of the vectors) 
       * 2. non-configurable edges (2nd part of the vectors) 
       */
      void partition_edges();
  
      /* Graph-level Clean-up, remove invalid nodes/edges etc.
       * This will clear the dirty flag (query by is_dirty()) of RRGraph object, if it was set 
       */
      void compress();
  
      /* top-level function to free, should be called when to delete a RRGraph */
      void clear();
  
    private: /* Internal Mutators to perform edge partitioning */
      /* classify the input edges of each node to be configurable (1st part) and non-configurable (2nd part) */
      void partition_node_in_edges(const RRNodeId& node);
  
      /* classify the output edges of each node to be configurable (1st part) and non-configurable (2nd part) */
      void partition_node_out_edges(const RRNodeId& node);
  
      /* classify the input edges of each node to be configurable (1st part) and non-configurable (2nd part) */
      void partition_in_edges();
  
      /* classify the output edges of each node to be configurable (1st part) and non-configurable (2nd part) */
      void partition_out_edges();
  
    private: /* Internal free functions */
      void clear_nodes();
      void clear_edges();
      void clear_switches();
      void clear_segments();
  
    private: /* Graph Compression related */
      void build_id_maps(vtr::vector<RRNodeId, RRNodeId>& node_id_map,
                         vtr::vector<RREdgeId, RREdgeId>& edge_id_map);
      void clean_nodes(const vtr::vector<RRNodeId, RRNodeId>& node_id_map);
      void clean_edges(const vtr::vector<RREdgeId, RREdgeId>& edge_id_map);
      void rebuild_node_refs(const vtr::vector<RREdgeId, RREdgeId>& edge_id_map);
  
      void set_dirty();
      void clear_dirty();
  
    private: /* Internal validators and builders */
      /* Fast look-up builders and validators */
      void build_fast_node_lookup() const;
      void invalidate_fast_node_lookup() const;
      bool valid_fast_node_lookup() const;
      void initialize_fast_node_lookup() const;
  
      /* Graph property Validation */
      bool validate_sizes() const;
      bool validate_node_sizes() const;
      bool validate_edge_sizes() const;
      bool validate_switch_sizes() const;
      bool validate_segment_sizes() const;
  
      bool validate_invariants() const;
      bool validate_unique_edges_invariant() const;
  
      bool validate_crossrefs() const;
      bool validate_node_edge_crossrefs() const;
  
      /* Node-level validators */
      bool validate_node_segment(const RRNodeId& node) const;
      bool validate_node_in_edges(const RRNodeId& node) const;
      bool validate_node_out_edges(const RRNodeId& node) const;
      bool validate_node_edges(const RRNodeId& node) const;
  
      /* Edge-level checking */
      bool validate_node_is_edge_src(const RRNodeId& node, const RREdgeId& edge) const;
      bool validate_node_is_edge_sink(const RRNodeId& node, const RREdgeId& edge) const;
      bool validate_edge_switch(const RREdgeId& edge) const;
      bool validate_edge_src_node(const RREdgeId& edge) const;
      bool validate_edge_sink_node(const RREdgeId& edge) const;
  
      /* List-level checking */
      bool validate_nodes_in_edges() const;
      bool validate_nodes_out_edges() const;
      bool validate_nodes_edges() const;
      bool validate_node_segments() const;
      bool validate_edge_switches() const;
      bool validate_edge_src_nodes() const;
      bool validate_edge_sink_nodes() const;
  
      /* Validate switch list */
      bool valid_switch_id(const RRSwitchId& switch_id) const;
  
      /* Validate segment list */
      bool valid_segment_id(const RRSegmentId& segment_id) const;
  
    private: /* Internal Data */
      /* Node related data */
      vtr::vector<RRNodeId, RRNodeId> node_ids_; /* Unique identifiers for the nodes */
      vtr::vector<RRNodeId, t_rr_type> node_types_;
  
      vtr::vector<RRNodeId, vtr::Rect<short>> node_bounding_boxes_;
  
      vtr::vector<RRNodeId, short> node_capacities_;
      vtr::vector<RRNodeId, short> node_ptc_nums_;
      vtr::vector<RRNodeId, short> node_cost_indices_;
      vtr::vector<RRNodeId, Direction> node_directions_;
      vtr::vector<RRNodeId, e_side> node_sides_;
      vtr::vector<RRNodeId, float> node_Rs_;
      vtr::vector<RRNodeId, float> node_Cs_;
      vtr::vector<RRNodeId, RRSegmentId> node_segments_; /* Segment ids for each node */
      /* Record the dividing point between configurable and non-configurable edges for each node */
      vtr::vector<RRNodeId, size_t> node_num_non_configurable_in_edges_;
      vtr::vector<RRNodeId, size_t> node_num_non_configurable_out_edges_;
  
      vtr::vector<RRNodeId, std::vector<RREdgeId>> node_in_edges_;
      vtr::vector<RRNodeId, std::vector<RREdgeId>> node_out_edges_;
  
      /* Edge related data */
      vtr::vector<RREdgeId, RREdgeId> edge_ids_; /* unique identifiers for edges */
      vtr::vector<RREdgeId, RRNodeId> edge_src_nodes_;
      vtr::vector<RREdgeId, RRNodeId> edge_sink_nodes_;
      vtr::vector<RREdgeId, RRSwitchId> edge_switches_;
  
      /* Switch related data
       * Note that so far there has been no need to remove
       * switches, so no such facility exists
       */
      /* Unique identifiers for switches which are used in the RRGraph */
      vtr::vector<RRSwitchId, RRSwitchId> switch_ids_;
      /* Detailed information about the switches, which are used in the RRGraph */
      vtr::vector<RRSwitchId, t_rr_switch_inf> switches_;
  
      /* Segment relatex data 
       * Segment info should be corrected annotated for each rr_node
       * whose type is CHANX and CHANY
       */
      vtr::vector<RRSegmentId, RRSegmentId> segment_ids_; /* unique identifiers for routing segments which are used in the RRGraph */
      vtr::vector<RRSegmentId, t_segment_inf> segments_;  /* detailed information about the segments, which are used in the RRGraph */
  
      /* Misc. */
      /* A flag to indicate if the graph contains invalid elements (nodes/edges etc.) */
      bool dirty_ = false;
  
      /* Fast look-up to search a node by its type, coordinator and ptc_num 
       * Indexing of fast look-up: [0..xmax][0..ymax][0..NUM_TYPES-1][0..ptc_max][0..NUM_SIDES-1] 
       */
      typedef std::vector<std::vector<std::vector<std::vector<std::vector<RRNodeId>>>>> NodeLookup;
      mutable NodeLookup node_lookup_;
  };
  
  #endif
  