src

Go monorepo.
git clone git://code.dwrz.net/src
Log | Files | Refs

order.go (2198B)

      1 // Copyright 2026 The Go Authors. All rights reserved.
      2 // Use of this source code is governed by a BSD-style
      3 // license that can be found in the LICENSE file.
      4 
      5 package graph
      6 
      7 import "slices"
      8 
      9 // Postorder returns the sequence of nodes in the spanning DAG of g, in
     10 // postorder.
     11 //
     12 // For rootless subgraphs, it breaks cycles by starting at the lowest numbered
     13 // node.
     14 //
     15 // This algorithm runs in O(V + E) time and O(V + E) space.
     16 func Postorder[NodeID comparable](g Graph[NodeID]) []NodeID {
     17 	cg, nodeMap := Compact(g)
     18 
     19 	numNodes := cg.NumNodes()
     20 	if numNodes == 0 {
     21 		return nil
     22 	}
     23 
     24 	result := make([]NodeID, 0, numNodes)
     25 	visited := newBitset(numNodes)
     26 	onStack := newBitset(numNodes)
     27 
     28 	// visit performs a Depth-First Search.
     29 	var visit func(u int)
     30 	visit = func(u int) {
     31 		if !visited.add(u) {
     32 			return
     33 		}
     34 		onStack.add(u)
     35 
     36 		for v := range cg.Out(u) {
     37 			if onStack.contains(v) {
     38 				// Cycle detected (back-edge).
     39 				// To resolve, we simply skip processing this edge further in the
     40 				// current recursion, effectively "breaking" the cycle at this point.
     41 				continue
     42 			}
     43 			visit(v)
     44 		}
     45 
     46 		onStack.remove(u)
     47 		// Post-order: add to result after all descendants are processed.
     48 		result = append(result, nodeMap.Value(u))
     49 	}
     50 
     51 	// Visit every node in ascending order to ensure stability.
     52 	for u := range numNodes {
     53 		visit(u)
     54 	}
     55 
     56 	return result
     57 }
     58 
     59 // ReversePostorder returns the nodes of the graph in reverse post-order.
     60 //
     61 // If g is a directed acyclic graph (DAG), the result is a topological sort of
     62 // g.
     63 //
     64 // See [Postorder] for how this handles back-edges and cycles.
     65 //
     66 // This algorithm runs in O(V + E) time and O(V + E) space.
     67 func ReversePostorder[NodeID comparable](g Graph[NodeID]) []NodeID {
     68 	result := Postorder(g)
     69 	slices.Reverse(result)
     70 	return result
     71 }
     72 
     73 // bitset is a simple fixed-size bitset used to reduce memory overhead.
     74 type bitset []uint64
     75 
     76 func newBitset(n int) bitset {
     77 	return make(bitset, (n+63)/64)
     78 }
     79 
     80 func (b bitset) add(u int) bool {
     81 	if b.contains(u) {
     82 		return false
     83 	}
     84 	b[u/64] |= 1 << (u % 64)
     85 	return true
     86 }
     87 
     88 func (b bitset) remove(u int) {
     89 	b[u/64] &= ^(1 << (u % 64))
     90 }
     91 
     92 func (b bitset) contains(u int) bool {
     93 	return b[u/64]&(1<<(u%64)) != 0
     94 }