![image](https://private-user-images.githubusercontent.com/77624873/298075068-5122057a-65fc-4962-97dc-590b017e429a.png?jwt=eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJpc3MiOiJnaXRodWIuY29tIiwiYXVkIjoicmF3LmdpdGh1YnVzZXJjb250ZW50LmNvbSIsImtleSI6ImtleTUiLCJleHAiOjE3MjU5OTcyNTMsIm5iZiI6MTcyNTk5Njk1MywicGF0aCI6Ii83NzYyNDg3My8yOTgwNzUwNjgtNTEyMjA1N2EtNjVmYy00OTYyLTk3ZGMtNTkwYjAxN2U0MjlhLnBuZz9YLUFtei1BbGdvcml0aG09QVdTNC1ITUFDLVNIQTI1NiZYLUFtei1DcmVkZW50aWFsPUFLSUFWQ09EWUxTQTUzUFFLNFpBJTJGMjAyNDA5MTAlMkZ1cy1lYXN0LTElMkZzMyUyRmF3czRfcmVxdWVzdCZYLUFtei1EYXRlPTIwMjQwOTEwVDE5MzU1M1omWC1BbXotRXhwaXJlcz0zMDAmWC1BbXotU2lnbmF0dXJlPTNkNDRiMjk3ZjQ0YTY0MzdjN2M3NzJhYzBjM2E2OTU3ODZhN2FlNDMyYjlkMzI4ZDA4ZTNjZGQwZWVkNjJiNTUmWC1BbXotU2lnbmVkSGVhZGVycz1ob3N0JmFjdG9yX2lkPTAma2V5X2lkPTAmcmVwb19pZD0wIn0.YZ8CYX594tHGnfHjAhGNW2n7AiloVx0QR-W74i1v4oY)
This project aims to create a graph visualizer using p5js.org and to find the articulation points (also known as cut vertices) in an undirected graph. Articulation points are the vertices in a graph whose removal increases the number of connected components in the graph. They play a crucial role in the study of graph theory and network analysis.
I used these ressources to learn about articulation points, and try to implement them :
for the implementation I was inspired by :
I'm using JavaScript
which is not the best option when it comes to error handling and type sentetive compared to Typescript
, It would be better to use Typescript
The project's folder structure is organized as follows:
-
src: This folder contains the JavaScript classes and modules for the project.
graph.js
: Defines theGraph
class to represent the graph structure.edge.js
: Defines theEdge
class to represent edges between vertices.vertex.js
: Defines theVertex
class to represent vertices in the graph.controls.js
: Provides button controls to add vertices, add edges, delete vertices, and find articulation points.logic.js
: Contains logic for finding articulation points using depth-first search (DFS).
-
root: This is the main directory where the core logic and sketch are implemented.
sketch.js
: Utilizes p5.js to draw the canvas and handle user events for the graph visualization.- Other files may include HTML and CSS if used for rendering the user interface.
To use the application, open the index.html
file or run a local server to visualize and interact with the graph. The application provides controls for adding vertices, adding edges, deleting vertices, and finding articulation points.
Please note that this project is currently a work in progress, and some features may not be fully functional or accurate. Contributions and improvements are welcome.
Articulation points, also known as cut vertices, are vertices in an undirected graph whose removal increases the number of connected components in the graph. They have a significant impact on graph connectivity and are essential in various graph-related applications.
![image](https://private-user-images.githubusercontent.com/77624873/298075253-eb00d2f8-5d3b-4309-892a-175863deb09b.png?jwt=eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJpc3MiOiJnaXRodWIuY29tIiwiYXVkIjoicmF3LmdpdGh1YnVzZXJjb250ZW50LmNvbSIsImtleSI6ImtleTUiLCJleHAiOjE3MjU5OTcyNTMsIm5iZiI6MTcyNTk5Njk1MywicGF0aCI6Ii83NzYyNDg3My8yOTgwNzUyNTMtZWIwMGQyZjgtNWQzYi00MzA5LTg5MmEtMTc1ODYzZGViMDliLnBuZz9YLUFtei1BbGdvcml0aG09QVdTNC1ITUFDLVNIQTI1NiZYLUFtei1DcmVkZW50aWFsPUFLSUFWQ09EWUxTQTUzUFFLNFpBJTJGMjAyNDA5MTAlMkZ1cy1lYXN0LTElMkZzMyUyRmF3czRfcmVxdWVzdCZYLUFtei1EYXRlPTIwMjQwOTEwVDE5MzU1M1omWC1BbXotRXhwaXJlcz0zMDAmWC1BbXotU2lnbmF0dXJlPWExMWVkNWQzZmE4Mjg0OTNmZjg2MGMxYTMzNDdkZjVkNDJkOWUxMjA1MGQyY2E2MzJiZWU5MjljNTY5NjQ1YjgmWC1BbXotU2lnbmVkSGVhZGVycz1ob3N0JmFjdG9yX2lkPTAma2V5X2lkPTAmcmVwb19pZD0wIn0.boJ935vCzQtGRKYcIqgMXsFO2yvnYleHX5ehwbe-7h0)