I have created a topology from OSM data and would like to simulate a car driving every possible route along the map. The purpose is to "survey" the osm data as if in a car. My ultimate objective is to find every unique journey segment of five miles, I am aware that there will be a LOT of them.
I am using pgrouting/postgis and have created a topology from roads. I've also written an algorithm that given any osm_id will find all connected osm_id's to a depth of N. This works by finding all connected osm_ids and then recursing through these until the depth is reached.
I could modify this to change N to a distance of five miles.
But is there a better way of traversing every possible path in a network?
For information, here is my current algorithm which is sub-optimal as it does not deal well with junctions that have more than one connection
** Find connections **
CREATE OR REPLACE FUNCTION ng_research.get_connections(id bigint, table_param character varying) RETURNS bigint AS $BODY$ DECLARE ret_vals integer ; BEGIN --quite simply given a source node for a line string returns all of the connected nodes including its own target WITH CTE AS ( SELECT source from ng_research.all_roads WHERE osm_id=id ) SELECT array_agg(osm_id) into ret_vals FROM ng_research.all_roads AR,CTE WHERE AR.target=CTE.source or AR.source=CTE.source; RETURN ret_vals; END; $BODY$ LANGUAGE plpgsql VOLATILE
** Build linestring arrays **
CREATE OR REPLACE FUNCTION ng_research.road_string_finder(node bigint, table_param character varying, depth integer default 0, max_depth integer default 2, previous_nodes bigint DEFAULT NULL::integer) RETURNS bigint AS $BODY$ DECLARE connected_nodes bigint; node_var integer; BEGIN IF depth = 0 THEN DROP TABLE IF EXISTS ng_research.nodes_visited; CREATE TABLE ng_research.nodes_visited (id bigint); END IF; previous_nodes := array_append(previous_nodes, node); SELECT ng_research.get_connections(node, table_param) INTO connected_nodes; IF connected_nodes IS NOT NULL THEN FOREACH node_var IN ARRAY connected_nodes LOOP IF NOT (node_var = ANY(previous_nodes)) THEN RAISE NOTICE '% : %', node_var, previous_nodes; IF depth < max_depth THEN IF (SELECT node_var from ng_research.nodes_visited WHERE id=node) IS NULL THEN SELECT ng_research.road_string_finder(node_var, table_param, depth + 1, max_depth, previous_nodes) INTO previous_nodes; INSERT INTO ng_research.nodes_visited (id) VALUES (node_var); END IF; END IF; ELSE RAISE NOTICE 'SEEN YOU'; END IF; END LOOP; END IF; IF array_length(previous_nodes,1) > 1 THEN previous_nodes := array_remove(previous_nodes, node); END IF; return previous_nodes; END; $BODY$ LANGUAGE PLPGSQL;
** find connections for a single linestring **
SELECT ng_research.road_string_finder(204359430, 'ng_research.all_roads',0,5);