#ifndef LLVM_CODEGEN_PBQP_GRAPH_H
#define LLVM_CODEGEN_PBQP_GRAPH_H
#include "llvm/ADT/ilist.h"
#include "llvm/ADT/ilist_node.h"
#include "llvm/Support/Debug.h"
#include <list>
#include <map>
#include <set>
#include <vector>
namespace llvm {
namespace PBQP {
class GraphBase {
public:
typedef unsigned NodeId;
typedef unsigned EdgeId;
static NodeId invalidNodeId() {
return std::numeric_limits<NodeId>::max();
}
static EdgeId invalidEdgeId() {
return std::numeric_limits<EdgeId>::max();
}
};
template <typename SolverT>
class Graph : public GraphBase {
private:
typedef typename SolverT::CostAllocator CostAllocator;
public:
typedef typename SolverT::RawVector RawVector;
typedef typename SolverT::RawMatrix RawMatrix;
typedef typename SolverT::Vector Vector;
typedef typename SolverT::Matrix Matrix;
typedef typename CostAllocator::VectorPtr VectorPtr;
typedef typename CostAllocator::MatrixPtr MatrixPtr;
typedef typename SolverT::NodeMetadata NodeMetadata;
typedef typename SolverT::EdgeMetadata EdgeMetadata;
typedef typename SolverT::GraphMetadata GraphMetadata;
private:
class NodeEntry {
public:
typedef std::vector<EdgeId> AdjEdgeList;
typedef AdjEdgeList::size_type AdjEdgeIdx;
typedef AdjEdgeList::const_iterator AdjEdgeItr;
static AdjEdgeIdx getInvalidAdjEdgeIdx() {
return std::numeric_limits<AdjEdgeIdx>::max();
}
NodeEntry(VectorPtr Costs) : Costs(Costs) {}
AdjEdgeIdx addAdjEdgeId(EdgeId EId) {
AdjEdgeIdx Idx = AdjEdgeIds.size();
AdjEdgeIds.push_back(EId);
return Idx;
}
void removeAdjEdgeId(Graph &G, NodeId ThisNId, AdjEdgeIdx Idx) {
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(Costs) {
NIds[0] = N1Id;
NIds[1] = N2Id;
ThisEdgeAdjIdxs[0] = NodeEntry::getInvalidAdjEdgeIdx();
ThisEdgeAdjIdxs[1] = NodeEntry::getInvalidAdjEdgeIdx();
}
void invalidate() {
NIds[0] = NIds[1] = Graph::invalidNodeId();
ThisEdgeAdjIdxs[0] = ThisEdgeAdjIdxs[1] =
NodeEntry::getInvalidAdjEdgeIdx();
Costs = nullptr;
}
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 connectTo(Graph &G, EdgeId ThisEdgeId, NodeId NId) {
if (NId == NIds[0])
connectToN(G, ThisEdgeId, 0);
else {
assert(NId == NIds[1] && "Edge does not connect NId.");
connectToN(G, ThisEdgeId, 1);
}
}
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];
};
GraphMetadata Metadata;
CostAllocator CostAlloc;
SolverT *Solver;
typedef std::vector<NodeEntry> NodeVector;
typedef std::vector<NodeId> FreeNodeVector;
NodeVector Nodes;
FreeNodeVector FreeNodeIds;
typedef std::vector<EdgeEntry> EdgeVector;
typedef std::vector<EdgeId> FreeEdgeVector;
EdgeVector Edges;
FreeEdgeVector FreeEdgeIds;
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);
NE.connect(*this, EId);
return EId;
}
Graph(const Graph &Other) {}
void operator=(const Graph &Other) {}
public:
typedef typename NodeEntry::AdjEdgeItr AdjEdgeItr;
class NodeItr {
public:
typedef std::forward_iterator_tag iterator_category;
typedef NodeId value_type;
typedef int difference_type;
typedef NodeId* pointer;
typedef NodeId& reference;
NodeItr(NodeId CurNId, const Graph &G)
: CurNId(CurNId), EndNId(G.Nodes.size()), FreeNodeIds(G.FreeNodeIds) {
this->CurNId = findNextInUse(CurNId); }
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 &&
std::find(FreeNodeIds.begin(), FreeNodeIds.end(), NId) !=
FreeNodeIds.end()) {
++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); }
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 &&
std::find(FreeEdgeIds.begin(), FreeEdgeIds.end(), EId) !=
FreeEdgeIds.end()) {
++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;
};
Graph() : Solver(nullptr) {}
Graph(GraphMetadata Metadata) : Metadata(Metadata), Solver(nullptr) {}
GraphMetadata& getMetadata() { return Metadata; }
const GraphMetadata& getMetadata() const { return 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);
}
void unsetSolver() {
assert(Solver && "Solver not set.");
Solver = nullptr;
}
template <typename OtherVectorT>
NodeId addNode(OtherVectorT Costs) {
VectorPtr AllocatedCosts = CostAlloc.getVector(std::move(Costs));
NodeId NId = addConstructedNode(NodeEntry(AllocatedCosts));
if (Solver)
Solver->handleAddNode(NId);
return NId;
}
template <typename OtherVectorPtrT>
NodeId addNodeBypassingCostAllocator(OtherVectorPtrT Costs) {
NodeId NId = addConstructedNode(NodeEntry(Costs));
if (Solver)
Solver->handleAddNode(NId);
return NId;
}
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.");
MatrixPtr AllocatedCosts = CostAlloc.getMatrix(std::move(Costs));
EdgeId EId = addConstructedEdge(EdgeEntry(N1Id, N2Id, AllocatedCosts));
if (Solver)
Solver->handleAddEdge(EId);
return EId;
}
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.");
EdgeId EId = addConstructedEdge(EdgeEntry(N1Id, N2Id, Costs));
if (Solver)
Solver->handleAddEdge(EId);
return EId;
}
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)); }
unsigned getNumNodes() const { return NodeIdSet(*this).size(); }
unsigned getNumEdges() const { return EdgeIdSet(*this).size(); }
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;
}
const VectorPtr& getNodeCostsPtr(NodeId NId) const {
return getNode(NId).Costs;
}
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();
}
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;
}
const MatrixPtr& getEdgeCostsPtr(EdgeId EId) const {
return getEdge(EId).Costs;
}
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;
}
NodeId getEdgeNode1Id(EdgeId EId) const {
return getEdge(EId).getN1Id();
}
NodeId getEdgeNode2Id(EdgeId EId) const {
return getEdge(EId).getN2Id();
}
NodeId getEdgeOtherNodeId(EdgeId EId, NodeId NId) {
EdgeEntry &E = getEdge(EId);
if (E.getN1Id() == NId) {
return E.getN2Id();
} return E.getN1Id();
}
EdgeId findEdge(NodeId N1Id, NodeId N2Id) {
for (auto AEId : adjEdgeIds(N1Id)) {
if ((getEdgeNode1Id(AEId) == N2Id) ||
(getEdgeNode2Id(AEId) == N2Id)) {
return AEId;
}
}
return invalidEdgeId();
}
void removeNode(NodeId NId) {
if (Solver)
Solver->handleRemoveNode(NId);
NodeEntry &N = getNode(NId);
for (AdjEdgeItr AEItr = N.adjEdgesBegin(),
AEEnd = N.adjEdgesEnd();
AEItr != AEEnd;) {
EdgeId EId = *AEItr;
++AEItr;
removeEdge(EId);
}
FreeNodeIds.push_back(NId);
}
void disconnectEdge(EdgeId EId, NodeId NId) {
if (Solver)
Solver->handleDisconnectEdge(EId, NId);
EdgeEntry &E = getEdge(EId);
E.disconnectFrom(*this, NId);
}
void disconnectAllNeighborsFromNode(NodeId NId) {
for (auto AEId : adjEdgeIds(NId))
disconnectEdge(AEId, getEdgeOtherNodeId(AEId, NId));
}
void reconnectEdge(EdgeId EId, NodeId NId) {
EdgeEntry &E = getEdge(EId);
E.connectTo(*this, EId, NId);
if (Solver)
Solver->handleReconnectEdge(EId, NId);
}
void removeEdge(EdgeId EId) {
if (Solver)
Solver->handleRemoveEdge(EId);
EdgeEntry &E = getEdge(EId);
E.disconnect();
FreeEdgeIds.push_back(EId);
Edges[EId].invalidate();
}
void clear() {
Nodes.clear();
FreeNodeIds.clear();
Edges.clear();
FreeEdgeIds.clear();
}
};
} }
#endif // LLVM_CODEGEN_PBQP_GRAPH_HPP