include/llvm/CodeGen/PBQP/Graph.h - llvm - Git at Google

 //===- Graph.h - PBQP Graph -------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // PBQP Graph class.
 //
 //===----------------------------------------------------------------------===//

 #ifndef LLVM_CODEGEN_PBQP_GRAPH_H
 #define LLVM_CODEGEN_PBQP_GRAPH_H

 #include "llvm/ADT/STLExtras.h"
 #include <algorithm>
 #include <cassert>
 #include <iterator>
 #include <limits>
 #include <vector>

 namespace llvm {
 namespace PBQP {

   class GraphBase {
   public:
     using NodeId = unsigned;
     using EdgeId = unsigned;

     /// Returns a value representing an invalid (non-existent) node.
     static NodeId invalidNodeId() {
       return std::numeric_limits<NodeId>::max();
     }

     /// Returns a value representing an invalid (non-existent) edge.
     static EdgeId invalidEdgeId() {
       return std::numeric_limits<EdgeId>::max();
     }
   };

   /// PBQP Graph class.
   /// Instances of this class describe PBQP problems.
   ///
   template <typename SolverT>
   class Graph : public GraphBase {
   private:
     using CostAllocator = typename SolverT::CostAllocator;

   public:
     using RawVector = typename SolverT::RawVector;
     using RawMatrix = typename SolverT::RawMatrix;
     using Vector = typename SolverT::Vector;
     using Matrix = typename SolverT::Matrix;
     using VectorPtr = typename CostAllocator::VectorPtr;
     using MatrixPtr = typename CostAllocator::MatrixPtr;
     using NodeMetadata = typename SolverT::NodeMetadata;
     using EdgeMetadata = typename SolverT::EdgeMetadata;
     using GraphMetadata = typename SolverT::GraphMetadata;

   private:
     class NodeEntry {
     public:
       using AdjEdgeList = std::vector<EdgeId>;
       using AdjEdgeIdx = AdjEdgeList::size_type;
       using AdjEdgeItr = AdjEdgeList::const_iterator;

       NodeEntry(VectorPtr Costs) : Costs(std::move(Costs)) {}

       static AdjEdgeIdx getInvalidAdjEdgeIdx() {
         return std::numeric_limits<AdjEdgeIdx>::max();
       }

       AdjEdgeIdx addAdjEdgeId(EdgeId EId) {
         AdjEdgeIdx Idx = AdjEdgeIds.size();
         AdjEdgeIds.push_back(EId);
         return Idx;
       }

       void removeAdjEdgeId(Graph &G, NodeId ThisNId, AdjEdgeIdx Idx) {
         // Swap-and-pop for fast removal.
         //   1) Update the adj index of the edge currently at back().
         //   2) Move last Edge down to Idx.
         //   3) pop_back()
         // If Idx == size() - 1 then the setAdjEdgeIdx and swap are
         // redundant, but both operations are cheap.
         G.getEdge(AdjEdgeIds.back()).setAdjEdgeIdx(ThisNId, Idx);
         AdjEdgeIds[Idx] = AdjEdgeIds.back();
         AdjEdgeIds.pop_back();
       }

       const AdjEdgeList& getAdjEdgeIds() const { return AdjEdgeIds; }

       VectorPtr Costs;
       NodeMetadata Metadata;

     private:
       AdjEdgeList AdjEdgeIds;
     };

     class EdgeEntry {
     public:
       EdgeEntry(NodeId N1Id, NodeId N2Id, MatrixPtr Costs)
           : Costs(std::move(Costs)) {
         NIds[0] = N1Id;
         NIds[1] = N2Id;
         ThisEdgeAdjIdxs[0] = NodeEntry::getInvalidAdjEdgeIdx();
         ThisEdgeAdjIdxs[1] = NodeEntry::getInvalidAdjEdgeIdx();
       }

       void connectToN(Graph &G, EdgeId ThisEdgeId, unsigned NIdx) {
         assert(ThisEdgeAdjIdxs[NIdx] == NodeEntry::getInvalidAdjEdgeIdx() &&
                "Edge already connected to NIds[NIdx].");
         NodeEntry &N = G.getNode(NIds[NIdx]);
         ThisEdgeAdjIdxs[NIdx] = N.addAdjEdgeId(ThisEdgeId);
       }

       void connect(Graph &G, EdgeId ThisEdgeId) {
         connectToN(G, ThisEdgeId, 0);
         connectToN(G, ThisEdgeId, 1);
       }

       void setAdjEdgeIdx(NodeId NId, typename NodeEntry::AdjEdgeIdx NewIdx) {
         if (NId == NIds[0])
           ThisEdgeAdjIdxs[0] = NewIdx;
         else {
           assert(NId == NIds[1] && "Edge not connected to NId");
           ThisEdgeAdjIdxs[1] = NewIdx;
         }
       }

       void disconnectFromN(Graph &G, unsigned NIdx) {
         assert(ThisEdgeAdjIdxs[NIdx] != NodeEntry::getInvalidAdjEdgeIdx() &&
                "Edge not connected to NIds[NIdx].");
         NodeEntry &N = G.getNode(NIds[NIdx]);
         N.removeAdjEdgeId(G, NIds[NIdx], ThisEdgeAdjIdxs[NIdx]);
         ThisEdgeAdjIdxs[NIdx] = NodeEntry::getInvalidAdjEdgeIdx();
       }

       void disconnectFrom(Graph &G, NodeId NId) {
         if (NId == NIds[0])
           disconnectFromN(G, 0);
         else {
           assert(NId == NIds[1] && "Edge does not connect NId");
           disconnectFromN(G, 1);
         }
       }

       NodeId getN1Id() const { return NIds[0]; }
       NodeId getN2Id() const { return NIds[1]; }

       MatrixPtr Costs;
       EdgeMetadata Metadata;

     private:
       NodeId NIds[2];
       typename NodeEntry::AdjEdgeIdx ThisEdgeAdjIdxs[2];
     };

     // ----- MEMBERS -----

     GraphMetadata Metadata;
     CostAllocator CostAlloc;
     SolverT *Solver = nullptr;

     using NodeVector = std::vector<NodeEntry>;
     using FreeNodeVector = std::vector<NodeId>;
     NodeVector Nodes;
     FreeNodeVector FreeNodeIds;

     using EdgeVector = std::vector<EdgeEntry>;
     using FreeEdgeVector = std::vector<EdgeId>;
     EdgeVector Edges;
     FreeEdgeVector FreeEdgeIds;

     Graph(const Graph &Other) {}

     // ----- INTERNAL METHODS -----

     NodeEntry &getNode(NodeId NId) {
       assert(NId < Nodes.size() && "Out of bound NodeId");
       return Nodes[NId];
     }
     const NodeEntry &getNode(NodeId NId) const {
       assert(NId < Nodes.size() && "Out of bound NodeId");
       return Nodes[NId];
     }

     EdgeEntry& getEdge(EdgeId EId) { return Edges[EId]; }
     const EdgeEntry& getEdge(EdgeId EId) const { return Edges[EId]; }

     NodeId addConstructedNode(NodeEntry N) {
       NodeId NId = 0;
       if (!FreeNodeIds.empty()) {
         NId = FreeNodeIds.back();
         FreeNodeIds.pop_back();
         Nodes[NId] = std::move(N);
       } else {
         NId = Nodes.size();
         Nodes.push_back(std::move(N));
       }
       return NId;
     }

     EdgeId addConstructedEdge(EdgeEntry E) {
       assert(findEdge(E.getN1Id(), E.getN2Id()) == invalidEdgeId() &&
              "Attempt to add duplicate edge.");
       EdgeId EId = 0;
       if (!FreeEdgeIds.empty()) {
         EId = FreeEdgeIds.back();
         FreeEdgeIds.pop_back();
         Edges[EId] = std::move(E);
       } else {
         EId = Edges.size();
         Edges.push_back(std::move(E));
       }

       EdgeEntry &NE = getEdge(EId);

       // Add the edge to the adjacency sets of its nodes.
       NE.connect(*this, EId);
       return EId;
     }

     void operator=(const Graph &Other) {}

   public:
     using AdjEdgeItr = typename NodeEntry::AdjEdgeItr;

     class NodeItr {
     public:
       using iterator_category = std::forward_iterator_tag;
       using value_type = NodeId;
       using difference_type = int;
       using pointer = NodeId *;
       using reference = NodeId &;

       NodeItr(NodeId CurNId, const Graph &G)
         : CurNId(CurNId), EndNId(G.Nodes.size()), FreeNodeIds(G.FreeNodeIds) {
         this->CurNId = findNextInUse(CurNId); // Move to first in-use node id
       }

       bool operator==(const NodeItr &O) const { return CurNId == O.CurNId; }
       bool operator!=(const NodeItr &O) const { return !(*this == O); }
       NodeItr& operator++() { CurNId = findNextInUse(++CurNId); return *this; }
       NodeId operator*() const { return CurNId; }

     private:
       NodeId findNextInUse(NodeId NId) const {
         while (NId < EndNId && is_contained(FreeNodeIds, NId)) {
           ++NId;
         }
         return NId;
       }

       NodeId CurNId, EndNId;
       const FreeNodeVector &FreeNodeIds;
     };

     class EdgeItr {
     public:
       EdgeItr(EdgeId CurEId, const Graph &G)
         : CurEId(CurEId), EndEId(G.Edges.size()), FreeEdgeIds(G.FreeEdgeIds) {
         this->CurEId = findNextInUse(CurEId); // Move to first in-use edge id
       }

       bool operator==(const EdgeItr &O) const { return CurEId == O.CurEId; }
       bool operator!=(const EdgeItr &O) const { return !(*this == O); }
       EdgeItr& operator++() { CurEId = findNextInUse(++CurEId); return *this; }
       EdgeId operator*() const { return CurEId; }

     private:
       EdgeId findNextInUse(EdgeId EId) const {
         while (EId < EndEId && is_contained(FreeEdgeIds, EId)) {
           ++EId;
         }
         return EId;
       }

       EdgeId CurEId, EndEId;
       const FreeEdgeVector &FreeEdgeIds;
     };

     class NodeIdSet {
     public:
       NodeIdSet(const Graph &G) : G(G) {}

       NodeItr begin() const { return NodeItr(0, G); }
       NodeItr end() const { return NodeItr(G.Nodes.size(), G); }

       bool empty() const { return G.Nodes.empty(); }

       typename NodeVector::size_type size() const {
         return G.Nodes.size() - G.FreeNodeIds.size();
       }

     private:
       const Graph& G;
     };

     class EdgeIdSet {
     public:
       EdgeIdSet(const Graph &G) : G(G) {}

       EdgeItr begin() const { return EdgeItr(0, G); }
       EdgeItr end() const { return EdgeItr(G.Edges.size(), G); }

       bool empty() const { return G.Edges.empty(); }

       typename NodeVector::size_type size() const {
         return G.Edges.size() - G.FreeEdgeIds.size();
       }

     private:
       const Graph& G;
     };

     class AdjEdgeIdSet {
     public:
       AdjEdgeIdSet(const NodeEntry &NE) : NE(NE) {}

       typename NodeEntry::AdjEdgeItr begin() const {
         return NE.getAdjEdgeIds().begin();
       }

       typename NodeEntry::AdjEdgeItr end() const {
         return NE.getAdjEdgeIds().end();
       }

       bool empty() const { return NE.getAdjEdgeIds().empty(); }

       typename NodeEntry::AdjEdgeList::size_type size() const {
         return NE.getAdjEdgeIds().size();
       }

     private:
       const NodeEntry &NE;
     };

     /// Construct an empty PBQP graph.
     Graph() = default;

     /// Construct an empty PBQP graph with the given graph metadata.
     Graph(GraphMetadata Metadata) : Metadata(std::move(Metadata)) {}

     /// Get a reference to the graph metadata.
     GraphMetadata& getMetadata() { return Metadata; }

     /// Get a const-reference to the graph metadata.
     const GraphMetadata& getMetadata() const { return Metadata; }

     /// Lock this graph to the given solver instance in preparation
     /// for running the solver. This method will call solver.handleAddNode for
     /// each node in the graph, and handleAddEdge for each edge, to give the
     /// solver an opportunity to set up any requried metadata.
     void setSolver(SolverT &S) {
       assert(!Solver && "Solver already set. Call unsetSolver().");
       Solver = &S;
       for (auto NId : nodeIds())
         Solver->handleAddNode(NId);
       for (auto EId : edgeIds())
         Solver->handleAddEdge(EId);
     }

     /// Release from solver instance.
     void unsetSolver() {
       assert(Solver && "Solver not set.");
       Solver = nullptr;
     }

     /// Add a node with the given costs.
     /// @param Costs Cost vector for the new node.
     /// @return Node iterator for the added node.
     template <typename OtherVectorT>
     NodeId addNode(OtherVectorT Costs) {
       // Get cost vector from the problem domain
       VectorPtr AllocatedCosts = CostAlloc.getVector(std::move(Costs));
       NodeId NId = addConstructedNode(NodeEntry(AllocatedCosts));
       if (Solver)
         Solver->handleAddNode(NId);
       return NId;
     }

     /// Add a node bypassing the cost allocator.
     /// @param Costs Cost vector ptr for the new node (must be convertible to
     ///        VectorPtr).
     /// @return Node iterator for the added node.
     ///
     ///   This method allows for fast addition of a node whose costs don't need
     /// to be passed through the cost allocator. The most common use case for
     /// this is when duplicating costs from an existing node (when using a
     /// pooling allocator). These have already been uniqued, so we can avoid
     /// re-constructing and re-uniquing them by attaching them directly to the
     /// new node.
     template <typename OtherVectorPtrT>
     NodeId addNodeBypassingCostAllocator(OtherVectorPtrT Costs) {
       NodeId NId = addConstructedNode(NodeEntry(Costs));
       if (Solver)
         Solver->handleAddNode(NId);
       return NId;
     }

     /// Add an edge between the given nodes with the given costs.
     /// @param N1Id First node.
     /// @param N2Id Second node.
     /// @param Costs Cost matrix for new edge.
     /// @return Edge iterator for the added edge.
     template <typename OtherVectorT>
     EdgeId addEdge(NodeId N1Id, NodeId N2Id, OtherVectorT Costs) {
       assert(getNodeCosts(N1Id).getLength() == Costs.getRows() &&
              getNodeCosts(N2Id).getLength() == Costs.getCols() &&
              "Matrix dimensions mismatch.");
       // Get cost matrix from the problem domain.
       MatrixPtr AllocatedCosts = CostAlloc.getMatrix(std::move(Costs));
       EdgeId EId = addConstructedEdge(EdgeEntry(N1Id, N2Id, AllocatedCosts));
       if (Solver)
         Solver->handleAddEdge(EId);
       return EId;
     }

     /// Add an edge bypassing the cost allocator.
     /// @param N1Id First node.
     /// @param N2Id Second node.
     /// @param Costs Cost matrix for new edge.
     /// @return Edge iterator for the added edge.
     ///
     ///   This method allows for fast addition of an edge whose costs don't need
     /// to be passed through the cost allocator. The most common use case for
     /// this is when duplicating costs from an existing edge (when using a
     /// pooling allocator). These have already been uniqued, so we can avoid
     /// re-constructing and re-uniquing them by attaching them directly to the
     /// new edge.
     template <typename OtherMatrixPtrT>
     NodeId addEdgeBypassingCostAllocator(NodeId N1Id, NodeId N2Id,
                                          OtherMatrixPtrT Costs) {
       assert(getNodeCosts(N1Id).getLength() == Costs->getRows() &&
              getNodeCosts(N2Id).getLength() == Costs->getCols() &&
              "Matrix dimensions mismatch.");
       // Get cost matrix from the problem domain.
       EdgeId EId = addConstructedEdge(EdgeEntry(N1Id, N2Id, Costs));
       if (Solver)
         Solver->handleAddEdge(EId);
       return EId;
     }

     /// Returns true if the graph is empty.
     bool empty() const { return NodeIdSet(*this).empty(); }

     NodeIdSet nodeIds() const { return NodeIdSet(*this); }
     EdgeIdSet edgeIds() const { return EdgeIdSet(*this); }

     AdjEdgeIdSet adjEdgeIds(NodeId NId) { return AdjEdgeIdSet(getNode(NId)); }

     /// Get the number of nodes in the graph.
     /// @return Number of nodes in the graph.
     unsigned getNumNodes() const { return NodeIdSet(*this).size(); }

     /// Get the number of edges in the graph.
     /// @return Number of edges in the graph.
     unsigned getNumEdges() const { return EdgeIdSet(*this).size(); }

     /// Set a node's cost vector.
     /// @param NId Node to update.
     /// @param Costs New costs to set.
     template <typename OtherVectorT>
     void setNodeCosts(NodeId NId, OtherVectorT Costs) {
       VectorPtr AllocatedCosts = CostAlloc.getVector(std::move(Costs));
       if (Solver)
         Solver->handleSetNodeCosts(NId, *AllocatedCosts);
       getNode(NId).Costs = AllocatedCosts;
     }

     /// Get a VectorPtr to a node's cost vector. Rarely useful - use
     ///        getNodeCosts where possible.
     /// @param NId Node id.
     /// @return VectorPtr to node cost vector.
     ///
     ///   This method is primarily useful for duplicating costs quickly by
     /// bypassing the cost allocator. See addNodeBypassingCostAllocator. Prefer
     /// getNodeCosts when dealing with node cost values.
     const VectorPtr& getNodeCostsPtr(NodeId NId) const {
       return getNode(NId).Costs;
     }

     /// Get a node's cost vector.
     /// @param NId Node id.
     /// @return Node cost vector.
     const Vector& getNodeCosts(NodeId NId) const {
       return *getNodeCostsPtr(NId);
     }

     NodeMetadata& getNodeMetadata(NodeId NId) {
       return getNode(NId).Metadata;
     }

     const NodeMetadata& getNodeMetadata(NodeId NId) const {
       return getNode(NId).Metadata;
     }

     typename NodeEntry::AdjEdgeList::size_type getNodeDegree(NodeId NId) const {
       return getNode(NId).getAdjEdgeIds().size();
     }

     /// Update an edge's cost matrix.
     /// @param EId Edge id.
     /// @param Costs New cost matrix.
     template <typename OtherMatrixT>
     void updateEdgeCosts(EdgeId EId, OtherMatrixT Costs) {
       MatrixPtr AllocatedCosts = CostAlloc.getMatrix(std::move(Costs));
       if (Solver)
         Solver->handleUpdateCosts(EId, *AllocatedCosts);
       getEdge(EId).Costs = AllocatedCosts;
     }

     /// Get a MatrixPtr to a node's cost matrix. Rarely useful - use
     ///        getEdgeCosts where possible.
     /// @param EId Edge id.
     /// @return MatrixPtr to edge cost matrix.
     ///
     ///   This method is primarily useful for duplicating costs quickly by
     /// bypassing the cost allocator. See addNodeBypassingCostAllocator. Prefer
     /// getEdgeCosts when dealing with edge cost values.
     const MatrixPtr& getEdgeCostsPtr(EdgeId EId) const {
       return getEdge(EId).Costs;
     }

     /// Get an edge's cost matrix.
     /// @param EId Edge id.
     /// @return Edge cost matrix.
     const Matrix& getEdgeCosts(EdgeId EId) const {
       return *getEdge(EId).Costs;
     }

     EdgeMetadata& getEdgeMetadata(EdgeId EId) {
       return getEdge(EId).Metadata;
     }

     const EdgeMetadata& getEdgeMetadata(EdgeId EId) const {
       return getEdge(EId).Metadata;
     }

     /// Get the first node connected to this edge.
     /// @param EId Edge id.
     /// @return The first node connected to the given edge.
     NodeId getEdgeNode1Id(EdgeId EId) const {
       return getEdge(EId).getN1Id();
     }

     /// Get the second node connected to this edge.
     /// @param EId Edge id.
     /// @return The second node connected to the given edge.
     NodeId getEdgeNode2Id(EdgeId EId) const {
       return getEdge(EId).getN2Id();
     }

     /// Get the "other" node connected to this edge.
     /// @param EId Edge id.
     /// @param NId Node id for the "given" node.
     /// @return The iterator for the "other" node connected to this edge.
     NodeId getEdgeOtherNodeId(EdgeId EId, NodeId NId) {
       EdgeEntry &E = getEdge(EId);
       if (E.getN1Id() == NId) {
         return E.getN2Id();
       } // else
       return E.getN1Id();
     }

     /// 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 (auto AEId : adjEdgeIds(N1Id)) {
         if ((getEdgeNode1Id(AEId) == N2Id) ||
             (getEdgeNode2Id(AEId) == N2Id)) {
           return AEId;
         }
       }
       return invalidEdgeId();
     }

     /// Remove a node from the graph.
     /// @param NId Node id.
     void removeNode(NodeId NId) {
       if (Solver)
         Solver->handleRemoveNode(NId);
       NodeEntry &N = getNode(NId);
       // TODO: Can this be for-each'd?
       for (AdjEdgeItr AEItr = N.adjEdgesBegin(),
              AEEnd = N.adjEdgesEnd();
            AEItr != AEEnd;) {
         EdgeId EId = *AEItr;
         ++AEItr;
         removeEdge(EId);
       }
       FreeNodeIds.push_back(NId);
     }

     /// Disconnect an edge from the given node.
     ///
     /// Removes the given edge from the adjacency list of the given node.
     /// This operation leaves the edge in an 'asymmetric' state: It will no
     /// longer appear in an iteration over the given node's (NId's) edges, but
     /// will appear in an iteration over the 'other', unnamed node's edges.
     ///
     /// This does not correspond to any normal graph operation, but exists to
     /// support efficient PBQP graph-reduction based solvers. It is used to
     /// 'effectively' remove the unnamed node from the graph while the solver
     /// is performing the reduction. The solver will later call reconnectNode
     /// to restore the edge in the named node's adjacency list.
     ///
     /// Since the degree of a node is the number of connected edges,
     /// disconnecting an edge from a node 'u' will cause the degree of 'u' to
     /// drop by 1.
     ///
     /// A disconnected edge WILL still appear in an iteration over the graph
     /// edges.
     ///
     /// A disconnected edge should not be removed from the graph, it should be
     /// reconnected first.
     ///
     /// A disconnected edge can be reconnected by calling the reconnectEdge
     /// method.
     void disconnectEdge(EdgeId EId, NodeId NId) {
       if (Solver)
         Solver->handleDisconnectEdge(EId, NId);

       EdgeEntry &E = getEdge(EId);
       E.disconnectFrom(*this, NId);
     }

     /// Convenience method to disconnect all neighbours from the given
     ///        node.
     void disconnectAllNeighborsFromNode(NodeId NId) {
       for (auto AEId : adjEdgeIds(NId))
         disconnectEdge(AEId, getEdgeOtherNodeId(AEId, NId));
     }

     /// Re-attach an edge to its nodes.
     ///
     /// Adds an edge that had been previously disconnected back into the
     /// adjacency set of the nodes that the edge connects.
     void reconnectEdge(EdgeId EId, NodeId NId) {
       EdgeEntry &E = getEdge(EId);
       E.connectTo(*this, EId, NId);
       if (Solver)
         Solver->handleReconnectEdge(EId, NId);
     }

     /// Remove an edge from the graph.
     /// @param EId Edge id.
     void removeEdge(EdgeId EId) {
       if (Solver)
         Solver->handleRemoveEdge(EId);
       EdgeEntry &E = getEdge(EId);
       E.disconnect();
       FreeEdgeIds.push_back(EId);
       Edges[EId].invalidate();
     }

     /// Remove all nodes and edges from the graph.
     void clear() {
       Nodes.clear();
       FreeNodeIds.clear();
       Edges.clear();
       FreeEdgeIds.clear();
     }
   };

 } // end namespace PBQP
 } // end namespace llvm

 #endif // LLVM_CODEGEN_PBQP_GRAPH_HPP
	//===- Graph.h - PBQP Graph -------------------------------------- C++ --===//
	//
	// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
	// See https://llvm.org/LICENSE.txt for license information.
	// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
	//
	//===----------------------------------------------------------------------===//
	//
	// PBQP Graph class.
	//
	//===----------------------------------------------------------------------===//

	#ifndef LLVM_CODEGEN_PBQP_GRAPH_H
	#define LLVM_CODEGEN_PBQP_GRAPH_H

	#include "llvm/ADT/STLExtras.h"
	#include <algorithm>
	#include <cassert>
	#include <iterator>
	#include <limits>
	#include <vector>

	namespace llvm {
	namespace PBQP {

	class GraphBase {
	public:
	using NodeId = unsigned;
	using EdgeId = unsigned;

	/// Returns a value representing an invalid (non-existent) node.
	static NodeId invalidNodeId() {
	return std::numeric_limits<NodeId>::max();
	}

	/// Returns a value representing an invalid (non-existent) edge.
	static EdgeId invalidEdgeId() {
	return std::numeric_limits<EdgeId>::max();
	}
	};

	/// PBQP Graph class.
	/// Instances of this class describe PBQP problems.
	///
	template <typename SolverT>
	class Graph : public GraphBase {
	private:
	using CostAllocator = typename SolverT::CostAllocator;

	public:
	using RawVector = typename SolverT::RawVector;
	using RawMatrix = typename SolverT::RawMatrix;
	using Vector = typename SolverT::Vector;
	using Matrix = typename SolverT::Matrix;
	using VectorPtr = typename CostAllocator::VectorPtr;
	using MatrixPtr = typename CostAllocator::MatrixPtr;
	using NodeMetadata = typename SolverT::NodeMetadata;
	using EdgeMetadata = typename SolverT::EdgeMetadata;
	using GraphMetadata = typename SolverT::GraphMetadata;

	private:
	class NodeEntry {
	public:
	using AdjEdgeList = std::vector<EdgeId>;
	using AdjEdgeIdx = AdjEdgeList::size_type;
	using AdjEdgeItr = AdjEdgeList::const_iterator;

	NodeEntry(VectorPtr Costs) : Costs(std::move(Costs)) {}

	static AdjEdgeIdx getInvalidAdjEdgeIdx() {
	return std::numeric_limits<AdjEdgeIdx>::max();
	}

	AdjEdgeIdx addAdjEdgeId(EdgeId EId) {
	AdjEdgeIdx Idx = AdjEdgeIds.size();
	AdjEdgeIds.push_back(EId);
	return Idx;
	}

	void removeAdjEdgeId(Graph &G, NodeId ThisNId, AdjEdgeIdx Idx) {
	// Swap-and-pop for fast removal.
	// 1) Update the adj index of the edge currently at back().
	// 2) Move last Edge down to Idx.
	// 3) pop_back()
	// If Idx == size() - 1 then the setAdjEdgeIdx and swap are
	// redundant, but both operations are cheap.
	G.getEdge(AdjEdgeIds.back()).setAdjEdgeIdx(ThisNId, Idx);
	AdjEdgeIds[Idx] = AdjEdgeIds.back();
	AdjEdgeIds.pop_back();
	}

	const AdjEdgeList& getAdjEdgeIds() const { return AdjEdgeIds; }

	VectorPtr Costs;
	NodeMetadata Metadata;

	private:
	AdjEdgeList AdjEdgeIds;
	};

	class EdgeEntry {
	public:
	EdgeEntry(NodeId N1Id, NodeId N2Id, MatrixPtr Costs)
	: Costs(std::move(Costs)) {
	NIds[0] = N1Id;
	NIds[1] = N2Id;
	ThisEdgeAdjIdxs[0] = NodeEntry::getInvalidAdjEdgeIdx();
	ThisEdgeAdjIdxs[1] = NodeEntry::getInvalidAdjEdgeIdx();
	}

	void connectToN(Graph &G, EdgeId ThisEdgeId, unsigned NIdx) {
	assert(ThisEdgeAdjIdxs[NIdx] == NodeEntry::getInvalidAdjEdgeIdx() &&
	"Edge already connected to NIds[NIdx].");
	NodeEntry &N = G.getNode(NIds[NIdx]);
	ThisEdgeAdjIdxs[NIdx] = N.addAdjEdgeId(ThisEdgeId);
	}

	void connect(Graph &G, EdgeId ThisEdgeId) {
	connectToN(G, ThisEdgeId, 0);
	connectToN(G, ThisEdgeId, 1);
	}

	void setAdjEdgeIdx(NodeId NId, typename NodeEntry::AdjEdgeIdx NewIdx) {
	if (NId == NIds[0])
	ThisEdgeAdjIdxs[0] = NewIdx;
	else {
	assert(NId == NIds[1] && "Edge not connected to NId");
	ThisEdgeAdjIdxs[1] = NewIdx;
	}
	}

	void disconnectFromN(Graph &G, unsigned NIdx) {
	assert(ThisEdgeAdjIdxs[NIdx] != NodeEntry::getInvalidAdjEdgeIdx() &&
	"Edge not connected to NIds[NIdx].");
	NodeEntry &N = G.getNode(NIds[NIdx]);
	N.removeAdjEdgeId(G, NIds[NIdx], ThisEdgeAdjIdxs[NIdx]);
	ThisEdgeAdjIdxs[NIdx] = NodeEntry::getInvalidAdjEdgeIdx();
	}

	void disconnectFrom(Graph &G, NodeId NId) {
	if (NId == NIds[0])
	disconnectFromN(G, 0);
	else {
	assert(NId == NIds[1] && "Edge does not connect NId");
	disconnectFromN(G, 1);
	}
	}

	NodeId getN1Id() const { return NIds[0]; }
	NodeId getN2Id() const { return NIds[1]; }

	MatrixPtr Costs;
	EdgeMetadata Metadata;

	private:
	NodeId NIds[2];
	typename NodeEntry::AdjEdgeIdx ThisEdgeAdjIdxs[2];
	};

	// ----- MEMBERS -----

	GraphMetadata Metadata;
	CostAllocator CostAlloc;
	SolverT *Solver = nullptr;

	using NodeVector = std::vector<NodeEntry>;
	using FreeNodeVector = std::vector<NodeId>;
	NodeVector Nodes;
	FreeNodeVector FreeNodeIds;

	using EdgeVector = std::vector<EdgeEntry>;
	using FreeEdgeVector = std::vector<EdgeId>;
	EdgeVector Edges;
	FreeEdgeVector FreeEdgeIds;

	Graph(const Graph &Other) {}

	// ----- INTERNAL METHODS -----

	NodeEntry &getNode(NodeId NId) {
	assert(NId < Nodes.size() && "Out of bound NodeId");
	return Nodes[NId];
	}
	const NodeEntry &getNode(NodeId NId) const {
	assert(NId < Nodes.size() && "Out of bound NodeId");
	return Nodes[NId];
	}

	EdgeEntry& getEdge(EdgeId EId) { return Edges[EId]; }
	const EdgeEntry& getEdge(EdgeId EId) const { return Edges[EId]; }

	NodeId addConstructedNode(NodeEntry N) {
	NodeId NId = 0;
	if (!FreeNodeIds.empty()) {
	NId = FreeNodeIds.back();
	FreeNodeIds.pop_back();
	Nodes[NId] = std::move(N);
	} else {
	NId = Nodes.size();
	Nodes.push_back(std::move(N));
	}
	return NId;
	}

	EdgeId addConstructedEdge(EdgeEntry E) {
	assert(findEdge(E.getN1Id(), E.getN2Id()) == invalidEdgeId() &&
	"Attempt to add duplicate edge.");
	EdgeId EId = 0;
	if (!FreeEdgeIds.empty()) {
	EId = FreeEdgeIds.back();
	FreeEdgeIds.pop_back();
	Edges[EId] = std::move(E);
	} else {
	EId = Edges.size();
	Edges.push_back(std::move(E));
	}

	EdgeEntry &NE = getEdge(EId);

	// Add the edge to the adjacency sets of its nodes.
	NE.connect(*this, EId);
	return EId;
	}

	void operator=(const Graph &Other) {}

	public:
	using AdjEdgeItr = typename NodeEntry::AdjEdgeItr;

	class NodeItr {
	public:
	using iterator_category = std::forward_iterator_tag;
	using value_type = NodeId;
	using difference_type = int;
	using pointer = NodeId *;
	using reference = NodeId &;

	NodeItr(NodeId CurNId, const Graph &G)
	: CurNId(CurNId), EndNId(G.Nodes.size()), FreeNodeIds(G.FreeNodeIds) {
	this->CurNId = findNextInUse(CurNId); // Move to first in-use node id
	}

	bool operator==(const NodeItr &O) const { return CurNId == O.CurNId; }
	bool operator!=(const NodeItr &O) const { return !(*this == O); }
	NodeItr& operator++() { CurNId = findNextInUse(++CurNId); return *this; }
	NodeId operator*() const { return CurNId; }

	private:
	NodeId findNextInUse(NodeId NId) const {
	while (NId < EndNId && is_contained(FreeNodeIds, NId)) {
	++NId;
	}
	return NId;
	}

	NodeId CurNId, EndNId;
	const FreeNodeVector &FreeNodeIds;
	};

	class EdgeItr {
	public:
	EdgeItr(EdgeId CurEId, const Graph &G)
	: CurEId(CurEId), EndEId(G.Edges.size()), FreeEdgeIds(G.FreeEdgeIds) {
	this->CurEId = findNextInUse(CurEId); // Move to first in-use edge id
	}

	bool operator==(const EdgeItr &O) const { return CurEId == O.CurEId; }
	bool operator!=(const EdgeItr &O) const { return !(*this == O); }
	EdgeItr& operator++() { CurEId = findNextInUse(++CurEId); return *this; }
	EdgeId operator*() const { return CurEId; }

	private:
	EdgeId findNextInUse(EdgeId EId) const {
	while (EId < EndEId && is_contained(FreeEdgeIds, EId)) {
	++EId;
	}
	return EId;
	}

	EdgeId CurEId, EndEId;
	const FreeEdgeVector &FreeEdgeIds;
	};

	class NodeIdSet {
	public:
	NodeIdSet(const Graph &G) : G(G) {}

	NodeItr begin() const { return NodeItr(0, G); }
	NodeItr end() const { return NodeItr(G.Nodes.size(), G); }

	bool empty() const { return G.Nodes.empty(); }

	typename NodeVector::size_type size() const {
	return G.Nodes.size() - G.FreeNodeIds.size();
	}

	private:
	const Graph& G;
	};

	class EdgeIdSet {
	public:
	EdgeIdSet(const Graph &G) : G(G) {}

	EdgeItr begin() const { return EdgeItr(0, G); }
	EdgeItr end() const { return EdgeItr(G.Edges.size(), G); }

	bool empty() const { return G.Edges.empty(); }

	typename NodeVector::size_type size() const {
	return G.Edges.size() - G.FreeEdgeIds.size();
	}

	private:
	const Graph& G;
	};

	class AdjEdgeIdSet {
	public:
	AdjEdgeIdSet(const NodeEntry &NE) : NE(NE) {}

	typename NodeEntry::AdjEdgeItr begin() const {
	return NE.getAdjEdgeIds().begin();
	}

	typename NodeEntry::AdjEdgeItr end() const {
	return NE.getAdjEdgeIds().end();
	}

	bool empty() const { return NE.getAdjEdgeIds().empty(); }

	typename NodeEntry::AdjEdgeList::size_type size() const {
	return NE.getAdjEdgeIds().size();
	}

	private:
	const NodeEntry &NE;
	};

	/// Construct an empty PBQP graph.
	Graph() = default;

	/// Construct an empty PBQP graph with the given graph metadata.
	Graph(GraphMetadata Metadata) : Metadata(std::move(Metadata)) {}

	/// Get a reference to the graph metadata.
	GraphMetadata& getMetadata() { return Metadata; }

	/// Get a const-reference to the graph metadata.
	const GraphMetadata& getMetadata() const { return Metadata; }

	/// Lock this graph to the given solver instance in preparation
	/// for running the solver. This method will call solver.handleAddNode for
	/// each node in the graph, and handleAddEdge for each edge, to give the
	/// solver an opportunity to set up any requried metadata.
	void setSolver(SolverT &S) {
	assert(!Solver && "Solver already set. Call unsetSolver().");
	Solver = &S;
	for (auto NId : nodeIds())
	Solver->handleAddNode(NId);
	for (auto EId : edgeIds())
	Solver->handleAddEdge(EId);
	}

	/// Release from solver instance.
	void unsetSolver() {
	assert(Solver && "Solver not set.");
	Solver = nullptr;
	}

	/// Add a node with the given costs.
	/// @param Costs Cost vector for the new node.
	/// @return Node iterator for the added node.
	template <typename OtherVectorT>
	NodeId addNode(OtherVectorT Costs) {
	// Get cost vector from the problem domain
	VectorPtr AllocatedCosts = CostAlloc.getVector(std::move(Costs));
	NodeId NId = addConstructedNode(NodeEntry(AllocatedCosts));
	if (Solver)
	Solver->handleAddNode(NId);
	return NId;
	}

	/// Add a node bypassing the cost allocator.
	/// @param Costs Cost vector ptr for the new node (must be convertible to
	/// VectorPtr).
	/// @return Node iterator for the added node.
	///
	/// This method allows for fast addition of a node whose costs don't need
	/// to be passed through the cost allocator. The most common use case for
	/// this is when duplicating costs from an existing node (when using a
	/// pooling allocator). These have already been uniqued, so we can avoid
	/// re-constructing and re-uniquing them by attaching them directly to the
	/// new node.
	template <typename OtherVectorPtrT>
	NodeId addNodeBypassingCostAllocator(OtherVectorPtrT Costs) {
	NodeId NId = addConstructedNode(NodeEntry(Costs));
	if (Solver)
	Solver->handleAddNode(NId);
	return NId;
	}

	/// Add an edge between the given nodes with the given costs.
	/// @param N1Id First node.
	/// @param N2Id Second node.
	/// @param Costs Cost matrix for new edge.
	/// @return Edge iterator for the added edge.
	template <typename OtherVectorT>
	EdgeId addEdge(NodeId N1Id, NodeId N2Id, OtherVectorT Costs) {
	assert(getNodeCosts(N1Id).getLength() == Costs.getRows() &&
	getNodeCosts(N2Id).getLength() == Costs.getCols() &&
	"Matrix dimensions mismatch.");
	// Get cost matrix from the problem domain.
	MatrixPtr AllocatedCosts = CostAlloc.getMatrix(std::move(Costs));
	EdgeId EId = addConstructedEdge(EdgeEntry(N1Id, N2Id, AllocatedCosts));
	if (Solver)
	Solver->handleAddEdge(EId);
	return EId;
	}

	/// Add an edge bypassing the cost allocator.
	/// @param N1Id First node.
	/// @param N2Id Second node.
	/// @param Costs Cost matrix for new edge.
	/// @return Edge iterator for the added edge.
	///
	/// This method allows for fast addition of an edge whose costs don't need
	/// to be passed through the cost allocator. The most common use case for
	/// this is when duplicating costs from an existing edge (when using a
	/// pooling allocator). These have already been uniqued, so we can avoid
	/// re-constructing and re-uniquing them by attaching them directly to the
	/// new edge.
	template <typename OtherMatrixPtrT>
	NodeId addEdgeBypassingCostAllocator(NodeId N1Id, NodeId N2Id,
	OtherMatrixPtrT Costs) {
	assert(getNodeCosts(N1Id).getLength() == Costs->getRows() &&
	getNodeCosts(N2Id).getLength() == Costs->getCols() &&
	"Matrix dimensions mismatch.");
	// Get cost matrix from the problem domain.
	EdgeId EId = addConstructedEdge(EdgeEntry(N1Id, N2Id, Costs));
	if (Solver)
	Solver->handleAddEdge(EId);
	return EId;
	}

	/// Returns true if the graph is empty.
	bool empty() const { return NodeIdSet(*this).empty(); }

	NodeIdSet nodeIds() const { return NodeIdSet(*this); }
	EdgeIdSet edgeIds() const { return EdgeIdSet(*this); }

	AdjEdgeIdSet adjEdgeIds(NodeId NId) { return AdjEdgeIdSet(getNode(NId)); }

	/// Get the number of nodes in the graph.
	/// @return Number of nodes in the graph.
	unsigned getNumNodes() const { return NodeIdSet(*this).size(); }

	/// Get the number of edges in the graph.
	/// @return Number of edges in the graph.
	unsigned getNumEdges() const { return EdgeIdSet(*this).size(); }

	/// Set a node's cost vector.
	/// @param NId Node to update.
	/// @param Costs New costs to set.
	template <typename OtherVectorT>
	void setNodeCosts(NodeId NId, OtherVectorT Costs) {
	VectorPtr AllocatedCosts = CostAlloc.getVector(std::move(Costs));
	if (Solver)
	Solver->handleSetNodeCosts(NId, *AllocatedCosts);
	getNode(NId).Costs = AllocatedCosts;
	}

	/// Get a VectorPtr to a node's cost vector. Rarely useful - use
	/// getNodeCosts where possible.
	/// @param NId Node id.
	/// @return VectorPtr to node cost vector.
	///
	/// This method is primarily useful for duplicating costs quickly by
	/// bypassing the cost allocator. See addNodeBypassingCostAllocator. Prefer
	/// getNodeCosts when dealing with node cost values.
	const VectorPtr& getNodeCostsPtr(NodeId NId) const {
	return getNode(NId).Costs;
	}

	/// Get a node's cost vector.
	/// @param NId Node id.
	/// @return Node cost vector.
	const Vector& getNodeCosts(NodeId NId) const {
	return *getNodeCostsPtr(NId);
	}

	NodeMetadata& getNodeMetadata(NodeId NId) {
	return getNode(NId).Metadata;
	}

	const NodeMetadata& getNodeMetadata(NodeId NId) const {
	return getNode(NId).Metadata;
	}

	typename NodeEntry::AdjEdgeList::size_type getNodeDegree(NodeId NId) const {
	return getNode(NId).getAdjEdgeIds().size();
	}

	/// Update an edge's cost matrix.
	/// @param EId Edge id.
	/// @param Costs New cost matrix.
	template <typename OtherMatrixT>
	void updateEdgeCosts(EdgeId EId, OtherMatrixT Costs) {
	MatrixPtr AllocatedCosts = CostAlloc.getMatrix(std::move(Costs));
	if (Solver)
	Solver->handleUpdateCosts(EId, *AllocatedCosts);
	getEdge(EId).Costs = AllocatedCosts;
	}

	/// Get a MatrixPtr to a node's cost matrix. Rarely useful - use
	/// getEdgeCosts where possible.
	/// @param EId Edge id.
	/// @return MatrixPtr to edge cost matrix.
	///
	/// This method is primarily useful for duplicating costs quickly by
	/// bypassing the cost allocator. See addNodeBypassingCostAllocator. Prefer
	/// getEdgeCosts when dealing with edge cost values.
	const MatrixPtr& getEdgeCostsPtr(EdgeId EId) const {
	return getEdge(EId).Costs;
	}

	/// Get an edge's cost matrix.
	/// @param EId Edge id.
	/// @return Edge cost matrix.
	const Matrix& getEdgeCosts(EdgeId EId) const {
	return *getEdge(EId).Costs;
	}

	EdgeMetadata& getEdgeMetadata(EdgeId EId) {
	return getEdge(EId).Metadata;
	}

	const EdgeMetadata& getEdgeMetadata(EdgeId EId) const {
	return getEdge(EId).Metadata;
	}

	/// Get the first node connected to this edge.
	/// @param EId Edge id.
	/// @return The first node connected to the given edge.
	NodeId getEdgeNode1Id(EdgeId EId) const {
	return getEdge(EId).getN1Id();
	}

	/// Get the second node connected to this edge.
	/// @param EId Edge id.
	/// @return The second node connected to the given edge.
	NodeId getEdgeNode2Id(EdgeId EId) const {
	return getEdge(EId).getN2Id();
	}

	/// Get the "other" node connected to this edge.
	/// @param EId Edge id.
	/// @param NId Node id for the "given" node.
	/// @return The iterator for the "other" node connected to this edge.
	NodeId getEdgeOtherNodeId(EdgeId EId, NodeId NId) {
	EdgeEntry &E = getEdge(EId);
	if (E.getN1Id() == NId) {
	return E.getN2Id();
	} // else
	return E.getN1Id();
	}

	/// 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 (auto AEId : adjEdgeIds(N1Id)) {
	if ((getEdgeNode1Id(AEId) == N2Id) \|\|
	(getEdgeNode2Id(AEId) == N2Id)) {
	return AEId;
	}
	}
	return invalidEdgeId();
	}

	/// Remove a node from the graph.
	/// @param NId Node id.
	void removeNode(NodeId NId) {
	if (Solver)
	Solver->handleRemoveNode(NId);
	NodeEntry &N = getNode(NId);
	// TODO: Can this be for-each'd?
	for (AdjEdgeItr AEItr = N.adjEdgesBegin(),
	AEEnd = N.adjEdgesEnd();
	AEItr != AEEnd;) {
	EdgeId EId = *AEItr;
	++AEItr;
	removeEdge(EId);
	}
	FreeNodeIds.push_back(NId);
	}

	/// Disconnect an edge from the given node.
	///
	/// Removes the given edge from the adjacency list of the given node.
	/// This operation leaves the edge in an 'asymmetric' state: It will no
	/// longer appear in an iteration over the given node's (NId's) edges, but
	/// will appear in an iteration over the 'other', unnamed node's edges.
	///
	/// This does not correspond to any normal graph operation, but exists to
	/// support efficient PBQP graph-reduction based solvers. It is used to
	/// 'effectively' remove the unnamed node from the graph while the solver
	/// is performing the reduction. The solver will later call reconnectNode
	/// to restore the edge in the named node's adjacency list.
	///
	/// Since the degree of a node is the number of connected edges,
	/// disconnecting an edge from a node 'u' will cause the degree of 'u' to
	/// drop by 1.
	///
	/// A disconnected edge WILL still appear in an iteration over the graph
	/// edges.
	///
	/// A disconnected edge should not be removed from the graph, it should be
	/// reconnected first.
	///
	/// A disconnected edge can be reconnected by calling the reconnectEdge
	/// method.
	void disconnectEdge(EdgeId EId, NodeId NId) {
	if (Solver)
	Solver->handleDisconnectEdge(EId, NId);

	EdgeEntry &E = getEdge(EId);
	E.disconnectFrom(*this, NId);
	}

	/// Convenience method to disconnect all neighbours from the given
	/// node.
	void disconnectAllNeighborsFromNode(NodeId NId) {
	for (auto AEId : adjEdgeIds(NId))
	disconnectEdge(AEId, getEdgeOtherNodeId(AEId, NId));
	}

	/// Re-attach an edge to its nodes.
	///
	/// Adds an edge that had been previously disconnected back into the
	/// adjacency set of the nodes that the edge connects.
	void reconnectEdge(EdgeId EId, NodeId NId) {
	EdgeEntry &E = getEdge(EId);
	E.connectTo(*this, EId, NId);
	if (Solver)
	Solver->handleReconnectEdge(EId, NId);
	}

	/// Remove an edge from the graph.
	/// @param EId Edge id.
	void removeEdge(EdgeId EId) {
	if (Solver)
	Solver->handleRemoveEdge(EId);
	EdgeEntry &E = getEdge(EId);
	E.disconnect();
	FreeEdgeIds.push_back(EId);
	Edges[EId].invalidate();
	}

	/// Remove all nodes and edges from the graph.
	void clear() {
	Nodes.clear();
	FreeNodeIds.clear();
	Edges.clear();
	FreeEdgeIds.clear();
	}
	};

	} // end namespace PBQP
	} // end namespace llvm

	#endif // LLVM_CODEGEN_PBQP_GRAPH_HPP