bfs.go raw

   1  package cayley
   2  
   3  import (
   4  	"fmt"
   5  	"sort"
   6  )
   7  
   8  // PathFinder stores precomputed shortest paths from root to all vertices
   9  // in the Cayley graph of SL(2, Z_P) with a given generator set.
  10  type PathFinder struct {
  11  	GS     *GeneratorSet
  12  	P      int64
  13  	Dist   map[Mat2]int    // distance from root (ID) to each vertex
  14  	Parent map[Mat2]Mat2   // parent in BFS tree
  15  	Edge   map[Mat2]int8   // generator index from parent to this vertex
  16  	BFSMax int              // maximum distance found
  17  }
  18  
  19  // BFS computes shortest paths from ID to all reachable vertices via BFS.
  20  // Returns the number of vertices reached and the maximum distance.
  21  func (gs *GeneratorSet) BFS(maxDist int) *PathFinder {
  22  	pf := &PathFinder{
  23  		GS:     gs,
  24  		P:      gs.P,
  25  		Dist:   make(map[Mat2]int),
  26  		Parent: make(map[Mat2]Mat2),
  27  		Edge:   make(map[Mat2]int8),
  28  	}
  29  
  30  	root := ID()
  31  	pf.Dist[root] = 0
  32  	queue := []Mat2{root}
  33  	pf.BFSMax = 0
  34  
  35  	for len(queue) > 0 {
  36  		cur := queue[0]
  37  		queue = queue[1:]
  38  		d := pf.Dist[cur]
  39  
  40  		if maxDist >= 0 && d >= maxDist {
  41  			continue
  42  		}
  43  
  44  		for i, g := range gs.Gens {
  45  			next := cur.Mul(g, gs.P)
  46  			if _, ok := pf.Dist[next]; !ok {
  47  				pf.Dist[next] = d + 1
  48  				pf.Parent[next] = cur
  49  				pf.Edge[next] = int8(i)
  50  				queue = append(queue, next)
  51  				if d+1 > pf.BFSMax {
  52  					pf.BFSMax = d + 1
  53  				}
  54  			}
  55  		}
  56  	}
  57  	return pf
  58  }
  59  
  60  // PathTo returns the shortest path from root to target (reversed — root to target).
  61  func (pf *PathFinder) PathTo(target Mat2) ([]int8, bool) {
  62  	if _, ok := pf.Dist[target]; !ok {
  63  		return nil, false
  64  	}
  65  	var path []int8
  66  	cur := target
  67  	for !cur.Eq(ID()) {
  68  		parent := pf.Parent[cur]
  69  		// Find which generator takes parent → cur.
  70  		edge := pf.Edge[cur]
  71  		path = append([]int8{edge}, path...)
  72  		cur = parent
  73  	}
  74  	return path, true
  75  }
  76  
  77  // Distance returns the shortest path distance from root to target.
  78  func (pf *PathFinder) Distance(target Mat2) int {
  79  	return pf.Dist[target]
  80  }
  81  
  82  // Reachable returns the number of vertices reached by BFS.
  83  func (pf *PathFinder) Reachable() int {
  84  	return len(pf.Dist)
  85  }
  86  
  87  // MaxDist returns the maximum distance found (diameter lower bound).
  88  func (pf *PathFinder) MaxDist() int { return pf.BFSMax }
  89  
  90  // DistHist returns a histogram of distances.
  91  func (pf *PathFinder) DistHist() map[int]int {
  92  	h := make(map[int]int)
  93  	for _, d := range pf.Dist {
  94  		h[d]++
  95  	}
  96  	return h
  97  }
  98  
  99  // DistStats returns mean, median, max distance.
 100  func (pf *PathFinder) DistStats() (mean float64, median float64, maxDist int) {
 101  	dists := make([]int, 0, len(pf.Dist))
 102  	for _, d := range pf.Dist {
 103  		dists = append(dists, d)
 104  		if d > maxDist {
 105  			maxDist = d
 106  		}
 107  	}
 108  	sort.Ints(dists)
 109  	n := len(dists)
 110  	var sum int
 111  	for _, d := range dists {
 112  		sum += d
 113  	}
 114  	mean = float64(sum) / float64(n)
 115  	median = float64(dists[n/2])
 116  	return
 117  }
 118  
 119  // Report prints BFS statistics.
 120  func (pf *PathFinder) Report() string {
 121  	reachable := pf.Reachable()
 122  	maxD := pf.MaxDist()
 123  	mean, median, _ := pf.DistStats()
 124  	hist := pf.DistHist()
 125  	return fmt.Sprintf("BFS: P=%d reached=%d diam≥%d mean=%.1f median=%.0f hist=%v",
 126  		pf.P, reachable, maxD, mean, median, hist)
 127  }
 128  
 129  // DistStatsMean returns the mean distance.
 130  func (pf *PathFinder) DistStatsMean() float64 {
 131  	var sum int
 132  	for _, d := range pf.Dist {
 133  		sum += d
 134  	}
 135  	return float64(sum) / float64(len(pf.Dist))
 136  }
 137