多河流分支结构的排序

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

2条回答

网友

1楼 · 编辑于 2024-06-11 22:29:13

下面简单介绍一下如何创建正确的河流图以及遍历河流图所需的所有方法。你知道吗

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)

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

网友

2楼 · 编辑于 2024-06-11 22:29:13

您需要将段表示为图形数据结构。然后，熟悉的图算法，如DFS、BFS和拓扑排序，应该为您完成这项工作，具体取决于您需要什么。你知道吗

如果你能用一个简单的例子或图片来澄清你的问题，以便清楚地了解你需要的排序顺序，我也许能提供一个更具体的方向。你知道吗

相关问题更多 >

编程相关推荐

热门问题

热门文章