Sorting a multiple river stream branch structure

I have a list of numbered Stream segments. And each one lists the next down stream stream segment. The last stream segment of course has no down stream segment referenced.

I need to order the entire river, starting from the topmost stream and progressing down stream. At junctions I need to jump to the top of the next branch, work down stream to the junction, then continue to the next branch. There may be multiple branches (any number) joined at a junction.

For example: Sub5 flows to Sub 12 SubSINK is the LAst stream segment. UNSORTED:

#####START_TOPOLOGY_BLOCK##########|###########|###########|###########|
Sub5,2454692.294,2603426.954,2456317.294,2596676.954,Sub12
Sub7,2453067.294,2598176.954,2453317.294,2596676.954,Sub12
Sub11,2462692.294,2607676.954,2461067.294,2605176.954,Sub12
Sub13,2449817.294,2601426.954,2450317.294,2593176.954,SubSINK
Sub2,2464567.294,2596801.954,2467317.294,2585676.954,Sub12
Sub12,2469942.294,2601051.954,2470817.294,2593676.954,Sub13
Sub1,2436567.294,2599676.954,2433067.294,2594676.954,Sub2
Sub3,2481067.294,2601301.954,2483067.294,2594676.954,Sub5
Sub4,24开发者_开发知识库55817.294,2588801.954,2458317.294,2576426.954,Sub5
Sub6,2445067.294,2592926.954,2452817.294,2585176.954,Sub7
Sub8,2457942.294,2593551.954,2461067.294,2587426.954,Sub11
Sub9,2471442.294,2592676.954,2467817.294,2585676.954,Sub11
Sub10,2435692.294,2595176.954,2436567.294,2591176.954,Sub11

SORTED:

#####START_TOPOLOGY_BLOCK##########|###########|###########|###########|
Sub6,2445067.294,2592926.954,2452817.294,2585176.954,Sub7
Sub7,2453067.294,2598176.954,2453317.294,2596676.954,Sub12
Sub9,2471442.294,2592676.954,2467817.294,2585676.954,Sub11
Sub10,2435692.294,2595176.954,2436567.294,2591176.954,Sub11
Sub8,2457942.294,2593551.954,2461067.294,2587426.954,Sub11
Sub11,2462692.294,2607676.954,2461067.294,2605176.954,Sub12
Sub1,2436567.294,2599676.954,2433067.294,2594676.954,Sub2
Sub2,2464567.294,2596801.954,2467317.294,2585676.954,Sub12
Sub4,2455817.294,2588801.954,2458317.294,2576426.954,Sub5
Sub3,2481067.294,2601301.954,2483067.294,2594676.954,Sub5
Sub5,2454692.294,2603426.954,2456317.294,2596676.954,Sub12
Sub12,2469942.294,2601051.954,2470817.294,2593676.954,Sub13
Sub13,2449817.294,2601426.954,2450317.294,2593176.954,SubSINK

How can I do this efficiently ?? Thank you

Regards Rudy

2nd Example of River Topology

Sub16,2454692.294,2603426.954,2456317.294,2596676.954,Sub17 Sub7,2453067.294,2598176.954,2453317.294,2596676.954,Sub9 Sub8,2462692.294,2607676.954,2461067.294,2605176.954,Sub9 Sub4,2449817.294,2601426.954,2450317.294,2593176.954,Sub5 Sub1,2464567.294,2596801.954,2467317.294,2585676.954,Sub2 Sub14,2469942.294,2601051.954,2470817.294,2593676.954,Sub15 Sub19,2436567.294,2599676.954,2433067.294,2594676.954,Sub20 Sub13,2481067.294,2601301.954,2483067.294,2594676.954,Sub20 Sub10,2455817.294,2588801.954,2458317.294,2576426.954,Sub11 Sub6,2445067.294,2592926.954,2452817.294,2585176.954,Sub11 Sub17,2457942.294,2593551.954,2461067.294,2587426.954,Sub18 Sub15,2471442.294,2592676.954,2467817.294,2585676.954,Sub18 Sub9,2435692.294,2595176.954,2436567.294,2591176.954,Sub10 Sub2,2475817.294,2597426.954,2474067.294,2594176.954,Sub3 Sub18,2481442.294,2593801.954,2482567.294,2587926.954,Sub19 Sub12,2484817.294,2588051.954,2483817.294,2584676.954,Sub13 Sub21,2478067.294,2592801.954,2481317.294,2587676.954,SubSINK Sub5,2437942.294,2589801.954,2437067.294,2587176.954,Sub6 Sub3,2439442.294,2589801.954,2439317.294,2589676.954,Sub5 Sub20,2435067.294,2583801.954,2441067.294,2574426.954,Sub21 Sub11,2476317.294,2590801.954,2476067.294,2590426.954,Sub12 Sub32,2473067.294,2587301.954,2468317.294,2583426.954,Sub31 Sub33,2469817.294,2557926.954,2461317.294,2549426.954,Sub31 Sub33,2475942.294,2590551.954,2475817.294,2590426.954,Sub31 Sub34,2477692.294,2582426.954,2474567.294,2573926.954,Sub26

