Skip to content

Instantly share code, notes, and snippets.

@xixasdev

xixasdev/dag-snapshot.cpp

Last active January 20, 2022 07:43
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save xixasdev/64514589b69fcb617bb836e7522c48a9 to your computer and use it in GitHub Desktop.
Save xixasdev/64514589b69fcb617bb836e7522c48a9 to your computer and use it in GitHub Desktop.
Download ZIP
Gaming: World-state snapshot example for non-interrupting saves - DAG - NO LOCKS
Raw
dag-snapshot.cpp
// dag-snapshot.cpp (C++11)
// AUTHOR: xixas | DATE: 2022.01.17 | LICENSE: WTFPL/PDM/CC0... your choice
// DESCRIPTION: Gaming: World-state snapshot example for non-interrupting saves.
// Repeated directed acyclic graph vertex replacement.
// NO LOCKS.
// BUILD: g++ --std=c++11 -O3 -lpthread -o dag-snapshot dag-snapshot.cpp
#include <atomic>
#include <chrono>
#include <cstdlib>
#include <initializer_list>
#include <iostream>
#include <set>
#include <sstream>
#include <string>
#include <thread>
#include <time.h>
#include <unordered_set>
#include <vector>
// ---------------------------------------------------------------------------
// Atomics used for test synchronization
// ---------------------------------------------------------------------------
std::atomic<bool> willSave(false);
std::atomic<bool> isSaving(false);
std::atomic<bool> saveComplete(false);
std::atomic<bool> endGame(false);
// ---------------------------------------------------------------------------
// Updateable object registration
// ---------------------------------------------------------------------------
class Updateable;
std::unordered_set<Updateable*> updateables_beforesave;
std::unordered_set<Updateable*> updateables_aftersave;
struct Updateable {
Updateable() { updateables_aftersave.insert(this); }
Updateable(bool onsave):Updateable() { if (onsave) updateables_beforesave.insert(this); }
virtual ~Updateable(){};
virtual void update() = 0;
};
void update_beforesave() { for (auto u : updateables_beforesave) u->update(); }
void update_aftersave() { for (auto u : updateables_aftersave) u->update(); }
// ---------------------------------------------------------------------------
// Generic snapshot template class
// ---------------------------------------------------------------------------
template <typename T> class Saveable : public virtual Updateable {
T snap, live;
public:
Saveable() { snap = live = T(); }
Saveable(const T& t) { snap = live = t; }
Saveable(const Saveable<T>& o) { snap = o.snap; live = o.live; }
~Saveable() {}
Saveable<T>& operator=(const Saveable<T>& t) { setValue(t.live); return *this; }
Saveable<T>& operator=(const T& t) { setValue(t); return *this; }
operator T&() { return live; }
operator const T&() const { return live; }
T& operator *() { return live; }
const T& operator *() const { return live; }
T& operator +() { return snap; }
const T& operator +() const { return snap; }
void update() override { snap = live; }
void setValue(const T& t) { live = t; if (!isSaving) snap = t; }
T& getValue() { return live; }
const T& getValue() const { return live; }
T& getSaveValue() { return snap; }
const T& getSaveValue() const { return snap; }
};
template <typename T> inline bool operator <(const Saveable<T>& lhs, const Saveable<T>& rhs) { return *lhs < *rhs; }
template <typename T> inline bool operator ==(const Saveable<T>& lhs, const Saveable<T>& rhs) { return *lhs == *rhs; }
template <typename T> inline std::ostream& operator <<(std::ostream& os, const Saveable<T>& t) { os << *t; return os; }
// ---------------------------------------------------------------------------
// Vertex with saveable values
// All values are stored twice when a save is not in progress
// Automatically freezes a snapshot when isSaving is true
// ---------------------------------------------------------------------------
class Vertex {
Saveable<std::vector<Vertex*>> _owns;
public:
Saveable<std::string> name;
Saveable<int> value;
const Saveable<std::vector<Vertex*>>& owns = _owns;
Vertex():name(),value(),_owns(){}
Vertex(const std::string& name, const int& value):name(name),value(value),_owns(){}
Vertex(const std::string& name, const int& value, const std::vector<Vertex*>& owns):name(name),value(value),_owns(owns){}
Vertex(const Vertex& o):name(o.name),value(o.value),_owns(o._owns){}
Vertex& operator=(const Vertex& o) { if (this != &o) { name = o.name; value = o.value; _owns = o._owns; } return *this; }
void own(const std::vector<Vertex*>& owns) { _owns = owns; }
std::string str() const {
std::ostringstream os;
os << "(\"" << name << "/" << value << "\")";
return os.str();
}
std::string saveableStr() const {
std::ostringstream os;
os << "(\"" << +name << "/" << +value << "\")";
return os.str();
}
};
inline bool operator<(const Vertex& lhs, const Vertex& rhs) {
return lhs.name < rhs.name;
}
// ---------------------------------------------------------------------------
// Edge (Vertex pair)
// Plain struct without any built-in snapshot ability
// ---------------------------------------------------------------------------
struct Edge {
Vertex *a, *b;
Edge(Vertex* a, Vertex* b):a(a),b(b){}
Edge(Vertex& a, Vertex& b):a(&a),b(&b){}
Edge(const Edge& o):a(o.a),b(o.b){}
Edge& operator=(const Edge& o) { if (this != &o) { a = o.a; b = o.b; } return *this; }
std::string str() const {
std::ostringstream os;
os << "{" << a->str() << ", " << b->str() << "}";
return os.str();
}
std::string saveableStr() const {
std::ostringstream os;
os << "{" << a->saveableStr() << ", " << b->saveableStr() << "}";
return os.str();
}
};
inline bool operator<(const Edge& lhs, const Edge& rhs) {
return lhs.a->name < rhs.a->name || (lhs.a->name == rhs.a->name && lhs.b->name < rhs.b->name);
}
// ---------------------------------------------------------------------------
// Graph (ordered set of Edges)
// No snapshot overhead on updates
// A snapshot must be manually requested when ready to save
// ---------------------------------------------------------------------------
class Graph : public virtual Updateable {
Saveable<std::set<Edge>> _edges;
public:
const Saveable<std::set<Edge>>& edges = _edges;
Graph():Updateable(true){}
Graph(std::initializer_list<Edge> edges):Updateable(true),_edges(edges){}
Graph(const Graph& o):Updateable(true),_edges(o._edges){}
Graph& operator=(const Graph& o) { if (this != &o) { _edges = o._edges; (*_edges) = _edges; } return *this; }
void update() override { _edges.update(); }
std::set<Vertex*> vertices() {
std::set<Vertex*> vertices;
for (auto it = (*_edges).begin(); it != (*_edges).end(); ++it) {
vertices.insert(it->a);
vertices.insert(it->b);
}
return vertices;
}
void add_edge(const Edge& edge) {
(*_edges).insert(edge);
}
void remove_edge(const Edge& edge) {
for (auto it = (*_edges).cbegin(); it != (*_edges).cend();) {
if (it->a->name == edge.a->name && it->b->name == edge.b->name) it = (*_edges).erase(it);
else ++it;
}
}
void remove_vertex(const Vertex& vertex) {
for (auto it = (*vertex.owns).cbegin(); it != (*vertex.owns).cend(); it++) {
remove_vertex(**it);
}
for (auto it = (*_edges).cbegin(); it != (*_edges).cend();) {
if (it->a->name == vertex.name || it->b->name == vertex.name) it = (*_edges).erase(it);
else ++it;
}
}
void replace_vertex(const Vertex& a, Vertex& b) {
std::vector<Edge> newEdges;
for (auto it = (*_edges).cbegin(); it != (*_edges).cend();) {
if (it->a->name == a.name) {
newEdges.push_back(Edge{&b, it->b});
it = (*_edges).erase(it);
} else if (it->b->name == a.name) {
newEdges.push_back({it->a, &b});
it = (*_edges).erase(it);
} else {
++it;
}
}
for (auto it = newEdges.cbegin(); it != newEdges.cend(); ++it) {
(*_edges).insert(std::move(*it));
}
}
void replace_vertices(const std::vector<Vertex*> a, const std::vector<Vertex*> b) {
auto begin1 = a.cbegin(), end1 = a.cend();
auto begin2 = b.cbegin(), end2 = b.cend();
for (auto it1 = begin1, it2 = begin2; it1 != end1 && it2 != end2;)
{
replace_vertex(**it1, **it2);
++it1; ++it2;
}
}
std::string str() const {
std::ostringstream os;
os << "[";
for (auto it = (*edges).cbegin(); it != (*edges).cend();) {
os << it->str();
++it;
if (it != (*edges).cend()) os << ", ";
}
os << "]";
return os.str();
}
std::string saveableStr() const {
std::ostringstream os;
os << "[";
for (auto it = (+edges).cbegin(); it != (+edges).cend();) {
os << it->saveableStr();
++it;
if (it != (+edges).cend()) os << ", ";
}
os << "]";
return os.str();
}
};
int main() {
std::srand(time(nullptr));
// Starting vertices
Vertex
g({"g", 0}),
f({"f", 0}),
e({"E", 9}),
d({"D", 9}),
c({"C", 9, {&d}}),
b({"B", 9}),
a({"A", 9});
// Starting graph
Graph graph {
{a, b},
{a, c},
{a, d},
{a, e},
{b, d},
{c, d},
{c, e},
{d, e},
};
// =======================================================================
// Process explanation
// =======================================================================
std::cout << "========== BASIC PROCESS ==========" << std::endl
<< std::endl;
std::cout << "START - (L)IVE AND (S)NAPSHOT VALUES ARE THE SAME" << std::endl
<< "L " << graph.str() << std::endl
<< "S " << graph.saveableStr() << std::endl
<< std::endl;
std::cout << "REQUEST SAVE - NOTHING YET - WAIT FOR MAIN THREAD TO COMPLETE WRITES" << std::endl;
willSave.store(true);
std::cout << "L " << graph.str() << std::endl
<< "S " << graph.saveableStr() << std::endl
<< std::endl;
std::cout << "SET ALL VERTEX VALUES TO ZERO" << std::endl;
for (auto v : graph.vertices()) { v->value = 0; }
std::cout << "L " << graph.str() << std::endl
<< "S " << graph.saveableStr() << std::endl
<< std::endl;
std::cout << "BEGIN SAVE - MAIN THREAD ACKNOWLEDGED - SNAPSHOT IS LOCKED" << std::endl;
update_beforesave();
isSaving.store(true);
willSave.store(false);
std::cout << "L " << graph.str() << std::endl
<< "S " << graph.saveableStr() << std::endl
<< std::endl;
std::cout << "REPLACE (C) AND (D) WITH (f) AND (g)" << std::endl;
graph.replace_vertices({&c, &d}, {&f, &g});
std::cout << "L " << graph.str() << std::endl
<< "S " << graph.saveableStr() << std::endl
<< std::endl;
std::cout << "MARK SAVE COMPLETE - NOTHING YET - WAIT FOR MAIN THREAD TO COMPLETE WRITES" << std::endl;
saveComplete.store(false);
std::cout << "L " << graph.str() << std::endl
<< "S " << graph.saveableStr() << std::endl
<< std::endl;
std::cout << "ADD EDGE COUNT TO EACH VERTEX IN GRAPH" << std::endl;
for (auto it = (*graph.edges).begin(); it != (*graph.edges).end(); ++it) {
auto a = it->a, b = it->b;
a->value = a->value + 1;
b->value = b->value + 1;
}
std::cout << "L " << graph.str() << std::endl
<< "S " << graph.saveableStr() << std::endl
<< std::endl;
std::cout << "END SAVE - MAIN THREAD ACKNOWLEDGED - SNAPSHOT IS UNLOCKED" << std::endl;
update_aftersave();
isSaving.store(false);
saveComplete.store(false);
std::cout << "L " << graph.str() << std::endl
<< "S " << graph.saveableStr() << std::endl
<< std::endl;
// Wait 10 seconds
std::cout << "Pausing for 10 seconds to review..." << std::endl
<< std::endl;
std::this_thread::sleep_for(std::chrono::milliseconds(10000));
// =======================================================================
// Simulation of user interaction with game loop and saves
// =======================================================================
std::cout << "========== BEGIN FREE RUN ==========" << std::endl
<< std::endl;
// -----------------------------------------------------------------------
// Randomly swap vertices in and out of the graph
// -----------------------------------------------------------------------
Vertex
h({"h", 0}),
i({"i", 0});
std::vector<Vertex*> outVertices{&h, &i};
auto swapVertex = [&](bool log = false) {
// swap random vertex
auto inVertices = graph.vertices();
size_t iIn = rand() % inVertices.size();
size_t iOut = rand() % outVertices.size();
auto it = inVertices.begin();
std::advance(it, iIn);
Vertex* pIn = *it;
Vertex* pOut = outVertices[iOut];
outVertices[iOut] = pIn;
graph.replace_vertex(*pIn, *pOut);
// zero all edge counts
for (auto v : graph.vertices()) { v->value = 0; }
// count all edges
for (auto it = (*graph.edges).begin(); it != (*graph.edges).end(); ++it) {
auto a = it->a, b = it->b;
a->value = a->value + 1;
b->value = b->value + 1;
}
if (log) {
std::cout << std::endl
<< "REPLACE (" << pIn->name << ") WITH (" << pOut->name << ")" << std::endl
<< "L " << graph.str() << std::endl
<< "S " << graph.saveableStr() << std::endl
<< std::endl;
}
};
// -----------------------------------------------------------------------
// Called by the main thread when ready to serialize a save
// -----------------------------------------------------------------------
auto saveThread = [&]() {
std::cout << std::endl << "----- BEGIN SAVE THREAD -----" << std::endl << std::endl;
size_t pos = 0;
size_t count = 0;
auto& edges = +(graph.edges);
std::cerr << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>" << std::endl
<< "<graph>" << std::endl;
for (auto it = edges.cbegin(); it != edges.cend(); ++it) {
auto& edge = *it;
std::this_thread::sleep_for(std::chrono::milliseconds(500));
std::cerr << " <edge pos=\"" << ++pos << "\">" << std::endl
<< " <vertex name=\"" << +edge.a->name << "\" value=\"" << +edge.a->value << "\"/>" << std::endl
<< " <vertex name=\"" << +edge.b->name << "\" value=\"" << +edge.b->value << "\"/>" << std::endl
<< " </edge>" << std::endl;
}
std::cerr << "</graph>" << std::endl;
saveComplete.store(true);
std::cout << std::endl << "----- END SAVE THREAD -----" << std::endl << std::endl;
};
// -----------------------------------------------------------------------
// Main thread (game loop)
// -----------------------------------------------------------------------
auto mainThread = [&]() {
std::cout << std::endl << "----- BEGIN MAIN THREAD -----" << std::endl << std::endl;
std::thread save;
while (!endGame || isSaving || willSave) { // Until user quits and save is complete
if (saveComplete) { // Save finished
update_aftersave();
isSaving.store(false);
saveComplete.store(false);
save.join();
std::cout << std::endl
<< "END SAVE - SNAPSHOT IS UNLOCKED" << std::endl
<< "L " << graph.str() << std::endl
<< "S " << graph.saveableStr() << std::endl
<< std::endl;
} else if (willSave) { // User requested a save
update_beforesave();
isSaving.store(true);
willSave.store(false);
std::cout << std::endl
<< "BEGIN SAVE - SNAPSHOT IS LOCKED" << std::endl
<< "S " << graph.saveableStr() << std::endl
<< std::endl;
save = std::thread(saveThread);
} else if (endGame && isSaving) { // Finish save before terminating
save.join();
update_aftersave();
isSaving.store(false);
saveComplete.store(false);
std::cout << std::endl
<< "END SAVE - SNAPSHOT IS UNLOCKED" << std::endl
<< "L " << graph.str() << std::endl
<< "S " << graph.saveableStr() << std::endl
<< std::endl;
break;
}
// Do some some work
std::this_thread::sleep_for(std::chrono::milliseconds(300));
swapVertex(true);
}
std::cout << std::endl << "----- END MAIN THREAD -----" << std::endl << std::endl;
};
// -----------------------------------------------------------------------
// Simulated user interaction (requests to save and quit)
// -----------------------------------------------------------------------
std::thread main = std::thread(mainThread);
for (size_t i = 0; i < 3;) { // User saves 3 times
if (!willSave && !isSaving) {
std::cout << std::endl
<< "REQUEST SAVE - NOTHING YET - WAIT FOR MAIN THREAD TO COMPLETE WRITES" << std::endl
<< "L " << graph.str() << std::endl
<< "S " << graph.saveableStr() << std::endl
<< std::endl;
willSave.store(true);
++i;
std::this_thread::sleep_for(std::chrono::milliseconds(2000));
}
}
endGame.store(true); // User quits
std::cout << std::endl
<< "QUIT REQUESTED - WAIT FOR MAIN THREAD AND/OR SAVE TO COMPLETE WRITES" << std::endl
<< std::endl;
main.join();
// =======================================================================
// Stress test
// =======================================================================
std::cout << "========== SINGLE THREAD STRESS TEST ==========" << std::endl
<< "Swap random vertex 3_000_000 times." << std::endl
<< "Recalculate all graph edges after each swap." << std::endl
<< "Synchronize (copy entire graph) after each run" << std::endl
<< "as if a full save were about to occur." << std::endl
<< std::endl;
std::chrono::time_point<std::chrono::system_clock> startTime = std::chrono::system_clock::now();
size_t loopCount = 3000000;
for (size_t i = 0; i < loopCount; ++i) { swapVertex(); update_beforesave(); }
std::chrono::duration<double> duration = std::chrono::system_clock::now() - startTime;
std::cout << "L " << graph.str() << std::endl
<< "S " << graph.saveableStr() << std::endl
<< std::endl
<< "Total Test Time: " << duration.count() << " s" << std::endl
<< "Average Iteration: " << duration.count() / loopCount * 1000 << " ms" << std::endl
<< "Iterations per Second: " << loopCount / duration.count() << std::endl;
return 0;
}
@xixasdev
Copy link
Author

