graph_reduction.txt

Reducing a rail network to a minimal graph, using PostGIS
=========================================================

You will need:
- osmosis (shell commands below are run from the root of the osmosis distribution)
- PostgreSQL + PostGIS
- Python
- psycopg2 (Python PostgreSQL binding)

1) Extract railway-related nodes and ways from your OSM data source

./bin/osmosis --read-pbf wales.osm.pbf --tf accept-ways railway=* --tf reject-relations --used-node --write-xml railway-ways.osm
./bin/osmosis --read-pbf wales.osm.pbf --tf accept-nodes railway=* --tf reject-ways --tf reject-relations --write-xml railway-nodes.osm
./bin/osmosis --read-xml railway-ways.osm --read-xml railway-nodes.oxm --merge --write-xml railways_full.osm

2) Create a PostGIS-enabled database

createdb -Upostgres traingraph -T template_postgis
psql -Upostgres traingraph -f script/pgsimple_schema_0.6.sql 

3) Import data into the database

./bin/osmosis --read-xml ~/Sites/trainhack/railways_wales_fixed.osm --write-pgsimp user="postgres" database="traingraph"

4) Create table of stations

(at the PostgreSQL command line)

SELECT nodes.id, name_tags.v AS name, nodes.geom
INTO stations
FROM nodes
INNER JOIN node_tags AS rail_tags ON (nodes.id=rail_tags.node_id AND rail_tags.k='railway' AND rail_tags.v='station')
INNER JOIN node_tags AS name_tags ON (nodes.id=name_tags.node_id AND name_tags.k='name');

ALTER TABLE stations ADD PRIMARY KEY (id);

5) Create table of line segments that join two nodes:

SELECT DISTINCT
	-- order nodes such that node1_id < node2_id
	LEAST(way_node1.node_id, way_node2.node_id) AS node1_id,
	GREATEST(way_node1.node_id, way_node2.node_id) AS node2_id,
	NULL AS path_id -- will be populated by the build_paths script
INTO rail_segments
FROM way_nodes AS way_node1
INNER JOIN way_nodes AS way_node2 ON (way_node1.way_id = way_node2.way_id AND way_node1.sequence_id + 1 = way_node2.sequence_id)
INNER JOIN way_tags ON (
	way_node1.way_id = way_tags.way_id AND way_tags.k = 'railway' AND way_tags.v = 'rail'
	-- alter these criteria as appropriate, e.g. to include specific track types
);

ALTER TABLE rail_segments ADD FOREIGN KEY (node1_id) REFERENCES nodes(id);
ALTER TABLE rail_segments ADD FOREIGN KEY (node2_id) REFERENCES nodes(id);

CREATE INDEX idx_rail_segments_node1 ON rail_segments(node1_id);
CREATE INDEX idx_rail_segments_node2 ON rail_segments(node2_id);

6) Create a table of junctions (nodes with exactly one, or three or more, line segments leaving them):

SELECT id, neighbour_count,
	neighbour_count AS unfollowed_neighbour_count -- will be decremented by the build_paths script
INTO junctions
FROM (
	SELECT nodes.id, (SELECT COUNT(*) FROM rail_segments WHERE nodes.id = node1_id OR nodes.id = node2_id) AS neighbour_count
	FROM nodes
) foo
WHERE neighbour_count > 0 AND neighbour_count <> 2;

ALTER TABLE junctions ADD PRIMARY KEY (id);

7) Create a table of paths (maximal sequences of nodes that do not contain any branches) to be populated by the build_paths script:

CREATE SEQUENCE seq_path_id;
CREATE TABLE paths (
	id BIGINT NOT NULL DEFAULT NEXTVAL('seq_path_id'),
	node1_id BIGINT NOT NULL,
	node2_id BIGINT NOT NULL,
	linestring GEOMETRY,
	length FLOAT,

	PRIMARY KEY (id),
	FOREIGN KEY (node1_id) REFERENCES nodes(id),
	FOREIGN KEY (node2_id) REFERENCES nodes(id)
);
CREATE INDEX idx_paths_node1 ON paths(node1_id);
CREATE INDEX idx_paths_node2 ON paths(node2_id);

CREATE TABLE path_nodes (
	path_id BIGINT NOT NULL,
	node_id BIGINT NOT NULL,
	sequence_id INTEGER NOT NULL,

	FOREIGN KEY (path_id) REFERENCES paths(id),
	FOREIGN KEY (node_id) REFERENCES nodes(id)
);
CREATE INDEX idx_path_nodes_path ON path_nodes(path_id, sequence_id);

8) Run build_paths.py to populate the table of paths

python build_paths.py traingraph

9) Populate the linestring and length fields of the paths table

python add_linestrings.py traingraph

10) The database is now ready to run path-finding queries using the find_route script:

python find_route.py traingraph Oxford "London Paddington"

- which will output a KML LineString element indicating the shortest path between the two stations.