@freemo

# Module: Iced Quinn, 2021 # Algorithm: Jeffrey Phillips Freeman, 2017 # https://jeffreyfreeman.me/hyperassociative-map-explanation/ import math, random # chi: ideal distance between nodes # sigma: how strong unrelated nodes repel one another; smaller is stronger # nu: learning rate # beta: alignment threshold; stop when movement in an iteration falls below this # neighbors: any vertex connected by an edge to this one # non-neighbor: other vertices who are not connected by an edge # TODO don't take sqrts and use pre-squared values; saves time const Nu = 0.05 Beta = 0.005 type Vertex* = object x*, y*: float edges*: seq[int] Edge* = object v1*, v2*: int length*: float Solver* = object chi*, sigma*: float vertices*: seq[Vertex] edges*: seq[Edge] rng*: Rand func add*(self: var Solver; v: Vertex) {.inline.} = self.vertices.add v func add*(self: var Solver; e: Edge) {.inline.} = self.edges.add e self.vertices[e.v1].edges.add self.edges.high self.vertices[e.v2].edges.add self.edges.high func mag(s: varargs[float]): float = result = 0 for k in s: result += (k * k) result = sqrt(result) func relates(self: Edge; v: int): bool = result = false if self.v1 == v: return true if self.v2 == v: return true func opposite(self: Edge; v: int): int = if v == self.v1: return self.v2 if v == self.v2: return self.v1 # TODO find proper exception raise new_exception(Defect, "Vertex was not in edge") func set_defaults*(self: var Solver) = self.chi = 1 self.sigma = 2 func validate(self: Edge) = assert self.length > 0 func validate(self: Solver) = assert self.sigma > 1 func randomize(self: var Solver) = # TODO somehow check if the randomizer is uninitialized, as that will cause an infinite lockup for i in 0..<self.vertices.len: self.vertices[i].x = self.rng.gauss() self.vertices[i].y = self.rng.gauss() iterator neighbors(self: Solver; vi: int): lent Vertex = # yield only nodes which do share edges with v_i for ei in self.vertices[vi].edges: yield self.vertices[opposite(self.edges[ei], vi)] iterator neighbors_edge(self: Solver; vi: int): (lent Vertex, float) = # yield only nodes which do share edges with v_i for ei in self.vertices[vi].edges: yield (self.vertices[opposite(self.edges[ei], vi)], self.edges[ei].length) iterator not_neighbors(self: Solver; vi: int): lent Vertex = # yield only nodes which do not have edges with v_i for i in 0..<self.vertices.len: block mushroom: for ei in self.vertices[i].edges: if relates(self.edges[ei], vi): break mushroom yield self.vertices[i] func align(self: var Solver; vi: int): (float, float) = var v = addr self.vertices[vi] let px = v.x let py = v.y var dpx = 0.0 var dpy = 0.0 for (m, chi) in neighbors_edge(self, vi): let qx = m.x - px let qy = m.y - py let q = mag(qx, qy) dpx += qx * (((q - chi) * Nu) / q) dpy += qy * (((q - chi) * Nu) / q) for m in not_neighbors(self, vi): let qx = m.x - px let qy = m.y - py let q = mag(qx, qy) var cx = qx * (-Nu / (pow(q, self.sigma + 1))) var cy = qy * (-Nu / (pow(q, self.sigma + 1))) let c = mag(cx, cy) if c > self.chi: cx *= (self.chi / c) cy *= (self.chi / c) dpx += cx dpy += cy return (dpx, dpy) func align_all(self: var Solver): float = result = 0 for i in 0..<self.vertices.len: var v = addr self.vertices[i] let (dpx, dpy) = align(self, i) let dp = mag(dpx, dpy) if dp > result: result = dp v.x += dpx v.y += dpy func solve*(self: var Solver) = validate(self) debugecho "> randomizing" randomize(self) debugecho "> solving" var i = 0 let target = Beta * self.chi while true: let energy = align_all(self) inc i debugecho i, ",", energy if energy < target: break # optional: could recenter the graph if you wanted