Graph ADT and shortest path algorithms + Polynomials ADT and CRC algorithm. Project that I created while taking course on Computer networks on faculty. I wanted to make an useful abstraction of graphs and polynomials so that algorithm implementations would be lightweight (e.g. I don't think that CRC algorithm should know how polynomial division is done. It should only ask for division and Polynomial ADT should take care of the rest.)
It can be devided into two parts:
- Graphs and shortest path algorithms
- Polynomials and CRC algorithm
NOTE: Do you like it? Show it by giving a ⭐️. 🚀
It comprises of following data structures:
| 🔎 | Data structure | Description |
|---|---|---|
| <> | Distance | Simple struct that represents tuple (vertex A, vertex B, edge weight) |
| <> | Edge | Makes comparing edges and summing edge weights easier. It also makes having edges with infinit or no weight easier. |
| <> | Graph | Represents graph that can be directed or undirected. |
| <> | GraphBuilder | Class inspired by StringBuilder provides handy way to build Graph (which are immutable). |
| <> | GraphWithTracking | Wraps around Graph and provides a lists to keep track of calculated distances between vertices and to keep track which vertices are visited. |
Algorithm implementations:
| 🔎 | Algorithm |
|---|---|
| <> | Dijkstra |
| <> | BellmanFord |
It comprises of following data structures:
| 🔎 | Data structure | Description |
|---|---|---|
| <> | DecimalMonomial | This class represents one part of the Polynomial. This is not an mathematical but artificial structure which is essential building block of Polynomials. In this polynomial 4x^3 + 2x - 1 monomials are [4x^3, 2x, -1]. |
| <> | DecimalPolynomial | Represents decimal polynomial internaly build out of DecimalMonomials. It makes addition, multiplication, comparison, ... among decimal polynomials easy. |
| <> | BinaryPolynomial | Represents binary polynomial internaly using one uint to hold polynomial. It makes addition, division, comparison, ... among binary polynomials easy. |
Algorithm implementations:
| 🔎 | Algorithm |
|---|---|
| <> | CrcAlgorithm |