Method TopologicalSort

backend/plugin/parser/base/topo_sort.go:43–78

()

}

func (g *Graph) TopologicalSort() ([]string, error) {
	var result []string
	inDegree := make(map[string]int)
	outEdge := make(map[string][]*Edge)

	for _, edge := range g.EdgeList {
		inDegree[edge.End]++
		outEdge[edge.Start] = append(outEdge[edge.Start], edge)
	}

	var queue []string
	for id := range g.NodeMap {
		if inDegree[id] == 0 {
			queue = append(queue, id)
		}
	}
	slices.Sort(queue)

	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		for _, edge := range outEdge[node] {
			inDegree[edge.End]--
			if inDegree[edge.End] == 0 {
				queue = append(queue, edge.End)
			}
		}
		result = append(result, node)
	}

	if len(result) != len(g.NodeMap) {
		return nil, errors.Errorf("graph has cycle")
	}

	return result, nil
}