commit f4610d5adb3d3472f9c21d68f131561f516c0880
parent 004a4ea4ddfaac30a4a426d4a6d8bba0e92ddde7
Author: Andrew Laack <andrew@laack.co>
Date: Wed, 16 Sep 2026 10:41:54 -0500
Reformatted, refactoring makefile.
Diffstat:
14 files changed, 959 insertions(+), 585 deletions(-)
diff --git a/.clang-format b/.clang-format
@@ -0,0 +1,358 @@
+---
+Language: Cpp
+AlignAfterOpenBracket: true
+AccessModifierOffset: -1
+AlignArrayOfStructures: None
+AlignConsecutiveAssignments:
+ Enabled: false
+ AcrossEmptyLines: false
+ AcrossComments: false
+ AlignCompound: false
+ AlignFunctionDeclarations: false
+ AlignFunctionPointers: false
+ PadOperators: true
+AlignConsecutiveBitFields:
+ Enabled: false
+ AcrossEmptyLines: false
+ AcrossComments: false
+ AlignCompound: false
+ AlignFunctionDeclarations: false
+ AlignFunctionPointers: false
+ PadOperators: false
+AlignConsecutiveDeclarations:
+ Enabled: false
+ AcrossEmptyLines: false
+ AcrossComments: false
+ AlignCompound: false
+ AlignFunctionDeclarations: true
+ AlignFunctionPointers: false
+ PadOperators: false
+AlignConsecutiveMacros:
+ Enabled: false
+ AcrossEmptyLines: false
+ AcrossComments: false
+ AlignCompound: false
+ AlignFunctionDeclarations: false
+ AlignFunctionPointers: false
+ PadOperators: false
+AlignConsecutiveShortCaseStatements:
+ Enabled: false
+ AcrossEmptyLines: false
+ AcrossComments: false
+ AlignCaseArrows: false
+ AlignCaseColons: false
+AlignConsecutiveTableGenBreakingDAGArgColons:
+ Enabled: false
+ AcrossEmptyLines: false
+ AcrossComments: false
+ AlignCompound: false
+ AlignFunctionDeclarations: false
+ AlignFunctionPointers: false
+ PadOperators: false
+AlignConsecutiveTableGenCondOperatorColons:
+ Enabled: false
+ AcrossEmptyLines: false
+ AcrossComments: false
+ AlignCompound: false
+ AlignFunctionDeclarations: false
+ AlignFunctionPointers: false
+ PadOperators: false
+AlignConsecutiveTableGenDefinitionColons:
+ Enabled: false
+ AcrossEmptyLines: false
+ AcrossComments: false
+ AlignCompound: false
+ AlignFunctionDeclarations: false
+ AlignFunctionPointers: false
+ PadOperators: false
+AlignEscapedNewlines: Left
+AlignOperands: Align
+AlignTrailingComments:
+ AlignPPAndNotPP: true
+ Kind: Always
+ OverEmptyLines: 0
+AllowAllArgumentsOnNextLine: true
+AllowAllParametersOfDeclarationOnNextLine: true
+AllowBreakBeforeNoexceptSpecifier: Never
+AllowBreakBeforeQtProperty: false
+AllowShortBlocksOnASingleLine: Never
+AllowShortCaseExpressionOnASingleLine: true
+AllowShortCaseLabelsOnASingleLine: false
+AllowShortCompoundRequirementOnASingleLine: true
+AllowShortEnumsOnASingleLine: true
+AllowShortFunctionsOnASingleLine: All
+AllowShortIfStatementsOnASingleLine: WithoutElse
+AllowShortLambdasOnASingleLine: All
+AllowShortLoopsOnASingleLine: true
+AllowShortNamespacesOnASingleLine: false
+AlwaysBreakAfterDefinitionReturnType: None
+AlwaysBreakBeforeMultilineStrings: true
+AttributeMacros:
+ - __capability
+ - absl_nonnull
+ - absl_nullable
+ - absl_nullability_unknown
+BinPackArguments: true
+BinPackLongBracedList: true
+BinPackParameters: BinPack
+BitFieldColonSpacing: Both
+BracedInitializerIndentWidth: -1
+BraceWrapping:
+ AfterCaseLabel: false
+ AfterClass: false
+ AfterControlStatement: Never
+ AfterEnum: false
+ AfterExternBlock: false
+ AfterFunction: false
+ AfterNamespace: false
+ AfterObjCDeclaration: false
+ AfterStruct: false
+ AfterUnion: false
+ BeforeCatch: false
+ BeforeElse: false
+ BeforeLambdaBody: false
+ BeforeWhile: false
+ IndentBraces: false
+ SplitEmptyFunction: true
+ SplitEmptyRecord: true
+ SplitEmptyNamespace: true
+BreakAdjacentStringLiterals: true
+BreakAfterAttributes: Leave
+BreakAfterJavaFieldAnnotations: false
+BreakAfterOpenBracketBracedList: false
+BreakAfterOpenBracketFunction: false
+BreakAfterOpenBracketIf: false
+BreakAfterOpenBracketLoop: false
+BreakAfterOpenBracketSwitch: false
+BreakAfterReturnType: None
+BreakArrays: true
+BreakBeforeBinaryOperators: None
+BreakBeforeCloseBracketBracedList: false
+BreakBeforeCloseBracketFunction: false
+BreakBeforeCloseBracketIf: false
+BreakBeforeCloseBracketLoop: false
+BreakBeforeCloseBracketSwitch: false
+BreakBeforeConceptDeclarations: Always
+BreakBeforeBraces: Attach
+BreakBeforeInlineASMColon: OnlyMultiline
+BreakBeforeTemplateCloser: false
+BreakBeforeTernaryOperators: true
+BreakBinaryOperations: Never
+BreakConstructorInitializers: BeforeColon
+BreakFunctionDefinitionParameters: false
+BreakInheritanceList: BeforeColon
+BreakStringLiterals: true
+BreakTemplateDeclarations: Yes
+ColumnLimit: 80
+CommentPragmas: '^ IWYU pragma:'
+CompactNamespaces: false
+ConstructorInitializerIndentWidth: 4
+ContinuationIndentWidth: 4
+Cpp11BracedListStyle: AlignFirstComment
+DerivePointerAlignment: false
+DisableFormat: false
+EmptyLineAfterAccessModifier: Never
+EmptyLineBeforeAccessModifier: LogicalBlock
+EnumTrailingComma: Leave
+ExperimentalAutoDetectBinPacking: false
+FixNamespaceComments: true
+ForEachMacros:
+ - foreach
+ - Q_FOREACH
+ - BOOST_FOREACH
+IfMacros:
+ - KJ_IF_MAYBE
+IncludeBlocks: Regroup
+IncludeCategories:
+ - Regex: '^<ext/.*\.h>'
+ Priority: 2
+ SortPriority: 0
+ CaseSensitive: false
+ - Regex: '^<.*\.h>'
+ Priority: 1
+ SortPriority: 0
+ CaseSensitive: false
+ - Regex: '^<.*'
+ Priority: 2
+ SortPriority: 0
+ CaseSensitive: false
+ - Regex: '.*'
+ Priority: 3
+ SortPriority: 0
+ CaseSensitive: false
+IncludeIsMainRegex: '([-_](test|unittest))?$'
+IncludeIsMainSourceRegex: ''
+IndentAccessModifiers: false
+IndentCaseBlocks: false
+IndentCaseLabels: true
+IndentExportBlock: true
+IndentExternBlock: AfterExternBlock
+IndentGotoLabels: true
+IndentPPDirectives: None
+IndentRequiresClause: true
+IndentWidth: 4
+IndentWrappedFunctionNames: false
+InsertBraces: false
+InsertNewlineAtEOF: false
+InsertTrailingCommas: None
+IntegerLiteralSeparator:
+ Binary: 0
+ BinaryMinDigitsInsert: 0
+ BinaryMaxDigitsRemove: 0
+ Decimal: 0
+ DecimalMinDigitsInsert: 0
+ DecimalMaxDigitsRemove: 0
+ Hex: 0
+ HexMinDigitsInsert: 0
+ HexMaxDigitsRemove: 0
+ BinaryMinDigits: 0
+ DecimalMinDigits: 0
+ HexMinDigits: 0
+JavaScriptQuotes: Leave
+JavaScriptWrapImports: true
+KeepEmptyLines:
+ AtEndOfFile: false
+ AtStartOfBlock: false
+ AtStartOfFile: true
+KeepFormFeed: false
+LambdaBodyIndentation: Signature
+LineEnding: DeriveLF
+MacroBlockBegin: ''
+MacroBlockEnd: ''
+MainIncludeChar: Quote
+MaxEmptyLinesToKeep: 1
+NamespaceIndentation: None
+NumericLiteralCase:
+ ExponentLetter: Leave
+ HexDigit: Leave
+ Prefix: Leave
+ Suffix: Leave
+ObjCBinPackProtocolList: Never
+ObjCBlockIndentWidth: 2
+ObjCBreakBeforeNestedBlockParam: true
+ObjCSpaceAfterProperty: false
+ObjCSpaceBeforeProtocolList: true
+OneLineFormatOffRegex: ''
+PackConstructorInitializers: NextLine
+PenaltyBreakAssignment: 2
+PenaltyBreakBeforeFirstCallParameter: 1
+PenaltyBreakBeforeMemberAccess: 150
+PenaltyBreakComment: 300
+PenaltyBreakFirstLessLess: 120
+PenaltyBreakOpenParenthesis: 0
+PenaltyBreakScopeResolution: 500
+PenaltyBreakString: 1000
+PenaltyBreakTemplateDeclaration: 10
+PenaltyExcessCharacter: 1000000
+PenaltyIndentedWhitespace: 0
+PenaltyReturnTypeOnItsOwnLine: 200
+PointerAlignment: Left
+PPIndentWidth: -1
+QualifierAlignment: Leave
+RawStringFormats:
+ - Language: Cpp
+ Delimiters:
+ - cc
+ - CC
+ - cpp
+ - Cpp
+ - CPP
+ - 'c++'
+ - 'C++'
+ CanonicalDelimiter: ''
+ BasedOnStyle: google
+ - Language: TextProto
+ Delimiters:
+ - pb
+ - PB
+ - proto
+ - PROTO
+ EnclosingFunctions:
+ - EqualsProto
+ - EquivToProto
+ - PARSE_PARTIAL_TEXT_PROTO
+ - PARSE_TEST_PROTO
+ - PARSE_TEXT_PROTO
+ - ParseTextOrDie
+ - ParseTextProtoOrDie
+ - ParseTestProto
+ - ParsePartialTestProto
+ CanonicalDelimiter: pb
+ BasedOnStyle: google
+ReferenceAlignment: Pointer
+ReflowComments: Always
+RemoveBracesLLVM: false
+RemoveEmptyLinesInUnwrappedLines: false
+RemoveParentheses: Leave
+RemoveSemicolon: false
+RequiresClausePosition: OwnLine
+RequiresExpressionIndentation: OuterScope
+SeparateDefinitionBlocks: Leave
+ShortNamespaceLines: 1
+SkipMacroDefinitionBody: false
+SortIncludes:
+ Enabled: true
+ IgnoreCase: false
+ IgnoreExtension: false
+SortJavaStaticImport: Before
+SortUsingDeclarations: LexicographicNumeric
+SpaceAfterCStyleCast: false
+SpaceAfterLogicalNot: false
+SpaceAfterOperatorKeyword: false
+SpaceAfterTemplateKeyword: true
+SpaceAroundPointerQualifiers: Default
+SpaceBeforeAssignmentOperators: true
+SpaceBeforeCaseColon: false
+SpaceBeforeCpp11BracedList: false
+SpaceBeforeCtorInitializerColon: true
+SpaceBeforeInheritanceColon: true
+SpaceBeforeJsonColon: false
+SpaceBeforeParens: ControlStatements
+SpaceBeforeParensOptions:
+ AfterControlStatements: true
+ AfterForeachMacros: true
+ AfterFunctionDefinitionName: false
+ AfterFunctionDeclarationName: false
+ AfterIfMacros: true
+ AfterNot: false
+ AfterOverloadedOperator: false
+ AfterPlacementOperator: true
+ AfterRequiresInClause: false
+ AfterRequiresInExpression: false
+ BeforeNonEmptyParentheses: false
+SpaceBeforeRangeBasedForLoopColon: true
+SpaceBeforeSquareBrackets: false
+SpaceInEmptyBraces: Never
+SpacesBeforeTrailingComments: 2
+SpacesInAngles: Never
+SpacesInContainerLiterals: true
+SpacesInLineCommentPrefix:
+ Minimum: 1
+ Maximum: -1
+SpacesInParens: Never
+SpacesInParensOptions:
+ ExceptDoubleParentheses: false
+ InCStyleCasts: false
+ InConditionalStatements: false
+ InEmptyParentheses: false
+ Other: false
+SpacesInSquareBrackets: false
+Standard: Auto
+StatementAttributeLikeMacros:
+ - Q_EMIT
+StatementMacros:
+ - Q_UNUSED
+ - QT_REQUIRE_VERSION
+TableGenBreakInsideDAGArg: DontBreak
+TabWidth: 8
+UseTab: Never
+VerilogBreakBetweenInstancePorts: true
+WhitespaceSensitiveMacros:
+ - BOOST_PP_STRINGIZE
+ - CF_SWIFT_NAME
+ - NS_SWIFT_NAME
+ - PP_STRINGIZE
+ - STRINGIZE
+WrapNamespaceBodyWithEmptyLines: Leave
+...
+
diff --git a/Makefile b/Makefile
@@ -8,8 +8,14 @@ install: build
clean:
rm abg.out
+# other
+fmt:
+ clang-format -i src/*.cpp
+ clang-format -i tests/*.cpp
+format: fmt
+
# snapshot update
-update-snapshot:
+snapshot-update:
${TCOMMAND_P} tests/snapshot_update.cpp ${TCOMMAND_S} -o snapshot_update
./snapshot_update
rm snapshot_update
@@ -28,4 +34,4 @@ algo-test:
./algo_tests
rm algo_tests
-test: snapshot-test graph-test algo-test
+test: format snapshot-test graph-test algo-test
diff --git a/src/background.cpp b/src/background.cpp
@@ -1,60 +1,61 @@
#include <X11/Xatom.h>
#include <X11/Xlib.h>
+#include <unistd.h>
+
#include <cstddef>
#include <cstdint>
#include <stdexcept>
#include <string>
-#include <unistd.h>
#include <vector>
std::vector<uint32_t> getScreenSize() {
- Display *dpy;
- Screen *screen;
- dpy = XOpenDisplay(NULL);
- int count = ScreenCount(dpy);
- if (count == 0) {
- throw std::runtime_error{"Unable to find screens."};
- }
- screen = ScreenOfDisplay(dpy, 0);
- std::vector<uint32_t> res{(uint32_t)screen->width, (uint32_t)screen->height};
- return res;
+ Display* dpy;
+ Screen* screen;
+ dpy = XOpenDisplay(NULL);
+ int count = ScreenCount(dpy);
+ if (count == 0) {
+ throw std::runtime_error{"Unable to find screens."};
+ }
+ screen = ScreenOfDisplay(dpy, 0);
+ std::vector<uint32_t> res{(uint32_t)screen->width,
+ (uint32_t)screen->height};
+ return res;
}
void sendToBg(std::string name) {
- Display *d = XOpenDisplay(nullptr);
- Window root = DefaultRootWindow(d), r, p, *kids;
- uint32_t n;
+ Display* d = XOpenDisplay(nullptr);
+ Window root = DefaultRootWindow(d), r, p, *kids;
+ uint32_t n;
- XQueryTree(d, root, &r, &p, &kids, &n);
- for (unsigned i = 0; i < n; i++) {
+ XQueryTree(d, root, &r, &p, &kids, &n);
+ for (unsigned i = 0; i < n; i++) {
+ char* wn = nullptr;
+ XFetchName(d, kids[i], &wn);
- char *wn = nullptr;
- XFetchName(d, kids[i], &wn);
+ if (wn == nullptr) {
+ continue;
+ }
- if (wn == nullptr) {
- continue;
- }
-
- bool hit = name == wn;
- XFree(wn);
+ bool hit = name == wn;
+ XFree(wn);
- if (!hit) {
- continue;
- }
+ if (!hit) {
+ continue;
+ }
- XSetWindowAttributes a;
+ XSetWindowAttributes a;
- a.override_redirect = True;
- XChangeWindowAttributes(d, kids[i], CWOverrideRedirect, &a);
+ a.override_redirect = True;
+ XChangeWindowAttributes(d, kids[i], CWOverrideRedirect, &a);
- // have to do unmap / map to make it bg for all tags
- XUnmapWindow(d, kids[i]);
- XMapWindow(d, kids[i]);
+ // have to do unmap / map to make it bg for all tags
+ XUnmapWindow(d, kids[i]);
+ XMapWindow(d, kids[i]);
- XLowerWindow(d, kids[i]);
- break;
- }
+ XLowerWindow(d, kids[i]);
+ break;
+ }
- XFree(kids);
- XCloseDisplay(d);
+ XFree(kids);
+ XCloseDisplay(d);
}
diff --git a/src/edge.cpp b/src/edge.cpp
@@ -1,4 +1,5 @@
#include "../include/edge.hpp"
+
#include <cstddef>
#include <string>
@@ -7,15 +8,15 @@ Edge::Edge(std::size_t v1, std::size_t v2, double length2,
: v1Index(v1), v2Index(v2), length2(length2), identifier(identifier) {}
std::string Edge::toString() const noexcept {
- return "(v1: " + std::to_string(this->v1Index) +
- ", v2: " + std::to_string(this->v2Index) +
- +", traversed: " + std::to_string(this->traversed) + ")";
+ return "(v1: " + std::to_string(this->v1Index) +
+ ", v2: " + std::to_string(this->v2Index) +
+ +", traversed: " + std::to_string(this->traversed) + ")";
}
-bool Edge::operator<(const Edge &other) const {
- return length2 < other.length2;
+bool Edge::operator<(const Edge& other) const {
+ return length2 < other.length2;
}
-bool Edge::operator>(const Edge &other) const {
- return length2 > other.length2;
+bool Edge::operator>(const Edge& other) const {
+ return length2 > other.length2;
}
diff --git a/src/graph.cpp b/src/graph.cpp
@@ -1,141 +1,141 @@
#include "../include/graph.hpp"
-#include "../include/constants.hpp"
-#include "../include/utils.hpp"
-#include "../include/vertex.hpp"
+
+#include <raylib.h>
+
#include <cstddef>
#include <cstdint>
-#include <raylib.h>
#include <stdexcept>
+#include "../include/constants.hpp"
+#include "../include/utils.hpp"
+#include "../include/vertex.hpp"
+
Graph::Graph(std::size_t edgeCount, std::size_t vertCount, uint32_t xMax,
uint32_t yMax) {
-
- if (edgeCount > 0 && vertCount <= 1) {
- throw std::invalid_argument("This graph does not support self-loops.");
- }
- if (xMax <= 0 || yMax <= 0) {
- throw std::invalid_argument("xMax and yMax must be > 0.");
- }
-
- for (std::size_t i = 0; i < vertCount; ++i) {
- Vector2 rnd = randomPosition(xMax, yMax);
- Vertex v{rnd, VERTEX_RENDER_SIZE};
- this->vertices.push_back(v);
- }
- for (std::size_t i = 0; i < edgeCount; ++i) {
- std::size_t idx1 = 0;
- std::size_t idx2 = 0;
- // no self-edges
- while (idx1 == idx2) {
- idx1 = std::rand() % vertCount;
- idx2 = std::rand() % vertCount;
+ if (edgeCount > 0 && vertCount <= 1) {
+ throw std::invalid_argument("This graph does not support self-loops.");
+ }
+ if (xMax <= 0 || yMax <= 0) {
+ throw std::invalid_argument("xMax and yMax must be > 0.");
}
- Edge e{idx1, idx2,
- distanceSquared(vertices[idx1].position, vertices[idx2].position),
- i};
- this->edges[idx1].push_back(e);
- this->edges[idx2].push_back(e);
- }
+ for (std::size_t i = 0; i < vertCount; ++i) {
+ Vector2 rnd = randomPosition(xMax, yMax);
+ Vertex v{rnd, VERTEX_RENDER_SIZE};
+ this->vertices.push_back(v);
+ }
+ for (std::size_t i = 0; i < edgeCount; ++i) {
+ std::size_t idx1 = 0;
+ std::size_t idx2 = 0;
+ // no self-edges
+ while (idx1 == idx2) {
+ idx1 = std::rand() % vertCount;
+ idx2 = std::rand() % vertCount;
+ }
+
+ Edge e{
+ idx1, idx2,
+ distanceSquared(vertices[idx1].position, vertices[idx2].position),
+ i};
+ this->edges[idx1].push_back(e);
+ this->edges[idx2].push_back(e);
+ }
}
std::string Graph::toString() noexcept {
+ std::string result = "edges: {";
- std::string result = "edges: {";
-
- for (auto pair : this->edges) {
- auto key = pair.first;
- for (auto edge : edges[key]) {
- result += edge.toString();
+ for (auto pair : this->edges) {
+ auto key = pair.first;
+ for (auto edge : edges[key]) {
+ result += edge.toString();
+ }
}
- }
- result += "}";
+ result += "}";
- result += "\nvertices: {";
+ result += "\nvertices: {";
- for (auto vertex : this->vertices) {
- result += vertex.toString();
- }
+ for (auto vertex : this->vertices) {
+ result += vertex.toString();
+ }
- result += "}";
- return result;
+ result += "}";
+ return result;
}
void Graph::render() noexcept {
+ // yes, this will double draw because we track 0 -> 1 and 1 -> 0
+
+ std::vector<Edge> visited{};
+ for (auto pair : this->edges) {
+ auto edges = this->edges[pair.first];
+ for (auto edge : edges) {
+ std::size_t idx1 = edge.v1Index;
+ std::size_t idx2 = edge.v2Index;
+ auto v1 = vertices[idx1].position;
+ auto v2 = vertices[idx2].position;
+ if (edge.traversed) {
+ visited.push_back(edge);
+ } else {
+ DrawLineEx(v1, v2, EDGE_REDNER_SIZE, DARKERGRAY);
+ }
+ }
+ }
- // yes, this will double draw because we track 0 -> 1 and 1 -> 0
-
- std::vector<Edge> visited{};
- for (auto pair : this->edges) {
- auto edges = this->edges[pair.first];
- for (auto edge : edges) {
- std::size_t idx1 = edge.v1Index;
- std::size_t idx2 = edge.v2Index;
- auto v1 = vertices[idx1].position;
- auto v2 = vertices[idx2].position;
- if (edge.traversed) {
- visited.push_back(edge);
- } else {
- DrawLineEx(v1, v2, EDGE_REDNER_SIZE, DARKERGRAY);
- }
+ for (auto vertex : this->vertices) {
+ vertex.render();
+ }
+
+ // ensure we draw visited over unvisited for better looks
+ for (auto edge : visited) {
+ std::size_t idx1 = edge.v1Index;
+ std::size_t idx2 = edge.v2Index;
+ auto v1 = vertices[idx1].position;
+ auto v2 = vertices[idx2].position;
+ DrawLineEx(v1, v2, EDGE_REDNER_SIZE, WHITE);
}
- }
-
- for (auto vertex : this->vertices) {
- vertex.render();
- }
-
- // ensure we draw visited over unvisited for better looks
- for (auto edge : visited) {
- std::size_t idx1 = edge.v1Index;
- std::size_t idx2 = edge.v2Index;
- auto v1 = vertices[idx1].position;
- auto v2 = vertices[idx2].position;
- DrawLineEx(v1, v2, EDGE_REDNER_SIZE, WHITE);
- }
}
void Graph::traverseVertexIdx(std::size_t idx) {
- this->vertices[idx].visited = true;
+ this->vertices[idx].visited = true;
}
std::vector<Edge> Graph::getEdgesOfVertexIdx(std::size_t idx) {
- return this->edges[idx];
+ return this->edges[idx];
}
void Graph::setEdgeTraversed(Edge e) {
+ std::size_t source = e.v1Index;
+ std::size_t destination = e.v2Index;
- std::size_t source = e.v1Index;
- std::size_t destination = e.v2Index;
-
- if (source == destination) {
- return;
- }
+ if (source == destination) {
+ return;
+ }
- auto &cEdges = edges[source];
+ auto& cEdges = edges[source];
- for (auto &edge : cEdges) {
- if (edge.v2Index == destination || edge.v1Index == destination) {
- edge.traversed = true;
+ for (auto& edge : cEdges) {
+ if (edge.v2Index == destination || edge.v1Index == destination) {
+ edge.traversed = true;
+ }
}
- }
- auto &oEdges = edges[destination];
+ auto& oEdges = edges[destination];
- for (auto &edge : oEdges) {
- if (edge.v2Index == source || edge.v1Index == source) {
- edge.traversed = true;
+ for (auto& edge : oEdges) {
+ if (edge.v2Index == source || edge.v1Index == source) {
+ edge.traversed = true;
+ }
}
- }
}
Vertex Graph::getVertex(std::size_t idx) {
- // idx can't be negative bc size_t
- if (idx >= vertices.size()) {
- throw std::invalid_argument("idx out of bounds for vertex list");
- }
- return vertices[idx];
+ // idx can't be negative bc size_t
+ if (idx >= vertices.size()) {
+ throw std::invalid_argument("idx out of bounds for vertex list");
+ }
+ return vertices[idx];
}
std::size_t Graph::getVertexCount() const noexcept { return vertices.size(); }
diff --git a/src/main.cpp b/src/main.cpp
@@ -1,90 +1,92 @@
-#include "../include/background.hpp"
-#include "../include/constants.hpp"
-#include "../include/graph.hpp"
-#include "../include/prim.hpp"
-#include "../vendor/argparse.hpp"
+#include <raylib.h>
+#include <unistd.h>
+
#include <cstdint>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <queue>
-#include <raylib.h>
-#include <unistd.h>
#include <unordered_set>
-int main(int argc, char **argv) {
-
- srand(clock());
-
- // reverse semver
- // software does get completed at some point, and for me that's at 1.0.0.
-
- argparse::ArgumentParser program("abg", "10.0.0");
-
- program.add_argument("--vertices")
- .help("number of vertices in the graph")
- .default_value(DEFAULT_VERTEX_COUNT)
- .scan<'i', std::size_t>();
-
- program.add_argument("--sleep", "-s")
- .help("amount of time to sleep between traversals")
- .default_value(DEFAULT_SLEEP_TIME)
- .scan<'g', float>();
-
- // edges != total number of unique edges where uniqueness is defined by
- // vertices this is because we allow multiple edges between two vertices
- // (though they aren't rendered differently) we don't allow self-edges though.
-
- program.add_argument("--edges", "-e")
- .help("number of edges in the graph")
- .default_value(DEFAULT_EDGE_COUNT)
- .scan<'i', std::size_t>();
-
- try {
- program.parse_args(argc, argv);
- } catch (const std::exception &err) {
- std::cerr << err.what() << std::endl;
- std::cerr << program;
- std::exit(1);
- }
+#include "../include/background.hpp"
+#include "../include/constants.hpp"
+#include "../include/graph.hpp"
+#include "../include/prim.hpp"
+#include "../vendor/argparse.hpp"
- std::size_t vertexCount = program.get<std::size_t>("--vertices");
- std::size_t edgeCount = program.get<std::size_t>("--edges");
- float sleepTime = program.get<float>("--sleep");
+int main(int argc, char** argv) {
+ srand(clock());
- SetTraceLogLevel(LOG_ERROR);
+ // reverse semver
+ // software does get completed at some point, and for me that's at 1.0.0.
- auto ss = getScreenSize();
+ argparse::ArgumentParser program("abg", "10.0.0");
- uint32_t xMax = ss[0];
- uint32_t yMax = ss[1];
+ program.add_argument("--vertices")
+ .help("number of vertices in the graph")
+ .default_value(DEFAULT_VERTEX_COUNT)
+ .scan<'i', std::size_t>();
- // would be nice to do this all in background.cpp, but raylib and x11 can't
- // both be imported by the same file because of some dependency chain thing
- // with Font.
+ program.add_argument("--sleep", "-s")
+ .help("amount of time to sleep between traversals")
+ .default_value(DEFAULT_SLEEP_TIME)
+ .scan<'g', float>();
- InitWindow(xMax, yMax, "abg");
- sendToBg("abg");
+ // edges != total number of unique edges where uniqueness is defined by
+ // vertices this is because we allow multiple edges between two vertices
+ // (though they aren't rendered differently) we don't allow self-edges
+ // though.
- while (!WindowShouldClose()) {
+ program.add_argument("--edges", "-e")
+ .help("number of edges in the graph")
+ .default_value(DEFAULT_EDGE_COUNT)
+ .scan<'i', std::size_t>();
- Graph g = Graph(edgeCount, vertexCount, xMax, yMax);
- std::unordered_set<std::size_t> visitedIndices{};
- std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> toVisit{};
- std::vector<Edge> edges = g.getEdgesOfVertexIdx(0);
- for (auto edge : edges) {
- toVisit.push(edge);
+ try {
+ program.parse_args(argc, argv);
+ } catch (const std::exception& err) {
+ std::cerr << err.what() << std::endl;
+ std::cerr << program;
+ std::exit(1);
}
- g.traverseVertexIdx(0);
- visitedIndices.insert(0);
-
- while (!WindowShouldClose() && toVisit.size() != 0) {
- BeginDrawing();
- ClearBackground(BLACK);
- g.render();
- EndDrawing();
- usleep((int)(sleepTime * 1000000));
- oneStepPrim(toVisit, visitedIndices, g);
+
+ std::size_t vertexCount = program.get<std::size_t>("--vertices");
+ std::size_t edgeCount = program.get<std::size_t>("--edges");
+ float sleepTime = program.get<float>("--sleep");
+
+ SetTraceLogLevel(LOG_ERROR);
+
+ auto ss = getScreenSize();
+
+ uint32_t xMax = ss[0];
+ uint32_t yMax = ss[1];
+
+ // would be nice to do this all in background.cpp, but raylib and x11 can't
+ // both be imported by the same file because of some dependency chain thing
+ // with Font.
+
+ InitWindow(xMax, yMax, "abg");
+ sendToBg("abg");
+
+ while (!WindowShouldClose()) {
+ Graph g = Graph(edgeCount, vertexCount, xMax, yMax);
+ std::unordered_set<std::size_t> visitedIndices{};
+ std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>>
+ toVisit{};
+ std::vector<Edge> edges = g.getEdgesOfVertexIdx(0);
+ for (auto edge : edges) {
+ toVisit.push(edge);
+ }
+ g.traverseVertexIdx(0);
+ visitedIndices.insert(0);
+
+ while (!WindowShouldClose() && toVisit.size() != 0) {
+ BeginDrawing();
+ ClearBackground(BLACK);
+ g.render();
+ EndDrawing();
+ usleep((int)(sleepTime * 1000000));
+ oneStepPrim(toVisit, visitedIndices, g);
+ }
}
- }
}
diff --git a/src/prim.cpp b/src/prim.cpp
@@ -1,52 +1,55 @@
#include "../include/prim.hpp"
-#include "../include/graph.hpp"
-#include <cstdlib>
-#include <queue>
+
#include <raylib.h>
#include <unistd.h>
+
+#include <cstdlib>
+#include <queue>
#include <unordered_set>
+#include "../include/graph.hpp"
+
void explore(
std::size_t cIdx,
- std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> &toVisit,
- Edge ¤t, Graph &g, std::unordered_set<std::size_t> &visitedIndices) {
+ std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>>& toVisit,
+ Edge& current, Graph& g, std::unordered_set<std::size_t>& visitedIndices) {
+ visitedIndices.insert(cIdx);
+ g.traverseVertexIdx(cIdx);
- visitedIndices.insert(cIdx);
- g.traverseVertexIdx(cIdx);
+ g.setEdgeTraversed(current);
- g.setEdgeTraversed(current);
-
- std::vector<Edge> edges = g.getEdgesOfVertexIdx(cIdx);
- for (auto edge : edges) {
- toVisit.push(edge);
- }
+ std::vector<Edge> edges = g.getEdgesOfVertexIdx(cIdx);
+ for (auto edge : edges) {
+ toVisit.push(edge);
+ }
}
void oneStepPrim(
- std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> &toVisit,
- std::unordered_set<std::size_t> &visitedIndices, Graph &g) {
- bool found = false;
- if (toVisit.size() == 0) {
- return;
- }
- while (found == false) {
+ std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>>& toVisit,
+ std::unordered_set<std::size_t>& visitedIndices, Graph& g) {
+ bool found = false;
if (toVisit.size() == 0) {
- return;
+ return;
}
-
- found = true;
- auto current = toVisit.top();
- toVisit.pop();
-
- if (visitedIndices.find(current.v2Index) == visitedIndices.end()) {
- auto cIdx = current.v2Index;
- explore(cIdx, toVisit, current, g, visitedIndices);
-
- } else if (visitedIndices.find(current.v1Index) == visitedIndices.end()) {
- auto cIdx = current.v1Index;
- explore(cIdx, toVisit, current, g, visitedIndices);
- } else {
- found = false;
+ while (found == false) {
+ if (toVisit.size() == 0) {
+ return;
+ }
+
+ found = true;
+ auto current = toVisit.top();
+ toVisit.pop();
+
+ if (visitedIndices.find(current.v2Index) == visitedIndices.end()) {
+ auto cIdx = current.v2Index;
+ explore(cIdx, toVisit, current, g, visitedIndices);
+
+ } else if (visitedIndices.find(current.v1Index) ==
+ visitedIndices.end()) {
+ auto cIdx = current.v1Index;
+ explore(cIdx, toVisit, current, g, visitedIndices);
+ } else {
+ found = false;
+ }
}
- }
}
diff --git a/src/utils.cpp b/src/utils.cpp
@@ -1,4 +1,5 @@
#include "../include/utils.hpp"
+
#include <cassert>
#include <cstdint>
#include <cstdlib>
@@ -7,16 +8,16 @@ float square(float x) { return x * x; }
// call srand before invocation as this is a pure function.
Vector2 randomPosition(uint32_t xMax, uint32_t yMax) {
- uint32_t r1 = rand() % xMax;
- uint32_t r2 = rand() % yMax;
- Vector2 v{(float)r1, (float)r2};
- return v;
+ uint32_t r1 = rand() % xMax;
+ uint32_t r2 = rand() % yMax;
+ Vector2 v{(float)r1, (float)r2};
+ return v;
}
float distanceSquared(Vector2 v1, Vector2 v2) {
- float xSquare = square(v1.x - v2.x);
- float ySquare = square(v1.y - v2.y);
- float result = xSquare + ySquare;
- assert(result >= 0);
- return result;
+ float xSquare = square(v1.x - v2.x);
+ float ySquare = square(v1.y - v2.y);
+ float result = xSquare + ySquare;
+ assert(result >= 0);
+ return result;
}
diff --git a/src/vertex.cpp b/src/vertex.cpp
@@ -1,21 +1,23 @@
#include "../include/vertex.hpp"
+
#include <raylib.h>
+
#include <string>
Vertex::Vertex(Vector2 position, float drawSize)
: position(position), drawSize(drawSize) {}
std::string Vertex::toString() {
- std::string result = "(x: " + std::to_string(this->position.x) +
- ", y: " + std::to_string(this->position.y) +
- ", visited: " + std::to_string(this->visited) + ")";
- return result;
+ std::string result = "(x: " + std::to_string(this->position.x) +
+ ", y: " + std::to_string(this->position.y) +
+ ", visited: " + std::to_string(this->visited) + ")";
+ return result;
}
void Vertex::render() {
- if (visited) {
- DrawCircle(position.x, position.y, drawSize, WHITE);
- } else {
- DrawCircle(position.x, position.y, drawSize, DARKGRAY);
- }
+ if (visited) {
+ DrawCircle(position.x, position.y, drawSize, WHITE);
+ } else {
+ DrawCircle(position.x, position.y, drawSize, DARKGRAY);
+ }
}
diff --git a/tests/algo_test.cpp b/tests/algo_test.cpp
@@ -1,205 +1,204 @@
-#include "../include/prim.hpp"
-
#include <catch2/catch_test_macros.hpp>
#include <cstddef>
-TEST_CASE("Small Prim algorithm", "[small prim algo]") {
- std::size_t edgeCount = 1;
- std::size_t vertCount = 2;
-
- float xMax = 5120;
- float yMax = 1440;
-
- Graph g = Graph(edgeCount, vertCount, xMax, yMax);
- std::unordered_set<std::size_t> visitedIndices{};
- std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> toVisit{};
- std::vector<Edge> edges = g.getEdgesOfVertexIdx(0);
-
- for (auto edge : edges) {
- toVisit.push(edge);
- }
-
- g.traverseVertexIdx(0);
- visitedIndices.insert(0);
-
- while (toVisit.size() != 0) {
- oneStepPrim(toVisit, visitedIndices, g);
- }
- // this will be true bc 2 vertices 1 edge...
- // our graph may have multi-edges.
- REQUIRE(visitedIndices.size() == 2);
-}
+#include "../include/prim.hpp"
-bool isConnected(Graph g) {
+TEST_CASE("Small Prim algorithm", "[small prim algo]") {
+ std::size_t edgeCount = 1;
+ std::size_t vertCount = 2;
- std::unordered_set<std::size_t> verticesFound{0};
+ float xMax = 5120;
+ float yMax = 1440;
- std::vector<std::size_t> current{};
+ Graph g = Graph(edgeCount, vertCount, xMax, yMax);
+ std::unordered_set<std::size_t> visitedIndices{};
+ std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> toVisit{};
+ std::vector<Edge> edges = g.getEdgesOfVertexIdx(0);
- while (true) {
- for (auto key : verticesFound) {
- auto edges = g.getEdgesOfVertexIdx(key);
- for (auto edge : edges) {
- current.push_back(edge.v1Index);
- current.push_back(edge.v2Index);
- }
- }
- std::size_t len = verticesFound.size();
- for (auto idx : current) {
- verticesFound.insert(idx);
- }
- if (len == verticesFound.size()) {
- break;
+ for (auto edge : edges) {
+ toVisit.push(edge);
}
- }
-
- return verticesFound.size() == g.getVertexCount();
-}
-
-TEST_CASE("Large Prim algorithm", "[Large prim algo]") {
- std::size_t edgeCount = 3000;
- std::size_t vertCount = 1000;
-
- float xMax = 5120;
- float yMax = 1440;
-
- Graph g = Graph(edgeCount, vertCount, xMax, yMax);
- std::unordered_set<std::size_t> visitedIndices{};
- std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> toVisit{};
- do {
- g = Graph(edgeCount, vertCount, xMax, yMax);
- } while (!isConnected(g));
-
- g.traverseVertexIdx(0);
- visitedIndices.insert(0);
-
- std::vector<Edge> edges = g.getEdgesOfVertexIdx(0);
-
- for (auto edge : edges) {
- toVisit.push(edge);
- }
-
- while (toVisit.size() != 0) {
- oneStepPrim(toVisit, visitedIndices, g);
- }
+ g.traverseVertexIdx(0);
+ visitedIndices.insert(0);
- REQUIRE(visitedIndices.size() == vertCount);
+ while (toVisit.size() != 0) {
+ oneStepPrim(toVisit, visitedIndices, g);
+ }
+ // this will be true bc 2 vertices 1 edge...
+ // our graph may have multi-edges.
+ REQUIRE(visitedIndices.size() == 2);
}
-TEST_CASE("Medium Prim algorithm", "[Medium prim algo]") {
- std::size_t edgeCount = 70;
- std::size_t vertCount = 51;
-
- float xMax = 5120;
- float yMax = 1440;
-
- Graph g = Graph(edgeCount, vertCount, xMax, yMax);
- std::unordered_set<std::size_t> visitedIndices{};
- std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> toVisit{};
-
- do {
- g = Graph(edgeCount, vertCount, xMax, yMax);
- } while (!isConnected(g));
-
- g.traverseVertexIdx(0);
- visitedIndices.insert(0);
-
- std::vector<Edge> edges = g.getEdgesOfVertexIdx(0);
+bool isConnected(Graph g) {
+ std::unordered_set<std::size_t> verticesFound{0};
- for (auto edge : edges) {
- toVisit.push(edge);
- }
+ std::vector<std::size_t> current{};
- while (toVisit.size() != 0) {
- oneStepPrim(toVisit, visitedIndices, g);
- }
+ while (true) {
+ for (auto key : verticesFound) {
+ auto edges = g.getEdgesOfVertexIdx(key);
+ for (auto edge : edges) {
+ current.push_back(edge.v1Index);
+ current.push_back(edge.v2Index);
+ }
+ }
+ std::size_t len = verticesFound.size();
+ for (auto idx : current) {
+ verticesFound.insert(idx);
+ }
+ if (len == verticesFound.size()) {
+ break;
+ }
+ }
- REQUIRE(visitedIndices.size() == vertCount);
+ return verticesFound.size() == g.getVertexCount();
}
-TEST_CASE("Staircase Prim algorithm", "[Staircase prim algo]") {
- for (int i = 2; i < 30; ++i) {
- for (int x = i - 1; x < 60; ++x) {
- std::size_t edgeCount = x;
- std::size_t vertCount = i;
+TEST_CASE("Large Prim algorithm", "[Large prim algo]") {
+ std::size_t edgeCount = 3000;
+ std::size_t vertCount = 1000;
- float xMax = 5120;
- float yMax = 1440;
+ float xMax = 5120;
+ float yMax = 1440;
- Graph g = Graph(edgeCount, vertCount, xMax, yMax);
- std::unordered_set<std::size_t> visitedIndices{};
- std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>>
- toVisit{};
+ Graph g = Graph(edgeCount, vertCount, xMax, yMax);
+ std::unordered_set<std::size_t> visitedIndices{};
+ std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> toVisit{};
- do {
+ do {
g = Graph(edgeCount, vertCount, xMax, yMax);
- } while (!isConnected(g));
+ } while (!isConnected(g));
+
+ g.traverseVertexIdx(0);
+ visitedIndices.insert(0);
- std::vector<Edge> edges = g.getEdgesOfVertexIdx(0);
- for (auto edge : edges) {
+ std::vector<Edge> edges = g.getEdgesOfVertexIdx(0);
+
+ for (auto edge : edges) {
toVisit.push(edge);
- }
- g.traverseVertexIdx(0);
- visitedIndices.insert(0);
+ }
- while (toVisit.size() != 0) {
+ while (toVisit.size() != 0) {
oneStepPrim(toVisit, visitedIndices, g);
- }
-
- REQUIRE(visitedIndices.size() == vertCount);
}
- }
+
+ REQUIRE(visitedIndices.size() == vertCount);
}
-TEST_CASE("Small Prim Test", "[Small full validation]") {
- for (int i = 0; i < 100; ++i) {
- std::size_t edgeCount = 10;
- std::size_t vertCount = 5;
+TEST_CASE("Medium Prim algorithm", "[Medium prim algo]") {
+ std::size_t edgeCount = 70;
+ std::size_t vertCount = 51;
float xMax = 5120;
float yMax = 1440;
Graph g = Graph(edgeCount, vertCount, xMax, yMax);
- do {
- g = Graph(edgeCount, vertCount, xMax, yMax);
- } while (!isConnected(g));
-
std::unordered_set<std::size_t> visitedIndices{};
std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> toVisit{};
- for (auto edge : g.getEdgesOfVertexIdx(0))
- toVisit.push(edge);
+ do {
+ g = Graph(edgeCount, vertCount, xMax, yMax);
+ } while (!isConnected(g));
+
g.traverseVertexIdx(0);
visitedIndices.insert(0);
- std::unordered_set<std::size_t> vBefore = visitedIndices;
+ std::vector<Edge> edges = g.getEdgesOfVertexIdx(0);
- bool havePrior = false;
- Edge prior = toVisit.top();
- std::unordered_set<std::size_t> visibleAtPrior;
+ for (auto edge : edges) {
+ toVisit.push(edge);
+ }
while (toVisit.size() != 0) {
- auto current = toVisit.top();
- if (havePrior) {
- bool wasPresent = visibleAtPrior.count(current.v1Index) > 0 ||
- visibleAtPrior.count(current.v2Index) > 0;
- // anytime we use the same source node two steps in a row, the second
- // weight must be smaller.
- if (wasPresent) {
- REQUIRE(current.length2 >= prior.length2);
- }
- }
-
- prior = current;
- visibleAtPrior = visitedIndices;
- havePrior = true;
- oneStepPrim(toVisit, visitedIndices, g);
- bool valid = vBefore.size() + 1 == visitedIndices.size() ||
- vBefore.size() == vertCount;
- REQUIRE(valid);
- vBefore = visitedIndices;
+ oneStepPrim(toVisit, visitedIndices, g);
}
+
REQUIRE(visitedIndices.size() == vertCount);
- }
+}
+
+TEST_CASE("Staircase Prim algorithm", "[Staircase prim algo]") {
+ for (int i = 2; i < 30; ++i) {
+ for (int x = i - 1; x < 60; ++x) {
+ std::size_t edgeCount = x;
+ std::size_t vertCount = i;
+
+ float xMax = 5120;
+ float yMax = 1440;
+
+ Graph g = Graph(edgeCount, vertCount, xMax, yMax);
+ std::unordered_set<std::size_t> visitedIndices{};
+ std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>>
+ toVisit{};
+
+ do {
+ g = Graph(edgeCount, vertCount, xMax, yMax);
+ } while (!isConnected(g));
+
+ std::vector<Edge> edges = g.getEdgesOfVertexIdx(0);
+ for (auto edge : edges) {
+ toVisit.push(edge);
+ }
+ g.traverseVertexIdx(0);
+ visitedIndices.insert(0);
+
+ while (toVisit.size() != 0) {
+ oneStepPrim(toVisit, visitedIndices, g);
+ }
+
+ REQUIRE(visitedIndices.size() == vertCount);
+ }
+ }
+}
+
+TEST_CASE("Small Prim Test", "[Small full validation]") {
+ for (int i = 0; i < 100; ++i) {
+ std::size_t edgeCount = 10;
+ std::size_t vertCount = 5;
+
+ float xMax = 5120;
+ float yMax = 1440;
+
+ Graph g = Graph(edgeCount, vertCount, xMax, yMax);
+ do {
+ g = Graph(edgeCount, vertCount, xMax, yMax);
+ } while (!isConnected(g));
+
+ std::unordered_set<std::size_t> visitedIndices{};
+ std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>>
+ toVisit{};
+
+ for (auto edge : g.getEdgesOfVertexIdx(0)) toVisit.push(edge);
+ g.traverseVertexIdx(0);
+ visitedIndices.insert(0);
+
+ std::unordered_set<std::size_t> vBefore = visitedIndices;
+
+ bool havePrior = false;
+ Edge prior = toVisit.top();
+ std::unordered_set<std::size_t> visibleAtPrior;
+
+ while (toVisit.size() != 0) {
+ auto current = toVisit.top();
+ if (havePrior) {
+ bool wasPresent = visibleAtPrior.count(current.v1Index) > 0 ||
+ visibleAtPrior.count(current.v2Index) > 0;
+ // anytime we use the same source node two steps in a row, the
+ // second weight must be smaller.
+ if (wasPresent) {
+ REQUIRE(current.length2 >= prior.length2);
+ }
+ }
+
+ prior = current;
+ visibleAtPrior = visitedIndices;
+ havePrior = true;
+ oneStepPrim(toVisit, visitedIndices, g);
+ bool valid = vBefore.size() + 1 == visitedIndices.size() ||
+ vBefore.size() == vertCount;
+ REQUIRE(valid);
+ vBefore = visitedIndices;
+ }
+ REQUIRE(visitedIndices.size() == vertCount);
+ }
}
diff --git a/tests/graph_test.cpp b/tests/graph_test.cpp
@@ -5,119 +5,117 @@
#include <unordered_set>
TEST_CASE("Graph traversal invariants", "[graph traversal]") {
- int vertCount = 10;
- int edgeCount = 10;
- float xMax = 10;
- float yMax = 10;
- auto g = Graph(edgeCount, vertCount, xMax, yMax);
- for (int i = 0; i < vertCount; ++i) {
- g.traverseVertexIdx(i);
- }
- for (int i = 0; i < vertCount; ++i) {
- REQUIRE(g.getVertex(i).visited);
- }
-
- bool error = false;
-
- try {
- g.getVertex(vertCount + 1);
- } catch (std::invalid_argument& e) {
- error = true;
- }
-
- REQUIRE(error);
+ int vertCount = 10;
+ int edgeCount = 10;
+ float xMax = 10;
+ float yMax = 10;
+ auto g = Graph(edgeCount, vertCount, xMax, yMax);
+ for (int i = 0; i < vertCount; ++i) {
+ g.traverseVertexIdx(i);
+ }
+ for (int i = 0; i < vertCount; ++i) {
+ REQUIRE(g.getVertex(i).visited);
+ }
+
+ bool error = false;
+
+ try {
+ g.getVertex(vertCount + 1);
+ } catch (std::invalid_argument& e) {
+ error = true;
+ }
+
+ REQUIRE(error);
}
void createGraph(int vertCount, int edgeCount) {
- auto g = Graph(edgeCount, vertCount, 10, 10);
+ auto g = Graph(edgeCount, vertCount, 10, 10);
}
TEST_CASE("Graph gracefully handles stupid fucking inputs",
"[graph bad inputs]") {
- int vertCount = 0;
- int edgeCount = 0; // some trivial and stupid graph
+ int vertCount = 0;
+ int edgeCount = 0; // some trivial and stupid graph
- bool error = false;
+ bool error = false;
- try {
- createGraph(vertCount, edgeCount);
- } catch (std::invalid_argument& e) {
- error = true;
- }
- REQUIRE(!error);
+ try {
+ createGraph(vertCount, edgeCount);
+ } catch (std::invalid_argument& e) {
+ error = true;
+ }
+ REQUIRE(!error);
- vertCount = 0;
- edgeCount = 1; // bad
+ vertCount = 0;
+ edgeCount = 1; // bad
- error = false;
- try {
- createGraph(vertCount, edgeCount);
- } catch (std::invalid_argument& e) {
- error = true;
- }
+ error = false;
+ try {
+ createGraph(vertCount, edgeCount);
+ } catch (std::invalid_argument& e) {
+ error = true;
+ }
- REQUIRE(error);
+ REQUIRE(error);
}
TEST_CASE("Graph respects max x and max y values", "[graph max values]") {
- int vertCount = 10;
- int edgeCount = 10;
-
- for (int z = 2; z < 100; ++z) {
-
- float xMax = 0;
- float yMax = 0;
-
- while (xMax == 0 || yMax == 0) {
- xMax = rand() % z;
- yMax = rand() % z;
+ int vertCount = 10;
+ int edgeCount = 10;
+
+ for (int z = 2; z < 100; ++z) {
+ float xMax = 0;
+ float yMax = 0;
+
+ while (xMax == 0 || yMax == 0) {
+ xMax = rand() % z;
+ yMax = rand() % z;
+ }
+
+ auto g = Graph(edgeCount, vertCount, xMax, yMax);
+
+ for (int i = 0; i < vertCount; ++i) {
+ REQUIRE(g.getVertex(i).position.x <= xMax);
+ }
+ for (int i = 0; i < vertCount; ++i) {
+ REQUIRE(g.getVertex(i).position.y <= yMax);
+ }
}
-
- auto g = Graph(edgeCount, vertCount, xMax, yMax);
+ auto g = Graph(edgeCount, vertCount, UINT32_MAX, UINT32_MAX);
for (int i = 0; i < vertCount; ++i) {
- REQUIRE(g.getVertex(i).position.x <= xMax);
+ REQUIRE(g.getVertex(i).position.x <= UINT32_MAX);
}
for (int i = 0; i < vertCount; ++i) {
- REQUIRE(g.getVertex(i).position.y <= yMax);
+ REQUIRE(g.getVertex(i).position.y <= UINT32_MAX);
}
- }
- auto g = Graph(edgeCount, vertCount, UINT32_MAX, UINT32_MAX);
-
- for (int i = 0; i < vertCount; ++i) {
- REQUIRE(g.getVertex(i).position.x <= UINT32_MAX);
- }
- for (int i = 0; i < vertCount; ++i) {
- REQUIRE(g.getVertex(i).position.y <= UINT32_MAX);
- }
}
std::size_t countEdges(Graph g) {
- std::size_t vertexCount = g.getVertexCount();
- std::unordered_set<std::size_t> unique{};
-
- for (std::size_t i = 0; i < vertexCount; ++i) {
- auto edges = g.getEdgesOfVertexIdx(i);
- for (auto edge : edges) {
- unique.insert(edge.identifier);
+ std::size_t vertexCount = g.getVertexCount();
+ std::unordered_set<std::size_t> unique{};
+
+ for (std::size_t i = 0; i < vertexCount; ++i) {
+ auto edges = g.getEdgesOfVertexIdx(i);
+ for (auto edge : edges) {
+ unique.insert(edge.identifier);
+ }
}
- }
- return unique.size();
+ return unique.size();
}
TEST_CASE("Graph vertex and edge counts", "[graph counts]") {
-
- for (int i = 2; i < 100; ++i) {
- for (int x = 1; x < 10; ++x) {
- std::size_t vertCount = i;
- std::size_t edgeCount = x;
- float xMax = 10;
- float yMax = 10;
-
- auto g = Graph(edgeCount, vertCount, xMax, yMax);
-
- REQUIRE(g.getVertexCount() == vertCount);
- REQUIRE(countEdges(g) == edgeCount);
+ for (int i = 2; i < 100; ++i) {
+ for (int x = 1; x < 10; ++x) {
+ std::size_t vertCount = i;
+ std::size_t edgeCount = x;
+ float xMax = 10;
+ float yMax = 10;
+
+ auto g = Graph(edgeCount, vertCount, xMax, yMax);
+
+ REQUIRE(g.getVertexCount() == vertCount);
+ REQUIRE(countEdges(g) == edgeCount);
+ }
}
- }
}
diff --git a/tests/snapshot_shared.cpp b/tests/snapshot_shared.cpp
@@ -1,69 +1,70 @@
-#include "../include/graph.hpp"
-#include "../include/prim.hpp"
#include <catch2/catch_test_macros.hpp>
#include <queue>
#include <unordered_set>
+#include "../include/graph.hpp"
+#include "../include/prim.hpp"
+
Graph basicGraphSerialization() {
- srand(42);
- int vertCount = 10;
- int edgeCount = 10;
- float xMax = 10;
- float yMax = 10;
- auto g = Graph(edgeCount, vertCount, xMax, yMax);
- return g;
+ srand(42);
+ int vertCount = 10;
+ int edgeCount = 10;
+ float xMax = 10;
+ float yMax = 10;
+ auto g = Graph(edgeCount, vertCount, xMax, yMax);
+ return g;
}
Graph fullTraversalSerialization() {
- srand(42);
- std::size_t edgeCount = 1;
- std::size_t vertCount = 2;
+ srand(42);
+ std::size_t edgeCount = 1;
+ std::size_t vertCount = 2;
- float xMax = 5120;
- float yMax = 1440;
+ float xMax = 5120;
+ float yMax = 1440;
- Graph g = Graph(edgeCount, vertCount, xMax, yMax);
- std::unordered_set<std::size_t> visitedIndices{};
- std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> toVisit{};
- std::vector<Edge> edges = g.getEdgesOfVertexIdx(0);
+ Graph g = Graph(edgeCount, vertCount, xMax, yMax);
+ std::unordered_set<std::size_t> visitedIndices{};
+ std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> toVisit{};
+ std::vector<Edge> edges = g.getEdgesOfVertexIdx(0);
- for (auto edge : edges) {
- toVisit.push(edge);
- }
+ for (auto edge : edges) {
+ toVisit.push(edge);
+ }
- g.traverseVertexIdx(0);
- visitedIndices.insert(0);
+ g.traverseVertexIdx(0);
+ visitedIndices.insert(0);
- while (toVisit.size() != 0) {
- oneStepPrim(toVisit, visitedIndices, g);
- }
+ while (toVisit.size() != 0) {
+ oneStepPrim(toVisit, visitedIndices, g);
+ }
- return g;
+ return g;
}
Graph fullTraversalLargerSerialization() {
- srand(42);
- std::size_t edgeCount = 25;
- std::size_t vertCount = 15;
+ srand(42);
+ std::size_t edgeCount = 25;
+ std::size_t vertCount = 15;
- float xMax = 5120;
- float yMax = 1440;
+ float xMax = 5120;
+ float yMax = 1440;
- Graph g = Graph(edgeCount, vertCount, xMax, yMax);
- std::unordered_set<std::size_t> visitedIndices{};
- std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> toVisit{};
- std::vector<Edge> edges = g.getEdgesOfVertexIdx(0);
+ Graph g = Graph(edgeCount, vertCount, xMax, yMax);
+ std::unordered_set<std::size_t> visitedIndices{};
+ std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> toVisit{};
+ std::vector<Edge> edges = g.getEdgesOfVertexIdx(0);
- for (auto edge : edges) {
- toVisit.push(edge);
- }
+ for (auto edge : edges) {
+ toVisit.push(edge);
+ }
- g.traverseVertexIdx(0);
- visitedIndices.insert(0);
+ g.traverseVertexIdx(0);
+ visitedIndices.insert(0);
- while (toVisit.size() != 0) {
- oneStepPrim(toVisit, visitedIndices, g);
- }
+ while (toVisit.size() != 0) {
+ oneStepPrim(toVisit, visitedIndices, g);
+ }
- return g;
+ return g;
}
diff --git a/tests/snapshot_test.cpp b/tests/snapshot_test.cpp
@@ -1,31 +1,32 @@
-#include "../include/graph.hpp"
-#include "snapshot_shared.cpp"
#include <catch2/catch_test_macros.hpp>
#include <fstream>
#include <iostream>
#include <sstream>
+#include "../include/graph.hpp"
+#include "snapshot_shared.cpp"
+
std::string readFileToString(std::string filename) {
- auto in = std::ifstream("tests/snapshot/" + filename + ".out");
- std::ostringstream sstr;
- sstr << in.rdbuf();
- return sstr.str();
+ auto in = std::ifstream("tests/snapshot/" + filename + ".out");
+ std::ostringstream sstr;
+ sstr << in.rdbuf();
+ return sstr.str();
}
TEST_CASE("Basic graph serialization snapshot",
"[basic graph serialization snapshot]") {
- Graph g = basicGraphSerialization();
- REQUIRE(readFileToString("basicGraph") == g.toString());
+ Graph g = basicGraphSerialization();
+ REQUIRE(readFileToString("basicGraph") == g.toString());
}
TEST_CASE("Traversed graph serialization snapshot",
"[traversed graph serialization snapshot]") {
- Graph g = fullTraversalSerialization();
- REQUIRE(readFileToString("traversedGraph") == g.toString());
+ Graph g = fullTraversalSerialization();
+ REQUIRE(readFileToString("traversedGraph") == g.toString());
}
TEST_CASE("Traversed graph serialization snapshot larger",
"[traversed graph serialization snapshot larger]") {
- Graph g = fullTraversalLargerSerialization();
- REQUIRE(readFileToString("traversedLargerGraph") == g.toString());
+ Graph g = fullTraversalLargerSerialization();
+ REQUIRE(readFileToString("traversedLargerGraph") == g.toString());
}
diff --git a/tests/snapshot_update.cpp b/tests/snapshot_update.cpp
@@ -1,21 +1,22 @@
-#include "../include/graph.hpp"
-#include "snapshot_shared.cpp"
#include <filesystem>
#include <fstream>
+#include "../include/graph.hpp"
+#include "snapshot_shared.cpp"
+
void snapshotGraph(std::string testName, Graph g) {
- std::filesystem::path path{"tests/snapshot"};
- path /= testName + ".out";
- std::filesystem::create_directories(path.parent_path());
- std::ofstream ofs(path);
- ofs << g.toString();
+ std::filesystem::path path{"tests/snapshot"};
+ path /= testName + ".out";
+ std::filesystem::create_directories(path.parent_path());
+ std::ofstream ofs(path);
+ ofs << g.toString();
}
int main() {
- Graph g1 = basicGraphSerialization();
- snapshotGraph("basicGraph", g1);
- Graph g2 = fullTraversalSerialization();
- snapshotGraph("traversedGraph", g2);
- Graph g3 = fullTraversalLargerSerialization();
- snapshotGraph("traversedLargerGraph", g3);
+ Graph g1 = basicGraphSerialization();
+ snapshotGraph("basicGraph", g1);
+ Graph g2 = fullTraversalSerialization();
+ snapshotGraph("traversedGraph", g2);
+ Graph g3 = fullTraversalLargerSerialization();
+ snapshotGraph("traversedLargerGraph", g3);
}
