title: search recursively for dead-ends in topological network table
body: <p>I've been trying for weeks to figure this out:
  I need to recursively search a topological network, OpenStreetMap streets in this case, for dead ends, and neighborhoods that hang from the rest of the network by only one edge. These are places where you might expect to see a no-exit sign if your city is considerate like that. </p>
  
  <p>My table has a record for each edge in the network. Each edge has a 'target' and 'source' field, identifying the node to which that side of the edge is connected. I've added a binary column called 'dangling' to indicate whether the edge has been identified as a dea-ending segment. I initialize this column as FALSE, assuming the best.</p>
  
  <p>So far, I've been able to get to identify simply branching dead-ends with the following SQL</p>
  
  <pre><code>WITH node_counts AS ( -- get all unique nodes
  SELECT target AS node FROM edge_table WHERE NOT dangling
  UNION ALL
  SELECT source AS node FROM edge_table WHERE NOT dangling),
  single_nodes AS ( -- select only those that occur once
  SELECT node 
  FROM node_counts
  GROUP BY node
  HAVING count(*) = 1
  ) -- 
  UPDATE edge_table SET dangling = true 
  FROM single_nodes
  WHERE node = target OR node = source;
  </code></pre>
  
  <p>I simply keep running this query until no rows are updated. 
  The result looks like this(red is dangling = true):</p>
  
  <p><a href="http://i.stack.imgur.com/OE1rZ.png" rel="nofollow">http://i.stack.imgur.com/OE1rZ.png</a></p>
  
  <p>Excellent! This is working great...but there are still cul-de-sac <em>neighborhoods</em> if you will, which are only connected to the larger network by one edge. How can I identify those?</p>
  
  <p>My best guess is that I'm going to need a WITH RECURSIVE at some point, but that's about as far as my unmathmatical mind will go. Can anyone point me in the right direction?</p>