4 ms·

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 cry

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?
- lawrjone 10y ago
  In the case where you'd require a bfs to traverse a graph, you're already doing something that is algorithmic, and will otherwise be prohibitively costly if explored in a dfs manner. The most complicated part of this algorithm is highly unlikely to be the bfs itself, with it's highly likely 10 lines of code in total. In this case, someone who didn't have the time to visualise exactly how the bfs is operating shouldn't be writing the algorithm. Pretending like you don't need to know the details of how it traverses the tree when you needed to choose the specific implementation for this algorithm to be performant is a lie. It's not like Guassian elimination, where the concept is far more abstract, this is a concrete idea of how you're moving through the graph and shouldn't be some black magic. On top of this, who writes this code and doesn't test that it does what you expected it to do on sample data. If you bfs implementation was bust, then you'd miss nodes or revisit them, which becomes immediately apparent from testing the algorithm you're writing. > It ought to require an exceptional circumstance to stoop to implementing it myself. Maybe the problem here is that I see a bfs as a fundamentally simple algorithm. Saying writing it yourself must be an exceptional circumstance sounds about as crazy to me as saying no-one should ever use for loops, they expose you to making mistakes with an index you may forget is zero-based, please use anonymous iterators instead. When something takes 5m to write, is heavily tested by default (as it will be a feature under test anyway and possible flaws will be highly obvious) and is at the same level of abstraction as the code you'll be writing around it, then just write the damn thing. EDIT - Try writing a BFS that operates on an acyclic graph that outputs the value of each node, that compiles and runs and prints at least two node values that has a bug. Try writing bugs into this, it's actually difficult to screw up.
  - p4wnc6 10y ago
    > Maybe the problem here is that I see a bfs as a fundamentally simple algorithm. Yes, this kind of hubris is often the root of the problem when so-called 'simple' algorithms get homebrewed, then later on unexpected corner cases pop up, testing isn't adequate, you didn't implement it in an extensible way, your implementation is unacceptably inefficient, etc. etc. > On top of this, who writes this code and doesn't test that it does what you expected it to do on sample data. If you bfs implementation was bust, then you'd miss nodes or revisit them, which becomes immediately apparent from testing the algorithm you're writing. Yes, but the point is that testing isn't free. If you commit to writing your own implementation of something to interface with whatever larger business / domain-specific project created the need for it in the first place, then you have to dedicate not just the time to write it, but also the time to test it, and to test how it integrates, and to maintain the API for it and maintain its integration (possibly backward compatibility, etc. etc.) If you adopt a standard to use a certain library, then up to the degree to which you trust the library, those problems are mostly offloaded to others. For things like classical algorithms, the libraries are extremely trustworthy, so many of the pitfalls of adding a dependency don't apply. > In this case, someone who didn't have the time to visualise exactly how the bfs is operating shouldn't be writing the algorithm. It's not about being too pressed for time. Even if you had all day, it's a poor use of time to create more future work for yourself by yoking yourself to all the extra responsibilities that come along with rolling your own. Yoking yourself to those responsibilities should require an exception reason for doing so. > Saying writing it yourself must be an exceptional circumstance sounds about as crazy to me as saying no-one should ever use for loops, they expose you to making mistakes with an index you may forget is zero-based, please use anonymous iterators instead. This is an extremely fallacious comparison. Basic control structure are built in features of the language. You don't have to test or maintain the runtime execution of a for loop, that's the job of language designers. Making mistakes in the usage of something (like an off-by-one index) is completely non sequitur to this entire discussion. I don't see how you would think that type of bug is related to anything I'm saying. In general, you also assume a much higher fidelity of testing than what happens in the real world. In 99% of software jobs, you'll be extremely lucky if someone even documents their homemade BFS algorithm, let alone writing even the most superficial of tests. Expecting them to give you an adequate bank of automated tests is like believing in the Easter Bunny. > Try writing bugs into this, it's actually difficult to screw up. Ugh.

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?

