diff --git a/vpr/src/route/rr_graph.cpp b/vpr/src/route/rr_graph.cpp
index 33e3d45..d7768e4 100644
--- a/vpr/src/route/rr_graph.cpp
+++ b/vpr/src/route/rr_graph.cpp
@@ -138,6 +138,36 @@
     return RREdgeId::INVALID();
 }
 
+RRNodeId RRGraph::find_node(short x, short y, t_rr_type type, int ptc, e_side side) const {
+    if (!valid_fast_node_lookup()) {
+        build_fast_node_lookup();
+    }
+    size_t itype = type;
+    size_t iside = side;
+    return node_lookup_[x][y][itype][ptc][iside];
+}
+
+RRGraph::node_range RRGraph::find_nodes(short x, short y, t_rr_type type, int ptc) const {
+    if (!valid_fast_node_lookup()) {
+        build_fast_node_lookup();
+    }
+
+    const auto& matching_nodes = node_lookup_[x][y][type][ptc];
+
+    return vtr::make_range(matching_nodes.begin(), matching_nodes.end());
+}
+
+bool RRGraph::is_dirty() const {
+    return dirty_;
+}
+
+void RRGraph::set_dirty() {
+    dirty_ = true;
+}
+
+void RRGraph::clear_dirty() {
+    dirty_ = false;
+}
 
 //Mutators
 RRNodeId RRGraph::create_node(t_rr_type type) {
@@ -161,6 +191,8 @@
     node_in_edges_.emplace_back(); //Initially empty
     node_out_edges_.emplace_back(); //Initially empty
 
+    invalidate_fast_node_lookup();
+
     VTR_ASSERT(validate_sizes());
 
     return node_id;
@@ -212,7 +244,10 @@
     //Mark node invalid
     node_ids_[node] = RRNodeId::INVALID();
 
-    dirty_ = true;
+    //Invalidate the node look-up
+    invalidate_fast_node_lookup();
+
+    set_dirty();
 }
 
 void RRGraph::remove_edge(RREdgeId edge) {
@@ -237,7 +272,7 @@
     //Mark edge invalid
     edge_ids_[edge] = RREdgeId::INVALID();
 
-    dirty_ = true;
+    set_dirty();
 }
 
 void RRGraph::set_node_xlow(RRNodeId node, short xlow) {
@@ -340,6 +375,54 @@
     node_Cs_[node] = C;
 }
 
+void RRGraph::build_fast_node_lookup() const {
+    invalidate_fast_node_lookup();
+
+    for (auto node : nodes()) {
+        size_t x = node_xlow(node);
+        if (x < node_lookup_.size()) {
+            node_lookup_.resize(x + 1);
+        }
+
+        size_t y = node_ylow(node);
+        if (y < node_lookup_[x].size()) {
+            node_lookup_[x].resize(y + 1);
+        }
+
+        size_t itype = node_type(node);
+        if (itype < node_lookup_[x][y].size()) {
+            node_lookup_[x][y].resize(itype + 1);
+        }
+
+        size_t ptc = node_ptc_num(node);
+        if (ptc < node_lookup_[x][y][itype].size()) {
+            node_lookup_[x][y][itype].resize(ptc + 1);
+        }
+
+        size_t iside = -1;
+        if (node_type(node) == OPIN || node_type(node) == IPIN) {
+            iside = node_side(node); 
+        } else {
+            iside = NUM_SIDES;
+        }
+
+        if (iside < node_lookup_[x][y][itype][ptc].size()) {
+            node_lookup_[x][y][itype][ptc].resize(iside + 1);
+        }
+
+        //Save node in lookup
+        node_lookup_[x][y][itype][ptc][iside] = node;
+    }
+}
+
+void RRGraph::invalidate_fast_node_lookup() const {
+    node_lookup_.clear();
+}
+
+bool RRGraph::valid_fast_node_lookup() const {
+    return !node_lookup_.empty();
+}
+
 bool RRGraph::validate() {
     bool success = true;
     success &= validate_sizes();
@@ -495,7 +578,9 @@
 
     rebuild_node_refs(edge_id_map);
 
-    dirty_ = false;
+    invalidate_fast_node_lookup();
+
+    clear_dirty();
 }
 
 void RRGraph::build_id_maps(vtr::vector<RRNodeId,RRNodeId>& node_id_map,
diff --git a/vpr/src/route/rr_graph.h b/vpr/src/route/rr_graph.h
index 1ef8c89..0dcf779 100644
--- a/vpr/src/route/rr_graph.h
+++ b/vpr/src/route/rr_graph.h
@@ -60,6 +60,9 @@
 
         //Utilities
         RREdgeId find_edge(RRNodeId src_node, RRNodeId sink_node) const;
+        RRNodeId find_node(short x, short y, t_rr_type type, int ptc, e_side side=NUM_SIDES) const;
+        node_range find_nodes(short x, short y, t_rr_type type, int ptc) const;
+        bool is_dirty() const;
     public: //Mutators
         RRNodeId create_node(t_rr_type type);
         RREdgeId create_edge(RRNodeId source, RRNodeId sink, RRSwitchId switch_id);
@@ -90,6 +93,14 @@
         void compress();
         bool validate();
     private: //Internal
+        void set_dirty();
+        void clear_dirty();
+
+        //Fast look-up
+        void build_fast_node_lookup() const;
+        void invalidate_fast_node_lookup() const;
+        bool valid_fast_node_lookup() const;
+
         //Validation
         bool valid_node_id(RRNodeId node) const;
         bool valid_edge_id(RREdgeId edge) const;
@@ -143,6 +154,10 @@
 
         //Misc.
         bool dirty_ = false;
+
+        //Fast look-up 
+        typedef std::vector<std::vector<std::vector<std::vector<std::vector<RRNodeId>>>>> NodeLookup;
+        mutable NodeLookup node_lookup_; //[0..xmax][0..ymax][0..NUM_TYPES-1][0..ptc_max][0..NUM_SIDES-1]
 };
 
 #endif