在围棋中从孩子身上走过一个谱系

Question

我有一个大的群体谱系(map[int][]int)，其中关键是动物，而父母(两个)在价值切片。没有父母的动物会对父母有负整数。

其次，我有一个动物列表，我想要建立他们的特定的血统，并写入一个文件。我名单上所有的动物血统都应该写在同一个档案里。

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

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

，更重要的是，，在我的名单中，动物被认为是引起系谱循环的动物(动物4成为自己的伟大父母)。

我尝试了以下代码：

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恐慌。我相信我的一些问题是：

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

• An动物是，而不是，基础动物(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)
}