graph.go raw
1 package nostr
2
3 import "strconv"
4
5 // EventGraph builds a coherence graph from ingested Nostr events.
6 // Events cluster by author (pubkey) and kind. References (e-tags, p-tags)
7 // form bonds between events. References to unknown events or pubkeys
8 // are recorded as orphans — the negative space of what's missing.
9 //
10 // This is Stage 4b (Coagula): evaluate what was ingested, find the
11 // structure, and identify the gaps.
12
13 // GraphNode is one event in the graph, with its cluster memberships
14 // and reference edges.
15 type GraphNode struct {
16 Event *Event
17 InRefs []string // IDs of events that reference this one
18 }
19
20 // Cluster groups events that share a common property.
21 type Cluster struct {
22 Key string // the shared value (pubkey hex, or "kind:<N>")
23 Type string // "author" or "kind"
24 Events []string // event IDs in this cluster
25 }
26
27 // Orphan is a reference to something not present in the graph.
28 // It is the shape of what's missing — typed negative space.
29 type Orphan struct {
30 Type string // "event" or "pubkey"
31 ID string // the missing event ID or pubkey hex
32 RefBy string // the event ID that references it
33 TagIdx int // index of the tag within the referencing event
34 }
35
36 // GraphStats summarizes the graph structure.
37 type GraphStats struct {
38 TotalEvents int
39 AuthorClusters int // distinct pubkeys
40 KindClusters int // distinct kinds
41 RefBonds int // resolved e-tag references (both ends present)
42 Orphans int // unresolved references
43 LargestAuthor int // size of the largest author cluster
44 LargestKind int // size of the largest kind cluster
45 }
46
47 // EventGraph is the coherence graph over a set of ingested events.
48 type EventGraph struct {
49 Nodes map[string]*GraphNode // event ID → node
50 Authors map[string]*Cluster // pubkey → author cluster
51 Kinds map[string]*Cluster // "kind:<N>" → kind cluster
52 Orphans []Orphan // unresolved references
53 PubkeysR map[string][]string // pubkey → event IDs that p-tag it (for resolve check)
54 }
55
56 // NewEventGraph creates an empty event graph.
57 func NewEventGraph() *EventGraph {
58 return &EventGraph{
59 Nodes: make(map[string]*GraphNode),
60 Authors: make(map[string]*Cluster),
61 Kinds: make(map[string]*Cluster),
62 PubkeysR: make(map[string][]string),
63 }
64 }
65
66 // Add inserts a validated event into the graph.
67 // The event is added to its author and kind clusters.
68 func (g *EventGraph) Add(ev *Event) {
69 if _, exists := g.Nodes[ev.ID]; exists {
70 return // deduplicate
71 }
72
73 g.Nodes[ev.ID] = &GraphNode{Event: ev}
74
75 // Author cluster.
76 ac, ok := g.Authors[ev.Pubkey]
77 if !ok {
78 ac = &Cluster{Key: ev.Pubkey, Type: "author"}
79 g.Authors[ev.Pubkey] = ac
80 }
81 ac.Events = append(ac.Events, ev.ID)
82
83 // Kind cluster.
84 kk := kindKey(ev.Kind)
85 kc, ok := g.Kinds[kk]
86 if !ok {
87 kc = &Cluster{Key: kk, Type: "kind"}
88 g.Kinds[kk] = kc
89 }
90 kc.Events = append(kc.Events, ev.ID)
91 }
92
93 // Resolve walks all events, resolving e-tag and p-tag references.
94 // Resolved references become InRef edges on the target node.
95 // Unresolved references become Orphans.
96 func (g *EventGraph) Resolve() {
97 g.Orphans = nil
98
99 for _, node := range g.Nodes {
100 for i, tag := range node.Event.Tags {
101 if len(tag) < 2 {
102 continue
103 }
104 switch tag[0] {
105 case "e":
106 // Event reference.
107 targetID := tag[1]
108 if target, ok := g.Nodes[targetID]; ok {
109 // Bond: both ends present.
110 target.InRefs = append(target.InRefs, node.Event.ID)
111 } else {
112 // Orphan: referencing an event we don't have.
113 g.Orphans = append(g.Orphans, Orphan{
114 Type: "event",
115 ID: targetID,
116 RefBy: node.Event.ID,
117 TagIdx: i,
118 })
119 }
120 case "p":
121 // Pubkey mention.
122 targetPK := tag[1]
123 g.PubkeysR[targetPK] = append(g.PubkeysR[targetPK], node.Event.ID)
124 if _, ok := g.Authors[targetPK]; !ok {
125 // Orphan: mentioning an author we haven't seen.
126 g.Orphans = append(g.Orphans, Orphan{
127 Type: "pubkey",
128 ID: targetPK,
129 RefBy: node.Event.ID,
130 TagIdx: i,
131 })
132 }
133 }
134 }
135 }
136 }
137
138 // Stats returns a summary of the graph structure.
139 func (g *EventGraph) Stats() GraphStats {
140 s := GraphStats{
141 TotalEvents: len(g.Nodes),
142 AuthorClusters: len(g.Authors),
143 KindClusters: len(g.Kinds),
144 Orphans: len(g.Orphans),
145 }
146
147 // Count resolved reference bonds.
148 for _, node := range g.Nodes {
149 s.RefBonds += len(node.InRefs)
150 }
151
152 // Find largest clusters.
153 for _, c := range g.Authors {
154 if len(c.Events) > s.LargestAuthor {
155 s.LargestAuthor = len(c.Events)
156 }
157 }
158 for _, c := range g.Kinds {
159 if len(c.Events) > s.LargestKind {
160 s.LargestKind = len(c.Events)
161 }
162 }
163
164 return s
165 }
166
167 // OrphansByType returns orphans grouped by type ("event" or "pubkey").
168 func (g *EventGraph) OrphansByType() map[string][]Orphan {
169 m := make(map[string][]Orphan)
170 for _, o := range g.Orphans {
171 m[o.Type] = append(m[o.Type], o)
172 }
173 return m
174 }
175
176 // kindKey produces the cluster key for a kind value.
177 func kindKey(kind int) string {
178 return "kind:" + strconv.Itoa(kind)
179 }
180