func transitiveClosure()

in generator/transitive_closure.go [26:65]

• 35 lines of code
• 12 McCabe index (conditional complexity)

func transitiveClosure(in map[string][]string) map[string][]string {
	adj := make(map[edge]bool)
	imports := make(map[string]struct{})
	for from, tos := range in {
		for _, to := range tos {
			adj[edge{from, to}] = true
			imports[to] = struct{}{}
		}
	}

	// Warshal's algorithm
	for k := range in {
		for i := range in {
			if !adj[edge{i, k}] {
				continue
			}
			for j := range imports {
				if adj[edge{i, j}] {
					continue
				}
				if adj[edge{k, j}] {
					adj[edge{i, j}] = true
				}
			}
		}
	}

	out := make(map[string][]string, len(in))
	for i := range in {
		for j := range imports {
			if adj[edge{i, j}] {
				out[i] = append(out[i], j)
			}
		}

		sort.Strings(out[i])
	}

	return out
}