src

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

transpose.go (1203B)

      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 (
      8 	"iter"
      9 	"slices"
     10 )
     11 
     12 type transpose[NodeID comparable] struct {
     13 	Graph Graph[NodeID]
     14 	preds map[NodeID][]NodeID
     15 }
     16 
     17 // transpose returns a graph like g but with all edges reversed. Node IDs are
     18 // identical to the underlying graph.
     19 //
     20 // Transpose preserves compactness.
     21 func Transpose[NodeID comparable](g Graph[NodeID]) Graph[NodeID] {
     22 	if g, ok := g.(transpose[NodeID]); ok {
     23 		// Transpose(Transpose(g)) == g
     24 		return g.Graph
     25 	}
     26 
     27 	preds := make(map[NodeID][]NodeID)
     28 	for nid := range g.Nodes() {
     29 		for succ := range g.Out(nid) {
     30 			preds[succ] = append(preds[succ], nid)
     31 		}
     32 	}
     33 	return transpose[NodeID]{g, preds}
     34 }
     35 
     36 func (t transpose[NodeID]) NumNodes() int {
     37 	return len(t.preds)
     38 }
     39 
     40 func (t transpose[NodeID]) Nodes() iter.Seq[NodeID] {
     41 	return t.Graph.Nodes()
     42 }
     43 
     44 func (t transpose[NodeID]) Out(n NodeID) iter.Seq[NodeID] {
     45 	return slices.Values(t.preds[n])
     46 }
     47 
     48 //lint:ignore U1000 False positive in Staticcheck 2026.1 and older.
     49 func (t transpose[NodeID]) unwrapPreservingNodes() Graph[NodeID] {
     50 	return t.Graph
     51 }