xixasdev commented Jan 18, 2022 •
edited

Designed specifically around this graph from the DAG Wikipedia Page.

Sample Run

========== BASIC PROCESS ==========

START - (L)IVE AND (S)NAPSHOT VALUES ARE THE SAME
L [{("A/9"), ("B/9")}, {("A/9"), ("C/9")}, {("A/9"), ("D/9")}, {("A/9"), ("E/9")}, {("B/9"), ("D/9")}, {("C/9"), ("D/9")}, {("C/9"), ("E/9")}, {("D/9"), ("E/9")}]
S [{("A/9"), ("B/9")}, {("A/9"), ("C/9")}, {("A/9"), ("D/9")}, {("A/9"), ("E/9")}, {("B/9"), ("D/9")}, {("C/9"), ("D/9")}, {("C/9"), ("E/9")}, {("D/9"), ("E/9")}]

REQUEST SAVE - NOTHING YET - WAIT FOR MAIN THREAD TO COMPLETE WRITES
L [{("A/9"), ("B/9")}, {("A/9"), ("C/9")}, {("A/9"), ("D/9")}, {("A/9"), ("E/9")}, {("B/9"), ("D/9")}, {("C/9"), ("D/9")}, {("C/9"), ("E/9")}, {("D/9"), ("E/9")}]
S [{("A/9"), ("B/9")}, {("A/9"), ("C/9")}, {("A/9"), ("D/9")}, {("A/9"), ("E/9")}, {("B/9"), ("D/9")}, {("C/9"), ("D/9")}, {("C/9"), ("E/9")}, {("D/9"), ("E/9")}]

