vpr/src/route/router_lookahead_map.cpp
/* runs Dijkstra's algorithm from specified node until all nodes have been visited. Each time a pin is visited, the delay/congestion information
 * to that pin is stored is added to an entry in the routing_cost_map */
runs Dijkstra's algorithm from specified node until all nodes have been visited. Each time a pin is visited, the delay/congestion information
to that pin is stored is added to an entry in the routing_cost_map
runs Dijkstra ' s algorithm from specified node until all nodes have been visited . Each time a pin is visited the delay / congestion information to that pin is stored is added to an entry in the routing_cost_map
static void run_dijkstra(const RRNodeId& start_node_ind, int start_x, int start_y, t_routing_cost_map& routing_cost_map) {
    auto& device_ctx = g_vpr_ctx.device();
    vtr::vector<RRNodeId, bool> node_expanded(device_ctx.rr_graph.nodes().size(), false);
    vtr::vector<RRNodeId, float> node_visited_costs(device_ctx.rr_graph.nodes().size(), -1.0);
    std::priority_queue<PQ_Entry> pq;
    PQ_Entry first_entry(start_node_ind, UNDEFINED, 0, 0, 0, true);
    pq.push(first_entry);
    while (!pq.empty()) {
        PQ_Entry current = pq.top();
        pq.pop();
        RRNodeId node_ind = current.rr_node_ind;
        if (node_expanded[node_ind]) {
            continue;
        }
        if (device_ctx.rr_graph.node_type(node_ind) == IPIN) {
            int ipin_x = device_ctx.rr_graph.node_xlow(node_ind);
            int ipin_y = device_ctx.rr_graph.node_ylow(node_ind);
            if (ipin_x >= start_x && ipin_y >= start_y) {
                int delta_x, delta_y;
                get_xy_deltas(start_node_ind, node_ind, &delta_x, &delta_y);
                routing_cost_map[delta_x][delta_y].add_cost_entry(current.delay, current.congestion_upstream);
            }
        }
        expand_dijkstra_neighbours(current, node_visited_costs, node_expanded, pq);
        node_expanded[node_ind] = true;
    }
}
static void run_dijkstra ( const RRNodeId & start_node_ind , int start_x , int start_y , t_routing_cost_map & routing_cost_map ) { auto & device_ctx = g_vpr_ctx . device ( ) ; vtr :: vector < RRNodeId , bool > node_expanded ( device_ctx . rr_graph . nodes ( ) . size ( ) , false ) ; vtr :: vector < RRNodeId , float > node_visited_costs ( device_ctx . rr_graph . nodes ( ) . size ( ) , -1.0 ) ; std :: priority_queue < PQ_Entry > pq ; PQ_Entry first_entry ( start_node_ind , UNDEFINED , 0 , 0 , 0 , true ) ; pq . push ( first_entry ) ; while ( ! pq . empty ( ) ) { PQ_Entry current = pq . top ( ) ; pq . pop ( ) ; RRNodeId node_ind = current . rr_node_ind ; if ( node_expanded [ node_ind ] ) { continue ; } if ( device_ctx . rr_graph . node_type ( node_ind ) == IPIN ) { int ipin_x = device_ctx . rr_graph . node_xlow ( node_ind ) ; int ipin_y = device_ctx . rr_graph . node_ylow ( node_ind ) ; if ( ipin_x >= start_x && ipin_y >= start_y ) { int delta_x , delta_y ; get_xy_deltas ( start_node_ind , node_ind , & delta_x , & delta_y ) ; routing_cost_map [ delta_x ] [ delta_y ] . add_cost_entry ( current . delay , current . congestion_upstream ) ; } } expand_dijkstra_neighbours ( current , node_visited_costs , node_expanded , pq ) ; node_expanded [ node_ind ] = true ; } }
runs Dijkstra's algorithm from specified node until all nodes have been visited.
runs Dijkstra ' s algorithm from specified node until all nodes have been visited .
/* a list of boolean flags (one for each rr node) to figure out if a certain node has already been expanded */ /* for each node keep a list of the cost with which that node has been visited (used to determine whether to push
     * a candidate node onto the expansion queue */ /* a priority queue for expansion */ /* first entry has no upstream delay or congestion */ /* now do routing */ /* check that we haven't already expanded from this node */ /* if this node is an ipin record its congestion/delay in the routing_cost_map */