[FEATURE REQUEST] Articulation Point and Bridge for graphs.

[Prabhat-Kumar-42]

What would you like to Propose?

Adding Code for finding Articulation Points and Bridges.

Problem Statement :

Given an adjacency list of a graph with vertices = v, having 0 based indexing. Find all Articulation Points and Articulation Bridge Present in Graph.

Applications :

1. Network Flow
2. Used in map/city-path related computer programs

Issue details

Articulation Point : vertex whcih when removed increases the number of connected component in graph.

Articulation Bridge : edge which when removed increases the number of connected component in graph.

eg : Given graph with vertices = 5 and adj list is : vertex -> neighbours (Assuming all edges are bidirectional) 0 -> 1, 2 1 -> 2 2 -> 3 3 -> 4

   Graph is :

             0-------1
             |      /
             |     /
             |    /
             |   /
             |  /       4
             | /        |
             |/         |
             2----------3

  current connected component = 1

-> Articulation Points : 2 , 3 Explanation :

          -> When removing 2, graph changes to below and connected components increases
             from 1 to 2.

             0-------1
             |      /
             |     /
             |    /
             |   /
             |  /       4  
             | /        |
             |/         |
                        3


           -> When removing 3, graph changes to below and connected components increases
             from 1 to 2.

             0-------1
             |      /
             |     /
             |    /
             |   /
             |  /       4
             | /
             |/
             2

-> Articulation Bridges: edge : 2-3, edge: 3-4 Explanation :

          -> When removing edge : 2-3, graph changes to below and connected components increases
             from 1 to 2.

             0-------1
             |      /
             |     /
             |    /
             |   /
             |  /       4
             | /        |
             |/         |
             2          3


           -> When removing edge : 3-4, graph changes to below and connected components increases
             from 1 to 2.

             0-------1
             |      /
             |     /
             |    /
             |   /
             |  /       4
             | /
             |/
             2----------3

Additional Information

No response

[Prabhat-Kumar-42]

I had already submitted a PR for this. I am new to open-source. I read in contribution.md about opening a new issue for a new feature but, I was unsure if submitting a PR directly for a new feature is allowed. So I created an Issue just in case.

Thank you.

[sahill-chand]

@Prabhat-Kumar-42 Please assign me this issue.I will complete this project in one day by using comments, appropriate variable names and in most efficient way.Greatly looking ahead to work with you.

[Prabhat-Kumar-42]

@Prabhat-Kumar-42 Please assign me this issue.I will complete this project in one day by using comments, appropriate variable names and in most efficient way.Greatly looking ahead to work with you.

@PRONOBITA I am not the maintainer so, I can't assign any issues. I am also new to open-source. Regarding this issue, I got my PR related to this verified and I am now waiting to hear from the maintainer(s).

[github-actions[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

[github-actions[bot]]

Please reopen this issue once you have made the required changes. If you need help, feel free to ask in our Discord server or ping one of the maintainers here. Thank you for your contribution!