SET ALL VERTEX VALUES TO ZERO
L [{("A/0"), ("B/0")}, {("A/0"), ("C/0")}, {("A/0"), ("D/0")}, {("A/0"), ("E/0")}, {("B/0"), ("D/0")}, {("C/0"), ("D/0")}, {("C/0"), ("E/0")}, {("D/0"), ("E/0")}]
S [{("A/0"), ("B/0")}, {("A/0"), ("C/0")}, {("A/0"), ("D/0")}, {("A/0"), ("E/0")}, {("B/0"), ("D/0")}, {("C/0"), ("D/0")}, {("C/0"), ("E/0")}, {("D/0"), ("E/0")}]

BEGIN SAVE - MAIN THREAD ACKNOWLEDGED - SNAPSHOT IS LOCKED
L [{("A/0"), ("B/0")}, {("A/0"), ("C/0")}, {("A/0"), ("D/0")}, {("A/0"), ("E/0")}, {("B/0"), ("D/0")}, {("C/0"), ("D/0")}, {("C/0"), ("E/0")}, {("D/0"), ("E/0")}]
S [{("A/0"), ("B/0")}, {("A/0"), ("C/0")}, {("A/0"), ("D/0")}, {("A/0"), ("E/0")}, {("B/0"), ("D/0")}, {("C/0"), ("D/0")}, {("C/0"), ("E/0")}, {("D/0"), ("E/0")}]

REPLACE (C) AND (D) WITH (f) AND (g)
L [{("A/0"), ("B/0")}, {("A/0"), ("E/0")}, {("A/0"), ("f/0")}, {("A/0"), ("g/0")}, {("B/0"), ("g/0")}, {("f/0"), ("E/0")}, {("f/0"), ("g/0")}, {("g/0"), ("E/0")}]
S [{("A/0"), ("B/0")}, {("A/0"), ("C/0")}, {("A/0"), ("D/0")}, {("A/0"), ("E/0")}, {("B/0"), ("D/0")}, {("C/0"), ("D/0")}, {("C/0"), ("E/0")}, {("D/0"), ("E/0")}]