You need to represent your segments as a graph data structure. Then, familiar graph algorithms like DFS, BFS and topological sort should do the work for you, depending on what you need exactly.

If you could clarify your question with a simple example or a picture so it's clearly understood which sorting order you need, I may be able to provide a more specific direction.

Something simple along the following lines hopefully demonstrates how to create the proper river graph and all the methods needed to traverse on it.

class Point:
    def __init__(self, x, y): self.xy= float(x), float(y)

def _insert(G, n, x, y, kind= 0):
    if n[kind] not in G: G[n[kind]]= [[], [], Point(x, y)]
    G[n[kind]][kind].append(n[not kind])

class River:
    def __init__(self, S= None):
        self.G= {}
        if S is not None:
            for s in S: self.insert(s)

    def insert(self, s):
        n= s[0], s[5]
        _insert(self.G, n, s[1], s[2])
        _insert(self.G, n, s[3], s[4], 1)

    def degree(self, n, kind= 1): return len(self.G[n][kind])

    def sink(self):
        for n in self.G:
            if not self.G[n][0]: return n

    def traverse(self, n0, fun, level= 0):
        for n1 in self.G[n0][1]:
            self.traverse(n1, fun, level+ 1)
            fun(n0, n1, level)

And a test

if __name__ == '__main__':
    import csv
    reader= csv.reader(open('river.dat', 'r'))
    reader.next()
    r= River([s for s in reader])
    def fun(n0, n1, level):
        """segment (n1, n0) has:
        level, indicating a 'hop' distance from the sink
        degree(n1, 1), in degree to segment (0 indicates a source)
        n1, id of segments start
        n0, id of segments end
        degree(n0, 0), out degree from segment (0 indicates a sink)
        """
        print '{}:({}:{} -> {}:{})'.format(
        level, r.degree(n1), n1, n0, r.degree(n0, 0))
    r.traverse(r.sink(), fun)

will print:

3:(0:Sub3 -> Sub5:1)
3:(0:Sub4 -> Sub5:1)
2:(2:Sub5 -> Sub12:1)
3:(0:Sub6 -> Sub7:1)
2:(1:Sub7 -> Sub12:1)
3:(0:Sub8 -> Sub11:1)
3:(0:Sub9 -> Sub11:1)
3:(0:Sub10 -> Sub11:1)
2:(3:Sub11 -> Sub12:1)
3:(0:Sub1 -> Sub2:1)
2:(1:Sub2 -> Sub12:1)
1:(4:Sub12 -> Sub13:1)
0:(1:Sub13 -> SubSINK:0)

Edit: With your second example. First note that you have more than 1 sink. If that's intentional, it should be quite straightforward to handle forests as well (like letting sink return all of them and then process traversing in a loop). But anyway with the first 22 rows the output is:

5:(0:Sub16 -> Sub17:1)
4:(1:Sub17 -> Sub18:1)
5:(0:Sub14 -> Sub15:1)
4:(1:Sub15 -> Sub18:1)
3:(2:Sub18 -> Sub19:1)
2:(1:Sub19 -> Sub20:1)
7:(0:Sub7 -> Sub9:1)
7:(0:Sub8 -> Sub9:1)
6:(2:Sub9 -> Sub10:1)
5:(1:Sub10 -> Sub11:1)
7:(0:Sub4 -> Sub5:1)
9:(0:Sub1 -> Sub2:1)
8:(1:Sub2 -> Sub3:1)
7:(1:Sub3 -> Sub5:1)
6:(2:Sub5 -> Sub6:1)
5:(1:Sub6 -> Sub11:1)
4:(2:Sub11 -> Sub12:1)
3:(1:Sub12 -> Sub13:1)
2:(1:Sub13 -> Sub20:1)
1:(2:Sub20 -> Sub21:1)
0:(1:Sub21 -> SubSINK:0)

Edit 2: My answer is more to give some ideas how to handle the river tree itself. For your particular application you most probable can find better ways to actually handle the points. But anyway you can access them now like:

In []: r.G['Sub8'][2].xy
Out[]: (2462692.294, 2607676.954)
In []: r.G['Sub8'][2].xy[0]
Out[]: 2462692.294

You may also ignore totally the class Point and modify _insert like:

def _insert(G, n, x, y, kind= 0):
    # if n[kind] not in G: G[n[kind]]= [[], [], Point(x, y)]
    if n[kind] not in G: G[n[kind]]= [[], [], (x, y)]
    G[n[kind]][kind].append(n[not kind])

Then you'll access points like:

In []: r.G['Sub8'][2]
Out[]: ('2462692.294', '2607676.954')
In []: r.G['Sub8'][2][0]
Out[]: '2462692.294'