Revert r194300 which broke the build.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@194308 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 158 insertions, 188 deletions

diff --git a/include/llvm/CodeGen/PBQP/Graph.h b/include/llvm/CodeGen/PBQP/Graph.h
index 9f9a567..b57abca 100644
--- a/include/llvm/CodeGen/PBQP/Graph.h
+++ b/include/llvm/CodeGen/PBQP/Graph.h
@@ -20,63 +20,79 @@
 #include "llvm/ADT/ilist_node.h"
 #include <list>
 #include <map>
-#include <set>
 
 namespace PBQP {
 
   /// PBQP Graph class.
   /// Instances of this class describe PBQP problems.
   class Graph {
+  private:
+
+    // ----- TYPEDEFS -----
+    class NodeEntry;
+    class EdgeEntry;
+
+    typedef llvm::ilist<NodeEntry> NodeList;
+    typedef llvm::ilist<EdgeEntry> EdgeList;
+
   public:
 
-    typedef unsigned NodeId;
-    typedef unsigned EdgeId;
+    typedef NodeList::iterator NodeItr;
+    typedef NodeList::const_iterator ConstNodeItr;
 
-  private:
+    typedef EdgeList::iterator EdgeItr;
+    typedef EdgeList::const_iterator ConstEdgeItr;
 
-    typedef std::set<NodeId> AdjEdgeList;
+  private:
 
+    typedef std::list<EdgeItr> AdjEdgeList;
+  
   public:
 
     typedef AdjEdgeList::iterator AdjEdgeItr;
 
   private:
 
-    class NodeEntry {
+    class NodeEntry : public llvm::ilist_node<NodeEntry> {
+      friend struct llvm::ilist_sentinel_traits<NodeEntry>;
     private:
       Vector costs;      
       AdjEdgeList adjEdges;
+      unsigned degree;
       void *data;
       NodeEntry() : costs(0, 0) {}
     public:
-      NodeEntry(const Vector &costs) : costs(costs), data(0) {}
+      NodeEntry(const Vector &costs) : costs(costs), degree(0) {}
       Vector& getCosts() { return costs; }
       const Vector& getCosts() const { return costs; }
-      unsigned getDegree() const { return adjEdges.size(); }
+      unsigned getDegree() const { return degree; }
       AdjEdgeItr edgesBegin() { return adjEdges.begin(); }
       AdjEdgeItr edgesEnd() { return adjEdges.end(); }
-      AdjEdgeItr addEdge(EdgeId e) {
+      AdjEdgeItr addEdge(EdgeItr e) {
+        ++degree;
         return adjEdges.insert(adjEdges.end(), e);
       }
       void removeEdge(AdjEdgeItr ae) {
+        --degree;
         adjEdges.erase(ae);
       }
       void setData(void *data) { this->data = data; }
       void* getData() { return data; }
     };
 
-    class EdgeEntry {
+    class EdgeEntry : public llvm::ilist_node<EdgeEntry> {
+      friend struct llvm::ilist_sentinel_traits<EdgeEntry>;
     private:
-      NodeId node1, node2;
+      NodeItr node1, node2;
       Matrix costs;
       AdjEdgeItr node1AEItr, node2AEItr;
       void *data;
-      EdgeEntry() : costs(0, 0, 0), data(0) {}
+      EdgeEntry() : costs(0, 0, 0) {}
     public:
-      EdgeEntry(NodeId node1, NodeId node2, const Matrix &costs)
+      EdgeEntry(NodeItr node1, NodeItr node2, const Matrix &costs)
         : node1(node1), node2(node2), costs(costs) {}
-      NodeId getNode1() const { return node1; }
-      NodeId getNode2() const { return node2; }
+      NodeItr getNode1() const { return node1; }
+      NodeItr getNode2() const { return node2; }
       Matrix& getCosts() { return costs; }
       const Matrix& getCosts() const { return costs; }
       void setNode1AEItr(AdjEdgeItr ae) { node1AEItr = ae; }
@@ -89,126 +105,52 @@ namespace PBQP {
 
     // ----- MEMBERS -----
 
-    typedef std::vector<NodeEntry> NodeVector;
-    typedef std::vector<NodeVector::size_type> FreeNodeVector;
-    NodeVector nodes;
-    FreeNodeVector freeNodes;
+    NodeList nodes;
+    unsigned numNodes;
 
-    typedef std::vector<EdgeEntry> EdgeVector;
-    typedef std::vector<EdgeVector::size_type> FreeEdgeVector;
-    EdgeVector edges;
-    FreeEdgeVector freeEdges;
+    EdgeList edges;
+    unsigned numEdges;
 
     // ----- INTERNAL METHODS -----
 
-    NodeEntry& getNode(NodeId nId) { return nodes[nId]; }
-    const NodeEntry& getNode(NodeId nId) const { return nodes[nId]; }
-
-    EdgeEntry& getEdge(EdgeId eId) { return edges[eId]; }
-    const EdgeEntry& getEdge(EdgeId eId) const { return edges[eId]; }
-
-    NodeId addConstructedNode(const NodeEntry &n) {
-      NodeId nodeId = 0;
-      if (!freeNodes.empty()) {
-        nodeId = freeNodes.back();
-        freeNodes.pop_back();
-        nodes[nodeId] = n;
-      } else {
-        nodeId = nodes.size();
-        nodes.push_back(n);
-      }
-      return nodeId;
+    NodeEntry& getNode(NodeItr nItr) { return *nItr; }
+    const NodeEntry& getNode(ConstNodeItr nItr) const { return *nItr; }
+
+    EdgeEntry& getEdge(EdgeItr eItr) { return *eItr; }
+    const EdgeEntry& getEdge(ConstEdgeItr eItr) const { return *eItr; }
+
+    NodeItr addConstructedNode(const NodeEntry &n) {
+      ++numNodes;
+      return nodes.insert(nodes.end(), n);
     }
 
-    EdgeId addConstructedEdge(const EdgeEntry &e) {
-      assert(findEdge(e.getNode1(), e.getNode2()) == invalidEdgeId() &&
+    EdgeItr addConstructedEdge(const EdgeEntry &e) {
+      assert(findEdge(e.getNode1(), e.getNode2()) == edges.end() &&
              "Attempt to add duplicate edge.");
-      EdgeId edgeId = 0;
-      if (!freeEdges.empty()) {
-        edgeId = freeEdges.back();
-        freeEdges.pop_back();
-        edges[edgeId] = e;
-      } else {
-        edgeId = edges.size();
-        edges.push_back(e);
-      }
-
-      EdgeEntry &ne = getEdge(edgeId);
+      ++numEdges;
+      EdgeItr edgeItr = edges.insert(edges.end(), e);
+      EdgeEntry &ne = getEdge(edgeItr);
       NodeEntry &n1 = getNode(ne.getNode1());
       NodeEntry &n2 = getNode(ne.getNode2());
-
       // Sanity check on matrix dimensions:
       assert((n1.getCosts().getLength() == ne.getCosts().getRows()) &&
              (n2.getCosts().getLength() == ne.getCosts().getCols()) &&
              "Edge cost dimensions do not match node costs dimensions.");
-
-      ne.setNode1AEItr(n1.addEdge(edgeId));
-      ne.setNode2AEItr(n2.addEdge(edgeId));
-      return edgeId;
+      ne.setNode1AEItr(n1.addEdge(edgeItr));
+      ne.setNode2AEItr(n2.addEdge(edgeItr));
+      return edgeItr;
     }
 
     inline void copyFrom(const Graph &other);
   public:
 
-    class NodeItr {
-    public:
-      NodeItr(NodeId nodeId, const Graph &g)
-        : nodeId(nodeId), endNodeId(g.nodes.size()), freeNodes(g.freeNodes) {
-        this->nodeId = findNextInUse(nodeId); // Move to the first in-use nodeId
-      }
-
-      bool operator==(const NodeItr& n) const { return nodeId == n.nodeId; }
-      bool operator!=(const NodeItr& n) const { return !(*this == n); }
-      NodeItr& operator++() { nodeId = findNextInUse(++nodeId); return *this; }
-      NodeId operator*() const { return nodeId; }
-
-    private:
-      NodeId findNextInUse(NodeId n) const {
-        while (n < endNodeId &&
-               std::find(freeNodes.begin(), freeNodes.end(), n) !=
-                 freeNodes.end()) {
-          ++n;
-        }
-        return n;
-      }
-
-      NodeId nodeId, endNodeId;
-      const FreeNodeVector& freeNodes;
-    };
-
-    class EdgeItr {
-    public:
-      EdgeItr(EdgeId edgeId, const Graph &g)
-        : edgeId(edgeId), endEdgeId(g.edges.size()), freeEdges(g.freeEdges) {
-        this->edgeId = findNextInUse(edgeId); // Move to the first in-use edgeId
-      }
-
-      bool operator==(const EdgeItr& n) const { return edgeId == n.edgeId; }
-      bool operator!=(const EdgeItr& n) const { return !(*this == n); }
-      EdgeItr& operator++() { edgeId = findNextInUse(++edgeId); return *this; }
-      EdgeId operator*() const { return edgeId; }
-
-    private:
-      EdgeId findNextInUse(EdgeId n) const {
-        while (n < endEdgeId &&
-               std::find(freeEdges.begin(), freeEdges.end(), n) !=
-                 freeEdges.end()) {
-          ++n;
-        }
-        return n;
-      }
-
-      EdgeId edgeId, endEdgeId;
-      const FreeEdgeVector& freeEdges;
-    };
-
     /// \brief Construct an empty PBQP graph.
-    Graph() {}
+    Graph() : numNodes(0), numEdges(0) {}
 
     /// \brief Copy construct this graph from "other". Note: Does not copy node
     ///        and edge data, only graph structure and costs.
     /// @param other Source graph to copy from.
-    Graph(const Graph &other) {
+    Graph(const Graph &other) : numNodes(0), numEdges(0) {
       copyFrom(other);
     }
 
@@ -228,7 +170,7 @@ namespace PBQP {
     /// \brief Add a node with the given costs.
     /// @param costs Cost vector for the new node.
     /// @return Node iterator for the added node.
-    NodeId addNode(const Vector &costs) {
+    NodeItr addNode(const Vector &costs) {
       return addConstructedNode(NodeEntry(costs));
     }
 
@@ -236,31 +178,32 @@ namespace PBQP {
     /// @param n1Itr First node.
     /// @param n2Itr Second node.
     /// @return Edge iterator for the added edge.
-    EdgeId addEdge(NodeId n1Id, NodeId n2Id, const Matrix &costs) {
-      assert(getNodeCosts(n1Id).getLength() == costs.getRows() &&
-             getNodeCosts(n2Id).getLength() == costs.getCols() &&
+    EdgeItr addEdge(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr,
+                    const Matrix &costs) {
+      assert(getNodeCosts(n1Itr).getLength() == costs.getRows() &&
+             getNodeCosts(n2Itr).getLength() == costs.getCols() &&
              "Matrix dimensions mismatch.");
-      return addConstructedEdge(EdgeEntry(n1Id, n2Id, costs)); 
+      return addConstructedEdge(EdgeEntry(n1Itr, n2Itr, costs)); 
     }
 
     /// \brief Get the number of nodes in the graph.
     /// @return Number of nodes in the graph.
-    unsigned getNumNodes() const { return nodes.size() - freeNodes.size(); }
+    unsigned getNumNodes() const { return numNodes; }
 
     /// \brief Get the number of edges in the graph.
     /// @return Number of edges in the graph.
-    unsigned getNumEdges() const { return edges.size() - freeEdges.size(); }
+    unsigned getNumEdges() const { return numEdges; }
 
     /// \brief Get a node's cost vector.
     /// @param nItr Node iterator.
     /// @return Node cost vector.
-    Vector& getNodeCosts(NodeId nId) { return getNode(nId).getCosts(); }
+    Vector& getNodeCosts(NodeItr nItr) { return getNode(nItr).getCosts(); }
 
     /// \brief Get a node's cost vector (const version).
     /// @param nItr Node iterator.
     /// @return Node cost vector.
-    const Vector& getNodeCosts(NodeId nId) const {
-      return getNode(nId).getCosts();
+    const Vector& getNodeCosts(ConstNodeItr nItr) const {
+      return getNode(nItr).getCosts();
     }
 
     /// \brief Set a node's data pointer.
@@ -268,23 +211,23 @@ namespace PBQP {
     /// @param data Pointer to node data.
     ///
     /// Typically used by a PBQP solver to attach data to aid in solution.
-    void setNodeData(NodeId nId, void *data) { getNode(nId).setData(data); }
+    void setNodeData(NodeItr nItr, void *data) { getNode(nItr).setData(data); }
 
     /// \brief Get the node's data pointer.
     /// @param nItr Node iterator.
     /// @return Pointer to node data.
-    void* getNodeData(NodeId nId) { return getNode(nId).getData(); }
+    void* getNodeData(NodeItr nItr) { return getNode(nItr).getData(); }
     
     /// \brief Get an edge's cost matrix.
     /// @param eItr Edge iterator.
     /// @return Edge cost matrix.
-    Matrix& getEdgeCosts(EdgeId eId) { return getEdge(eId).getCosts(); }
+    Matrix& getEdgeCosts(EdgeItr eItr) { return getEdge(eItr).getCosts(); }
 
     /// \brief Get an edge's cost matrix (const version).
     /// @param eItr Edge iterator.
     /// @return Edge cost matrix.
-    const Matrix& getEdgeCosts(EdgeId eId) const {
-      return getEdge(eId).getCosts();
+    const Matrix& getEdgeCosts(ConstEdgeItr eItr) const {
+      return getEdge(eItr).getCosts();
     }
 
     /// \brief Set an edge's data pointer.
@@ -292,120 +235,124 @@ namespace PBQP {
     /// @param data Pointer to edge data.
     ///
     /// Typically used by a PBQP solver to attach data to aid in solution.
-    void setEdgeData(EdgeId eId, void *data) { getEdge(eId).setData(data); }
+    void setEdgeData(EdgeItr eItr, void *data) { getEdge(eItr).setData(data); }
 
     /// \brief Get an edge's data pointer.
     /// @param eItr Edge iterator.
     /// @return Pointer to edge data. 
-    void* getEdgeData(EdgeId eId) { return getEdge(eId).getData(); }
+    void* getEdgeData(EdgeItr eItr) { return getEdge(eItr).getData(); }
 
     /// \brief Get a node's degree.
     /// @param nItr Node iterator.
     /// @return The degree of the node.
-    unsigned getNodeDegree(NodeId nId) const {
-      return getNode(nId).getDegree();
+    unsigned getNodeDegree(NodeItr nItr) const {
+      return getNode(nItr).getDegree();
     }
 
     /// \brief Begin iterator for node set.
-    NodeItr nodesBegin() const { return NodeItr(0, *this);  }
+    NodeItr nodesBegin() { return nodes.begin(); }
+
+    /// \brief Begin const iterator for node set.
+    ConstNodeItr nodesBegin() const { return nodes.begin(); }
 
     /// \brief End iterator for node set.
-    NodeItr nodesEnd() const { return NodeItr(nodes.size(), *this); }
+    NodeItr nodesEnd() { return nodes.end(); }
+
+    /// \brief End const iterator for node set.
+    ConstNodeItr nodesEnd() const { return nodes.end(); }
 
     /// \brief Begin iterator for edge set.
-    EdgeItr edgesBegin() const { return EdgeItr(0, *this); }
+    EdgeItr edgesBegin() { return edges.begin(); }
 
     /// \brief End iterator for edge set.
-    EdgeItr edgesEnd() const { return EdgeItr(edges.size(), *this); }
+    EdgeItr edgesEnd() { return edges.end(); }
 
     /// \brief Get begin iterator for adjacent edge set.
     /// @param nItr Node iterator.
     /// @return Begin iterator for the set of edges connected to the given node.
-    AdjEdgeItr adjEdgesBegin(NodeId nId) {
-      return getNode(nId).edgesBegin();
+    AdjEdgeItr adjEdgesBegin(NodeItr nItr) {
+      return getNode(nItr).edgesBegin();
     }
 
     /// \brief Get end iterator for adjacent edge set.
     /// @param nItr Node iterator.
     /// @return End iterator for the set of edges connected to the given node.
-    AdjEdgeItr adjEdgesEnd(NodeId nId) {
-      return getNode(nId).edgesEnd();
+    AdjEdgeItr adjEdgesEnd(NodeItr nItr) {
+      return getNode(nItr).edgesEnd();
     }
 
     /// \brief Get the first node connected to this edge.
     /// @param eItr Edge iterator.
     /// @return The first node connected to the given edge. 
-    NodeId getEdgeNode1(EdgeId eId) {
-      return getEdge(eId).getNode1();
+    NodeItr getEdgeNode1(EdgeItr eItr) {
+      return getEdge(eItr).getNode1();
     }
 
     /// \brief Get the second node connected to this edge.
     /// @param eItr Edge iterator.
     /// @return The second node connected to the given edge. 
-    NodeId getEdgeNode2(EdgeId eId) {
-      return getEdge(eId).getNode2();
+    NodeItr getEdgeNode2(EdgeItr eItr) {
+      return getEdge(eItr).getNode2();
     } 
 
     /// \brief Get the "other" node connected to this edge.
     /// @param eItr Edge iterator.
     /// @param nItr Node iterator for the "given" node.
     /// @return The iterator for the "other" node connected to this edge. 
-    NodeId getEdgeOtherNode(EdgeId eId, NodeId nId) {
-      EdgeEntry &e = getEdge(eId);
-      if (e.getNode1() == nId) {
+    NodeItr getEdgeOtherNode(EdgeItr eItr, NodeItr nItr) {
+      EdgeEntry &e = getEdge(eItr);
+      if (e.getNode1() == nItr) {
         return e.getNode2();
       } // else
       return e.getNode1();
     }
 
-    EdgeId invalidEdgeId() const {
-      return std::numeric_limits<EdgeVector::size_type>::max();
-    }
-
     /// \brief Get the edge connecting two nodes.
-    /// @param n1Id First node id.
-    /// @param n2Id Second node id.
-    /// @return An id for edge (n1Id, n2Id) if such an edge exists,
-    ///         otherwise returns an invalid edge id.
-    EdgeId findEdge(NodeId n1Id, NodeId n2Id) {
-      for (AdjEdgeItr aeItr = adjEdgesBegin(n1Id), aeEnd = adjEdgesEnd(n1Id);
+    /// @param n1Itr First node iterator.
+    /// @param n2Itr Second node iterator.
+    /// @return An iterator for edge (n1Itr, n2Itr) if such an edge exists,
+    ///         otherwise returns edgesEnd(). 
+    EdgeItr findEdge(NodeItr n1Itr, NodeItr n2Itr) {
+      for (AdjEdgeItr aeItr = adjEdgesBegin(n1Itr), aeEnd = adjEdgesEnd(n1Itr);
          aeItr != aeEnd; ++aeItr) {
-        if ((getEdgeNode1(*aeItr) == n2Id) ||
-            (getEdgeNode2(*aeItr) == n2Id)) {
+        if ((getEdgeNode1(*aeItr) == n2Itr) ||
+            (getEdgeNode2(*aeItr) == n2Itr)) {
           return *aeItr;
         }
       }
-      return invalidEdgeId();
+      return edges.end();
     }
 
     /// \brief Remove a node from the graph.
-    /// @param nItr Node id.
-    void removeNode(NodeId nId) {
-      NodeEntry &n = getNode(nId);
-      for (AdjEdgeItr itr = n.edgesBegin(), end = n.edgesEnd(); itr != end; ++itr) {
-        EdgeId eId = *itr;
-        removeEdge(eId); 
+    /// @param nItr Node iterator.
+    void removeNode(NodeItr nItr) {
+      NodeEntry &n = getNode(nItr);
+      for (AdjEdgeItr itr = n.edgesBegin(), end = n.edgesEnd(); itr != end;) {
+        EdgeItr eItr = *itr;
+        ++itr;
+        removeEdge(eItr); 
       }
-      freeNodes.push_back(nId);
+      nodes.erase(nItr);
+      --numNodes;
     }
 
     /// \brief Remove an edge from the graph.
     /// @param eItr Edge iterator.
-    void removeEdge(EdgeId eId) {
-      EdgeEntry &e = getEdge(eId);
+    void removeEdge(EdgeItr eItr) {
+      EdgeEntry &e = getEdge(eItr);
       NodeEntry &n1 = getNode(e.getNode1());
       NodeEntry &n2 = getNode(e.getNode2());
       n1.removeEdge(e.getNode1AEItr());
       n2.removeEdge(e.getNode2AEItr());
-      freeEdges.push_back(eId);
+      edges.erase(eItr);
+      --numEdges;
     }
 
     /// \brief Remove all nodes and edges from the graph.
     void clear() {
       nodes.clear();
-      freeNodes.clear();
       edges.clear();
-      freeEdges.clear();
+      numNodes = numEdges = 0;
     }
 
     /// \brief Dump a graph to an output stream.
@@ -415,7 +362,7 @@ namespace PBQP {
 
       for (NodeItr nodeItr = nodesBegin(), nodeEnd = nodesEnd();
            nodeItr != nodeEnd; ++nodeItr) {
-        const Vector& v = getNodeCosts(*nodeItr);
+        const Vector& v = getNodeCosts(nodeItr);
         os << "\n" << v.getLength() << "\n";
         assert(v.getLength() != 0 && "Empty vector in graph.");
         os << v[0];
@@ -427,10 +374,10 @@ namespace PBQP {
 
       for (EdgeItr edgeItr = edgesBegin(), edgeEnd = edgesEnd();
            edgeItr != edgeEnd; ++edgeItr) {
-        NodeId n1 = getEdgeNode1(*edgeItr);
-        NodeId n2 = getEdgeNode2(*edgeItr);
+        unsigned n1 = std::distance(nodesBegin(), getEdgeNode1(edgeItr));
+        unsigned n2 = std::distance(nodesBegin(), getEdgeNode2(edgeItr));
         assert(n1 != n2 && "PBQP graphs shound not have self-edges.");
-        const Matrix& m = getEdgeCosts(*edgeItr);
+        const Matrix& m = getEdgeCosts(edgeItr);
         os << "\n" << n1 << " " << n2 << "\n"
            << m.getRows() << " " << m.getCols() << "\n";
         assert(m.getRows() != 0 && "No rows in matrix.");
@@ -456,7 +403,7 @@ namespace PBQP {
            nodeItr != nodeEnd; ++nodeItr) {
 
         os << "  node" << nodeItr << " [ label=\""
-           << nodeItr << ": " << getNodeCosts(*nodeItr) << "\" ]\n";
+           << nodeItr << ": " << getNodeCosts(nodeItr) << "\" ]\n";
       }
 
       os << "  edge [ len=" << getNumNodes() << " ]\n";
@@ -464,11 +411,11 @@ namespace PBQP {
       for (EdgeItr edgeItr = edgesBegin(), edgeEnd = edgesEnd();
            edgeItr != edgeEnd; ++edgeItr) {
 
-        os << "  node" << getEdgeNode1(*edgeItr)
-           << " -- node" << getEdgeNode2(*edgeItr)
+        os << "  node" << getEdgeNode1(edgeItr)
+           << " -- node" << getEdgeNode2(edgeItr)
            << " [ label=\"";
 
-        const Matrix &edgeCosts = getEdgeCosts(*edgeItr);
+        const Matrix &edgeCosts = getEdgeCosts(edgeItr);
 
         for (unsigned i = 0; i < edgeCosts.getRows(); ++i) {
           os << edgeCosts.getRowAsVector(i) << "\\n";
@@ -480,16 +427,39 @@ namespace PBQP {
 
   };
 
-//  void Graph::copyFrom(const Graph &other) {
-//     std::map<Graph::ConstNodeItr, Graph::NodeItr,
-//              NodeItrComparator> nodeMap;
+  class NodeItrComparator {
+  public:
+    bool operator()(Graph::NodeItr n1, Graph::NodeItr n2) const {
+      return &*n1 < &*n2;
+    }
+
+    bool operator()(Graph::ConstNodeItr n1, Graph::ConstNodeItr n2) const {
+      return &*n1 < &*n2;
+    }
+  };
+
+  class EdgeItrCompartor {
+  public:
+    bool operator()(Graph::EdgeItr e1, Graph::EdgeItr e2) const {
+      return &*e1 < &*e2;
+    }
+
+    bool operator()(Graph::ConstEdgeItr e1, Graph::ConstEdgeItr e2) const {
+      return &*e1 < &*e2;
+    }
+  };
+
+  void Graph::copyFrom(const Graph &other) {
+    std::map<Graph::ConstNodeItr, Graph::NodeItr,
+             NodeItrComparator> nodeMap;
 
-//      for (Graph::ConstNodeItr nItr = other.nodesBegin(),
-//                              nEnd = other.nodesEnd();
-//          nItr != nEnd; ++nItr) {
-//       nodeMap[nItr] = addNode(other.getNodeCosts(nItr));
-//     }      
-//  }
+     for (Graph::ConstNodeItr nItr = other.nodesBegin(),
+                             nEnd = other.nodesEnd();
+         nItr != nEnd; ++nItr) {
+      nodeMap[nItr] = addNode(other.getNodeCosts(nItr));
+    }
+      
+  }
 
 }