MARK SAVE COMPLETE - NOTHING YET - WAIT FOR MAIN THREAD TO COMPLETE WRITES
L [{("A/0"), ("B/0")}, {("A/0"), ("E/0")}, {("A/0"), ("f/0")}, {("A/0"), ("g/0")}, {("B/0"), ("g/0")}, {("f/0"), ("E/0")}, {("f/0"), ("g/0")}, {("g/0"), ("E/0")}]
S [{("A/0"), ("B/0")}, {("A/0"), ("C/0")}, {("A/0"), ("D/0")}, {("A/0"), ("E/0")}, {("B/0"), ("D/0")}, {("C/0"), ("D/0")}, {("C/0"), ("E/0")}, {("D/0"), ("E/0")}]

ADD EDGE COUNT TO EACH VERTEX IN GRAPH
L [{("A/4"), ("B/2")}, {("A/4"), ("E/3")}, {("A/4"), ("f/3")}, {("A/4"), ("g/4")}, {("B/2"), ("g/4")}, {("f/3"), ("E/3")}, {("f/3"), ("g/4")}, {("g/4"), ("E/3")}]
S [{("A/0"), ("B/0")}, {("A/0"), ("C/0")}, {("A/0"), ("D/0")}, {("A/0"), ("E/0")}, {("B/0"), ("D/0")}, {("C/0"), ("D/0")}, {("C/0"), ("E/0")}, {("D/0"), ("E/0")}]

END SAVE - MAIN THREAD ACKNOWLEDGED - SNAPSHOT IS UNLOCKED
L [{("A/4"), ("B/2")}, {("A/4"), ("E/3")}, {("A/4"), ("f/3")}, {("A/4"), ("g/4")}, {("B/2"), ("g/4")}, {("f/3"), ("E/3")}, {("f/3"), ("g/4")}, {("g/4"), ("E/3")}]
S [{("A/4"), ("B/2")}, {("A/4"), ("E/3")}, {("A/4"), ("f/3")}, {("A/4"), ("g/4")}, {("B/2"), ("g/4")}, {("f/3"), ("E/3")}, {("f/3"), ("g/4")}, {("g/4"), ("E/3")}]

Pausing for 10 seconds to review...

========== BEGIN FREE RUN ==========


REQUEST SAVE - NOTHING YET - WAIT FOR MAIN THREAD TO COMPLETE WRITES
L [{("A/4"), ("B/2")}, {("A/4"), ("E/3")}, {("A/4"), ("f/3")}, {("A/4"), ("g/4")}, {("B/2"), ("g/4")}, {("f/3"), ("E/3")}, {("f/3"), ("g/4")}, {("g/4"), ("E/3")}]

----- BEGIN MAIN THREAD -----

S [{("A/4"), ("B/2")}, {("A/4"), ("E/3")}, {("A/4"), ("f/3")}, {("A/4"), ("g/4")}, {("B/2"), ("g/4")}, {("f/3"), ("E/3")}, {("f/3"), ("g/4")}, {("g/4"), ("E/3")}]


REPLACE (g) WITH (h)
L [{("A/4"), ("B/2")}, {("A/4"), ("E/3")}, {("A/4"), ("f/3")}, {("A/4"), ("h/4")}, {("B/2"), ("h/4")}, {("f/3"), ("E/3")}, {("f/3"), ("h/4")}, {("h/4"), ("E/3")}]
S [{("A/4"), ("B/2")}, {("A/4"), ("E/3")}, {("A/4"), ("f/3")}, {("A/4"), ("g/4")}, {("B/2"), ("g/4")}, {("f/3"), ("E/3")}, {("f/3"), ("g/4")}, {("g/4"), ("E/3")}]


BEGIN SAVE - SNAPSHOT IS LOCKED
S [{("A/4"), ("B/2")}, {("A/4"), ("E/3")}, {("A/4"), ("f/3")}, {("A/4"), ("h/4")}, {("B/2"), ("h/4")}, {("f/3"), ("E/3")}, {("f/3"), ("h/4")}, {("h/4"), ("E/3")}]


----- BEGIN SAVE THREAD -----

<?xml version="1.0" encoding="UTF-8"?>
<graph>

REPLACE (f) WITH (g)
L [{("A/4"), ("B/2")}, {("A/4"), ("E/3")}, {("A/4"), ("g/3")}, {("A/4"), ("h/4")}, {("B/2"), ("h/4")}, {("g/3"), ("E/3")}, {("g/3"), ("h/4")}, {("h/4"), ("E/3")}]
S [{("A/4"), ("B/2")}, {("A/4"), ("E/3")}, {("A/4"), ("f/3")}, {("A/4"), ("h/4")}, {("B/2"), ("h/4")}, {("f/3"), ("E/3")}, {("f/3"), ("h/4")}, {("h/4"), ("E/3")}]

  <edge pos="1">
    <vertex name="A" value="4"/>
    <vertex name="B" value="2"/>
  </edge>

REPLACE (B) WITH (i)
L [{("A/4"), ("E/3")}, {("A/4"), ("g/3")}, {("A/4"), ("h/4")}, {("A/4"), ("i/2")}, {("g/3"), ("E/3")}, {("g/3"), ("h/4")}, {("h/4"), ("E/3")}, {("i/2"), ("h/4")}]
S [{("A/4"), ("B/2")}, {("A/4"), ("E/3")}, {("A/4"), ("f/3")}, {("A/4"), ("h/4")}, {("B/2"), ("h/4")}, {("f/3"), ("E/3")}, {("f/3"), ("h/4")}, {("h/4"), ("E/3")}]


REPLACE (i) WITH (B)
L [{("A/4"), ("B/2")}, {("A/4"), ("E/3")}, {("A/4"), ("g/3")}, {("A/4"), ("h/4")}, {("B/2"), ("h/4")}, {("g/3"), ("E/3")}, {("g/3"), ("h/4")}, {("h/4"), ("E/3")}]
S [{("A/4"), ("B/2")}, {("A/4"), ("E/3")}, {("A/4"), ("f/3")}, {("A/4"), ("h/4")}, {("B/2"), ("h/4")}, {("f/3"), ("E/3")}, {("f/3"), ("h/4")}, {("h/4"), ("E/3")}]

  <edge pos="2">
    <vertex name="A" value="4"/>
    <vertex name="E" value="3"/>
  </edge>

REPLACE (g) WITH (i)
L [{("A/4"), ("B/2")}, {("A/4"), ("E/3")}, {("A/4"), ("h/4")}, {("A/4"), ("i/3")}, {("B/2"), ("h/4")}, {("h/4"), ("E/3")}, {("i/3"), ("E/3")}, {("i/3"), ("h/4")}]
S [{("A/4"), ("B/2")}, {("A/4"), ("E/3")}, {("A/4"), ("f/3")}, {("A/4"), ("h/4")}, {("B/2"), ("h/4")}, {("f/3"), ("E/3")}, {("f/3"), ("h/4")}, {("h/4"), ("E/3")}]

  <edge pos="3">
    <vertex name="A" value="4"/>
    <vertex name="f" value="3"/>
  </edge>

