Сортировка нескольких ветвей речной структуры - PullRequest
Новая
       8

Сортировка нескольких ветвей речной структуры

2 голосов
/ 05 мая 2011

У меня есть список пронумерованных сегментов потока.И каждый перечисляет следующий сегмент потока вниз по течению.Последний сегмент потока, конечно, не имеет ссылки на сегмент нисходящего потока.

Мне нужно упорядочить всю реку, начиная с самого верхнего потока и прогрессируя вниз по течению.На перекрестках мне нужно прыгнуть на вершину следующей ветви, перейти вниз по течению до перехода, затем перейти к следующей ветви.Может быть несколько ветвей (любое число), соединенных в соединении.

Например: Sub5 переходит к Sub 12 SubSINK - это сегмент потока LAst.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,2455817.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

Как я могу сделать это эффективно ??Спасибо

С уважением, Руди

2-й пример топологии реки

START_TOPOLOGY_BLOCK ########## | ########### | ########### | ########### |* 1016., 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 Sub18,2481442.294,2593801.954,2482567.294,2587926.954, Sub19 Sub12 2484817.294,2588051.954,2483817,294,2584676.954, Sub13 Sub21,2478067.294,25928317544676,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

Ответы [ 2 ]

1 голос
/ 05 мая 2011

Что-то простое в следующих строках, мы надеемся, демонстрирует, как создать правильный граф реки и все методы, необходимые для его прохождения. 

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)

И тест 

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)

будетпечать: 

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)

Редактировать : с вашим вторым примером.Сначала обратите внимание, что у вас более 1 раковины.Если это преднамеренно, то также должно быть достаточно просто обрабатывать леса (например, позволить приемнику вернуть все из них, а затем обработать обход в цикле).Но в любом случае с первыми 22 строками получается: 

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 : Мой ответ - дать несколько идей о том, как обращаться с деревом реки.Для вашего конкретного приложения вы, вероятнее всего, сможете найти более эффективные способы решения проблем.Но в любом случае вы можете получить к ним доступ сейчас, например: 

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

Вы также можете полностью игнорировать class Point и изменить _insert следующим образом: 

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])

Тогда вы получите такие точки доступа, как: 

In []: r.G['Sub8'][2]
Out[]: ('2462692.294', '2607676.954')
In []: r.G['Sub8'][2][0]
Out[]: '2462692.294'
1 голос
/ 05 мая 2011

Вам необходимо представить свои сегменты в виде структуры данных графа.Затем знакомые алгоритмы графов, такие как DFS, BFS и топологическая сортировка, должны выполнить работу за вас, в зависимости от того, что вам нужно.

Если вы могли бы прояснить свой вопрос с помощью простого примера или рисунка, чтобы было ясно, какиеПорядок сортировки вам нужен, возможно, я смогу дать более конкретное направление.

...