Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- 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 ≠

    };

    /// 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_H