src

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

allpaths.go (701B)

      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 // AllPaths returns the set of nodes that are part of at least one path from src to dst.
      8 func AllPaths[NodeID comparable](g Graph[NodeID], src, dst NodeID) map[NodeID]bool {
      9 	// We intersect the forward closure of 'src' with
     10 	// the reverse closure of 'dst'. This is not the most
     11 	// efficient implementation, but it's the clearest,
     12 	// and the previous one had bugs.
     13 
     14 	fwd := Reachable(g, src)
     15 	rev := Reachable(Transpose(g), dst)
     16 
     17 	// Intersection
     18 	for n := range fwd {
     19 		if !rev[n] {
     20 			delete(fwd, n)
     21 		}
     22 	}
     23 	return fwd
     24 }