Project 2 for CSCE 4600
Go to file
2022-05-13 05:45:53 +00:00
inc Knotted should work now. I really was over-complicating it. I have commented the code and removed unused includes from the file. 2022-04-28 21:09:37 -05:00
src Finalize 2022-04-28 23:56:52 -05:00
.clang-format Configure clang-format 2022-04-23 17:55:53 -05:00
.gitignore C++-ify it some more, begin readfile 2022-04-17 22:03:17 -05:00
LICENSE Anti-MIT License 2022-05-13 05:43:54 +00:00
Makefile Update file headers and includes 2022-04-23 20:16:15 -05:00
Project-2-input-example-1.txt Knotted should work now. I really was over-complicating it. I have commented the code and removed unused includes from the file. 2022-04-28 21:09:37 -05:00
README.md Update 'README.md' 2022-05-13 05:45:53 +00:00
test1.txt Refactor for robustness and clarity 2022-04-23 04:47:55 -05:00

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