Re: Demo: Modelling Cost of Travel Paths Between Towns
Date: 8 Nov 2004 14:14:59 -0800
Message-ID: <18c7b3c2.0411081414.2f0f8b8e_at_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 - 23:14:59 CET