Skip to content
Snippets Groups Projects
Select Git revision
  • fafc34f8f9295ac0b8bcd6903b33e89d6ab6fb09
  • master default protected
  • v1.23.2
  • v1.23.1
  • v1.23.0
  • v1.22.0
  • v1.21.1
  • v1.21.0
  • v1.20.3
  • v1.20.2
  • v1.20.1
  • v1.20.0
  • v1.19.4
  • v1.19.3
  • v1.19.2
  • v1.19.1
  • v1.19.0
  • v1.18.2
  • v1.18.1
  • v1.18.0
  • v1.17.0
  • v1.16.1
22 results

topological-sort.go

Blame
  • topological-sort.go 2.28 KiB
    package jobqueue
    
    import "container/heap"
    
    // idPriority is a type that holds a JobID and a Priority
    type idPriority struct {
    	id       JobID
    	priority Priority
    }
    
    // idPriorityQueue is a type that holds a slice of idPriority
    type idPriorityQueue []idPriority
    
    // Len implements heap.Interface.Len
    func (pq *idPriorityQueue) Len() int { return len(*pq) }
    
    // Less implements heap.Interface.Less
    func (pq *idPriorityQueue) Less(i, j int) bool {
    	return (*pq)[i].priority > (*pq)[j].priority
    }
    
    // Swap implements heap.Interface.Swap
    func (pq *idPriorityQueue) Swap(i, j int) {
    	(*pq)[i], (*pq)[j] = (*pq)[j], (*pq)[i]
    }
    
    // Push implements heap.Interface.Push
    func (pq *idPriorityQueue) Push(x interface{}) {
    	item := x.(idPriority)
    	*pq = append(*pq, item)
    }
    
    // Pop implements heap.Interface.Pop
    func (pq *idPriorityQueue) Pop() interface{} {
    	old := *pq
    	n := len(old)
    	item := old[n-1]
    	*pq = old[0 : n-1]
    	return item
    }
    
    // topologicalSortJobs returns a slice of JobIDs in the order they should be executed
    // if there is a cycle, it returns ErrCycleDetected
    // if there is a missing dependency, it returns ErrMissingDependency
    func topologicalSortJobs(jobs []GenericJob) ([]JobID, error) {
    	inDegrees := make(map[JobID]int)
    	jobMap := make(map[JobID]GenericJob)
    	dependents := make(map[JobID][]JobID)
    
    	for _, job := range jobs {
    		jobID := job.GetID()
    		inDegrees[jobID] = 0
    		jobMap[jobID] = job
    	}
    
    	for _, job := range jobs {
    		jobID := job.GetID()
    		for _, depID := range job.GetDependencies() {
    			if _, ok := jobMap[depID]; !ok {
    				return nil, ErrMissingDependency
    			}
    			inDegrees[jobID]++
    			dependents[depID] = append(dependents[depID], jobID)
    		}
    	}
    
    	pq := make(idPriorityQueue, 0)
    	heap.Init(&pq)
    
    	for id, inDegree := range inDegrees {
    		if inDegree == 0 {
    			heap.Push(&pq, idPriority{id: id, priority: jobMap[id].GetPriority()})
    		}
    	}
    
    	result := make([]JobID, 0)
    
    	for len(pq) > 0 {
    		idPrio := heap.Pop(&pq).(idPriority)
    		jobID := idPrio.id
    		result = append(result, jobID)
    
    		for _, dependent := range dependents[jobID] {
    			inDegrees[dependent]--
    			if inDegrees[dependent] == 0 {
    				heap.Push(&pq, idPriority{id: dependent, priority: jobMap[dependent].GetPriority()})
    			}
    		}
    	}
    
    	for _, inDegree := range inDegrees {
    		if inDegree > 0 {
    			return nil, ErrCycleDetected
    		}
    	}
    
    	return result, nil
    }