REPLACE (h) WITH (f)
L [{("A/4"), ("B/2")}, {("A/4"), ("E/3")}, {("A/4"), ("f/4")}, {("A/4"), ("i/3")}, {("B/2"), ("f/4")}, {("f/4"), ("E/3")}, {("i/3"), ("E/3")}, {("i/3"), ("f/4")}]
S [{("A/4"), ("B/2")}, {("A/4"), ("E/3")}, {("A/4"), ("f/3")}, {("A/4"), ("h/4")}, {("B/2"), ("h/4")}, {("f/3"), ("E/3")}, {("f/3"), ("h/4")}, {("h/4"), ("E/3")}]


REPLACE (f) WITH (g)
L [{("A/4"), ("B/2")}, {("A/4"), ("E/3")}, {("A/4"), ("g/4")}, {("A/4"), ("i/3")}, {("B/2"), ("g/4")}, {("g/4"), ("E/3")}, {("i/3"), ("E/3")}, {("i/3"), ("g/4")}]
S [{("A/4"), ("B/2")}, {("A/4"), ("E/3")}, {("A/4"), ("f/3")}, {("A/4"), ("h/4")}, {("B/2"), ("h/4")}, {("f/3"), ("E/3")}, {("f/3"), ("h/4")}, {("h/4"), ("E/3")}]

  <edge pos="4">
    <vertex name="A" value="4"/>
    <vertex name="h" value="4"/>
  </edge>

REPLACE (g) WITH (h)
L [{("A/4"), ("B/2")}, {("A/4"), ("E/3")}, {("A/4"), ("h/4")}, {("A/4"), ("i/3")}, {("B/2"), ("h/4")}, {("h/4"), ("E/3")}, {("i/3"), ("E/3")}, {("i/3"), ("h/4")}]
S [{("A/4"), ("B/2")}, {("A/4"), ("E/3")}, {("A/4"), ("f/3")}, {("A/4"), ("h/4")}, {("B/2"), ("h/4")}, {("f/3"), ("E/3")}, {("f/3"), ("h/4")}, {("h/4"), ("E/3")}]


REPLACE (A) WITH (f)
L [{("B/2"), ("h/4")}, {("f/4"), ("B/2")}, {("f/4"), ("E/3")}, {("f/4"), ("h/4")}, {("f/4"), ("i/3")}, {("h/4"), ("E/3")}, {("i/3"), ("E/3")}, {("i/3"), ("h/4")}]
S [{("A/4"), ("B/2")}, {("A/4"), ("E/3")}, {("A/4"), ("f/3")}, {("A/4"), ("h/4")}, {("B/2"), ("h/4")}, {("f/3"), ("E/3")}, {("f/3"), ("h/4")}, {("h/4"), ("E/3")}]

  <edge pos="5">
    <vertex name="B" value="2"/>
    <vertex name="h" value="4"/>
  </edge>

REPLACE (E) WITH (g)
L [{("B/2"), ("h/4")}, {("f/4"), ("B/2")}, {("f/4"), ("g/3")}, {("f/4"), ("h/4")}, {("f/4"), ("i/3")}, {("h/4"), ("g/3")}, {("i/3"), ("g/3")}, {("i/3"), ("h/4")}]
S [{("A/4"), ("B/2")}, {("A/4"), ("E/3")}, {("A/4"), ("f/3")}, {("A/4"), ("h/4")}, {("B/2"), ("h/4")}, {("f/3"), ("E/3")}, {("f/3"), ("h/4")}, {("h/4"), ("E/3")}]

  <edge pos="6">
    <vertex name="f" value="3"/>
    <vertex name="E" value="3"/>
  </edge>

REPLACE (g) WITH (A)
L [{("B/2"), ("h/4")}, {("f/4"), ("A/3")}, {("f/4"), ("B/2")}, {("f/4"), ("h/4")}, {("f/4"), ("i/3")}, {("h/4"), ("A/3")}, {("i/3"), ("A/3")}, {("i/3"), ("h/4")}]
S [{("A/4"), ("B/2")}, {("A/4"), ("E/3")}, {("A/4"), ("f/3")}, {("A/4"), ("h/4")}, {("B/2"), ("h/4")}, {("f/3"), ("E/3")}, {("f/3"), ("h/4")}, {("h/4"), ("E/3")}]


REPLACE (A) WITH (g)
L [{("B/2"), ("h/4")}, {("f/4"), ("B/2")}, {("f/4"), ("g/3")}, {("f/4"), ("h/4")}, {("f/4"), ("i/3")}, {("h/4"), ("g/3")}, {("i/3"), ("g/3")}, {("i/3"), ("h/4")}]
S [{("A/4"), ("B/2")}, {("A/4"), ("E/3")}, {("A/4"), ("f/3")}, {("A/4"), ("h/4")}, {("B/2"), ("h/4")}, {("f/3"), ("E/3")}, {("f/3"), ("h/4")}, {("h/4"), ("E/3")}]

  <edge pos="7">
    <vertex name="f" value="3"/>
    <vertex name="h" value="4"/>
  </edge>

REPLACE (g) WITH (E)
L [{("B/2"), ("h/4")}, {("f/4"), ("B/2")}, {("f/4"), ("E/3")}, {("f/4"), ("h/4")}, {("f/4"), ("i/3")}, {("h/4"), ("E/3")}, {("i/3"), ("E/3")}, {("i/3"), ("h/4")}]
S [{("A/4"), ("B/2")}, {("A/4"), ("E/3")}, {("A/4"), ("f/3")}, {("A/4"), ("h/4")}, {("B/2"), ("h/4")}, {("f/3"), ("E/3")}, {("f/3"), ("h/4")}, {("h/4"), ("E/3")}]


REPLACE (h) WITH (A)
L [{("A/4"), ("E/3")}, {("B/2"), ("A/4")}, {("f/4"), ("A/4")}, {("f/4"), ("B/2")}, {("f/4"), ("E/3")}, {("f/4"), ("i/3")}, {("i/3"), ("A/4")}, {("i/3"), ("E/3")}]
S [{("A/4"), ("B/2")}, {("A/4"), ("E/3")}, {("A/4"), ("f/3")}, {("A/4"), ("h/4")}, {("B/2"), ("h/4")}, {("f/3"), ("E/3")}, {("f/3"), ("h/4")}, {("h/4"), ("E/3")}]

  <edge pos="8">
    <vertex name="h" value="4"/>
    <vertex name="E" value="3"/>
  </edge>
</graph>

----- END SAVE THREAD -----


REPLACE (i) WITH (g)
L [{("A/4"), ("E/3")}, {("B/2"), ("A/4")}, {("f/4"), ("A/4")}, {("f/4"), ("B/2")}, {("f/4"), ("E/3")}, {("f/4"), ("g/3")}, {("g/3"), ("A/4")}, {("g/3"), ("E/3")}]
S [{("A/4"), ("B/2")}, {("A/4"), ("E/3")}, {("A/4"), ("f/3")}, {("A/4"), ("h/4")}, {("B/2"), ("h/4")}, {("f/3"), ("E/3")}, {("f/3"), ("h/4")}, {("h/4"), ("E/3")}]


