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.
Biconnected components
11–20 of 22 posts
Re: Biconnected components
#12There 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.
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.
Re: Biconnected components
#13There 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.
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.
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.
Re: Biconnected components
#14Earlier quoted context omitted.
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.
Re: Biconnected components
#15Earlier quoted context omitted.
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.
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.
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...
Re: Biconnected components
#16>Especially in competitive programming it is vital to know about this concept. What is competitive programming?
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 ther…
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
Re: Biconnected components
#17Earlier quoted context omitted.
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 ther…
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
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.
Re: Biconnected components
#18Earlier quoted context omitted.
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 ther…
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.
Thanks, replies like yours are exactly why I prefer asking it here instead of googling.
Re: Biconnected components
#19For the vertex biconnected components can you say how your implementation compares technically with Boost Graph library's `biconnected_components` and `articulation_points`?
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?
Re: Biconnected components
#20For the vertex biconnected components can you say how your implementation compares technically with Boost Graph library's `biconnected_components` and `articulation_points`? 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?
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).