Depth First Search Function

[woodbri]

The follow question was posted to the postgis list. This could be easily solved using pgrouting is we had a generic function(s) that would to a breadth first or depth first traversal of a graph. If the traversal function took a set of edges with the pgrouting topology, a flag to indicate breath or depth first, and a user supplied function name that implements some standard arguments, then the traversal function could call the user supplied function passing something like myfunc(node_id_from_parent, node_id_from, node_id_to, edge_id, edge_id_parent) or something like that and the user function could then apply arbitrary computations on the edge.

A----e1----B----e2-----C

Where the current edge is B-e2-C and the parent edge is A-e1-B.

A general purpose graph traversal function would allow users a lot of flexibility to implement custom algorithms for graph analysis, labeling, and other search algorithms that are common to graph problems.

------------- email from postgis list -------------------
I want to go down the (all unnamed) roads in my future mountain
community assigning house numbers every 50 meters.

   50-100   170-200
    /         /
1  / 107 147 /  213
+-+---+---+-+----+--240--main-road--
2 48   \   168
        \
      120-140

I stay on my main road, but whenever encountering a fork, first go down it.
"Depth first pre-order ordered labeled rooted binary tree traversal but with central path"?
http://math.stackexchange.com/questions/1856814/binary-tree-traversal-with-fixed-final-node

OK for PostGIS, given a few linestrings, I suppose I first (somehow)
connect them to form a network, then ride my virtual car down it. And
whenever my odometer reaches another 50m, make a mark on the centerline.
(Assume a strict binary tree (mountain roads with no 4-way junctions))
At each road junction I first choose a side road, and if already on a
side road, first choose the left road, before choosing the right road.
When backtracking turn off my odometer, until finally back on to my main
road.

Holy smokes, sounds tough. Can I do this with PostGIS or should I go
back to GRASS or what?

(I am thinking instead of using ST_OffsetCurve (previous project, thanks
Sandro) to put odd on the left even on the right, down the centerline
I'll just put odd numbers at 25, 75m, padded "1 ", and even at 50, 100m
reverse padded " 2".) These points and their labels are what I want for output.

[jidanni]

Thanks. What might be a unique traversal I discovered would be the first to use this.
http://jidanni.org/geo/house_numbering/taizhong/dongshi/zaokeng.html

[cvvergara]

@krashish8
I know we have this one now.
We need to put appropriate labels, link to PR, and close

[cvvergara]

A detailed specification can be found on #1348
The Functionality has been added #1599

[krashish8]

Also, the breadth-first search functionality has been added in this PR: #1240