REQUEST SAVE - NOTHING YET - WAIT FOR MAIN THREAD TO COMPLETE WRITES
L [{("A/4"), ("E/3")}, {("B/2"), ("A/4")}, {("f/4"), ("A/4")}, {("f/4"), ("B/2")}, {("f/4"), ("E/3")}, {("f/4"), ("g/3")}, {("g/3"), ("A/4")}, {("g/3"), ("E/3")}]
S [{("A/4"), ("E/3")}, {("B/2"), ("A/4")}, {("f/4"), ("A/4")}, {("f/4"), ("B/2")}, {("f/4"), ("E/3")}, {("f/4"), ("g/3")}, {("g/3"), ("A/4")}, {("g/3"), ("E/3")}]


END SAVE - SNAPSHOT IS UNLOCKED
L [{("A/4"), ("E/3")}, {("B/2"), ("A/4")}, {("f/4"), ("A/4")}, {("f/4"), ("B/2")}, {("f/4"), ("E/3")}, {("f/4"), ("g/3")}, {("g/3"), ("A/4")}, {("g/3"), ("E/3")}]
S [{("A/4"), ("E/3")}, {("B/2"), ("A/4")}, {("f/4"), ("A/4")}, {("f/4"), ("B/2")}, {("f/4"), ("E/3")}, {("f/4"), ("g/3")}, {("g/3"), ("A/4")}, {("g/3"), ("E/3")}]


REPLACE (A) WITH (h)
L [{("B/2"), ("h/4")}, {("f/4"), ("B/2")}, {("f/4"), ("E/3")}, {("f/4"), ("g/3")}, {("f/4"), ("h/4")}, {("g/3"), ("E/3")}, {("g/3"), ("h/4")}, {("h/4"), ("E/3")}]
S [{("A/4"), ("E/3")}, {("B/2"), ("A/4")}, {("f/4"), ("A/4")}, {("f/4"), ("B/2")}, {("f/4"), ("E/3")}, {("f/4"), ("g/3")}, {("g/3"), ("A/4")}, {("g/3"), ("E/3")}]


BEGIN SAVE - SNAPSHOT IS LOCKED
S [{("B/2"), ("h/4")}, {("f/4"), ("B/2")}, {("f/4"), ("E/3")}, {("f/4"), ("g/3")}, {("f/4"), ("h/4")}, {("g/3"), ("E/3")}, {("g/3"), ("h/4")}, {("h/4"), ("E/3")}]


----- BEGIN SAVE THREAD -----

<?xml version="1.0" encoding="UTF-8"?>
<graph>

REPLACE (B) WITH (i)
L [{("f/4"), ("E/3")}, {("f/4"), ("g/3")}, {("f/4"), ("h/4")}, {("f/4"), ("i/2")}, {("g/3"), ("E/3")}, {("g/3"), ("h/4")}, {("h/4"), ("E/3")}, {("i/2"), ("h/4")}]
S [{("B/2"), ("h/4")}, {("f/4"), ("B/2")}, {("f/4"), ("E/3")}, {("f/4"), ("g/3")}, {("f/4"), ("h/4")}, {("g/3"), ("E/3")}, {("g/3"), ("h/4")}, {("h/4"), ("E/3")}]

  <edge pos="1">
    <vertex name="B" value="2"/>
    <vertex name="h" value="4"/>
  </edge>

REPLACE (i) WITH (B)
L [{("B/2"), ("h/4")}, {("f/4"), ("B/2")}, {("f/4"), ("E/3")}, {("f/4"), ("g/3")}, {("f/4"), ("h/4")}, {("g/3"), ("E/3")}, {("g/3"), ("h/4")}, {("h/4"), ("E/3")}]
S [{("B/2"), ("h/4")}, {("f/4"), ("B/2")}, {("f/4"), ("E/3")}, {("f/4"), ("g/3")}, {("f/4"), ("h/4")}, {("g/3"), ("E/3")}, {("g/3"), ("h/4")}, {("h/4"), ("E/3")}]


REPLACE (E) WITH (i)
L [{("B/2"), ("h/4")}, {("f/4"), ("B/2")}, {("f/4"), ("g/3")}, {("f/4"), ("h/4")}, {("f/4"), ("i/3")}, {("g/3"), ("h/4")}, {("g/3"), ("i/3")}, {("h/4"), ("i/3")}]
S [{("B/2"), ("h/4")}, {("f/4"), ("B/2")}, {("f/4"), ("E/3")}, {("f/4"), ("g/3")}, {("f/4"), ("h/4")}, {("g/3"), ("E/3")}, {("g/3"), ("h/4")}, {("h/4"), ("E/3")}]

  <edge pos="2">
    <vertex name="f" value="4"/>
    <vertex name="B" value="2"/>
  </edge>

REPLACE (h) WITH (E)
L [{("B/2"), ("E/4")}, {("E/4"), ("i/3")}, {("f/4"), ("B/2")}, {("f/4"), ("E/4")}, {("f/4"), ("g/3")}, {("f/4"), ("i/3")}, {("g/3"), ("E/4")}, {("g/3"), ("i/3")}]
S [{("B/2"), ("h/4")}, {("f/4"), ("B/2")}, {("f/4"), ("E/3")}, {("f/4"), ("g/3")}, {("f/4"), ("h/4")}, {("g/3"), ("E/3")}, {("g/3"), ("h/4")}, {("h/4"), ("E/3")}]

  <edge pos="3">
    <vertex name="f" value="4"/>
    <vertex name="E" value="3"/>
  </edge>

REPLACE (i) WITH (A)
L [{("B/2"), ("E/4")}, {("E/4"), ("A/3")}, {("f/4"), ("A/3")}, {("f/4"), ("B/2")}, {("f/4"), ("E/4")}, {("f/4"), ("g/3")}, {("g/3"), ("A/3")}, {("g/3"), ("E/4")}]
S [{("B/2"), ("h/4")}, {("f/4"), ("B/2")}, {("f/4"), ("E/3")}, {("f/4"), ("g/3")}, {("f/4"), ("h/4")}, {("g/3"), ("E/3")}, {("g/3"), ("h/4")}, {("h/4"), ("E/3")}]


REPLACE (f) WITH (i)
L [{("B/2"), ("E/4")}, {("E/4"), ("A/3")}, {("g/3"), ("A/3")}, {("g/3"), ("E/4")}, {("i/4"), ("A/3")}, {("i/4"), ("B/2")}, {("i/4"), ("E/4")}, {("i/4"), ("g/3")}]
S [{("B/2"), ("h/4")}, {("f/4"), ("B/2")}, {("f/4"), ("E/3")}, {("f/4"), ("g/3")}, {("f/4"), ("h/4")}, {("g/3"), ("E/3")}, {("g/3"), ("h/4")}, {("h/4"), ("E/3")}]

  <edge pos="4">
    <vertex name="f" value="4"/>
    <vertex name="g" value="3"/>
  </edge>

REPLACE (A) WITH (h)
L [{("B/2"), ("E/4")}, {("E/4"), ("h/3")}, {("g/3"), ("E/4")}, {("g/3"), ("h/3")}, {("i/4"), ("B/2")}, {("i/4"), ("E/4")}, {("i/4"), ("g/3")}, {("i/4"), ("h/3")}]
S [{("B/2"), ("h/4")}, {("f/4"), ("B/2")}, {("f/4"), ("E/3")}, {("f/4"), ("g/3")}, {("f/4"), ("h/4")}, {("g/3"), ("E/3")}, {("g/3"), ("h/4")}, {("h/4"), ("E/3")}]


