Пройдите родословную от ребенка в Go - PullRequest
Новая
       5

Пройдите родословную от ребенка в Go

0 голосов
/ 28 февраля 2020

У меня большая популяционная родословная (map[int][]int), где ключом является животное, а родители (два) в срезе значения. Животные без родителей будут иметь отрицательные целые числа для родителей.

Во-вторых, у меня есть список животных, для которых я хочу построить свои родословные специфицированные c и записать в файл. Родословная всех животных из моего списка должна быть записана в один файл. 

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
}

Моя родословная состоит из примерно 13 миллионов животных , но я не могу заставить функцию остановиться в нужной точке и получить stack overflow pani c после нескольких животных. Я считаю, что некоторые из моих проблем:

  • Животное, которое участвует в цикле, является базовым животным, поэтому я должен проверить, является ли animal == base (1->2->3->1)
  • Животным, которое является участие в цикле НЕ базовое животное (1->2->3->4->5->6->3)

Любая помощь будет оценена.

1 Ответ

2 голосов
/ 28 февраля 2020

Поскольку у вас могут быть петли на вашей родословной карте, вы, вероятно, попадаете в один из таких l oop. Это означает, что вы должны обнаружить петли и перестать строить там. Вы можете сделать это, немного изменив дерево.

Сначала вы передаете объект 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)

Затем добавьте функцию для проверки, если вы вводите al oop: 

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

И проверьте, вводите ли вы все oop: 

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