Например:
Шаг 1: Имеется четыре регистра
[r1, r2, r3, r4]
Шаг 2 (ввод): Примеры инструкций:
g1[r1, r3]
g2[r4]
g3[r3]
g4[r2]
g5[r1, r3]
g6[r1]
g1 [r1, r3] означает, что регистры r1 и r3 используются инструкцией g1. Таким образом, любая другая инструкция с r1 или r3 или обоими может быть выполнена только после g1, то есть g3, потому что она является зависимой.
Однако регистр для g2 является запасным, поэтому он может выполняться параллельно с g1, поскольку он независим. После выполнения g1, g3 также становится независимым.
Шаг 3 (не требуется): Основываясь на приведенных выше инструкциях, образец визуализации графика может быть (нарисован вручную):
Шаг 4: Go код будет выглядеть так:
package main
import (
"fmt"
"github.com/twmb/algoimpl/go/graph"
)
func main() {
g := graph.New(graph.Directed)
instruction := make(map[string]graph.Node, 0)
instruction["g1"] = g.MakeNode()
instruction["g2"] = g.MakeNode()
instruction["g3"] = g.MakeNode()
instruction["g4"] = g.MakeNode()
instruction["g5"] = g.MakeNode()
instruction["g6"] = g.MakeNode()
for key, node := range instruction {
*node.Value = key
}
// Connect dependent edges
g.MakeEdge(instruction["g1"], instruction["g3"])
g.MakeEdge(instruction["g1"], instruction["g5"])
g.MakeEdge(instruction["g3"], instruction["g5"])
g.MakeEdge(instruction["g5"], instruction["g6"])
sorted := g.TopologicalSort()
for i := range sorted {
fmt.Println(*sorted[i].Value)
}
}
Проблема:
Сейчас я вручную подключаю зависимые ребра. Но если количество вводимых инструкций увеличится, подключение вручную будет невозможно. Поэтому я хочу знать, как написать код, который автоматически построит граф зависимостей на основе ввода (шаг 1 и шаг 2).
Это будет DAG, и топологическая сортировка будет использоваться для сортировки порядка выполнения, и на выходе будет
Шаг 5 (вывод): Пример вывода приведенный выше код (может быть в другой форме):
g1, g2, g4, g3, g5, g6