REPLACE (E) WITH (f)
L [{("B/2"), ("f/4")}, {("f/4"), ("h/3")}, {("g/3"), ("f/4")}, {("g/3"), ("h/3")}, {("i/4"), ("B/2")}, {("i/4"), ("f/4")}, {("i/4"), ("g/3")}, {("i/4"), ("h/3")}]
S [{("B/2"), ("h/4")}, {("f/4"), ("B/2")}, {("f/4"), ("E/3")}, {("f/4"), ("g/3")}, {("f/4"), ("h/4")}, {("g/3"), ("E/3")}, {("g/3"), ("h/4")}, {("h/4"), ("E/3")}]

  <edge pos="5">
    <vertex name="f" value="4"/>
    <vertex name="h" value="4"/>
  </edge>

REPLACE (h) WITH (E)
L [{("B/2"), ("f/4")}, {("f/4"), ("E/3")}, {("g/3"), ("E/3")}, {("g/3"), ("f/4")}, {("i/4"), ("B/2")}, {("i/4"), ("E/3")}, {("i/4"), ("f/4")}, {("i/4"), ("g/3")}]
S [{("B/2"), ("h/4")}, {("f/4"), ("B/2")}, {("f/4"), ("E/3")}, {("f/4"), ("g/3")}, {("f/4"), ("h/4")}, {("g/3"), ("E/3")}, {("g/3"), ("h/4")}, {("h/4"), ("E/3")}]

  <edge pos="6">
    <vertex name="g" value="3"/>
    <vertex name="E" value="3"/>
  </edge>

REPLACE (g) WITH (A)
L [{("A/3"), ("E/3")}, {("A/3"), ("f/4")}, {("B/2"), ("f/4")}, {("f/4"), ("E/3")}, {("i/4"), ("A/3")}, {("i/4"), ("B/2")}, {("i/4"), ("E/3")}, {("i/4"), ("f/4")}]
S [{("B/2"), ("h/4")}, {("f/4"), ("B/2")}, {("f/4"), ("E/3")}, {("f/4"), ("g/3")}, {("f/4"), ("h/4")}, {("g/3"), ("E/3")}, {("g/3"), ("h/4")}, {("h/4"), ("E/3")}]


REPLACE (B) WITH (g)
L [{("A/3"), ("E/3")}, {("A/3"), ("f/4")}, {("f/4"), ("E/3")}, {("g/2"), ("f/4")}, {("i/4"), ("A/3")}, {("i/4"), ("E/3")}, {("i/4"), ("f/4")}, {("i/4"), ("g/2")}]
S [{("B/2"), ("h/4")}, {("f/4"), ("B/2")}, {("f/4"), ("E/3")}, {("f/4"), ("g/3")}, {("f/4"), ("h/4")}, {("g/3"), ("E/3")}, {("g/3"), ("h/4")}, {("h/4"), ("E/3")}]

  <edge pos="7">
    <vertex name="g" value="3"/>
    <vertex name="h" value="4"/>
  </edge>

REPLACE (g) WITH (B)
L [{("A/3"), ("E/3")}, {("A/3"), ("f/4")}, {("B/2"), ("f/4")}, {("f/4"), ("E/3")}, {("i/4"), ("A/3")}, {("i/4"), ("B/2")}, {("i/4"), ("E/3")}, {("i/4"), ("f/4")}]
S [{("B/2"), ("h/4")}, {("f/4"), ("B/2")}, {("f/4"), ("E/3")}, {("f/4"), ("g/3")}, {("f/4"), ("h/4")}, {("g/3"), ("E/3")}, {("g/3"), ("h/4")}, {("h/4"), ("E/3")}]


REPLACE (A) WITH (h)
L [{("B/2"), ("f/4")}, {("f/4"), ("E/3")}, {("h/3"), ("E/3")}, {("h/3"), ("f/4")}, {("i/4"), ("B/2")}, {("i/4"), ("E/3")}, {("i/4"), ("f/4")}, {("i/4"), ("h/3")}]
S [{("B/2"), ("h/4")}, {("f/4"), ("B/2")}, {("f/4"), ("E/3")}, {("f/4"), ("g/3")}, {("f/4"), ("h/4")}, {("g/3"), ("E/3")}, {("g/3"), ("h/4")}, {("h/4"), ("E/3")}]

  <edge pos="8">
    <vertex name="h" value="4"/>
    <vertex name="E" value="3"/>
  </edge>
</graph>

----- END SAVE THREAD -----


REPLACE (E) WITH (g)
L [{("B/2"), ("f/4")}, {("f/4"), ("g/3")}, {("h/3"), ("f/4")}, {("h/3"), ("g/3")}, {("i/4"), ("B/2")}, {("i/4"), ("f/4")}, {("i/4"), ("g/3")}, {("i/4"), ("h/3")}]
S [{("B/2"), ("h/4")}, {("f/4"), ("B/2")}, {("f/4"), ("E/3")}, {("f/4"), ("g/3")}, {("f/4"), ("h/4")}, {("g/3"), ("E/3")}, {("g/3"), ("h/4")}, {("h/4"), ("E/3")}]


REQUEST SAVE - NOTHING YET - WAIT FOR MAIN THREAD TO COMPLETE WRITES
L 
END SAVE - SNAPSHOT IS UNLOCKED
L [{("B/2"), ("f/4")}, {("f/4"), ("g/3")}, {("h/3"), ("f/4")}, {("h/3"), ("g/3")}, {("i/4"), ("B/2")}, {("i/4"), ("f/4")}, {("i/4"), ("g/3")}, {("i/4"), ("h/3")}]
S [{("B/2"), ("f/4")}, {("f/4"), ("g/3")}, {("h/3"), ("f/4")}, {("h/3"), ("g/3")}, {("i/4"), ("B/2")}, {("i/4"), ("f/4")}, {("i/4"), ("g/3")}, {("i/4"), ("h/3")}]
S [{("B/2"), ("f/4")}, {("f/4"), ("g/3")}, {("h/3"), ("f/4")}, {("h/3"), ("g/3")}, {("i/4"), ("B/2")}, {("i/4"), ("f/4")}, {("i/4"), ("g/3")}, {("i/4"), ("h/3")}]

[{("B/2"), ("f/4")}, {("f/4"), ("g/3")}, {("h/3"), ("f/4")}, {("h/3"), ("g/3")}, {("i/4"), ("B/2")}, {("i/4"), ("f/4")}, {("i/4"), ("g/3")}, {("i/4"), ("h/3")}]


REPLACE (f) WITH (E)
L [{("B/2"), ("E/4")}, {("E/4"), ("g/3")}, {("h/3"), ("E/4")}, {("h/3"), ("g/3")}, {("i/4"), ("B/2")}, {("i/4"), ("E/4")}, {("i/4"), ("g/3")}, {("i/4"), ("h/3")}]
S [{("B/2"), ("f/4")}, {("f/4"), ("g/3")}, {("h/3"), ("f/4")}, {("h/3"), ("g/3")}, {("i/4"), ("B/2")}, {("i/4"), ("f/4")}, {("i/4"), ("g/3")}, {("i/4"), ("h/3")}]


