Understanding the Dijkstra example

[Matthew Browne]

Hi,
I am working on a Dijkstra example for my PHP library. I have working code that produces the correct result, and I understand the idea of a weighted graph (in a generic sense) and finding the shortest path, but I don't understand how it's supposed to relate to a Manhattan grid with streets and avenues.

Most of the DCI examples have a code comment like this:

    # Grid is of Manhattan form:
    #
    #    a - 2 - b - 3 - c
    #    |       |       |
    #    1       2       1
    #    |       |       |
    #    d - 1 - e - 1 - f
    #    |               |
    #    2               4
    #    |               |
    #    g - 1 - h - 2 - i

What do the numbers represent here? I would have thought they were just arbitrary distances for the sake of the example (e.g. various landmarks within Manhattan), but the C++ example code explicitly defines the horizontal lines as streets, and the vertical lines as avenues.

(For those who might not be familiar with the street grid of Manhattan, streets run east-to-west and avenues run north-to-south. Avenue blocks are approximately [but not exactly I don't think] 3 times as long as street blocks, but it seems like the example doesn't try to be realistic in that sense?)

As someone who lives in New York City very close to Manhattan, one of the first things that comes to mind as to what else these numbers could mean is traffic—during peak traffic, some blocks might indeed take a lot longer to travel through! But this is just a guess.

I also came across a wikipedia entry about Manhattan geometry, AKA taxicab geometry, but I assume that the code comment saying the grid is of "Manhattan form" just means streets and avenues like the actual street grid of Manhattan.

Thanks,
Matt

[James O Coplien]

Don’t read too much into it.

The Dijkstra algorithm works on unconstrained graphs. The arcs on the graph are annotated with symmetric weights (it doesn’t matter which of the pair of nodes is the starting point: the weight/cost/distance value is the same). The arcs are undirected and the graph is therefore acyclic.

The example just happens to be a Manhattan graph for the sake of simple demonstration. The numbers are just the weights/costs/distances between nodes.

I vaguely remember that I maybe had to reduce the example to Manhattan form to make the point I wanted to make (instead of a more general graph), but I’m having a hard time recalling what that reason was if indeed there was one at all.

Aha, now I remember it. This becomes an interesting DCI example only if you have an interesting number of Roles. Just having “Node” and “Arc” seemed awfully boring so I introduced a bit richer design with Streets and Avenues. But maybe I abandoned that fantasy in the end and in fact the trygve example may handle general graphs. I don’t remember.

With the time you are spending on this you will certainly soon be the expert on the Dijkstra example… ;-)

--
You received this message because you are subscribed to the Google Groups "object-composition" group.
To unsubscribe from this group and stop receiving emails from it, send an email to object-composit...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/object-composition/04dc4775-4001-4348-8bed-6a5cca7518e7%40gmail.com.