Saturday, April 12, 2008

When will I ever use this in real life? (Breadth First Search)

A lot of times, while taking classes, learning, being educated, etc, we ask ourselves, "when will I ever use this in real life?". "This" being some conceptual concept that is not concrete, but abstract.

In terms of computer science and algorithms, using all the good stuff you learned in school in practice might not happen that often, depending on the company you work for. I say this because a lot focus, or at least priority, is on functionality and feature design. When these come first, speed and efficiency come second, as the client expects this with their features and functions, and are not document as a requirement. Speed and efficiency then get rolled up into refactoring then, or base work, or core work, or whatever.

Recently I had an opportunity to implement an actual algorithm learned in school in practice. I had to implement a graph traversing algorithm for an relational analysis application I am working on. The objective of the project is to capture the connected structure of "things" and demonstrate that structure through images. The "things" and their "relationships" are stored in a generic graph structure. And so visualizing this requires a starting point and then show the graph from that starting point.

At first, I just hammered out some crap code to get it to work. The problem was that there was a bug that once a "thing" was shown, it was never visited again. So if A->B is shown when expanding A, B is never expanded.

When I had then chance, I fixed this using the breadth first search. Oh the fun, taking pseudo code to actual code, and making it fit my needs. My needs, being to generate a graphviz dot graph output to render images with a depth limit based on user input, as well as a node limit based on user input. As, my needs were not to search, but to just walk the graph. I didn't want depth first because I wanted to expand each depth as a time, and then move to the next. I figure this out later, after realizing the different of the two, depth verse breadth. All in PHP, with my datastore as a MySQL database (I'll expand on the schema of the database design in another post sometime).

Any way, when I was done, I reflected on how often I get to apply my educational concepts learned in practice. Since I realized it was not too often, for some reason I enjoyed doing so, and am looking forward to any opportunity to do more.

By the way, I went to Kent State for my undergraduate, and am attending Cleveland State for my graduate, both in computer science.

See Also:

No comments:

Share on Twitter