BEGIN SAVE - SNAPSHOT IS LOCKED
S [{("B/2"), ("E/4")}, {("E/4"), ("g/3")}, {("h/3"), ("E/4")}, {("h/3"), ("g/3")}, {("i/4"), ("B/2")}, {("i/4"), ("E/4")}, {("i/4"), ("g/3")}, {("i/4"), ("h/3")}]


----- BEGIN SAVE THREAD -----

<?xml version="1.0" encoding="UTF-8"?>
<graph>

REPLACE (g) WITH (A)
L [{("B/2"), ("E/4")}, {("E/4"), ("A/3")}, {("h/3"), ("A/3")}, {("h/3"), ("E/4")}, {("i/4"), ("A/3")}, {("i/4"), ("B/2")}, {("i/4"), ("E/4")}, {("i/4"), ("h/3")}]
S [{("B/2"), ("E/4")}, {("E/4"), ("g/3")}, {("h/3"), ("E/4")}, {("h/3"), ("g/3")}, {("i/4"), ("B/2")}, {("i/4"), ("E/4")}, {("i/4"), ("g/3")}, {("i/4"), ("h/3")}]

  <edge pos="1">
    <vertex name="B" value="2"/>
    <vertex name="E" value="4"/>
  </edge>

REPLACE (B) WITH (g)
L [{("E/4"), ("A/3")}, {("g/2"), ("E/4")}, {("h/3"), ("A/3")}, {("h/3"), ("E/4")}, {("i/4"), ("A/3")}, {("i/4"), ("E/4")}, {("i/4"), ("g/2")}, {("i/4"), ("h/3")}]
S [{("B/2"), ("E/4")}, {("E/4"), ("g/3")}, {("h/3"), ("E/4")}, {("h/3"), ("g/3")}, {("i/4"), ("B/2")}, {("i/4"), ("E/4")}, {("i/4"), ("g/3")}, {("i/4"), ("h/3")}]


REPLACE (E) WITH (f)
L [{("f/4"), ("A/3")}, {("g/2"), ("f/4")}, {("h/3"), ("A/3")}, {("h/3"), ("f/4")}, {("i/4"), ("A/3")}, {("i/4"), ("f/4")}, {("i/4"), ("g/2")}, {("i/4"), ("h/3")}]
S [{("B/2"), ("E/4")}, {("E/4"), ("g/3")}, {("h/3"), ("E/4")}, {("h/3"), ("g/3")}, {("i/4"), ("B/2")}, {("i/4"), ("E/4")}, {("i/4"), ("g/3")}, {("i/4"), ("h/3")}]

  <edge pos="2">
    <vertex name="E" value="4"/>
    <vertex name="g" value="3"/>
  </edge>

REPLACE (f) WITH (E)
L [{("E/4"), ("A/3")}, {("g/2"), ("E/4")}, {("h/3"), ("A/3")}, {("h/3"), ("E/4")}, {("i/4"), ("A/3")}, {("i/4"), ("E/4")}, {("i/4"), ("g/2")}, {("i/4"), ("h/3")}]
S [{("B/2"), ("E/4")}, {("E/4"), ("g/3")}, {("h/3"), ("E/4")}, {("h/3"), ("g/3")}, {("i/4"), ("B/2")}, {("i/4"), ("E/4")}, {("i/4"), ("g/3")}, {("i/4"), ("h/3")}]

  <edge pos="3">
    <vertex name="h" value="3"/>
    <vertex name="E" value="4"/>
  </edge>

REPLACE (i) WITH (f)
L [{("E/4"), ("A/3")}, {("f/4"), ("A/3")}, {("f/4"), ("E/4")}, {("f/4"), ("g/2")}, {("f/4"), ("h/3")}, {("g/2"), ("E/4")}, {("h/3"), ("A/3")}, {("h/3"), ("E/4")}]
S [{("B/2"), ("E/4")}, {("E/4"), ("g/3")}, {("h/3"), ("E/4")}, {("h/3"), ("g/3")}, {("i/4"), ("B/2")}, {("i/4"), ("E/4")}, {("i/4"), ("g/3")}, {("i/4"), ("h/3")}]


QUIT REQUESTED - WAIT FOR MAIN THREAD AND/OR SAVE TO COMPLETE WRITES


REPLACE (E) WITH (i)
L [{("f/4"), ("A/3")}, {("f/4"), ("g/2")}, {("f/4"), ("h/3")}, {("f/4"), ("i/4")}, {("g/2"), ("i/4")}, {("h/3"), ("A/3")}, {("h/3"), ("i/4")}, {("i/4"), ("A/3")}]
S [{("B/2"), ("E/4")}, {("E/4"), ("g/3")}, {("h/3"), ("E/4")}, {("h/3"), ("g/3")}, {("i/4"), ("B/2")}, {("i/4"), ("E/4")}, {("i/4"), ("g/3")}, {("i/4"), ("h/3")}]

  <edge pos="4">
    <vertex name="h" value="3"/>
    <vertex name="g" value="3"/>
  </edge>
  <edge pos="5">
    <vertex name="i" value="4"/>
    <vertex name="B" value="2"/>
  </edge>
  <edge pos="6">
    <vertex name="i" value="4"/>
    <vertex name="E" value="4"/>
  </edge>
  <edge pos="7">
    <vertex name="i" value="4"/>
    <vertex name="g" value="3"/>
  </edge>
  <edge pos="8">
    <vertex name="i" value="4"/>
    <vertex name="h" value="3"/>
  </edge>
</graph>

----- END SAVE THREAD -----


END SAVE - SNAPSHOT IS UNLOCKED
L [{("f/4"), ("A/3")}, {("f/4"), ("g/2")}, {("f/4"), ("h/3")}, {("f/4"), ("i/4")}, {("g/2"), ("i/4")}, {("h/3"), ("A/3")}, {("h/3"), ("i/4")}, {("i/4"), ("A/3")}]
S [{("f/4"), ("A/3")}, {("f/4"), ("g/2")}, {("f/4"), ("h/3")}, {("f/4"), ("i/4")}, {("g/2"), ("i/4")}, {("h/3"), ("A/3")}, {("h/3"), ("i/4")}, {("i/4"), ("A/3")}]


----- END MAIN THREAD -----

========== SINGLE THREAD STRESS TEST ==========
Swap random vertex 3_000_000 times.
Recalculate all graph edges after each swap.
Synchronize (copy entire graph) after each run
as if a full save were about to occur.

L [{("A/2"), ("B/4")}, {("B/4"), ("E/3")}, {("g/4"), ("A/2")}, {("g/4"), ("B/4")}, {("g/4"), ("E/3")}, {("g/4"), ("i/3")}, {("i/3"), ("B/4")}, {("i/3"), ("E/3")}]
S [{("A/2"), ("B/4")}, {("B/4"), ("E/3")}, {("g/4"), ("A/2")}, {("g/4"), ("B/4")}, {("g/4"), ("E/3")}, {("g/4"), ("i/3")}, {("i/3"), ("B/4")}, {("i/3"), ("E/3")}]

Total Test Time:       5.14741 s
Average Iteration:     0.0017158 ms
Iterations per Second: 582818

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment