# Traversing all possible road routes

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);
``````
• It can help to refine your definition of "path" beforehand. For instance, would it count to have a car just zig-zag back and forth along one segment until its odometer reads five miles? If so, you have an impossible task, but if not, you need to stipulate what constitutes a valid "path" or what would make two of them essentially the same for your purposes. – whuber Feb 6 '14 at 23:02
• Once you have reached your "ultimate objective" what is next step? I'm asking since these "find all possible routes" keep coming up and they never seem to have any real-life relevance and they are not defined very well. – Uffe Kousgaard Feb 7 '14 at 8:01
• The objective is simple. Find all hills in a given area. This is done by looking at the linestrings and mapping them to height data, but a hill can traverse multiple linestrings (ie. junctions) hence the need for coverage of all routes. This hopefully answers the path question as well. – user1331131 Feb 7 '14 at 9:15
• Do you have height data at junctions only or also for each node along the linestrings (segments)? In other words, how detailed should the result be? – Uffe Kousgaard Feb 7 '14 at 9:51
• I have height data from any point on any linestring (derived from the free NASA datasets) – user1331131 Feb 7 '14 at 11:43