149 lines
2.7 KiB
Go
149 lines
2.7 KiB
Go
package main
|
|
|
|
import (
|
|
"fmt"
|
|
"math"
|
|
"sort"
|
|
)
|
|
|
|
type CycleError struct {
|
|
Processed int
|
|
Total int
|
|
RemainingNodeIDs []int
|
|
RemainingIRISample []string
|
|
}
|
|
|
|
func (e *CycleError) Error() string {
|
|
msg := fmt.Sprintf("Cycle detected in subClassOf graph (processed %d/%d nodes).", e.Processed, e.Total)
|
|
if len(e.RemainingIRISample) > 0 {
|
|
msg += " Example nodes: " + stringsJoin(e.RemainingIRISample, ", ")
|
|
}
|
|
return msg
|
|
}
|
|
|
|
func levelSynchronousKahnLayers(nodeCount int, edges [][2]int) ([][]int, *CycleError) {
|
|
n := nodeCount
|
|
if n <= 0 {
|
|
return [][]int{}, nil
|
|
}
|
|
|
|
adj := make([][]int, n)
|
|
indeg := make([]int, n)
|
|
|
|
for _, e := range edges {
|
|
u, v := e[0], e[1]
|
|
if u == v {
|
|
continue
|
|
}
|
|
if u < 0 || u >= n || v < 0 || v >= n {
|
|
continue
|
|
}
|
|
adj[u] = append(adj[u], v)
|
|
indeg[v]++
|
|
}
|
|
|
|
q := make([]int, 0, n)
|
|
for i, d := range indeg {
|
|
if d == 0 {
|
|
q = append(q, i)
|
|
}
|
|
}
|
|
|
|
layers := make([][]int, 0)
|
|
processed := 0
|
|
for len(q) > 0 {
|
|
layer := append([]int(nil), q...)
|
|
q = q[:0]
|
|
layers = append(layers, layer)
|
|
|
|
for _, u := range layer {
|
|
processed++
|
|
for _, v := range adj[u] {
|
|
indeg[v]--
|
|
if indeg[v] == 0 {
|
|
q = append(q, v)
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
if processed != n {
|
|
remaining := make([]int, 0)
|
|
for i, d := range indeg {
|
|
if d > 0 {
|
|
remaining = append(remaining, i)
|
|
}
|
|
}
|
|
return nil, &CycleError{Processed: processed, Total: n, RemainingNodeIDs: remaining}
|
|
}
|
|
|
|
return layers, nil
|
|
}
|
|
|
|
func radialPositionsFromLayers(nodeCount int, layers [][]int, maxR float64) (xs []float64, ys []float64) {
|
|
n := nodeCount
|
|
if n <= 0 {
|
|
return []float64{}, []float64{}
|
|
}
|
|
|
|
xs = make([]float64, n)
|
|
ys = make([]float64, n)
|
|
if len(layers) == 0 {
|
|
return xs, ys
|
|
}
|
|
|
|
twoPi := 2.0 * math.Pi
|
|
golden := math.Pi * (3.0 - math.Sqrt(5.0))
|
|
|
|
layerCount := float64(len(layers))
|
|
denom := layerCount + 1.0
|
|
|
|
for li, layer := range layers {
|
|
m := len(layer)
|
|
if m == 0 {
|
|
continue
|
|
}
|
|
r := (float64(li+1) / denom) * maxR
|
|
offset := math.Mod(float64(li)*golden, twoPi)
|
|
|
|
if m == 1 {
|
|
nid := layer[0]
|
|
if nid >= 0 && nid < n {
|
|
xs[nid] = r * math.Cos(offset)
|
|
ys[nid] = r * math.Sin(offset)
|
|
}
|
|
continue
|
|
}
|
|
|
|
step := twoPi / float64(m)
|
|
for j, nid := range layer {
|
|
if nid < 0 || nid >= n {
|
|
continue
|
|
}
|
|
t := offset + step*float64(j)
|
|
xs[nid] = r * math.Cos(t)
|
|
ys[nid] = r * math.Sin(t)
|
|
}
|
|
}
|
|
|
|
return xs, ys
|
|
}
|
|
|
|
func sortLayerByIRI(layer []int, idToIRI []string) {
|
|
sort.Slice(layer, func(i, j int) bool {
|
|
return idToIRI[layer[i]] < idToIRI[layer[j]]
|
|
})
|
|
}
|
|
|
|
func stringsJoin(parts []string, sep string) string {
|
|
if len(parts) == 0 {
|
|
return ""
|
|
}
|
|
out := parts[0]
|
|
for i := 1; i < len(parts); i++ {
|
|
out += sep
|
|
out += parts[i]
|
|
}
|
|
return out
|
|
}
|