]>
Commit | Line | Data |
---|---|---|
bae9f6d2 JC |
1 | package dag |
2 | ||
3 | import ( | |
4 | "fmt" | |
5 | "sort" | |
6 | "strings" | |
7 | ||
8 | "github.com/hashicorp/go-multierror" | |
9 | ) | |
10 | ||
11 | // AcyclicGraph is a specialization of Graph that cannot have cycles. With | |
12 | // this property, we get the property of sane graph traversal. | |
13 | type AcyclicGraph struct { | |
14 | Graph | |
15 | } | |
16 | ||
17 | // WalkFunc is the callback used for walking the graph. | |
18 | type WalkFunc func(Vertex) error | |
19 | ||
20 | // DepthWalkFunc is a walk function that also receives the current depth of the | |
21 | // walk as an argument | |
22 | type DepthWalkFunc func(Vertex, int) error | |
23 | ||
24 | func (g *AcyclicGraph) DirectedGraph() Grapher { | |
25 | return g | |
26 | } | |
27 | ||
28 | // Returns a Set that includes every Vertex yielded by walking down from the | |
29 | // provided starting Vertex v. | |
30 | func (g *AcyclicGraph) Ancestors(v Vertex) (*Set, error) { | |
31 | s := new(Set) | |
32 | start := AsVertexList(g.DownEdges(v)) | |
33 | memoFunc := func(v Vertex, d int) error { | |
34 | s.Add(v) | |
35 | return nil | |
36 | } | |
37 | ||
38 | if err := g.DepthFirstWalk(start, memoFunc); err != nil { | |
39 | return nil, err | |
40 | } | |
41 | ||
42 | return s, nil | |
43 | } | |
44 | ||
45 | // Returns a Set that includes every Vertex yielded by walking up from the | |
46 | // provided starting Vertex v. | |
47 | func (g *AcyclicGraph) Descendents(v Vertex) (*Set, error) { | |
48 | s := new(Set) | |
49 | start := AsVertexList(g.UpEdges(v)) | |
50 | memoFunc := func(v Vertex, d int) error { | |
51 | s.Add(v) | |
52 | return nil | |
53 | } | |
54 | ||
55 | if err := g.ReverseDepthFirstWalk(start, memoFunc); err != nil { | |
56 | return nil, err | |
57 | } | |
58 | ||
59 | return s, nil | |
60 | } | |
61 | ||
62 | // Root returns the root of the DAG, or an error. | |
63 | // | |
64 | // Complexity: O(V) | |
65 | func (g *AcyclicGraph) Root() (Vertex, error) { | |
66 | roots := make([]Vertex, 0, 1) | |
67 | for _, v := range g.Vertices() { | |
68 | if g.UpEdges(v).Len() == 0 { | |
69 | roots = append(roots, v) | |
70 | } | |
71 | } | |
72 | ||
73 | if len(roots) > 1 { | |
74 | // TODO(mitchellh): make this error message a lot better | |
75 | return nil, fmt.Errorf("multiple roots: %#v", roots) | |
76 | } | |
77 | ||
78 | if len(roots) == 0 { | |
79 | return nil, fmt.Errorf("no roots found") | |
80 | } | |
81 | ||
82 | return roots[0], nil | |
83 | } | |
84 | ||
85 | // TransitiveReduction performs the transitive reduction of graph g in place. | |
86 | // The transitive reduction of a graph is a graph with as few edges as | |
87 | // possible with the same reachability as the original graph. This means | |
88 | // that if there are three nodes A => B => C, and A connects to both | |
89 | // B and C, and B connects to C, then the transitive reduction is the | |
90 | // same graph with only a single edge between A and B, and a single edge | |
91 | // between B and C. | |
92 | // | |
93 | // The graph must be valid for this operation to behave properly. If | |
94 | // Validate() returns an error, the behavior is undefined and the results | |
95 | // will likely be unexpected. | |
96 | // | |
97 | // Complexity: O(V(V+E)), or asymptotically O(VE) | |
98 | func (g *AcyclicGraph) TransitiveReduction() { | |
99 | // For each vertex u in graph g, do a DFS starting from each vertex | |
100 | // v such that the edge (u,v) exists (v is a direct descendant of u). | |
101 | // | |
102 | // For each v-prime reachable from v, remove the edge (u, v-prime). | |
103 | defer g.debug.BeginOperation("TransitiveReduction", "").End("") | |
104 | ||
105 | for _, u := range g.Vertices() { | |
106 | uTargets := g.DownEdges(u) | |
107 | vs := AsVertexList(g.DownEdges(u)) | |
108 | ||
109 | g.DepthFirstWalk(vs, func(v Vertex, d int) error { | |
110 | shared := uTargets.Intersection(g.DownEdges(v)) | |
111 | for _, vPrime := range AsVertexList(shared) { | |
112 | g.RemoveEdge(BasicEdge(u, vPrime)) | |
113 | } | |
114 | ||
115 | return nil | |
116 | }) | |
117 | } | |
118 | } | |
119 | ||
120 | // Validate validates the DAG. A DAG is valid if it has a single root | |
121 | // with no cycles. | |
122 | func (g *AcyclicGraph) Validate() error { | |
123 | if _, err := g.Root(); err != nil { | |
124 | return err | |
125 | } | |
126 | ||
127 | // Look for cycles of more than 1 component | |
128 | var err error | |
129 | cycles := g.Cycles() | |
130 | if len(cycles) > 0 { | |
131 | for _, cycle := range cycles { | |
132 | cycleStr := make([]string, len(cycle)) | |
133 | for j, vertex := range cycle { | |
134 | cycleStr[j] = VertexName(vertex) | |
135 | } | |
136 | ||
137 | err = multierror.Append(err, fmt.Errorf( | |
138 | "Cycle: %s", strings.Join(cycleStr, ", "))) | |
139 | } | |
140 | } | |
141 | ||
142 | // Look for cycles to self | |
143 | for _, e := range g.Edges() { | |
144 | if e.Source() == e.Target() { | |
145 | err = multierror.Append(err, fmt.Errorf( | |
146 | "Self reference: %s", VertexName(e.Source()))) | |
147 | } | |
148 | } | |
149 | ||
150 | return err | |
151 | } | |
152 | ||
153 | func (g *AcyclicGraph) Cycles() [][]Vertex { | |
154 | var cycles [][]Vertex | |
155 | for _, cycle := range StronglyConnected(&g.Graph) { | |
156 | if len(cycle) > 1 { | |
157 | cycles = append(cycles, cycle) | |
158 | } | |
159 | } | |
160 | return cycles | |
161 | } | |
162 | ||
163 | // Walk walks the graph, calling your callback as each node is visited. | |
164 | // This will walk nodes in parallel if it can. Because the walk is done | |
165 | // in parallel, the error returned will be a multierror. | |
166 | func (g *AcyclicGraph) Walk(cb WalkFunc) error { | |
167 | defer g.debug.BeginOperation(typeWalk, "").End("") | |
168 | ||
169 | w := &Walker{Callback: cb, Reverse: true} | |
170 | w.Update(g) | |
171 | return w.Wait() | |
172 | } | |
173 | ||
174 | // simple convenience helper for converting a dag.Set to a []Vertex | |
175 | func AsVertexList(s *Set) []Vertex { | |
176 | rawList := s.List() | |
177 | vertexList := make([]Vertex, len(rawList)) | |
178 | for i, raw := range rawList { | |
179 | vertexList[i] = raw.(Vertex) | |
180 | } | |
181 | return vertexList | |
182 | } | |
183 | ||
184 | type vertexAtDepth struct { | |
185 | Vertex Vertex | |
186 | Depth int | |
187 | } | |
188 | ||
189 | // depthFirstWalk does a depth-first walk of the graph starting from | |
190 | // the vertices in start. This is not exported now but it would make sense | |
191 | // to export this publicly at some point. | |
192 | func (g *AcyclicGraph) DepthFirstWalk(start []Vertex, f DepthWalkFunc) error { | |
193 | defer g.debug.BeginOperation(typeDepthFirstWalk, "").End("") | |
194 | ||
195 | seen := make(map[Vertex]struct{}) | |
196 | frontier := make([]*vertexAtDepth, len(start)) | |
197 | for i, v := range start { | |
198 | frontier[i] = &vertexAtDepth{ | |
199 | Vertex: v, | |
200 | Depth: 0, | |
201 | } | |
202 | } | |
203 | for len(frontier) > 0 { | |
204 | // Pop the current vertex | |
205 | n := len(frontier) | |
206 | current := frontier[n-1] | |
207 | frontier = frontier[:n-1] | |
208 | ||
209 | // Check if we've seen this already and return... | |
210 | if _, ok := seen[current.Vertex]; ok { | |
211 | continue | |
212 | } | |
213 | seen[current.Vertex] = struct{}{} | |
214 | ||
215 | // Visit the current node | |
216 | if err := f(current.Vertex, current.Depth); err != nil { | |
217 | return err | |
218 | } | |
219 | ||
220 | // Visit targets of this in a consistent order. | |
221 | targets := AsVertexList(g.DownEdges(current.Vertex)) | |
222 | sort.Sort(byVertexName(targets)) | |
223 | for _, t := range targets { | |
224 | frontier = append(frontier, &vertexAtDepth{ | |
225 | Vertex: t, | |
226 | Depth: current.Depth + 1, | |
227 | }) | |
228 | } | |
229 | } | |
230 | ||
231 | return nil | |
232 | } | |
233 | ||
234 | // reverseDepthFirstWalk does a depth-first walk _up_ the graph starting from | |
235 | // the vertices in start. | |
236 | func (g *AcyclicGraph) ReverseDepthFirstWalk(start []Vertex, f DepthWalkFunc) error { | |
237 | defer g.debug.BeginOperation(typeReverseDepthFirstWalk, "").End("") | |
238 | ||
239 | seen := make(map[Vertex]struct{}) | |
240 | frontier := make([]*vertexAtDepth, len(start)) | |
241 | for i, v := range start { | |
242 | frontier[i] = &vertexAtDepth{ | |
243 | Vertex: v, | |
244 | Depth: 0, | |
245 | } | |
246 | } | |
247 | for len(frontier) > 0 { | |
248 | // Pop the current vertex | |
249 | n := len(frontier) | |
250 | current := frontier[n-1] | |
251 | frontier = frontier[:n-1] | |
252 | ||
253 | // Check if we've seen this already and return... | |
254 | if _, ok := seen[current.Vertex]; ok { | |
255 | continue | |
256 | } | |
257 | seen[current.Vertex] = struct{}{} | |
258 | ||
259 | // Add next set of targets in a consistent order. | |
260 | targets := AsVertexList(g.UpEdges(current.Vertex)) | |
261 | sort.Sort(byVertexName(targets)) | |
262 | for _, t := range targets { | |
263 | frontier = append(frontier, &vertexAtDepth{ | |
264 | Vertex: t, | |
265 | Depth: current.Depth + 1, | |
266 | }) | |
267 | } | |
268 | ||
269 | // Visit the current node | |
270 | if err := f(current.Vertex, current.Depth); err != nil { | |
271 | return err | |
272 | } | |
273 | } | |
274 | ||
275 | return nil | |
276 | } | |
277 | ||
278 | // byVertexName implements sort.Interface so a list of Vertices can be sorted | |
279 | // consistently by their VertexName | |
280 | type byVertexName []Vertex | |
281 | ||
282 | func (b byVertexName) Len() int { return len(b) } | |
283 | func (b byVertexName) Swap(i, j int) { b[i], b[j] = b[j], b[i] } | |
284 | func (b byVertexName) Less(i, j int) bool { | |
285 | return VertexName(b[i]) < VertexName(b[j]) | |
286 | } |