Project 2 for CSCE 4600
inc | ||
src | ||
.clang-format | ||
.gitignore | ||
LICENSE | ||
Makefile | ||
Project-2-input-example-1.txt | ||
README.md | ||
test1.txt |
4600-project-2
Project 2 for CSCE4600, for Team G4
We got a grade of 100% :D
Please ensure you've read and agree to abide by the license before continuing. This software's source code was made public under a restrictive license with the intent to allow comparison of Project 2 solutions with other former course-members and members of the general public. I'm not liable for any academic stupidity that may result from attempted plagiarism of this work.
You have been warned.
╔═══════════════════════════════════════════╗
║ Created 2022-04-16 Updated 2022-05-13 ║
╚═══════════════════════════════════════════╝
Build
Build with make
Run with ./main.out filename
Clean with make clean
Run
Run with `./main.out [input_f
Analysis, Benefits and Drawbacks
Analysis:
- We implemented the Graph Reduction algorithm on adjacency matrices, with some minor optimizations:
- By counting the number of remaining processes, and comparing it to the number of processes eliminated so far, we can detect when the algorithm has failed a single time, after which it'll fail forever.
Benefits:
- The graph reduction algorithm is very elegant, but also easy to optimize
- "Deleting" a node from an adjacency matrix can be performed by zeroing its respective row and column and re-running the algorithm, which is very simple!
Drawbacks:
- The adjacency matrix representation is used without interpretation, making the output somewhat hard to read
- Our implementation of knot detection didn't pan out.
Contributions:
John Breaux:
- src/graph.cpp, inc/graph.hpp (graph implementation)
- src/main.cpp
- src/read.cpp, inc/read.hpp (reading from graph)
- src/reducible.cpp (graph reduction)
- .clang-format
- Makefile (Makefile)
- Readme.md
- Hosted the git repo
Michael Laymon
- knotted.cpp