5 ms·

The pseudo-code of BFS is all of 20 lines, and that's accounting for a graph possibly containing cycles. A graph without cycles (such as a tree) would be even s

The pseudo-code of BFS is all of 20 lines, and that's accounting for a graph possibly containing cycles. A graph without cycles (such as a tree) would be even simpler/shorter. https://en.wikipedia.org/wiki/Breadth-first_search https://en.wikipedia.org/wiki/Breadth-first_search Correct arg parsing is actually significantly more complicated in comparison because of all the possibilities and edge cases. > Never (!) homebrew that shit unless you have to (like, you're in an embedded environment or your use case requires some bleeding edge research algorithm). I can't help but think this mentality is what lead to the recent left-pad debacle

p4wnc6 10y ago
> I can't help but think this mentality is what lead to the recent left-pad debacle It borders on category error to compare homebrewing argument parsing with an overreliance on microframeworks extending all the way down to leftpad. Argument parsing is almost always supported directly by the language implementers in a standard library. And even if it wasn't, it's such a critical task with huge overhead for handling corner cases, cross-platform details, etc., that the value of a central implementation is obvious. A left pad operation ought to be part of the standard language (which is actually what the leftpad debacle was about, Javascript's incredible failures as a language), but it's too trivial to compare it to something like argument parsing. > The pseudo-code of BFS is all of 20 lines, ... If it's only 20 lines, that's great because it means it was easy for the other 500 library writers to write it, write tests, and observe and fix issues over time. So, whew, that's 20 lines I totally shouldn't waste my time on, plus unit tests and routine maintenance I don't have to commit to. And also, given the wide acknowledgement that a good programmer should be writing at most a few hundred lines of code per day (otherwise it's probably mostly junk), 20 lines of code is not trivial. Probably most programmers write a whole lot more than that per day (especially if counting copy/pasted code), but this is in part a sign of a bad programmer, or perhaps more so a sign of the anti-quality constraints placed on them by most employers.
- lawrjone 10y ago
  What the hell sort of library would you crack out to do a breadth first search traversal? This is my main problem with the OP, BFS isn't some arcane complex cryptic algorithm, it's a way of moving through a data structure that becomes natural and very obvious when you think about how you can effectively traverse it for some tasks. If I were ever to want to traverse something in a breadth first search manner, then I would just write it. It would take longer to search for another library and read how it's somehow implemented this search than it would to write it, test it, get it reviewed, and we've still avoided adding another potentially crappy dependency to our project. It's not category error to compare this to leftpad. leftpad actually makes more sense imo, as it's a common microfunction that may be used more than once. BFS is typically far more coupled with the underlying data and is more naturally written inline.
  - microtherion 10y ago
    There is, for instance, the Boost Graph library in C++: http://www.boost.org/doc/libs/1_60_0/libs/graph/doc/table_of_contents.html http://www.boost.org/doc/libs/1_60_0/libs/graph/doc/table_of...
  - ljw1001 10y ago
    I would use one of the tree implementations in java.util. You may have heard of it.
  - p4wnc6 10y ago
    > we've still avoided adding another potentially crappy dependency to our project. No, you've just added the crappy dependency == your off the cuff implementation (which is even more work since you have to handle issues and unit testing for it too). > What the hell sort of library would you crack out to do a breadth first search traversal? In Python I would use networkx probably, unless there was a good reason I couldn't (such as working in an embedded environment where I couldn't install large libraries). It ought to require an exceptional circumstance to stoop to implementing it myself. Tell me, if we switched from talking about breadth first search to, say, inverting a matrix with Gaussian elimination and pivoting, do you feel the same? Are you going to trust your implementation over something you can get from netlib?

p4wnc6 10y ago

> I can't help but think this mentality is what lead to the recent left-pad debacle It borders on category error to compare homebrewing argument parsing with an overreliance on microframeworks extending all the way down to leftpad. Argument parsing is almost always supported directly by the language implementers in a standard library. And even if it wasn't, it's such a critical task with huge overhead for handling corner cases, cross-platform details, etc., that the value of a central implementation is obvious. A left pad operation ought to be part of the standard language (which is actually what the leftpad debacle was about, Javascript's incredible failures as a language), but it's too trivial to compare it to something like argument parsing. > The pseudo-code of BFS is all of 20 lines, ... If it's only 20 lines, that's great because it means it was easy for the other 500 library writers to write it, write tests, and observe and fix issues over time. So, whew, that's 20 lines I totally shouldn't waste my time on, plus unit tests and routine maintenance I don't have to commit to. And also, given the wide acknowledgement that a good programmer should be writing at most a few hundred lines of code per day (otherwise it's probably mostly junk), 20 lines of code is not trivial. Probably most programmers write a whole lot more than that per day (especially if counting copy/pasted code), but this is in part a sign of a bad programmer, or perhaps more so a sign of the anti-quality constraints placed on them by most employers.

lawrjone 10y ago
What the hell sort of library would you crack out to do a breadth first search traversal? This is my main problem with the OP, BFS isn't some arcane complex cryptic algorithm, it's a way of moving through a data structure that becomes natural and very obvious when you think about how you can effectively traverse it for some tasks. If I were ever to want to traverse something in a breadth first search manner, then I would just write it. It would take longer to search for another library and read how it's somehow implemented this search than it would to write it, test it, get it reviewed, and we've still avoided adding another potentially crappy dependency to our project. It's not category error to compare this to leftpad. leftpad actually makes more sense imo, as it's a common microfunction that may be used more than once. BFS is typically far more coupled with the underlying data and is more naturally written inline.
- microtherion 10y ago
  There is, for instance, the Boost Graph library in C++: http://www.boost.org/doc/libs/1_60_0/libs/graph/doc/table_of_contents.html http://www.boost.org/doc/libs/1_60_0/libs/graph/doc/table_of...
- ljw1001 10y ago
  I would use one of the tree implementations in java.util. You may have heard of it.
- p4wnc6 10y ago
  > we've still avoided adding another potentially crappy dependency to our project. No, you've just added the crappy dependency == your off the cuff implementation (which is even more work since you have to handle issues and unit testing for it too). > What the hell sort of library would you crack out to do a breadth first search traversal? In Python I would use networkx probably, unless there was a good reason I couldn't (such as working in an embedded environment where I couldn't install large libraries). It ought to require an exceptional circumstance to stoop to implementing it myself. Tell me, if we switched from talking about breadth first search to, say, inverting a matrix with Gaussian elimination and pivoting, do you feel the same? Are you going to trust your implementation over something you can get from netlib?