mirror of
https://github.com/RPCS3/llvm.git
synced 2026-01-31 01:25:19 +01:00
6b547686c5
to reflect the new license. We understand that people may be surprised that we're moving the header entirely to discuss the new license. We checked this carefully with the Foundation's lawyer and we believe this is the correct approach. Essentially, all code in the project is now made available by the LLVM project under our new license, so you will see that the license headers include that license only. Some of our contributors have contributed code under our old license, and accordingly, we have retained a copy of our old license notice in the top-level files in each project and repository. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@351636 91177308-0d34-0410-b5e6-96231b3b80d8
675 lines
22 KiB
C++
675 lines
22 KiB
C++
//===- 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
|