graph-follows.go raw
1 //go:build !(js && wasm)
2
3 package database
4
5 import (
6 "next.orly.dev/pkg/lol/log"
7 "next.orly.dev/pkg/database/indexes/types"
8 "next.orly.dev/pkg/nostr/encoders/hex"
9 )
10
11 // TraverseFollows performs BFS traversal of the follow graph starting from a seed pubkey.
12 // Returns pubkeys grouped by first-discovered depth (no duplicates across depths).
13 //
14 // The traversal works by:
15 // 1. Starting with the seed pubkey at depth 0 (not included in results)
16 // 2. For each pubkey at the current depth, find their kind-3 contact list
17 // 3. Extract p-tags from the contact list to get follows
18 // 4. Add new (unseen) follows to the next depth
19 // 5. Continue until maxDepth is reached or no new pubkeys are found
20 //
21 // Early termination occurs if two consecutive depths yield no new pubkeys.
22 func (d *D) TraverseFollows(seedPubkey []byte, maxDepth int) (*GraphResult, error) {
23 result := NewGraphResult()
24
25 if len(seedPubkey) != 32 {
26 return result, ErrPubkeyNotFound
27 }
28
29 // Get seed pubkey serial
30 seedSerial, err := d.GetPubkeySerial(seedPubkey)
31 if err != nil {
32 log.D.F("TraverseFollows: seed pubkey not in database: %s", hex.Enc(seedPubkey))
33 return result, nil // Not an error - just no results
34 }
35
36 // Track visited pubkeys by serial to avoid cycles
37 visited := make(map[uint64]bool)
38 visited[seedSerial.Get()] = true // Mark seed as visited but don't add to results
39
40 // Current frontier (pubkeys to process at this depth)
41 currentFrontier := []*types.Uint40{seedSerial}
42
43 // Track consecutive empty depths for early termination
44 consecutiveEmptyDepths := 0
45
46 for currentDepth := 1; currentDepth <= maxDepth; currentDepth++ {
47 var nextFrontier []*types.Uint40
48 newPubkeysAtDepth := 0
49
50 for _, pubkeySerial := range currentFrontier {
51 // Get follows for this pubkey
52 follows, err := d.GetFollowsFromPubkeySerial(pubkeySerial)
53 if err != nil {
54 log.D.F("TraverseFollows: error getting follows for serial %d: %v", pubkeySerial.Get(), err)
55 continue
56 }
57
58 for _, followSerial := range follows {
59 // Skip if already visited
60 if visited[followSerial.Get()] {
61 continue
62 }
63 visited[followSerial.Get()] = true
64
65 // Get pubkey hex for result
66 pubkeyHex, err := d.GetPubkeyHexFromSerial(followSerial)
67 if err != nil {
68 log.D.F("TraverseFollows: error getting pubkey hex for serial %d: %v", followSerial.Get(), err)
69 continue
70 }
71
72 // Add to results at this depth
73 result.AddPubkeyAtDepth(pubkeyHex, currentDepth)
74 newPubkeysAtDepth++
75
76 // Add to next frontier for further traversal
77 nextFrontier = append(nextFrontier, followSerial)
78 }
79 }
80
81 log.T.F("TraverseFollows: depth %d found %d new pubkeys", currentDepth, newPubkeysAtDepth)
82
83 // Check for early termination
84 if newPubkeysAtDepth == 0 {
85 consecutiveEmptyDepths++
86 if consecutiveEmptyDepths >= 2 {
87 log.T.F("TraverseFollows: early termination at depth %d (2 consecutive empty depths)", currentDepth)
88 break
89 }
90 } else {
91 consecutiveEmptyDepths = 0
92 }
93
94 // Move to next depth
95 currentFrontier = nextFrontier
96 }
97
98 log.D.F("TraverseFollows: completed with %d total pubkeys across %d depths",
99 result.TotalPubkeys, len(result.PubkeysByDepth))
100
101 return result, nil
102 }
103
104 // TraverseFollowers performs BFS traversal to find who follows the seed pubkey.
105 // This is the reverse of TraverseFollows - it finds users whose kind-3 lists
106 // contain the target pubkey(s).
107 //
108 // At each depth:
109 // - Depth 1: Users who directly follow the seed
110 // - Depth 2: Users who follow anyone at depth 1 (followers of followers)
111 // - etc.
112 func (d *D) TraverseFollowers(seedPubkey []byte, maxDepth int) (*GraphResult, error) {
113 result := NewGraphResult()
114
115 if len(seedPubkey) != 32 {
116 return result, ErrPubkeyNotFound
117 }
118
119 // Get seed pubkey serial
120 seedSerial, err := d.GetPubkeySerial(seedPubkey)
121 if err != nil {
122 log.D.F("TraverseFollowers: seed pubkey not in database: %s", hex.Enc(seedPubkey))
123 return result, nil
124 }
125
126 // Track visited pubkeys
127 visited := make(map[uint64]bool)
128 visited[seedSerial.Get()] = true
129
130 // Current frontier
131 currentFrontier := []*types.Uint40{seedSerial}
132
133 consecutiveEmptyDepths := 0
134
135 for currentDepth := 1; currentDepth <= maxDepth; currentDepth++ {
136 var nextFrontier []*types.Uint40
137 newPubkeysAtDepth := 0
138
139 for _, targetSerial := range currentFrontier {
140 // Get followers of this pubkey
141 followers, err := d.GetFollowersOfPubkeySerial(targetSerial)
142 if err != nil {
143 log.D.F("TraverseFollowers: error getting followers for serial %d: %v", targetSerial.Get(), err)
144 continue
145 }
146
147 for _, followerSerial := range followers {
148 if visited[followerSerial.Get()] {
149 continue
150 }
151 visited[followerSerial.Get()] = true
152
153 pubkeyHex, err := d.GetPubkeyHexFromSerial(followerSerial)
154 if err != nil {
155 continue
156 }
157
158 result.AddPubkeyAtDepth(pubkeyHex, currentDepth)
159 newPubkeysAtDepth++
160 nextFrontier = append(nextFrontier, followerSerial)
161 }
162 }
163
164 log.T.F("TraverseFollowers: depth %d found %d new pubkeys", currentDepth, newPubkeysAtDepth)
165
166 if newPubkeysAtDepth == 0 {
167 consecutiveEmptyDepths++
168 if consecutiveEmptyDepths >= 2 {
169 break
170 }
171 } else {
172 consecutiveEmptyDepths = 0
173 }
174
175 currentFrontier = nextFrontier
176 }
177
178 log.D.F("TraverseFollowers: completed with %d total pubkeys", result.TotalPubkeys)
179
180 return result, nil
181 }
182
183 // TraverseFollowsFromHex is a convenience wrapper that accepts hex-encoded pubkey.
184 func (d *D) TraverseFollowsFromHex(seedPubkeyHex string, maxDepth int) (*GraphResult, error) {
185 seedPubkey, err := hex.Dec(seedPubkeyHex)
186 if err != nil {
187 return nil, err
188 }
189 return d.TraverseFollows(seedPubkey, maxDepth)
190 }
191
192 // TraverseFollowersFromHex is a convenience wrapper that accepts hex-encoded pubkey.
193 func (d *D) TraverseFollowersFromHex(seedPubkeyHex string, maxDepth int) (*GraphResult, error) {
194 seedPubkey, err := hex.Dec(seedPubkeyHex)
195 if err != nil {
196 return nil, err
197 }
198 return d.TraverseFollowers(seedPubkey, maxDepth)
199 }
200