graph-follows.go raw
1 package neo4j
2
3 import (
4 "context"
5 "fmt"
6 "strings"
7
8 "next.orly.dev/pkg/nostr/encoders/hex"
9 "next.orly.dev/pkg/protocol/graph"
10 )
11
12 // TraverseFollows performs BFS traversal of the follow graph starting from a seed pubkey.
13 // Returns pubkeys grouped by first-discovered depth (no duplicates across depths).
14 //
15 // Uses Neo4j's native path queries with FOLLOWS relationships created by
16 // the social event processor from kind 3 contact list events.
17 //
18 // The traversal works by using variable-length path patterns:
19 // - Depth 1: Direct follows (seed)-[:FOLLOWS]->(followed)
20 // - Depth 2: Follows of follows (seed)-[:FOLLOWS*2]->(followed)
21 // - etc.
22 //
23 // Each pubkey appears only at the depth where it was first discovered.
24 func (n *N) TraverseFollows(seedPubkey []byte, maxDepth int) (graph.GraphResultI, error) {
25 result := NewGraphResult()
26
27 if len(seedPubkey) != 32 {
28 return result, fmt.Errorf("invalid pubkey length: expected 32, got %d", len(seedPubkey))
29 }
30
31 seedHex := strings.ToLower(hex.Enc(seedPubkey))
32 ctx := context.Background()
33
34 // Track visited pubkeys to ensure each appears only at first-discovered depth
35 visited := make(map[string]bool)
36 visited[seedHex] = true // Seed is at depth 0, not included in results
37
38 // Process each depth level separately to maintain BFS semantics
39 for depth := 1; depth <= maxDepth; depth++ {
40 // Query for pubkeys at exactly this depth that haven't been seen yet
41 // We use a variable-length path of exactly 'depth' hops
42 cypher := fmt.Sprintf(`
43 MATCH path = (seed:NostrUser {pubkey: $seed})-[:FOLLOWS*%d]->(target:NostrUser)
44 WHERE target.pubkey <> $seed
45 AND NOT target.pubkey IN $visited
46 RETURN DISTINCT target.pubkey AS pubkey
47 `, depth)
48
49 // Convert visited map to slice for query
50 visitedList := make([]string, 0, len(visited))
51 for pk := range visited {
52 visitedList = append(visitedList, pk)
53 }
54
55 params := map[string]any{
56 "seed": seedHex,
57 "visited": visitedList,
58 }
59
60 queryResult, err := n.ExecuteRead(ctx, cypher, params)
61 if err != nil {
62 n.Logger.Warningf("TraverseFollows: error at depth %d: %v", depth, err)
63 continue
64 }
65
66 newPubkeysAtDepth := 0
67 for queryResult.Next(ctx) {
68 record := queryResult.Record()
69 pubkey, ok := record.Values[0].(string)
70 if !ok || pubkey == "" {
71 continue
72 }
73
74 // Normalize to lowercase for consistency
75 pubkey = strings.ToLower(pubkey)
76
77 // Add to result if not already seen
78 if !visited[pubkey] {
79 visited[pubkey] = true
80 result.AddPubkeyAtDepth(pubkey, depth)
81 newPubkeysAtDepth++
82 }
83 }
84
85 n.Logger.Debugf("TraverseFollows: depth %d found %d new pubkeys", depth, newPubkeysAtDepth)
86
87 // Early termination if no new pubkeys found at this depth
88 if newPubkeysAtDepth == 0 {
89 break
90 }
91 }
92
93 n.Logger.Debugf("TraverseFollows: completed with %d total pubkeys across %d depths",
94 result.TotalPubkeys, len(result.PubkeysByDepth))
95
96 return result, nil
97 }
98
99 // TraverseFollowers performs BFS traversal to find who follows the seed pubkey.
100 // This is the reverse of TraverseFollows - it finds users whose kind-3 lists
101 // contain the target pubkey(s).
102 //
103 // Uses Neo4j's native path queries, but in reverse direction:
104 // - Depth 1: Users who directly follow the seed (follower)-[:FOLLOWS]->(seed)
105 // - Depth 2: Users who follow anyone at depth 1 (followers of followers)
106 // - etc.
107 func (n *N) TraverseFollowers(seedPubkey []byte, maxDepth int) (graph.GraphResultI, error) {
108 result := NewGraphResult()
109
110 if len(seedPubkey) != 32 {
111 return result, fmt.Errorf("invalid pubkey length: expected 32, got %d", len(seedPubkey))
112 }
113
114 seedHex := strings.ToLower(hex.Enc(seedPubkey))
115 ctx := context.Background()
116
117 // Track visited pubkeys
118 visited := make(map[string]bool)
119 visited[seedHex] = true
120
121 // Process each depth level separately for BFS semantics
122 for depth := 1; depth <= maxDepth; depth++ {
123 // Query for pubkeys at exactly this depth that haven't been seen yet
124 // Direction is reversed: we find users who follow the targets
125 cypher := fmt.Sprintf(`
126 MATCH path = (follower:NostrUser)-[:FOLLOWS*%d]->(seed:NostrUser {pubkey: $seed})
127 WHERE follower.pubkey <> $seed
128 AND NOT follower.pubkey IN $visited
129 RETURN DISTINCT follower.pubkey AS pubkey
130 `, depth)
131
132 visitedList := make([]string, 0, len(visited))
133 for pk := range visited {
134 visitedList = append(visitedList, pk)
135 }
136
137 params := map[string]any{
138 "seed": seedHex,
139 "visited": visitedList,
140 }
141
142 queryResult, err := n.ExecuteRead(ctx, cypher, params)
143 if err != nil {
144 n.Logger.Warningf("TraverseFollowers: error at depth %d: %v", depth, err)
145 continue
146 }
147
148 newPubkeysAtDepth := 0
149 for queryResult.Next(ctx) {
150 record := queryResult.Record()
151 pubkey, ok := record.Values[0].(string)
152 if !ok || pubkey == "" {
153 continue
154 }
155
156 pubkey = strings.ToLower(pubkey)
157
158 if !visited[pubkey] {
159 visited[pubkey] = true
160 result.AddPubkeyAtDepth(pubkey, depth)
161 newPubkeysAtDepth++
162 }
163 }
164
165 n.Logger.Debugf("TraverseFollowers: depth %d found %d new pubkeys", depth, newPubkeysAtDepth)
166
167 if newPubkeysAtDepth == 0 {
168 break
169 }
170 }
171
172 n.Logger.Debugf("TraverseFollowers: completed with %d total pubkeys", result.TotalPubkeys)
173
174 return result, nil
175 }
176
177 // TraverseFollowsFromHex is a convenience wrapper that accepts hex-encoded pubkey.
178 func (n *N) TraverseFollowsFromHex(seedPubkeyHex string, maxDepth int) (*GraphResult, error) {
179 seedPubkey, err := hex.Dec(seedPubkeyHex)
180 if err != nil {
181 return nil, err
182 }
183 result, err := n.TraverseFollows(seedPubkey, maxDepth)
184 if err != nil {
185 return nil, err
186 }
187 return result.(*GraphResult), nil
188 }
189
190 // TraverseFollowersFromHex is a convenience wrapper that accepts hex-encoded pubkey.
191 func (n *N) TraverseFollowersFromHex(seedPubkeyHex string, maxDepth int) (*GraphResult, error) {
192 seedPubkey, err := hex.Dec(seedPubkeyHex)
193 if err != nil {
194 return nil, err
195 }
196 result, err := n.TraverseFollowers(seedPubkey, maxDepth)
197 if err != nil {
198 return nil, err
199 }
200 return result.(*GraphResult), nil
201 }
202