[postgis-users] Topology/Network problem

[Stephen Woodbridge]

Hi,

Sorry for the cross post.

I think this is the kind of problem that one would typical ask of a 
topological model or maybe a graph model, but I'm pretty sure the 
topology code will not answer it yet :), And I'm pretty sure that 
pgRouting can not answer it yet either.

Basically I want to tag all the edges in my table with respect to 
whether they are connected or not. In graph theory this can be done with 
a simple depth first search and update the graph_id with a unique number 
for all edges connected to the graph with a unique number for that graph.

Table:
edge_id,    unique id for edge
source,     unique node number for start of edge
target,     unique node number for end of edge
             all interconnected edges will have a matching source or
             target node number
direction,  TF, FT, or ''|NULL to represent direction of travel
graph,      column to mark, all interconnected edges in the graph will
             will be marked with the same graph identifier
the_geom,   more columns
  ...

So I wrote the following code based on a recursive algorithm, but this 
generates a stack overflow very quickly. So I am thinking that this 
needs to be transformed into an iterative algorithm, but that needs a 
queue or stack to hold edges that have not been chased yet. That got me 
thinking that maybe there is a better way to do this with set theory 
along the lines:

loop while
   get a start edge from the table that is not marked
   initiate a queue and push this edge onto the queue
   mark the edge in the queue with graph_id number
   loop on queue
     replace the queue with the set of edges connected to those in the 
  queue and not already marked
     mark the edges in the queue with graph_id number
   end loop
   increment the graph_id number
end loop

I'm not sure what is an efficient way to replace the queue, this might 
be multiple steps in SQL.

The above assumes that all streets are two way and does not deal with 
the direction column which is used to identify oneway streets. 
"direction" can be FT - from -> to direction of travel, TF -  to - from 
direction of travel, otherwise it is assumed to be two way.

I realize that this is a little off-topic to the postgis list, but I 
hope it has value and interest to most of the list regardless.

Thanks,
   -Steve

--
-- tag-graphs - SQL functions to implement a depth first search on the
--              nodes of pgRouting prepped st table and tag each unique
--              interconnected set of edges as a unique graph.
--

CREATE OR REPLACE FUNCTION mark_edge(nid integer, g integer)
   RETURNS integer AS
$BODY$
DECLARE
     rec RECORD;
     cnt integer := 0;

BEGIN
     FOR rec IN SELECT gid, source, target FROM st
                 WHERE graph IS NULL AND (source=nid OR target=nid) LOOP
         cnt := cnt + 1;

         --RAISE NOTICE 'found gid=%, nid=%', rec.gid, nid;
         UPDATE st SET graph=g WHERE gid=rec.gid;
         IF rec.target=nid THEN
             cnt := cnt + mark_edge(rec.source, g);
         ELSE
             cnt := cnt + mark_edge(rec.target, g);
         END IF;
     END LOOP;
     RETURN cnt;
END;
$BODY$
   LANGUAGE 'plpgsql' VOLATILE STRICT
   COST 100;


CREATE OR REPLACE FUNCTION tag_graphs()
   RETURNS text AS
$BODY$
DECLARE
     g integer := 1;
     nid integer;
     cnt integer;

BEGIN
     BEGIN
         ALTER TABLE st ADD COLUMN graph integer;
     EXCEPTION
         WHEN duplicate_column THEN
             UPDATE st SET graph=NULL;
     END;

     LOOP
         SELECT INTO nid source FROM st WHERE graph IS NULL LIMIT 1;
         EXIT WHEN NOT FOUND;

         SELECT INTO cnt  mark_edge(nid, g);
         RAISE NOTICE 'graph % with % edges, starting with node % 
marked.', g, cnt, nid;
         g := g + 1;
     END LOOP;

     RETURN g::text || ' graphs found.';
END;
$BODY$
   LANGUAGE 'plpgsql' VOLATILE STRICT
   COST 100;