summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--rbmp.cpp62
1 files changed, 28 insertions, 34 deletions
diff --git a/rbmp.cpp b/rbmp.cpp
index 3a689b9..88bf18b 100644
--- a/rbmp.cpp
+++ b/rbmp.cpp
@@ -44,12 +44,6 @@ public:
tail = &vt;
head = &vh;
}
- Vertex& getHead() {
- return *head;
- }
- Vertex& getTail() {
- return *tail;
- }
const Vertex& getHead() const {
return *head;
}
@@ -64,11 +58,11 @@ public:
double weight;
Edge() : halfedges{*this, *this} {};
- void setVertices(Vertex& vt, Vertex& vh) {
- halfedges[0].setVertices(vt, vh);
- halfedges[1].setVertices(vh, vt);
- vt.addEdge(halfedges[0]);
- vh.addEdge(halfedges[1]);
+ void setVertices(Vertex& red, Vertex& blue) {
+ halfedges[0].setVertices(red, blue);
+ halfedges[1].setVertices(blue, red);
+ red.addEdge(halfedges[0]);
+ blue.addEdge(halfedges[1]);
}
double belief() const {
return halfedges[0].X + halfedges[1].X;
@@ -84,62 +78,62 @@ public:
std::vector<Edge> edges;
Graph(unsigned n, Rng& r) : vertices(2 * n * (n + 1)), edges(pow(2 * n, 2)) {
- for (unsigned i = 0; i < vertices.size() / 2; i++) {
+ unsigned M = vertices.size() / 2;
+ for (unsigned i = 0; i < M; i++) {
vertices[i].index = i;
vertices[i].coordinate = {2 * (i % (n + 1)), 2 * (i / (n + 1)) + 1};
- vertices[vertices.size() / 2 + i].index = i + vertices.size() / 2;
- vertices[vertices.size() / 2 + i].coordinate = {2 * (i % n) + 1, 2 * (i / n)};
+ vertices[M + i].index = M + i;
+ vertices[M + i].coordinate = {2 * (i % n) + 1, 2 * (i / n)};
}
for (unsigned i = 0; i < edges.size(); i++) {
- Vertex& blueVertex = vertices[vertices.size() / 2 + (i % (2 * n)) / 2 + n * (((i + 2*n) / 4) / n)];
- Vertex& redVertex = vertices[(1+(i % (2 * n))) / 2 + (n + 1) * ((i / 4) / (n))];
+ Vertex& redVertex = vertices[(1 + (i % (2 * n))) / 2 + (n + 1) * ((i / 4) / n)];
+ Vertex& blueVertex = vertices[M + (i % (2 * n)) / 2 + n * (((i + 2 * n) / 4) / n)];
edges[i].setVertices(redVertex, blueVertex);
edges[i].weight = r.variate<double, std::exponential_distribution>(1);
}
}
- double propagateBeliefs() {
+ void propagateBeliefs() {
for (Edge& e : edges) {
- for (HalfEdge& he : e.halfedges) {
+ for (HalfEdge& h : e.halfedges) {
double Xt = std::numeric_limits<double>::infinity();
- for (const HalfEdge& en : he.getHead().neighbors) {
- if (he.getTail().index != en.getHead().index) {
- Xt = std::min(en.edge.weight - en.oldX, Xt);
+ for (const HalfEdge& hn : h.getHead().neighbors) {
+ if (h.getTail().index != hn.getHead().index) {
+ Xt = std::min(hn.edge.weight - hn.oldX, Xt);
}
}
- he.X = Xt;
+ h.X = Xt;
}
}
- double ΔX = std::numeric_limits<double>::infinity();
-
for (Edge& e : edges) {
- ΔX = std::min(ΔX, e.belief());
-
for (HalfEdge& he : e.halfedges) {
he.oldX = he.X;
}
}
-
- return ΔX;
}
};
int main() {
+ unsigned n = 100;
+ unsigned steps = 1e5;
Rng r;
- Graph G(1000, r);
-
- double Δx = 0;
+ Graph G(n, r);
- while (Δx < 1) {
- Δx = G.propagateBeliefs();
+ for (unsigned i = 0; i < steps; i++) {
+ G.propagateBeliefs();
}
for (unsigned i = 0; i < G.edges.size(); i++) {
if (G.edges[i].active()) {
- std::cout << G.edges[i].halfedges[0].getTail().coordinate[0] << " " << G.edges[i].halfedges[0].getTail().coordinate[1] << " " << G.edges[i].halfedges[0].getHead().coordinate[0] << " " << G.edges[i].halfedges[0].getHead().coordinate[1] << std::endl;
+ std::cout
+ << G.edges[i].halfedges[0].getTail().coordinate[0] << " "
+ << G.edges[i].halfedges[0].getTail().coordinate[1] << " "
+ << G.edges[i].halfedges[0].getHead().coordinate[0] << " "
+ << G.edges[i].halfedges[0].getHead().coordinate[1] << std::endl;
}
}
+ return 0;
}