go - 在 Go 中遍历 child 的谱系

Question

我有一个庞大的人口谱系( map[int][]int )，其中关键是动物和值(value) slice 中的 parent (两个)。没有 parent 的动物将有 parent 的负整数。

其次，我有一个我想 build 的动物列表具体谱系并写入文件。我列表谱系中的所有动物都应该写入同一个文件。

pedigree := map[int][]int{
    1:  []int{2, 3},
    2:  []int{-1, 5},
    3:  []int{6, 7},
    4:  []int{8, 9},
    5:  []int{-1, -2},
    6:  []int{8, -2},
    7:  []int{-1, -2},
    8:  []int{-1, -2},
    9:  []int{10, -2},
    10: []int{-1, 4}
}

list := []int{1, 4}

以及我对 io.Writer 编写的文件的期望:

  1   2   3
  2  -1   5
  3   6   7
  5  -1  -2
  6   8  -2
  7  -1  -2
  8  -1  -2
  4   8   9
  9  10  -2
 10  -1   4

所以我需要一个递归函数来遍历从基础动物开始的谱系，然后在所有路径上继续，直到达到负数的 parent 。

更重要的是 我列表中的动物被确定为导致谱系循环的动物(动物 4 成为自己的伟大 parent )。

我已经使用以下代码进行了尝试:

type tree struct {
    sire   *tree
    dam    *tree
    animal int
    base   int
    path   []int
}

func newTree(a, s, d, b int) tree {
    return tree{
        animal: a,
        sire:   &tree{animal: s, base: b},
        dam:    &tree{animal: d, base: b},
        base:   b,
    }
}

for _, animal := range list {
    myTree = newTree(animal, pedigree[animal][0], pedigree[animal][1], 0)
    walk(myTree, written, fw) // written is a map of integers and fw is io.Writer
}

func walk(t tree, written map[int]int, writer io.Writer) tree {
    style := "%12d%12d%12d\n"
    if t.animal == t.base {
        return t
    }
    if t.base == 0 {  // for the first iteration
        t.base = t.animal
    }
    if _, ok := written[t.animal]; !ok {
        sire := t.sire.animal
        dam := t.dam.animal
        if sire == 0 {
            sire = t.base
        }
        if dam == 0 {
            dam = t.base
        }
        written[t.animal] = 0
        io.WriteString(writer, fmt.Sprintf(style, t.animal, sire, dam))
    }
    // Shift forward.
    if t.sire.animal > 0 {
        myTree := newTree(t.sire.animal, pedigree[t.sire.animal][0], pedigree[t.dam.animal][1], t.base)
        walk(myTree, written, writer)
    }
    if t.dam.animal > 0 {
        myTree := newTree(t.dam.animal, pedigree[t.dam.animal][0], pedigree[t.dam.animal][1], t.base)
        walk(myTree, written, writer)
    }
    return t
}

我的谱系由大约 1300 万只动物组成，但我无法让函数停在正确的位置并获得 stack overflow几只动物完成后 panic 。我相信我的一些问题是:

参与循环的动物是基础动物，所以我应该检查 animal == base (1->2->3->1)

参与循环的动物是不是 基础动物(1->2->3->4->5->6->3)

任何帮助将不胜感激。

Answer 1

由于您的系谱图中可以有循环，因此您可能会陷入这样的循环。这意味着您必须检测循环并停止在那里构建。你可以通过稍微改变你的树来做到这一点。

首先，您传递了 tree按值对象，但附加指向它的指针。将指针传递给周围的树:

func walk(t *tree, written map[int]int, writer io.Writer) *tree {
}

更好的方法可能是:

func (t *tree) walk(written map[int]int, writer io.Writer) {...}

您还应该添加 *parent到树，以便您可以检测循环:

type tree struct {
    parent *tree
    sire   *tree
    dam    *tree
    animal int
    base   int
    path   []int
}

每次创建新关卡时，适当设置父级:

myTree := newTree(t.sire.animal, pedigree[t.sire.animal][0], pedigree[t.dam.animal][1], t.base)
myTree.parent=t
myTree.walk(written, writer)

然后添加一个函数来测试你是否进入循环:

func (t *tree) loop(animal int) bool {
   for t!=nil {
       if t.animal==animal {
          return true
       }
       t=t.parent
   }
   return false
}

并检查您是否正在进入循环:

if !myTree.loop(myTree.animal) {
   myTree.walk(written, writer)
}