graph-pp.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/nostr/encoders/hex"
8 "next.orly.dev/pkg/database/indexes/types"
9 )
10
11 // TraversePubkeyPubkey performs BFS traversal of the pubkey↔pubkey graph using
12 // the ppg/gpp materialized index. This collapses the two-hop
13 // pubkey→event→pubkey traversal into a single prefix scan per frontier node.
14 //
15 // Direction selects which index to scan:
16 // - "out": ppg index (who does seed follow/reference?)
17 // - "in": gpp index (who references seed?)
18 // - "both": union of both directions at each depth
19 func (d *D) TraversePubkeyPubkey(seedPubkey []byte, maxDepth int, direction string) (*GraphResult, error) {
20 result := NewGraphResult()
21
22 if len(seedPubkey) != 32 {
23 return result, ErrPubkeyNotFound
24 }
25
26 seedSerial, err := d.GetPubkeySerial(seedPubkey)
27 if err != nil {
28 log.D.F("TraversePubkeyPubkey: seed not in database: %s", hex.Enc(seedPubkey))
29 return result, nil
30 }
31
32 visited := make(map[uint64]bool)
33 visited[seedSerial.Get()] = true
34
35 currentFrontier := []*types.Uint40{seedSerial}
36 consecutiveEmpty := 0
37
38 for depth := 1; depth <= maxDepth; depth++ {
39 var nextFrontier []*types.Uint40
40 newCount := 0
41
42 for _, serial := range currentFrontier {
43 var neighbors []*types.Uint40
44
45 if direction == "out" || direction == "both" {
46 outNeighbors, err := d.GetFollowsViaPPG(serial)
47 if err != nil {
48 log.D.F("TraversePubkeyPubkey: ppg scan error for serial %d: %v", serial.Get(), err)
49 continue
50 }
51 neighbors = append(neighbors, outNeighbors...)
52 }
53
54 if direction == "in" || direction == "both" {
55 inNeighbors, err := d.GetFollowersViaGPP(serial)
56 if err != nil {
57 log.D.F("TraversePubkeyPubkey: gpp scan error for serial %d: %v", serial.Get(), err)
58 continue
59 }
60 neighbors = append(neighbors, inNeighbors...)
61 }
62
63 for _, neighborSerial := range neighbors {
64 if visited[neighborSerial.Get()] {
65 continue
66 }
67 visited[neighborSerial.Get()] = true
68
69 pubkeyHex, err := d.GetPubkeyHexFromSerial(neighborSerial)
70 if err != nil {
71 continue
72 }
73
74 result.AddPubkeyAtDepth(pubkeyHex, depth)
75 newCount++
76 nextFrontier = append(nextFrontier, neighborSerial)
77 }
78 }
79
80 log.T.F("TraversePubkeyPubkey: depth %d found %d new pubkeys (ppg/gpp)", depth, newCount)
81
82 if newCount == 0 {
83 consecutiveEmpty++
84 if consecutiveEmpty >= 2 {
85 break
86 }
87 } else {
88 consecutiveEmpty = 0
89 }
90
91 currentFrontier = nextFrontier
92 }
93
94 log.D.F("TraversePubkeyPubkey: completed with %d pubkeys across %d depths",
95 result.TotalPubkeys, len(result.PubkeysByDepth))
96
97 return result, nil
98 }
99
100 // TraversePubkeyPubkeyBaseline performs the same BFS as TraversePubkeyPubkey
101 // but uses the old multi-hop approach: find kind-3 event → extract p-tags.
102 // This provides the benchmark baseline for comparison against the ppg/gpp index.
103 func (d *D) TraversePubkeyPubkeyBaseline(seedPubkey []byte, maxDepth int, direction string) (*GraphResult, error) {
104 result := NewGraphResult()
105
106 if len(seedPubkey) != 32 {
107 return result, ErrPubkeyNotFound
108 }
109
110 seedSerial, err := d.GetPubkeySerial(seedPubkey)
111 if err != nil {
112 log.D.F("TraversePubkeyPubkeyBaseline: seed not in database: %s", hex.Enc(seedPubkey))
113 return result, nil
114 }
115
116 visited := make(map[uint64]bool)
117 visited[seedSerial.Get()] = true
118
119 currentFrontier := []*types.Uint40{seedSerial}
120 consecutiveEmpty := 0
121
122 for depth := 1; depth <= maxDepth; depth++ {
123 var nextFrontier []*types.Uint40
124 newCount := 0
125
126 for _, serial := range currentFrontier {
127 var neighbors []*types.Uint40
128
129 if direction == "out" || direction == "both" {
130 // Old path: find kind-3 event, extract p-tags (two index lookups)
131 follows, err := d.GetFollowsFromPubkeySerial(serial)
132 if err != nil {
133 continue
134 }
135 neighbors = append(neighbors, follows...)
136 }
137
138 if direction == "in" || direction == "both" {
139 // Old path: find kind-3 events referencing target, get authors (O(N) lookups)
140 followers, err := d.GetFollowersOfPubkeySerial(serial)
141 if err != nil {
142 continue
143 }
144 neighbors = append(neighbors, followers...)
145 }
146
147 for _, neighborSerial := range neighbors {
148 if visited[neighborSerial.Get()] {
149 continue
150 }
151 visited[neighborSerial.Get()] = true
152
153 pubkeyHex, err := d.GetPubkeyHexFromSerial(neighborSerial)
154 if err != nil {
155 continue
156 }
157
158 result.AddPubkeyAtDepth(pubkeyHex, depth)
159 newCount++
160 nextFrontier = append(nextFrontier, neighborSerial)
161 }
162 }
163
164 log.T.F("TraversePubkeyPubkeyBaseline: depth %d found %d new pubkeys (multi-hop)", depth, newCount)
165
166 if newCount == 0 {
167 consecutiveEmpty++
168 if consecutiveEmpty >= 2 {
169 break
170 }
171 } else {
172 consecutiveEmpty = 0
173 }
174
175 currentFrontier = nextFrontier
176 }
177
178 log.D.F("TraversePubkeyPubkeyBaseline: completed with %d pubkeys across %d depths",
179 result.TotalPubkeys, len(result.PubkeysByDepth))
180
181 return result, nil
182 }
183
184 // TraversePubkeyEvent performs BFS traversal of pubkey↔event edges.
185 // Direction "out" = events authored by/referencing the seed pubkey (peg index).
186 // Direction "in" = events that reference the seed pubkey (epg reverse).
187 func (d *D) TraversePubkeyEvent(seedPubkey []byte, maxDepth int, direction string) (*GraphResult, error) {
188 result := NewGraphResult()
189
190 if len(seedPubkey) != 32 {
191 return result, ErrPubkeyNotFound
192 }
193
194 seedSerial, err := d.GetPubkeySerial(seedPubkey)
195 if err != nil {
196 log.D.F("TraversePubkeyEvent: seed not in database: %s", hex.Enc(seedPubkey))
197 return result, nil
198 }
199
200 // For pe queries, depth 1 = direct events for the seed pubkey
201 if direction == "out" || direction == "both" {
202 // Events authored by seed
203 eventSerials, err := d.GetEventsByAuthor(seedSerial, nil)
204 if err == nil {
205 for _, es := range eventSerials {
206 eventHex, err := d.GetEventIDFromSerial(es)
207 if err != nil {
208 continue
209 }
210 result.AddEventAtDepth(eventHex, 1)
211 }
212 }
213 }
214
215 if direction == "in" || direction == "both" {
216 // Events referencing seed via p-tag
217 eventSerials, err := d.GetEventsReferencingPubkey(seedSerial, nil)
218 if err == nil {
219 for _, es := range eventSerials {
220 eventHex, err := d.GetEventIDFromSerial(es)
221 if err != nil {
222 continue
223 }
224 result.AddEventAtDepth(eventHex, 1)
225 }
226 }
227 }
228
229 log.D.F("TraversePubkeyEvent: completed with %d events", result.TotalEvents)
230 return result, nil
231 }
232
233 // TraverseEventEventFromPubkey performs BFS traversal of event↔event edges,
234 // seeded from events authored by the given pubkey.
235 func (d *D) TraverseEventEventFromPubkey(seedPubkey []byte, maxDepth int, direction string) (*GraphResult, error) {
236 result := NewGraphResult()
237
238 if len(seedPubkey) != 32 {
239 return result, ErrPubkeyNotFound
240 }
241
242 seedSerial, err := d.GetPubkeySerial(seedPubkey)
243 if err != nil {
244 log.D.F("TraverseEventEvent: seed not in database: %s", hex.Enc(seedPubkey))
245 return result, nil
246 }
247
248 // Get seed events (authored by the pubkey)
249 seedEvents, err := d.GetEventsByAuthor(seedSerial, nil)
250 if err != nil {
251 return result, err
252 }
253
254 // Use the existing TraverseThread for each seed event
255 visited := make(map[uint64]bool)
256 for _, eventSerial := range seedEvents {
257 eventID, err := d.GetEventIdBySerial(eventSerial)
258 if err != nil {
259 continue
260 }
261 subResult, err := d.TraverseThread(eventID, maxDepth, direction)
262 if err != nil {
263 continue
264 }
265 // Merge sub-results
266 for depth, events := range subResult.EventsByDepth {
267 for _, e := range events {
268 _ = visited // TraverseThread handles its own dedup
269 result.AddEventAtDepth(e, depth)
270 }
271 }
272 }
273
274 log.D.F("TraverseEventEvent: completed with %d events from %d seed events",
275 result.TotalEvents, len(seedEvents))
276 return result, nil
277 }
278