Re: Demo: Modelling Cost of Travel Paths Between Towns

From: --CELKO-- <jcelko212_at_earthlink.net>
Date: 8 Nov 2004 14:14:59 -0800
Message-ID: <18c7b3c2.0411081414.2f0f8b8e@posting.google.com>

>> Four towns named a, b, c, d (imagine them forming a square). There are
paths from a to b, b to c, c to d and d to a. There are also opposite paths from a to d, d to c, c to b and b to a. In addition, there are two uni-directional cross paths, one from a to c and the second from b to d. The cost of travel from town a to town b on Monday between 00:00 and 24:00 is 1.00. <<

There is no such time as 24:00 Hrs; read ISO-8601. This is pretty straight forward in SQL.

CREATE TABLE Trips
(source_town CHAR(10) NOT NULL

     REFERENCES Towns(town_name)
     ON UPDATE CASCADE
     ON DELETE CASCADE,
 destination_town CHAR(10) NOT NULL
     REFERENCES Towns(town_name)
     ON UPDATE CASCADE
     ON DELETE CASCADE,

 travel_cost INTEGER DEFAULT 0 NOT NULL

    CHECK (travel_cost >= 0),
 start_time TIMESTAMP NOT NULL,
 end_time TIMESTAMP NOT NULL,
 CHECK (start_time < end_time),
 ..);

INSERT INTO Trips VALUES ('a', 'b', 1, '2004-11-08 00:00:00'
'2004-11-09 00:00:00');

INSERT INTO Trips VALUES ('b', 'c', 1, '2004-11-08 00:00:00'
'2004-11-09 00:00:00');

...
-- reverse paths
INSERT INTO Trips VALUES ('b', 'a', 1, '2004-11-08 00:00:00'
'2004-11-09 00:00:00');

INSERT INTO Trips VALUES ('c', 'b', 1, '2004-11-08 00:00:00'
'2004-11-09 00:00:00');

..
--diagonal paths
INSERT INTO Trips VALUES ('a', 'c', 1, '2004-11-08 00:00:00'
'2004-11-09 00:00:00');

INSERT INTO Trips VALUES ('b', 'd', 1, '2004-11-08 00:00:00'
'2004-11-09 00:00:00');

That gets all the (travel_cost = 1) edges in the graph. Next, use Warshall's algorithm to fill in travel costs on ('c', 'a'), ('d', 'b') and so forth. This will work for any adjacency list model. I would do the matrix multiplications in a host language like FORTRAN, C or Pascal, but I can do it in pure SQL if I have to (see that section in SQL FOR SMARTIES). Received on Mon Nov 08 2004 - 16:14:59 CST