当前位置： 文江博客话题详情

对多条河流支流结构进行排序

发布于 2024-11-05 01:47:38 字数 3464 浏览 2 评论 0原文

我有一个编号的流段列表。每个都列出了下一个下游流段。最后一个流段当然没有引用下游段。

我需要对整条河流进行排序，从最上面的溪流开始，一直到下游。在路口，我需要跳到下一个分支的顶部，顺流而下到路口，然后继续到下一个分支。一个交汇处可能有多个分支（任意数量）连接。

例如：Sub5 流向 Sub 12 SubSINK 是最后一个流段。 未排序：

#####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

已排序：

#####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

我怎样才能有效地做到这一点？ 谢谢你的

问候 Rudy

河流拓扑的第二个例子

START_TOPOLOGY_BLOCK##########|###########|###########|###########|

Sub16,2454692.294,2603426.954,2456317.294,2596676.954,Sub17 子7,2453067.294,2598176.954,2453317.294,2596676.954,子9 子8,2462692.294,2607676.954,2461067.294,2605176.954,子9 子4,2449817.294,2601426.954,2450317.294,2593176.954,子5 子1,2464567.294,2596801.954,2467317.294,2585676.954,子2 子14,2469942.294,2601051.954,2470817.294,2593676.954,子15 子19,2436567.294,2599676.954,2433067.294,2594676.954,子20 子13,2481067.294,2601301.954,2483067.294,2594676.954,子20 子10,2455817.294,2588801.954,2458317.294,2576426.954,子11 子6,2445067.294,2592926.954,2452817.294,2585176.954,子11 子17,2457942.294,2593551.954,2461067.294,2587426.954,子18 子15,2471442.294,2592676.954,2467817.294,2585676.954,子18 子9,2435692.294,2595176.954,2436567.294,2591176.954,子10 子2,2475817.294,2597426.954,2474067.294,2594176.954,子3 子18,2481442.294,2593801.954,2482567.294,2587926.954,子19 子12,2484817.294,2588051.954,2483817.294,2584676.954,子13 子21,2478067.294,2592801.954,2481317.294,2587676.954,SubSINK 子5,2437942.294,2589801.954,2437067.294,2587176.954,子6 子3,2439442.294,2589801.954,2439317.294,2589676.954,子5 子20,2435067.294,2583801.954,2441067.294,2574426.954,子21 子11,2476317.294,2590801.954,2476067.294,2590426.954,子12 子32,2473067.294,2587301.954,2468317.294,2583426.954,子31 子33,2469817.294,2557926.954,2461317.294,2549426.954,子31 子33,2475942.294,2590551.954,2475817.294,2590426.954,子31 子34,2477692.294,2582426.954,2474567.294,2573926.954,子26

原文

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,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

How can I do this efficiently ??
Thank you

Regards Rudy

2nd Example of River Topology

START_TOPOLOGY_BLOCK##########|###########|###########|###########|

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

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（2）

傲鸠 2024-11-12 01:47:38

您需要将段表示为图形数据结构。然后，熟悉的图算法（如 DFS、BFS 和拓扑排序）应该可以为您完成工作，具体取决于您的具体需求。

如果您可以用一个简单的示例或图片来澄清您的问题，以便清楚地了解您需要哪种排序顺序，我也许可以提供更具体的方向。

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.

回复 原文
手心的海 2024-11-12 01:47:38

以下简单的内容有望演示如何创建正确的河流图以及遍历它所需的所有方法。

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)

编辑：使用第二个示例。首先请注意，您有多个水槽。如果这是故意的，那么处理森林也应该非常简单（比如让水槽返回所有森林，然后循环处理遍历）。但无论如何，前 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)

编辑 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'

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'
回复 原文
~没有更多了~

关于作者

离鸿

暂无简介

0 文章
0 评论
24 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

胡图图

文章 0 评论 0

zt006

文章 0 评论 0

z祗昰~

文章 0 评论 0

冰葑

文章 0 评论 0

野の

文章 0 评论 0

天空

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文