1

I want to identify subgraphs within the planet_osm_line table of the osm2pgsql-schema. those subgraphs are classified by certain tags i want to check. My first attempt was to do this recursively with a sql-function like this:

CREATE FUNCTION private.find_subgraphs() RETURNS void AS $$
DECLARE
    good_way RECORD;
    id_rec RECORD;
    next_subgraph_rec RECORD;
    id BIGINT;
    next_subgraph_id BIGINT;
BEGIN
    SELECT osm_id FROM private.good_ways WHERE subgraph_id IS NULL LIMIT 1 INTO id_rec;
    id := id_rec.osm_id;
    WHILE (id IS NOT NULL) LOOP
        SELECT nextval('private.subgraph_seq') AS subgraph_id INTO next_subgraph_rec;
        next_subgraph_id := next_subgraph_rec.subgraph_id;

        WITH RECURSIVE waysForSubgraph(osm_id, previous_way, visited_ways, done) AS ( 
            SELECT osm_id, public.planet_osm_line.way, ARRAY[ROW(osm_id, public.planet_osm_line.way)], false 
                FROM public.planet_osm_line
                WHERE osm_id = id
            UNION ALL
            SELECT
                    public.planet_osm_line.osm_id,
                    public.planet_osm_line.way,
                    visited_ways || ROW(public.planet_osm_line.osm_id, way),
                    ROW(public.planet_osm_line.osm_id, public.planet_osm_line.way) = ANY (visited_ways)
            FROM waysForSubgraph, public.planet_osm_line JOIN private.good_ways
                ON public.planet_osm_line.osm_id = private.good_ways.osm_id
            WHERE ST_Intersects(previous_way, public.planet_osm_line.way) AND NOT done
        )
        UPDATE private.good_ways
            SET subgraph_id = next_subgraph_id 
            WHERE osm_id IN (SELECT osm_id FROM waysForSubgraph);

        SELECT osm_id FROM private.good_ways WHERE subgraph_id IS NULL LIMIT 1 INTO id_rec;
        id := id_rec.osm_id;
    END LOOP;
    RAISE NOTICE 'subgraph building done';  
END;
$$ LANGUAGE plpgsql;

I know, that the assignment of id and next_subgraph_id is not perfect, but works.

Now to the problem: For a small number of ways (like 10-20) this seems to work just fine. But when i run this on a sample of about 300 ways it looks like an infinite loop.

Does anybody have suggestions on where the actual problem is? Or does anybody have a better approach on finding subgraphs like the ones i am looking for?

Thanks in advance!

edit (in response to Mapper):

For now i am working on the lines of Germany (a little bit filtered). But here i am looking for ways that match certain criteria (like "is wihtin a forest (polygon)") and now i want to build subgraphs out of them. Of course, i am well aware of this being ressource hungry. But in this scenario it would be ok to run for one or two hours. Can you maybe a little bit more precise about that "smal set of subgraphs (Contraction hierarchies)" please? Thank you for your answer!

edit alogirthm:

For each good_way that is not in another subgraph already i look recursively for intersecting private.good_ways and than update their subgraph_id in private.good_ways with a common id i retrieve from the sequence private.subgraph_seq. The table good_ways has the osm_id of the ways that intersect forrests and the like (that match criteria for good ways). The way of a good_way is retrieved via the join with planet_oms_line. I hope you see what i try here. The problem seems to be, that the recursion is very very slow when the subgraph contains a lot of lines. But at least it should finish at some point, but it does not seem that way.

  • I'm not sure if I understand your approach right: You try to find all possible subgraphs on the graph of a whole OSM road network? Usually nobody does this calculation in preprocessing, as it's to ressource hungry. Instead routing is done with a live cost check (A*) or with a smal set of subgraphs (Contraction hierarchies). So can you please provide us more informations about your usecase and why you try to calculate what in which way? – Mapper Dec 10 '13 at 18:57
  • You needed approval to edit your question because you have multiple accounts. Please merge them to avoid this problem. – whuber Dec 10 '13 at 22:42
  • It would be much more readable if you didn't use NATURAL JOIN and you would put table names before the column names. Without knowing the table schema it's hard to guess what is being compared here: ` ST_Intersects(previous_way, way)` – Jakub Kania Dec 11 '13 at 11:50
  • Also, can you post input data for those 10 rows and result of SELECT * FROM waysForSubgraph for them? – Jakub Kania Dec 11 '13 at 12:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.