title: How to determine Strahler number on a directed graph for a stream network
body: <h1>Question / example / expected values</h1>
  
  <p>I need to determine a <a href="https://en.wikipedia.org/wiki/Strahler_number" rel="nofollow noreferrer"><strong>Strahler number</strong></a> or <em>Strahler stream order</em> for a directed graph representing a stream network. I can derive information <a href="https://stackoverflow.com/q/28688264/327026">forwards and backwards using <code>WITH RECURSIVE</code> queries</a>, but it seems I need to do something different to determine the Strahler number.</p>
  
  <p>For example, here is a 19 segment stream network with 10 tributaries and one outlet. The upstream portion of each segment is represented by a node ID.</p>
  
  <p><img src="https://i.imgur.com/UXu1da1.png" alt="stream_nodes"></p>
  
  <p>And the same data in a table structure, where the segments are connected by <code>to_node</code>, which is null for the basin outlet.</p>
  
  <pre><code>CREATE TABLE streams (
    node integer PRIMARY KEY,
    to_node integer REFERENCES streams(node),
    expected_order integer
  );
  INSERT INTO streams(node, to_node, expected_order) VALUES
  (1, NULL, 4),
  (2, 1, 4),
  (3, 2, 3),
  (4, 2, 3),
  (5, 4, 3),
  (6, 3, 2),
  (7, 3, 2),
  (8, 5, 2),
  (9, 5, 2),
  (10, 6, 1),
  (11, 6, 1),
  (12, 7, 1),
  (13, 7, 1),
  (14, 8, 1),
  (15, 8, 1),
  (16, 9, 1),
  (17, 9, 1),
  (18, 4, 1),
  (19, 1, 1);
  </code></pre>
  
  <p>The expected result (<code>expected_order</code>) for the Strahler numbers is visualized here:</p>
  
  <p><img src="https://i.stack.imgur.com/ZczT8.png" alt="expected_stream_order"></p>
  
  <p>There are three rules (from the <a href="http://svn.osgeo.org/grass/grass-addons/grass7/raster/r.stream.order/r.stream.order.html" rel="nofollow noreferrer">GRASS 7.0 Manual</a>):</p>
  
  <ol>
  <li>if the node has no children, it's Strahler order is 1.</li>
  <li>if the node has one and only one tributary with Strahler greatest order <em>i</em>, and all other tributaries have order less than i, then the order remains <em>i</em>.</li>
  <li>if the node has two or more tributaries with greatest order <em>i</em>, then the Strahler order of the node is <em>i</em> + 1.</li>
  </ol>
  
  <h1>What I've found / tried</h1>
  
  <p>From what I have found in digging to solve this problem is that this calculation <a href="http://proceedings.esri.com/library/userconf/proc12/papers/16_10.pdf" rel="nofollow noreferrer">can be done with SQL</a> (except I think their "SQL script" is written for MS SQL Server). However, I haven't found something that can be done with PostgreSQL 9.1.</p>
  
  <p>One of the best attempts I have is to count the number of upstream nodes from each node, which correctly identifies the tributaries (1st order), but not others:</p>
  
  <pre><code>WITH RECURSIVE search_graph AS (
    SELECT node AS start_node, node
    FROM streams
    -- Connect downstream towards outlet(s)
    UNION ALL
    SELECT sg.start_node, n.node
    FROM streams n
    JOIN search_graph sg ON n.to_node = sg.node
  )
  SELECT start_node, count(sg.node) as upstream_nodes, expected_order
  FROM search_graph sg
  JOIN streams s ON sg.start_node = s.node
  GROUP BY start_node, expected_order
  ORDER BY upstream_nodes DESC, start_node;
  
   start_node | upstream_nodes | expected_order
  ------------+----------------+----------------
            1 |             19 |              4
            2 |             17 |              4
            4 |              9 |              3
            3 |              7 |              3
            5 |              7 |              3
            6 |              3 |              2
            7 |              3 |              2
            8 |              3 |              2
            9 |              3 |              2
           10 |              1 |              1
           11 |              1 |              1
           12 |              1 |              1
           13 |              1 |              1
           14 |              1 |              1
           15 |              1 |              1
           16 |              1 |              1
           17 |              1 |              1
           18 |              1 |              1
           19 |              1 |              1
  (19 rows)
  </code></pre>
  
  <p>An idea is to use a <code>nth_value(value any, nth integer)</code> <a href="http://www.postgresql.org/docs/9.1/static/functions-window.html" rel="nofollow noreferrer">window function</a> with an <a href="http://www.postgresql.org/docs/9.1/static/sql-expressions.html#SYNTAX-WINDOW-FUNCTIONS" rel="nofollow noreferrer">appropriately set window frame range</a>. However, I'm not sure how to set this up, or if it can be set up to identify Strahler numbers. Another [less exciting] idea is to manually run iterations for each Strahler number, which I expect to be between five and eight orders (iterations) for my real world data. This can be done with a <a href="http://www.postgresql.org/docs/9.1/static/sql-do.html" rel="nofollow noreferrer"><code>DO</code> statement</a>. But any better ideas would be most welcome.</p>