/
7_build_order.go
142 lines (111 loc) · 2.98 KB
/
7_build_order.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
package chapter4
import (
"errors"
)
type DependencyGraph struct {
Nodes []*Project
ProjectMap map[string]*Project
}
func (graph *DependencyGraph) GetOrCreateNode(name string) *Project {
if _, ok := graph.ProjectMap[name]; !ok {
node := CreateProject(name)
graph.Nodes = append(graph.Nodes, node)
graph.ProjectMap[name] = node
}
return graph.ProjectMap[name]
}
func (graph *DependencyGraph) AddEdge(startName string, endName string) {
start := graph.GetOrCreateNode(startName)
end := graph.GetOrCreateNode(endName)
start.AddNeighbour(end)
}
func (graph *DependencyGraph) GetNodes() []*Project {
return graph.Nodes
}
type Project struct {
Children []*Project
Name string
dependencies int
ProjectMap map[string]*Project
}
func CreateProject(name string) *Project {
return &Project{
Children: nil,
Name: name,
dependencies: 0,
ProjectMap: map[string]*Project{},
}
}
func (project *Project) AddNeighbour(node *Project) {
if _, ok := project.ProjectMap[node.Name]; !ok {
project.Children = append(project.Children, node)
project.ProjectMap[node.Name] = node
node.IncrementDependencies()
}
}
func (project *Project) GetName() string {
return project.Name
}
func (project *Project) GetChildren() []*Project {
return project.Children
}
func (project *Project) GetNumberDependencies() int {
return project.dependencies
}
func (project *Project) IncrementDependencies() {
project.dependencies++
}
func (project *Project) DecrementDependencies() {
project.dependencies--
}
func BuildGraph(projects []string, dependencies [][]string) DependencyGraph {
graph := DependencyGraph{
Nodes: []*Project{},
ProjectMap: map[string]*Project{},
}
for _, project := range projects {
graph.GetOrCreateNode(project)
}
for _, dependency := range dependencies {
first := dependency[0]
second := dependency[1]
graph.AddEdge(first, second)
}
return graph
}
func FindBuildOrder(projects []string, dependencies [][]string) []*Project {
graph := BuildGraph(projects, dependencies)
return orderProjects(graph.Nodes)
}
func orderProjects(projects []*Project) []*Project {
var order []*Project
for _, project := range projects {
if project.GetNumberDependencies() == 0 {
order = append(order, project)
}
}
toBeProcessed := 0
for toBeProcessed < len(order) {
// We have a circular dependency since there are remaining projects with zero dependencies
if toBeProcessed > len(order)-1 {
panic(errors.New("circular dependency detected"))
}
// Remove project from list of dependencies
current := order[toBeProcessed]
children := current.GetChildren()
for _, child := range children {
child.DecrementDependencies()
}
// Add children that have to one depending on them
for _, child := range children {
if child.GetNumberDependencies() == 0 {
order = append(order, child)
}
}
toBeProcessed++
}
if len(order) != len(projects) {
panic(errors.New("exiting due to circular dependency"))
}
return order
}