Biconnected components(emi-h.com)
emi-h.com
Biconnected components
https://emi-h.com/articles/bcc.html
21 comments
The Boost algorithm computes the vertex-biconnected components rather than the edge-biconnected components, which are two different but related concepts. Articulation points are also more related to vertex-biconnectedness than to edge-biconnectedness (articulation points are vertices that lie in multiple vertex-biconnected components, i.e., if you remove one you split up the graph into more components). From what I can see in the Boost docs, it doesn't have an implementation of edge-biconnected components.
You can write an algorithm to compute all of the articulation points & bridges & edge-biconnected components & vertex-biconnected components in a single DFS. Because of this you refer to all of them as just "Tarjan's algorithm" even if you just compute one of them (he is kind of the Euler of graph algorithms in that like half of graph algorithms is named after him). So, on a technical level, I guess my implementation is similar to the algorithm in Boost because they both use DFS and this `low` map, but they compute different things.
Finding the vertex-biconnected components next to the articulation points involves more work though (the implementation I used to have manages to also do it in the same pass but also maintains a stack of edges).
You can write an algorithm to compute all of the articulation points & bridges & edge-biconnected components & vertex-biconnected components in a single DFS. Because of this you refer to all of them as just "Tarjan's algorithm" even if you just compute one of them (he is kind of the Euler of graph algorithms in that like half of graph algorithms is named after him). So, on a technical level, I guess my implementation is similar to the algorithm in Boost because they both use DFS and this `low` map, but they compute different things.
Finding the vertex-biconnected components next to the articulation points involves more work though (the implementation I used to have manages to also do it in the same pass but also maintains a stack of edges).
Thank you for the reply - appreciated.
vertex-biconnectedness can exist even if vertex-disjoint paths from to u1 - u2 in an equivalence relation stand as distinct outliers
the strategy of the periphery for bioconnectedness hosts p-2-p network once intermediate node has identified bridges
the strategy of the periphery for bioconnectedness hosts p-2-p network once intermediate node has identified bridges
There seems to be an error in the very first example.
They show (3,1) as a valid pair, but node 3 is not labeled as being in set A. Either the graph is mislabeled or the example valid pair is wrong.
They show (3,1) as a valid pair, but node 3 is not labeled as being in set A. Either the graph is mislabeled or the example valid pair is wrong.
Whoops, you got me. Fixed!
At some point I relabeled the vertices to match the DFS order, but I must have forgotten to update this example.
At some point I relabeled the vertices to match the DFS order, but I must have forgotten to update this example.
Nice. I'm liking the interactive diagrams!
I noticed another small error. Step 15 of the Tarjan's algorithm diagram reads:
> Since low[6] > 4, the edge is a bridge.
I think it should read:
> Since low[6] > low[4], the edge is a bridge.
I noticed another small error. Step 15 of the Tarjan's algorithm diagram reads:
> Since low[6] > 4, the edge is a bridge.
I think it should read:
> Since low[6] > low[4], the edge is a bridge.
That one is intentional. Note: a tree edge (u, v) is a bridge if and only if low[v] is strictly greater than the entry time of u.
Here 4 is the entry time of that node. (For convenience I made sure that the node labels are just the DFS entry times.)
Though maybe comparing both low values might also work, I'd have to think about that...
Here 4 is the entry time of that node. (For convenience I made sure that the node labels are just the DFS entry times.)
Though maybe comparing both low values might also work, I'd have to think about that...
>Especially in competitive programming it is vital to know about this concept.
What is competitive programming?
What is competitive programming?
Basically you get a bunch of problems (ranging from "check if a number is prime" to complicated graph theoretical problems) and some time to figure them out and code a correct & efficient solution. Often there are computer science concepts and reasoning techniques you need to know about (like biconnected components) to figure out how to make an efficient enough implementation.
The contests I used to go to, you got 11-13 problems and 5 hours to solve them with a team of 3. However, you only have one PC to share, so a lot of the time you are discussing, drawing stuff on paper and figuring out the solution in your head. There is also a printing service during the contest where you can literally get a paper version of your code :) so somebody else can code while you debug on paper.
See for instance https://www.acmicpc.net/category/detail/4319 for the kinds of problems they give (Korean website unfortunately but the problems are in English).
The contests I used to go to, you got 11-13 problems and 5 hours to solve them with a team of 3. However, you only have one PC to share, so a lot of the time you are discussing, drawing stuff on paper and figuring out the solution in your head. There is also a printing service during the contest where you can literally get a paper version of your code :) so somebody else can code while you debug on paper.
See for instance https://www.acmicpc.net/category/detail/4319 for the kinds of problems they give (Korean website unfortunately but the problems are in English).
Genuine question: why do people sometimes write comments like this instead of Googling? Two guesses I have:
- HN responses might contain more first-hand experience and thus be richer than what one could find via Google or an LLM.
- Some terms are contextual so Google might not give the right answer, and an LLM could give a more contextual answer but might still just be wrong.
Are those usually the reason, or are there other reasons as well?
- HN responses might contain more first-hand experience and thus be richer than what one could find via Google or an LLM.
- Some terms are contextual so Google might not give the right answer, and an LLM could give a more contextual answer but might still just be wrong.
Are those usually the reason, or are there other reasons as well?
I used to get annoyed by these kinds of questions, but honestly I love talking about things I'm passionate about anyway and I want to get more people interested in the subject. So, I'm happy to answer questions like this and simultaneously sneak in some of my own personal experiences.
This is a nice attitude. I think HN is overall pretty nice for geeking out and also hearing other people geek out, but there is still a strain of elitism (not like StackExchange thankfully) and so I'm happy to see comments like this.
> there is still a strain of elitism
Those types can't help themselves so patterns emerge and usernames become recognizable after a while. There are some people who I just don't bother engaging with any more. Of course, those experiences are my own and maybe not the same experience as others.
Those types can't help themselves so patterns emerge and usernames become recognizable after a while. There are some people who I just don't bother engaging with any more. Of course, those experiences are my own and maybe not the same experience as others.
Thanks, replies like yours are exactly why I prefer asking it here instead of googling.
1) locality of knowledge - people ask questions to clear the context of the discussion, not to learn stuff in the vacuum
2) sense of community - people ask questions because it's in human nature to teach others and learn within our groups. Programming culture is even more about joy of teaching others, so I don't understand your complaint
2) sense of community - people ask questions because it's in human nature to teach others and learn within our groups. Programming culture is even more about joy of teaching others, so I don't understand your complaint
Could you explain why you interpreted my question as a complaint? I clearly indicated that I was asking in good faith by even providing two possible explanations that seem reasonable.
if I'm being honest... combination of grandparent comment I sympathize with being downvoted, your comment being positive, while "just google it" stance I've parsed as disapproval of people it's directed towards
It's similar to math olympiad, but for algorithms.
https://www.boost.org/library/latest/graph/
https://www.boost.org/doc/libs/latest/libs/graph/doc/biconne...
Am I correct to suppose both are C++ implementations of Tarjan's algorithm?