# Strahler order of a graph(drainage network)

How can I find the Strahler order of a drainage network in Mathematica? For example the link created by joining links of order $i$ and $j$ is given by $k=max(i,j,Int\frac{1}{2}(i+j))$. The image of the drainage network is attached below. I have created the Skeleton graph of the original binary image by Morphological processing ie., by repeated erosion and dilation. I want to ascertain the network properties of the graph.

i=Import["D:\\class_shp_1.png"]
im=MorphologicalBinarize[i]
imo=Opening[im,DiskMatrix[15]]
ime=Erosion[imo, DiskMatrix[1]]
imed=Dilation[ime,DiskMatrix[1]]
imedel=DeleteSmallComponents[imed]
imedt=Thinning[imedel, Infinity]
imsk=SkeletonTransform[imedt]
immorph=MorphologicalGraph[imsk,VertexLabels->"Name"]


This generates the Graph as shown below for which I want to assign the Strahler order for each link. The strahler order for rivers is given by the above mentioned formula for $k$.

• What have you tried in terms of implementing the Strahler order? – b3m2a1 Aug 2 '18 at 17:07
• I am new to graph theory but for hydrological purposes I have used a Digital elevation model to define the natural flow direction and then compute the Strahler order based on angle of intersections and if the links are primary or not. I have not implemented it in Mathematica – vbj Aug 2 '18 at 17:11
• Try it in Mathematica and post where you get stuck. We tend to prefer to help people with where they are stuck, rather than just implementing things for people when they haven't tried it yet. – b3m2a1 Aug 2 '18 at 17:16
• This can be implemented with DepthFirstScan and "PostVisitVertex". The next version of IGraph/M will include this (implemented in C, not as mentioned here). Teaser: i.stack.imgur.com/m2tmQ.png – Szabolcs Nov 26 '18 at 10:29
• Can you contribute an interesting image that I could use as an illustration in the documentation? – Szabolcs Nov 26 '18 at 17:59

### NOT AN IMPLEMENTATION OF STRAHLER ORDER (but cleaner way to get the graph)

This appears to work:

g = ImageTake[
Import["https://i.stack.imgur.com/oBAuc.png"], {5, -5}, {5, -5}] // Dilation[#, 1] & // Binarize // MorphologicalGraph


And you can see the more standard formatting like this:

Graph[EdgeList@g]


### THIS HAS EVEN LESS TO DO WITH STRAHLER ORDER

Just as a fun thing we can use what I did here to turn this into a single radial graph:

sg = spoolGraph@g


where the vertex degree encodes the path length.

We can also see this in reverse:

ug = unSpoolGraph@sg


And although I don't have a metric for it, this and the original are isomorphic up to shifting of these nodes along these paths. That means it should preserve anything that only depends on the neighbors / length of chain you're on.

• Thanks for the answer. I did proceed til this step but I want to label the links depending on the strahler order like a link with order 1 and other with the same order gives a 2nd order link and so on – vbj Aug 2 '18 at 16:36
• @vbj I have no idea what that means (I don't know how the Strahler order corresponds to more standard graph properties) but you should put that in your post. And if the question isn't about generating the Graph you should provide the code that makes the graph, not the image. – b3m2a1 Aug 2 '18 at 16:38
• I have updated the question with codes and figure. – vbj Aug 2 '18 at 16:51