blob: 89de18c7f1a282fe687ad5e6681841fa6088798f (
plain) (
blame)
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
|
package util
import (
"fmt"
"strings"
"github.com/pyr-sh/dag"
)
// ValidateGraph checks that a given DAG has no cycles and no self-referential edges.
// We differ from the underlying DAG Validate method in that we allow multiple roots.
func ValidateGraph(graph *dag.AcyclicGraph) error {
// We use Cycles instead of Validate because
// our DAG has multiple roots (entrypoints).
// Validate mandates that there is only a single root node.
cycles := graph.Cycles()
if len(cycles) > 0 {
cycleLines := make([]string, len(cycles))
for i, cycle := range cycles {
vertices := make([]string, len(cycle))
for j, vertex := range cycle {
vertices[j] = vertex.(string)
}
cycleLines[i] = "\t" + strings.Join(vertices, ",")
}
return fmt.Errorf("cyclic dependency detected:\n%s", strings.Join(cycleLines, "\n"))
}
for _, e := range graph.Edges() {
if e.Source() == e.Target() {
return fmt.Errorf("%s depends on itself", e.Source())
}
}
return nil
}
|