/graph-articulation-points-viz

Finding articulation points ( cut vertices ) in an undirected graph using DFS , implemented using p5js

Primary LanguageJavaScript

Graph Visualizer and Articulation Points Finder

image

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.

Resources

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

image

Project Structure

The project's folder structure is organized as follows:

  • src: This folder contains the JavaScript classes and modules for the project.

    • graph.js: Defines the Graph class to represent the graph structure.
    • edge.js: Defines the Edge class to represent edges between vertices.
    • vertex.js: Defines the Vertex 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.
image

Usage

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

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