src

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

compact.go (2413B)

      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 "iter"
      8 
      9 // A CompactGraph is a Graph with nodes that are compactly numbered from [0,
     10 // NumNodes()).
     11 //
     12 // Compactly numbered graphs are useful for many graph algorithms, and many
     13 // graph representations are naturally compact.
     14 //
     15 // To compact an arbitrary graph, use [Compact].
     16 type CompactGraph interface {
     17 	Graph[int]
     18 	IsCompact()
     19 }
     20 
     21 // A nodePreserving graph is a transformation of another graph that preserves
     22 // node IDs.
     23 type nodePreserving interface {
     24 	Graph[int]
     25 	unwrapPreservingNodes() Graph[int]
     26 }
     27 
     28 // Compact takes a Graph with arbitrary NodeIDs and returns a compact graph.
     29 //
     30 // If g implements [CompactGraph], it assumes g is already compact and simply
     31 // returns g and an identity mapping.
     32 func Compact[NodeID comparable](g Graph[NodeID]) (CompactGraph, *Index[NodeID]) {
     33 	// If it's already compact, simply return it.
     34 	if gc, ok := g.(CompactGraph); ok {
     35 		// The above assertion ensures NodeID is int, so we know this type
     36 		// assertion will always succeed.
     37 		return gc, any(NewIdentityIndex(gc.NumNodes())).(*Index[NodeID])
     38 	}
     39 
     40 	// If it's a transformation and the underlying graph is compact, we can use
     41 	// an identity index. Though we still need to build a compactGraph to
     42 	// satisfy the CompactGraph interface.
     43 	g2, _ := g.(nodePreserving)
     44 	for g2 != nil {
     45 		unwrapped := g2.unwrapPreservingNodes()
     46 		if gc, ok := unwrapped.(CompactGraph); ok {
     47 			index := any(NewIdentityIndex(gc.NumNodes())).(*Index[NodeID])
     48 			cg := compactGraph[NodeID]{g, index}
     49 			return &cg, index
     50 		}
     51 		g2, _ = unwrapped.(nodePreserving)
     52 	}
     53 
     54 	// Nope, just build an index.
     55 	cg := compactGraph[NodeID]{g, NewIndex(g.Nodes())}
     56 	return &cg, cg.m
     57 }
     58 
     59 type compactGraph[NodeID comparable] struct {
     60 	g Graph[NodeID]
     61 	m *Index[NodeID]
     62 }
     63 
     64 func (g *compactGraph[NodeID]) Nodes() iter.Seq[int] {
     65 	return func(yield func(int) bool) {
     66 		for i := range g.g.NumNodes() {
     67 			if !yield(i) {
     68 				break
     69 			}
     70 		}
     71 	}
     72 }
     73 
     74 func (g *compactGraph[NodeID]) NumNodes() int {
     75 	return g.g.NumNodes()
     76 }
     77 
     78 func (g *compactGraph[NodeID]) Out(node int) iter.Seq[int] {
     79 	id := g.m.Value(node)
     80 	return func(yield func(int) bool) {
     81 		for nid := range g.g.Out(id) {
     82 			if !yield(g.m.Index(nid)) {
     83 				break
     84 			}
     85 		}
     86 	}
     87 }
     88 
     89 func (g *compactGraph[NodeID]) IsCompact() {}