lawrjone 10y ago
In the case where you'd require a bfs to traverse a graph, you're already doing something that is algorithmic, and will otherwise be prohibitively costly if explored in a dfs manner. The most complicated part of this algorithm is highly unlikely to be the bfs itself, with it's highly likely 10 lines of code in total. In this case, someone who didn't have the time to visualise exactly how the bfs is operating shouldn't be writing the algorithm. Pretending like you don't need to know the details of how it traverses the tree when you needed to choose the specific implementation for this algorithm to be performant is a lie. It's not like Guassian elimination, where the concept is far more abstract, this is a concrete idea of how you're moving through the graph and shouldn't be some black magic. On top of this, who writes this code and doesn't test that it does what you expected it to do on sample data. If you bfs implementation was bust, then you'd miss nodes or revisit them, which becomes immediately apparent from testing the algorithm you're writing. > It ought to require an exceptional circumstance to stoop to implementing it myself. Maybe the problem here is that I see a bfs as a fundamentally simple algorithm. Saying writing it yourself must be an exceptional circumstance sounds about as crazy to me as saying no-one should ever use for loops, they expose you to making mistakes with an index you may forget is zero-based, please use anonymous iterators instead. When something takes 5m to write, is heavily tested by default (as it will be a feature under test anyway and possible flaws will be highly obvious) and is at the same level of abstraction as the code you'll be writing around it, then just write the damn thing. EDIT - Try writing a BFS that operates on an acyclic graph that outputs the value of each node, that compiles and runs and prints at least two node values that has a bug. Try writing bugs into this, it's actually difficult to screw up.
- p4wnc6 10y ago
  > Maybe the problem here is that I see a bfs as a fundamentally simple algorithm. Yes, this kind of hubris is often the root of the problem when so-called 'simple' algorithms get homebrewed, then later on unexpected corner cases pop up, testing isn't adequate, you didn't implement it in an extensible way, your implementation is unacceptably inefficient, etc. etc. > On top of this, who writes this code and doesn't test that it does what you expected it to do on sample data. If you bfs implementation was bust, then you'd miss nodes or revisit them, which becomes immediately apparent from testing the algorithm you're writing. Yes, but the point is that testing isn't free. If you commit to writing your own implementation of something to interface with whatever larger business / domain-specific project created the need for it in the first place, then you have to dedicate not just the time to write it, but also the time to test it, and to test how it integrates, and to maintain the API for it and maintain its integration (possibly backward compatibility, etc. etc.) If you adopt a standard to use a certain library, then up to the degree to which you trust the library, those problems are mostly offloaded to others. For things like classical algorithms, the libraries are extremely trustworthy, so many of the pitfalls of adding a dependency don't apply. > In this case, someone who didn't have the time to visualise exactly how the bfs is operating shouldn't be writing the algorithm. It's not about being too pressed for time. Even if you had all day, it's a poor use of time to create more future work for yourself by yoking yourself to all the extra responsibilities that come along with rolling your own. Yoking yourself to those responsibilities should require an exception reason for doing so. > Saying writing it yourself must be an exceptional circumstance sounds about as crazy to me as saying no-one should ever use for loops, they expose you to making mistakes with an index you may forget is zero-based, please use anonymous iterators instead. This is an extremely fallacious comparison. Basic control structure are built in features of the language. You don't have to test or maintain the runtime execution of a for loop, that's the job of language designers. Making mistakes in the usage of something (like an off-by-one index) is completely non sequitur to this entire discussion. I don't see how you would think that type of bug is related to anything I'm saying. In general, you also assume a much higher fidelity of testing than what happens in the real world. In 99% of software jobs, you'll be extremely lucky if someone even documents their homemade BFS algorithm, let alone writing even the most superficial of tests. Expecting them to give you an adequate bank of automated tests is like believing in the Easter Bunny. > Try writing bugs into this, it's actually difficult to screw up. Ugh.