This repository contains a collection of C++ softwares based on the implementation of an Undirected Graph Class. This allows for the usage of ODE and PDE solvers, the implementation of a Breadth-First Search (BFS) algorithm, a solver of systems of sparse matrices and more, all using this class.
- Graph Class
- Breadth-First Search (BFS) Algorithm
- Mass Spring
- Conjugate Gradient and Sparse Matrices
- Parallel Computing using OpenMP
|
The Graph class is implemented using two sub-classes for Nodes and Edges. A Graph is made of two Hash Maps (called unorderded maps in the C++ STL), which contain the different Nodes and Edges of the Graph. The Nodes are implemented using a Design Pattern called a Proxy Pattern. Instead of storing all the information of a Node in the Node class, we define a Proxy Class which points to the underlying data of the Node. This allows for much lighter data structures and better encapsulation. All three classes (Node, Edge and Graph) are thoroughly tested using GoogleTest, a testing framework for C++ code by Google.
|
|
After implementing the Graph Class, a viewer is implemented using SFML combined with OpenGL for high-performance graphics. It is able to read sets of Nodes and Egdes files that contain their respective 3D positions. Thanks to appropriate usage of C++ STL data structures, the code is able to read through 10,000 Nodes and 300,000 Egdes within less than 1 second and automatically output the result. After this, a set of random 3D coordinates are chosen. Starting from the closest Node to those coordinates, a BFS algorithm is implemented to parse through all Nodes of the Graph and compute the shortest path in terms of the number of Edges to go through to get to the original Node. Using this, each Node is coloured according to how close or far it is from the original Node.
|
|
We use the Graph class to implement a solver for Spring Mass systems. Each node has zero as initial velocity and a mass equal to 1 / N, N being the number of nodes in the graph. We have a spring constant set to 100 and a rest-length L set uniformly across all Edges of the Graph. The mass spring simulation works by solving a differential equation using an iterative approach. To solve the numerical system, we update the position based on the velocity, compute the force using the new position and finally update the velocity. We use an OOP framework to represent forces by building a parent Force class and having 3 subclasses inheriting from it for gravity, damping and mass spring.
|
|
We implement the Conjugate Gradient (CG) algorithm for solving systems of equations with symmetric matrices and represent those using the Graph class. The CG solver is implemented to work efficiently for sparse matrix-vector products. Then, we implement the boundary conditions and solve the system using the Conjugate Gradient Solver. Compared to the mass spring approach where we approximated derivatives in time, here we approximate them in space. We can approximate the Laplacian operator by a discrete Laplacian matrix, which we use to solve the system Ax = b. Finally, we visualize the convergence of the solution by plotting the x and y coordinates of each node and the scalar solution to the Poisson problem of each node using the SFML viewer.
|
|
We re-implement the Mass Spring algorithm but in a parallel manner by using OpenMP and Thrust. This allows for much faster processing as each velocity and position of the Nodes can be computed at the same time. This allows to speed up the mass spring computation by a factor of 40 on a large grid (1M Nodes and 4M Edges).
|
