59 lines
915 B
Go
59 lines
915 B
Go
package grok
|
|
|
|
type graph map[string][]string
|
|
|
|
func reverseList(s []string) (r []string) {
|
|
for _, i := range s {
|
|
i := i
|
|
defer func() { r = append(r, i) }()
|
|
}
|
|
return
|
|
}
|
|
|
|
func sortGraph(g graph) (order, cyclic []string) {
|
|
L := make([]string, len(g))
|
|
i := len(L)
|
|
temp := map[string]bool{}
|
|
perm := map[string]bool{}
|
|
var cycleFound bool
|
|
var cycleStart string
|
|
var visit func(string)
|
|
visit = func(n string) {
|
|
switch {
|
|
case temp[n]:
|
|
cycleFound = true
|
|
cycleStart = n
|
|
return
|
|
case perm[n]:
|
|
return
|
|
}
|
|
temp[n] = true
|
|
for _, m := range g[n] {
|
|
visit(m)
|
|
if cycleFound {
|
|
if cycleStart > "" {
|
|
cyclic = append(cyclic, n)
|
|
if n == cycleStart {
|
|
cycleStart = ""
|
|
}
|
|
}
|
|
return
|
|
}
|
|
}
|
|
delete(temp, n)
|
|
perm[n] = true
|
|
i--
|
|
L[i] = n
|
|
}
|
|
for n := range g {
|
|
if perm[n] {
|
|
continue
|
|
}
|
|
visit(n)
|
|
if cycleFound {
|
|
return nil, cyclic
|
|
}
|
|
}
|
|
return L, nil
|
|
}
|