5 ms·

Biconnected components

53 points by emih 1y ago

shrx 1y ago
>Especially in competitive programming it is vital to know about this concept. What is competitive programming?
- polivier 1y ago
  https://en.m.wikipedia.org/wiki/Competitive_programming https://en.m.wikipedia.org/wiki/Competitive_programming
- emih 1y ago
  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 https://www.acmicpc.net/category/detail/4319 for the kinds of problems they give (Korean website unfortunately but the problems are in English).
- sestep 1y ago
  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?
  - emih 1y ago
    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.
    - mcyc 1y ago
      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.
      - stronglikedan 1y ago
        > 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.
    - shrx 1y ago
      Thanks, replies like yours are exactly why I prefer asking it here instead of googling.
  - NooneAtAll3 1y ago
    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
    - sestep 1y ago
      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.
- ufo 1y ago
  It's similar to math olympiad, but for algorithms.
revanwjy 1y ago
[flagged]
hamonrye 1y ago
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
spankalee 1y ago
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.
- emih 1y ago
  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.
  - spankalee 1y ago
    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.
    - emih 1y ago
      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...
delhanty 1y ago
For 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/library/latest/graph/ https://www.boost.org/doc/libs/latest/libs/graph/doc/biconnected_components.html https://www.boost.org/doc/libs/latest/libs/graph/doc/biconne... Am I correct to suppose both are C++ implementations of Tarjan's algorithm?
- emih 1y ago
  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).
  - delhanty 1y ago
    Thank you for the reply - appreciated.

53 points by emih 1y ago

shrx 1y ago

>Especially in competitive programming it is vital to know about this concept. What is competitive programming?

polivier 1y ago
https://en.m.wikipedia.org/wiki/Competitive_programming https://en.m.wikipedia.org/wiki/Competitive_programming
emih 1y ago
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 https://www.acmicpc.net/category/detail/4319 for the kinds of problems they give (Korean website unfortunately but the problems are in English).
sestep 1y ago
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?
- emih 1y ago
  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.
  - mcyc 1y ago
    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.
    - stronglikedan 1y ago
      > 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.
  - shrx 1y ago
    Thanks, replies like yours are exactly why I prefer asking it here instead of googling.
- NooneAtAll3 1y ago
  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
  - sestep 1y ago
    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.
ufo 1y ago
It's similar to math olympiad, but for algorithms.

revanwjy 1y ago

[flagged]

hamonrye 1y ago

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

spankalee 1y ago

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.

emih 1y ago
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.
- spankalee 1y ago
  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.
  - emih 1y ago
    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...

delhanty 1y ago

For 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/library/latest/graph/ https://www.boost.org/doc/libs/latest/libs/graph/doc/biconnected_components.html https://www.boost.org/doc/libs/latest/libs/graph/doc/biconne... Am I correct to suppose both are C++ implementations of Tarjan's algorithm?

emih 1y ago
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).
- delhanty 1y ago
  Thank you for the reply - appreciated.