Algorithms used for identifying articulation points

Usage
1

Hi,
I am using igraph library in R. Is depth first search or breadth first algorithm is implemented in igraph to identify articulation points?
Thanks
Priya

2

Hi Priya, you can simply use the articulation.points function to get articulation points. Or is your question how this function is actually implemented?

3

Yes, I am curious to know which algorithm is implemented in the articulation.point function. Both depth first search and breadth first search can be implemented. I have to give this detail in my thesis. Thanks
Priya

4

I think it uses a DFS. The actual identification of articulation points is done during the identification of the biconnected components, which I think, simply follows the classical implementation of Hopcroft and Tarjan (perhaps @szhorvat, you know by heart?). But if you want to make sure, you can check the code itself, it is available from here:

Perhaps it would be nice to include the documentation which implementation is used to identify biconnected components.

5

Why?

Articulation points are a well-defined concept. You can explain in your thesis what they are without talking about how some particular piece of software computed them.

You can also verify igraph’s result directly. You do not need to read the code or know the details of the implementation to be able to verify that the result is correct. You simply remove a vertex and see if the graph became disconnected.

1 Like
6

Actually, I disagree. It’s irrelevant, and we want to be able to change the implementation details as we see fit.

1 Like
7

Of course we could simply change the documentation if we change the implementation. For plenty of algorithms explicit references are provided, this could also be done for biconnected components.

8

It is not only for my thesis, as a researcher I would like to be clear about the methodology part.
Thanks
Priya

9

@Priyadarshini_Thirun, you are conflating the need to describe what you did with how it was done. igraph’s implementation is not part of the methodology. Simply explain what an articulation point is (a basic graph theory concept that one can find in many textbooks), and cite igraph. Talking about igraph internals will make zero difference to the reproducibility of your work.

I do recommend that you verify that the result is correct, regardless of whether you use igraph, or other software.

10

I would rather spend that time on commenting the code better to help in maintaining it. For that purpose, understanding the implementation details is actually important.

It seems to me that unlike many algorithms for which igraph has citations, this appears to be fairly standard textbook stuff on which no more research is being done (unlike e.g. max flow).

11

Thank you @szhorvat. I agree with you, it is important to verify my results
Thanks @vtraag, dfs algorithm is implemented. I checked the code uploaded in Github

12

What is important for a thesis / paper / other works:

  • Your readers should understand what was computed.
  • Your readers should be able to reproduce the calculation, ideally without being forced to use one particular software. This is satisfied, since biconnected components are a common concept, implemented in many different libraries. Furthermore, biconnected component calculation is well understood, with textbooks that describe the basic algorithms.

If you yourself wrote the program, then you can explain the details, even if you are implementing a well-known algorithm, because it is your work and demonstrates that you spent effort on it.

If in doubt, talk to your supervisor.

13

Thank you @szhorvat. I agree with you, it is important to verify my results
Thanks @vtraag, dfs algorithm is implemented. I checked the code uploaded in Github