## The Design of Software (CLOSED)A public forum for discussing the design of software, from the user interface to the code architecture. Now closed. |
||

The "Design of Software" discussion group has been merged with the main
Joel on Software discussion group.
The archives will remain online indefinitely. |
Hey all,
So I've been working on an algorithm that analyzes some simple graph data structures, where any element can be connected to any other (or more than one) elements. There are some simple rules for what to do with these elements depending on what they are connected to and what the elements actually are. It occurred to me that this resembles a parsing scenario, except instead of a linear stream of characters, we have a graph. As an example (not what I'm doing), imaging trying to "parse" a road network to figure out the function of each road based on the road type and the neighboring roads. Has anyone ever heard of a parser type algorithm being applied in such a scenario? I know it's a bit of a long shot, but it would be nice if it turned out there is an extensive theory on this topic.
There's graph theory, but I think you know of that and want something more specific. Your answer if anywhere would be in a doctoral thesis somewhere.
Art Wilkins Tuesday, July 04, 2006
This is a chapter from a book about roads that has a nice quick overview of graph theory.
http://people.hofstra.edu/geotrans/eng/ch2en/meth2en/ch2m1en.html http://people.hofstra.edu/geotrans/eng/ch2en/meth2en/ch2m2en.html http://people.hofstra.edu/geotrans/eng/ch2en/meth2en/ch2m3en.html Last page in particular you might find useful as a starting point.
Art Wilkins Tuesday, July 04, 2006
I haven't used it, but the Boost Graph library (http://www.boost.org/libs/graph/doc/ ) is probably worth looking into.
And there is an extensive literature on graph theory. Search on Amazon and you'll find a bunch of textbooks on it. I tried to find the one that I'd used when I took a Graph Theory class in college but I didn't see it.
"Has anyone ever heard of a parser type algorithm being applied in such a scenario?"
Yes. The Sabre airline reservation system uses something very similar in an attempt to solve the traveling salesman problem. Err, the basic idea is to make the salesman more enlightened about his choices instead of relying on one set of attributes (usually distance). For example, airlines would prefer to fly the longer route with a stopover instead of the more direct route if there's not enough passengers for the shorter route. I don't think you would have heard about parsing algorithms in this context because I don't recall anyone coming up with a formula to quantify just how much data is enough to solve the problem, in a useful timeframe. Take roads for example. Let's assume that the next node is one hour away. From what you're describing, it sounds like in addition to knowing how far away the node is, I also know whether the road is paved, how much traffic is likely to use it, what are the weather conditions (slippery when wet?), are there any potential obstacles such as low overpasses or children in the area. Not only that, I also know all this info about all nearby roads and alternative paths and shortcuts and so forth. By the time I crunch all that data and make a decision, I could have just driven there and back. I would be interested if you came up with such a formula. I also think that the "best solution" is largely subjective and too dependent upon environmental constraints such as CPU power and imposed deadlines, to be a subject researched much in academia.
TheDavid Thursday, July 06, 2006
"Parsing" generally means deducing structure (usually but not necessarily hierarchical structure) from a serialized representation. So input: a string; output: a tree. That's just what parsing is.
To ask if there are "parser-type algorithms" that take as input a graph, and output an analysis of the graph, is to generalize the concept of parsing to the point where it no longer fits its definition. So there may be (certainly are) useful graph analysis algorithms but almost by definition they are not parsers. Graph/network algorithms exist to answer questions like: is a graph connected? strongly commencted? bipartite? planar? etc. but none of them "parses" a graph using analogs of the algorithms (LL(1), LR(1), LALR, etc.) that deduce tree structure from an input string.
True.
I had interpreted the word "parsing" in the context of regular expressions; an input is analyzed for meaningful context in addition to a mathematical sequence. The original poster suggested as an example, that he was trying to deduce the function of the road based upon the road type. I'm assuming he's referring to making decisions such as "if the road is paved, reasonably straight and has no intersections, it must be an expressway." I would not define this as a "graph analysis algorithm" and apparently it's incorrect to call this a "parsing-type algorithm" so what kind of problem is this? A graph transformation problem/algorithm?
TheDavid Friday, July 07, 2006 |

Powered by FogBugz