1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
|
// SPDX-License-Identifier: GPL-3.0-or-later
#ifndef RCC_CODEGEN_PBQP_GRAPH_H
#define RCC_CODEGEN_PBQP_GRAPH_H
#include "rcc/CodeGen/PBQP/Math.h"
#include "rcc/Support/Error.h"
#include <compare>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <limits>
#include <optional>
#include <span>
#include <utility>
#include <vector>
namespace rcc::pbqp {
class NodeID final {
public:
constexpr NodeID() noexcept = default;
[[nodiscard]] static constexpr NodeID fromValue(std::uint32_t Value) noexcept {
return NodeID(Value);
}
[[nodiscard]] constexpr bool isValid() const noexcept {
return Value != InvalidValue;
}
[[nodiscard]] constexpr std::uint32_t value() const noexcept {
return Value;
}
friend constexpr bool operator==(NodeID, NodeID) noexcept = default;
friend constexpr auto operator<=>(NodeID, NodeID) noexcept = default;
private:
static constexpr std::uint32_t InvalidValue = std::numeric_limits<std::uint32_t>::max();
explicit constexpr NodeID(std::uint32_t Value) noexcept : Value(Value) {}
std::uint32_t Value = InvalidValue;
};
class EdgeID final {
public:
constexpr EdgeID() noexcept = default;
[[nodiscard]] static constexpr EdgeID fromValue(std::uint32_t Value) noexcept {
return EdgeID(Value);
}
[[nodiscard]] constexpr bool isValid() const noexcept {
return Value != InvalidValue;
}
[[nodiscard]] constexpr std::uint32_t value() const noexcept {
return Value;
}
friend constexpr bool operator==(EdgeID, EdgeID) noexcept = default;
friend constexpr auto operator<=>(EdgeID, EdgeID) noexcept = default;
private:
static constexpr std::uint32_t InvalidValue = std::numeric_limits<std::uint32_t>::max();
explicit constexpr EdgeID(std::uint32_t Value) noexcept : Value(Value) {}
std::uint32_t Value = InvalidValue;
};
struct Node final {
NodeID ID;
std::uint64_t StableKey = 0;
CostVector Costs;
std::vector<EdgeID> AdjacentEdges;
};
struct Edge final {
EdgeID ID;
NodeID First;
NodeID Second;
std::uint64_t StableKey = 0;
CostMatrix Costs;
};
class Graph final {
public:
[[nodiscard]] Expected<NodeID> addNode(CostVector Costs, std::uint64_t StableKey = 0) {
if (Costs.empty())
return makeUnexpected(ErrorCode::InvalidArgument, "PBQP node requires at least one option");
if (Nodes.size() >= std::numeric_limits<std::uint32_t>::max())
return makeUnexpected(ErrorCode::Unsupported, "PBQP node ID space is exhausted");
const NodeID ID = NodeID::fromValue(static_cast<std::uint32_t>(Nodes.size()));
Nodes.push_back(Node{ID, StableKey, std::move(Costs), {}});
return ID;
}
[[nodiscard]] Expected<EdgeID> addEdge(NodeID First, NodeID Second, CostMatrix Costs,
std::uint64_t StableKey = 0) {
const Node *FirstNode = node(First);
const Node *SecondNode = node(Second);
if (FirstNode == nullptr || SecondNode == nullptr || First == Second) {
return makeUnexpected(ErrorCode::InvalidArgument,
"PBQP edge requires two distinct known nodes");
}
if (edgeBetween(First, Second))
return makeUnexpected(ErrorCode::InvalidArgument, "PBQP graph already contains this edge");
if (Second < First) {
std::swap(First, Second);
Costs = Costs.transpose();
std::swap(FirstNode, SecondNode);
}
if (Costs.rows() != FirstNode->Costs.size() || Costs.columns() != SecondNode->Costs.size()) {
return makeUnexpected(ErrorCode::InvalidArgument,
"PBQP edge matrix dimensions do not match its nodes");
}
if (Edges.size() >= std::numeric_limits<std::uint32_t>::max())
return makeUnexpected(ErrorCode::Unsupported, "PBQP edge ID space is exhausted");
const EdgeID ID = EdgeID::fromValue(static_cast<std::uint32_t>(Edges.size()));
Edges.push_back(Edge{ID, First, Second, StableKey, std::move(Costs)});
Nodes[First.value()].AdjacentEdges.push_back(ID);
Nodes[Second.value()].AdjacentEdges.push_back(ID);
return ID;
}
[[nodiscard]] const Node *node(NodeID ID) const noexcept {
return ID.isValid() && ID.value() < Nodes.size() ? &Nodes[ID.value()] : nullptr;
}
[[nodiscard]] const Edge *edge(EdgeID ID) const noexcept {
return ID.isValid() && ID.value() < Edges.size() ? &Edges[ID.value()] : nullptr;
}
[[nodiscard]] const Edge *edgeBetween(NodeID Left, NodeID Right) const noexcept {
const Node *LeftNode = node(Left);
if (LeftNode == nullptr || node(Right) == nullptr)
return nullptr;
for (const EdgeID ID : LeftNode->AdjacentEdges) {
const Edge &Candidate = Edges[ID.value()];
if ((Candidate.First == Left && Candidate.Second == Right) ||
(Candidate.First == Right && Candidate.Second == Left))
return &Candidate;
}
return nullptr;
}
[[nodiscard]] std::span<const Node> nodes() const noexcept {
return Nodes;
}
[[nodiscard]] std::span<const Edge> edges() const noexcept {
return Edges;
}
[[nodiscard]] std::size_t nodeCount() const noexcept {
return Nodes.size();
}
[[nodiscard]] Expected<void> verify() const {
for (std::size_t Index = 0; Index < Nodes.size(); ++Index) {
const Node &Value = Nodes[Index];
if (Value.ID.value() != Index || Value.Costs.empty())
return makeUnexpected(ErrorCode::VerificationError, "PBQP graph contains an invalid node");
for (const EdgeID ID : Value.AdjacentEdges) {
const Edge *Adjacent = edge(ID);
if (Adjacent == nullptr || (Adjacent->First != Value.ID && Adjacent->Second != Value.ID)) {
return makeUnexpected(ErrorCode::VerificationError,
"PBQP node has an invalid adjacency entry");
}
}
}
for (std::size_t Index = 0; Index < Edges.size(); ++Index) {
const Edge &Value = Edges[Index];
const Node *First = node(Value.First);
const Node *Second = node(Value.Second);
if (Value.ID.value() != Index || First == nullptr || Second == nullptr ||
!(Value.First < Value.Second) || Value.Costs.rows() != First->Costs.size() ||
Value.Costs.columns() != Second->Costs.size()) {
return makeUnexpected(ErrorCode::VerificationError, "PBQP graph contains an invalid edge");
}
}
return {};
}
private:
std::vector<Node> Nodes;
std::vector<Edge> Edges;
};
} // namespace rcc::pbqp
template <> struct std::hash<rcc::pbqp::NodeID> {
[[nodiscard]] std::size_t operator()(rcc::pbqp::NodeID ID) const noexcept {
return std::hash<std::uint32_t>{}(ID.value());
}
};
template <> struct std::hash<rcc::pbqp::EdgeID> {
[[nodiscard]] std::size_t operator()(rcc::pbqp::EdgeID ID) const noexcept {
return std::hash<std::uint32_t>{}(ID.value());
}
};
#endif // RCC_CODEGEN_PBQP_GRAPH_H
|
