1/** 2 * graph-layout.js â Band-constrained layered layout algorithm. 3 * 4 * Supports two orientations: 5 * Vertical (default): bands stack top-to-bottom, flow downward. 6 * Horizontal: bands stack left-to-right, flow rightward. 7 * 8 * Within each band, molecules sit on one sub-row/column and reactions on another. 9 * Positions optimized via barycenter heuristic to reduce edge crossings. 10 */ 11(function() { 12 'use strict'; 13 14 var SV = window.SynthVis = window.SynthVis || {}; 15 16 // Layout constants 17 var C = SV.LAYOUT = { 18 CANVAS_W: 1800, 19 CANVAS_H: 1000, 20 MARGIN_X: 50, 21 MARGIN_Y: 30, 22 BAND_GAP: 4, // gap between bands 23 MOL_W: 100, 24 MOL_H: 100, 25 RXN_W: 120, 26 RXN_H: 44, 27 MIN_H_GAP: 50, // minimum gap between nodes 28 STARTING_ROW_H: 80, // height/width for starting molecule row/column 29 }; 30 31 // Layout orientation: 'vertical' (top-to-bottom) or 'horizontal' (left-to-right) 32 SV.layoutDirection = 'vertical'; 33 34 function isHorizontal() { 35 return SV.layoutDirection === 'horizontal'; 36 } 37 38 // Band order (top-to-bottom in vertical, left-to-right in horizontal) 39 var BANDS = ['Hydrothermal', 'Surface', 'Biochemical']; 40 41 /** 42 * Main entry: compute positions for all nodes. 43 * Returns Map<nodeId, {x, y, w, h}> 44 */ 45 SV.computeLayout = function(molecules, reactions, edges) { 46 var bandOf = assignBands(molecules, reactions); 47 48 // Separate starting molecules into their own row/column 49 var startingIds = []; 50 var bandNodes = {}; // band â { mols: [], rxns: [] } 51 BANDS.forEach(function(b) { bandNodes[b] = { mols: [], rxns: [] }; }); 52 53 molecules.forEach(function(mol, id) { 54 if (mol.role === 'starting') { 55 startingIds.push(id); 56 } else { 57 var band = bandOf.get(id) || 'Surface'; 58 bandNodes[band].mols.push(id); 59 } 60 }); 61 62 reactions.forEach(function(rxn, id) { 63 var band = bandOf.get(id) || 'Surface'; 64 bandNodes[band].rxns.push(id); 65 }); 66 67 // Dynamic canvas sizing based on node counts 68 computeDynamicCanvasSize(startingIds, bandNodes); 69 70 // Compute band rects AFTER dynamic sizing so they use updated canvas dimensions 71 var bandRects = computeBandRects(molecules, bandOf); 72 73 // Build neighbor map once for connectivity-based ordering 74 var neighbors = buildNeighbors(edges); 75 76 var positions = new Map(); 77 78 if (isHorizontal()) { 79 // --- Horizontal layout: bands as vertical columns, flow left-to-right --- 80 81 // Starting molecules in left column (no upstream, sort by ID) 82 startingIds.sort(); 83 placeColumn(startingIds, C.MARGIN_X, C.MOL_W, C.MOL_H, positions); 84 85 // Place nodes in each band column, ordered by connectivity 86 BANDS.forEach(function(band) { 87 var br = bandRects[band]; 88 if (!br) return; 89 90 var rxns = bandNodes[band].rxns; 91 var mols = bandNodes[band].mols; 92 93 var molX = br.x + br.w * 0.2; 94 var rxnX = br.x + br.w * 0.6; 95 96 // Reactions first (sorted by median of already-placed inputs) 97 var sortedRxns = sortByMedianNeighborPos(rxns, positions, neighbors, 'y'); 98 placeColumn(sortedRxns, rxnX, C.RXN_W, C.RXN_H, positions); 99 100 // Molecules next (sorted by median of already-placed reactions) 101 var sortedMols = sortByMedianNeighborPos(mols, positions, neighbors, 'y'); 102 placeColumn(sortedMols, molX, C.MOL_W, C.MOL_H, positions); 103 }); 104 105 // Barycenter optimization on Y positions 106 for (var pass = 0; pass < 20; pass++) { 107 barycenterPassH(positions, molecules, reactions, edges, startingIds, bandNodes); 108 } 109 resolveOverlapsH(positions, startingIds, bandNodes); 110 111 } else { 112 // --- Vertical layout (default): bands as horizontal rows, flow top-to-bottom --- 113
114 // Starting molecules in top row (no upstream, sort by ID) 115 startingIds.sort(); 116 placeRow(startingIds, C.MARGIN_Y, C.MOL_W, C.MOL_H, positions); 117 118 // Place nodes in each band row, ordered by connectivity 119 BANDS.forEach(function(band) { 120 var br = bandRects[band]; 121 if (!br) return; 122 123 var rxns = bandNodes[band].rxns; 124 var mols = bandNodes[band].mols; 125 126 var molY = br.y + br.h * 0.2; 127 var rxnY = br.y + br.h * 0.6; 128 129 // Reactions first (sorted by median X of already-placed inputs) 130 var sortedRxns = sortByMedianNeighborPos(rxns, positions, neighbors, 'x'); 131 placeRow(sortedRxns, rxnY, C.RXN_W, C.RXN_H, positions); 132 133 // Molecules next (sorted by median X of already-placed reactions) 134 var sortedMols = sortByMedianNeighborPos(mols, positions, neighbors, 'x'); 135 placeRow(sortedMols, molY, C.MOL_W, C.MOL_H, positions); 136 }); 137 138 // Barycenter optimization on X positions 139 for (var pass = 0; pass < 20; pass++) { 140 barycenterPass(positions, molecules, reactions, edges, startingIds, bandNodes); 141 } 142 resolveOverlaps(positions, startingIds, bandNodes); 143 } 144 145 return positions; 146 }; 147 148 /** 149 * Get band rect definitions for rendering. 150 */ 151 SV.getBandRects = function(molecules, bandOf) { 152 return computeBandRects(molecules, bandOf); 153 }; 154 155 /** 156 * Assign each node to a band. 157 */ 158 SV.assignBands = function(molecules, reactions) { 159 return assignBands(molecules, reactions); 160 }; 161 162 function assignBands(molecules, reactions) { 163 var bandOf = new Map(); 164 165 // Reactions: directly from environment field 166 reactions.forEach(function(rxn, id) { 167 bandOf.set(id, rxn.environment || 'Surface'); 168 }); 169 170 // Molecules: by role, environment_formed, or inferred from producing reactions 171 molecules.forEach(function(mol, id) { 172 if (mol.role === 'starting') { 173 bandOf.set(id, 'Hydrothermal'); // starting row is above Hydrothermal 174 } else if (mol.role === 'target') { 175 bandOf.set(id, 'Biochemical'); 176 } else if (mol.environmentFormed) { 177 bandOf.set(id, mol.environmentFormed); 178 } else { 179 // Infer from producing reactions 180 var inferredBand = null; 181 reactions.forEach(function(rxn) { 182 if (!inferredBand && rxn.outputs.indexOf(id) >= 0) { 183 inferredBand = rxn.environment; 184 } 185 }); 186 // If consumed by multiple bands, pick the earliest 187 if (!inferredBand) { 188 reactions.forEach(function(rxn) { 189 if (!inferredBand && rxn.inputs.indexOf(id) >= 0) { 190 inferredBand = rxn.environment; 191 } 192 }); 193 } 194 bandOf.set(id, inferredBand || 'Surface'); 195 } 196 }); 197 198 return bandOf; 199 } 200 201 /** 202 * Dynamically size the canvas based on node counts per row. 203 */ 204 function computeDynamicCanvasSize(startingIds, bandNodes) { 205 // Collect all group sizes to find the widest/tallest row 206 var groups = [startingIds.length]; 207 BANDS.forEach(function(band) { 208 var bn = bandNodes[band]; 209 groups.push(bn.mols.length); 210 groups.push(bn.rxns.length); 211 }); 212 213 var maxNodesInGroup = Math.max.apply(null, groups); 214 var maxNodeW = Math.max(C.MOL_W, C.RXN_W); 215 216 if (isHorizontal()) { 217 // Height needs to fit the tallest column 218 var neededH = maxNodesInGroup * maxNodeW 219 + (Math.max(0, maxNodesInGroup - 1)) * C.MIN_H_GAP 220 + 2 * C.MARGIN_Y + 100; 221 C.CANVAS_H = Math.max(1000, neededH); 222 223 // Width: count active bands 224 var activeBands = 0; 225 BANDS.forEach(function(band) { 226 var bn = bandNodes[band]; 227 if (bn.mols.length > 0 || bn.rxns.length > 0) activeBands++; 228 }); 229 var neededW = C.MARGIN_X + C.STARTING_ROW_H + 10 230 + activeBands * 350 231 + C.MARGIN_X; 232 C.CANVAS_W = Math.max(1800, neededW); 233 } else { 234 // Width needs to fit the widest row 235 var neededW = maxNodesInGroup * maxNodeW 236 + (Math.max(0, maxNodesInGroup - 1)) * C.MIN_H_GAP 237 + 2 * C.MARGIN_X + 100; 238 C.CANVAS_W = Math.max(1800, neededW); 239 240 // Height: count active bands 241 var activeBands = 0; 242 BANDS.forEach(function(band) { 243 var bn = bandNodes[band]; 244 if (bn.mols.length > 0 || bn.rxns.length > 0) activeBands++; 245 }); 246 var neededH = C.MARGIN_Y + C.STARTING_ROW_H + 10 247 + activeBands * 220 248 + C.MARGIN_Y; 249 C.CANVAS_H = Math.max(1000, neededH); 250 } 251 } 252 253 function computeBandRects(molecules, bandOf) { 254 // Count nodes per band to size bands 255 var counts = { Hydrothermal: 0, Surface: 0, Biochemical: 0 }; 256 if (bandOf) { 257 bandOf.forEach(function(band, id) { 258 if (counts[band] !== undefined) counts[band]++; 259 }); 260 } 261 262 var totalNodes = counts.Hydrothermal + counts.Surface + counts.Biochemical; 263 264 if (isHorizontal()) { 265 // Bands are vertical columns, left to right 266 var leftX = C.MARGIN_X + C.STARTING_ROW_H + 10; // after starting column 267 var availW = C.CANVAS_W - leftX - C.MARGIN_X; 268 269 var rects = {}; 270 var x = leftX; 271 BANDS.forEach(function(band) { 272 var frac = totalNodes > 0 ? Math.max(0.2, counts[band] / totalNodes) : (1 / 3); 273 var w = Math.max(200, availW * frac); 274 rects[band] = { band: band, x: x, y: 0, w: w, h: C.CANVAS_H }; 275 x += w + C.BAND_GAP; 276 }); 277 278 // Normalize to fit available width 279 var totalW = 0; 280 BANDS.forEach(function(b) { totalW += rects[b].w; }); 281 var scale = availW / (totalW + C.BAND_GAP * 2); 282 if (scale < 1) { 283 x = leftX; 284 BANDS.forEach(function(b) { 285 rects[b].w *= scale; 286 rects[b].x = x; 287 x += rects[b].w + C.BAND_GAP; 288 }); 289 } 290 291 return rects; 292 } 293 294 // Vertical: bands are horizontal rows, top to bottom 295 var topY = C.MARGIN_Y + C.STARTING_ROW_H + 10; // below starting row 296 var availH = C.CANVAS_H - topY - C.MARGIN_Y; 297 298 var rects = {}; 299 var y = topY; 300 BANDS.forEach(function(band) {
301 // Proportional height based on node count, with minimum 302 var frac = totalNodes > 0 ? Math.max(0.2, counts[band] / totalNodes) : (1 / 3); 303 var h = Math.max(140, availH * frac); 304 rects[band] = { band: band, x: 0, y: y, w: C.CANVAS_W, h: h }; 305 y += h + C.BAND_GAP; 306 }); 307 308 // Normalize to fit available height 309 var totalH = 0; 310 BANDS.forEach(function(b) { totalH += rects[b].h; }); 311 var scale = availH / (totalH + C.BAND_GAP * 2); 312 if (scale < 1) { 313 y = topY; 314 BANDS.forEach(function(b) { 315 rects[b].h *= scale; 316 rects[b].y = y; 317 y += rects[b].h + C.BAND_GAP; 318 }); 319 } 320 321 return rects; 322 } 323 324 // ===== Connectivity-based ordering helpers ===== 325 326 /** 327 * Sort node IDs by median position of their already-placed neighbors. 328 * Nodes with no placed neighbors are pushed to the end, sorted by ID. 329 */ 330 function sortByMedianNeighborPos(ids, positions, neighbors, axis) { 331 return ids.slice().sort(function(a, b) { 332 var aMedian = medianOfPlacedNeighbors(neighbors.get(a) || [], positions, axis); 333 var bMedian = medianOfPlacedNeighbors(neighbors.get(b) || [], positions, axis); 334 335 if (aMedian === null && bMedian === null) return a < b ? -1 : 1; 336 if (aMedian === null) return 1; 337 if (bMedian === null) return -1; 338 return aMedian - bMedian; 339 }); 340 } 341 342 /** 343 * Compute the median position (center) of already-placed neighbors. 344 * Returns null if no neighbors are placed yet. 345 */ 346 function medianOfPlacedNeighbors(nbrIds, positions, axis) { 347 var vals = []; 348 for (var i = 0; i < nbrIds.length; i++) { 349 var p = positions.get(nbrIds[i]); 350 if (p) { 351 vals.push(axis === 'x' ? p.x + p.w / 2 : p.y + p.h / 2); 352 } 353 } 354 if (vals.length === 0) return null; 355 vals.sort(function(a, b) { return a - b; }); 356 var mid = Math.floor(vals.length / 2); 357 return vals.length % 2 === 0 ? (vals[mid - 1] + vals[mid]) / 2 : vals[mid]; 358 } 359 360 // ===== Vertical layout helpers ===== 361 362 /** 363 * Place a row of nodes evenly centered horizontally. 364 * Caller is responsible for ordering ids. 365 */ 366 function placeRow(ids, centerY, nodeW, nodeH, positions) { 367 if (ids.length === 0) return; 368 var n = ids.length; 369 var totalW = n * nodeW + (n - 1) * C.MIN_H_GAP; 370 var startX = Math.max(C.MARGIN_X + 40, (C.CANVAS_W - totalW) / 2); 371 372 ids.forEach(function(id, i) { 373 positions.set(id, { 374 x: startX + i * (nodeW + C.MIN_H_GAP), 375 y: centerY - nodeH / 2, 376 w: nodeW, 377 h: nodeH 378 }); 379 }); 380 } 381 382 /** 383 * One pass of barycenter heuristic (vertical: optimizes X). 384 * Uses variable spacing â places nodes at ideal X, enforcing minimum gaps. 385 */ 386 function barycenterPass(positions, molecules, reactions, edges, startingIds, bandNodes) { 387 var neighbors = buildNeighbors(edges); 388 389 var groups = []; 390 groups.push({ ids: startingIds, nodeW: C.MOL_W }); 391 BANDS.forEach(function(band) { 392 var bn = bandNodes[band]; 393 groups.push({ ids: bn.mols, nodeW: C.MOL_W }); 394 groups.push({ ids: bn.rxns, nodeW: C.RXN_W }); 395 }); 396 397 groups.forEach(function(group) { 398 var ids = group.ids; 399 var nodeW = group.nodeW; 400 if (ids.length <= 1) return; 401 402 var ideals = ids.map(function(id) { 403 var nbrs = neighbors.get(id) || []; 404 var pos = positions.get(id); 405 if (!pos || nbrs.length === 0) return { id: id, idealX: pos ? pos.x : 0 }; 406 407 var sum = 0; 408 var count = 0; 409 nbrs.forEach(function(nbId) { 410 var npos = positions.get(nbId); 411 if (npos) { 412 sum += npos.x + npos.w / 2; 413 count++; 414 } 415 }); 416 var avgX = count > 0 ? (sum / count) - nodeW / 2 : pos.x; 417 return { id: id, idealX: avgX }; 418 }); 419 420 ideals.sort(function(a, b) { return a.idealX - b.idealX; }); 421 422 var n = ideals.length; 423 if (n === 0) return; 424 425 // Variable spacing: place at ideal positions, enforce minimum gaps 426 var placed = [ideals[0].idealX]; 427 for (var i = 1; i < n; i++) { 428 var minAllowed = placed[i - 1] + nodeW + C.MIN_H_GAP; 429 placed.push(Math.max(ideals[i].idealX, minAllowed)); 430 } 431 432 // Shift group to stay within canvas bounds 433 var groupLeft = placed[0]; 434 var groupRight = placed[n - 1] + nodeW; 435 var shift = 0; 436 if (groupLeft < C.MARGIN_X + 40) { 437 shift = (C.MARGIN_X + 40) - groupLeft; 438 } else if (groupRight > C.CANVAS_W - C.MARGIN_X) { 439 shift = (C.CANVAS_W - C.MARGIN_X) - groupRight; 440 } 441
442 ideals.forEach(function(item, i) { 443 var pos = positions.get(item.id); 444 if (pos) { 445 pos.x = placed[i] + shift; 446 } 447 }); 448 }); 449 } 450 451 /** 452 * Resolve overlaps (vertical): ensure minimum gaps between nodes on X axis. 453 * Preserves relative order and variable spacing from barycenter. 454 */ 455 function resolveOverlaps(positions, startingIds, bandNodes) { 456 var groups = []; 457 groups.push({ ids: startingIds, nodeW: C.MOL_W }); 458 BANDS.forEach(function(band) { 459 var bn = bandNodes[band]; 460 groups.push({ ids: bn.mols, nodeW: C.MOL_W }); 461 groups.push({ ids: bn.rxns, nodeW: C.RXN_W }); 462 }); 463 464 groups.forEach(function(group) { 465 var ids = group.ids; 466 var nodeW = group.nodeW; 467 if (ids.length <= 1) return; 468 469 var sorted = ids.slice().sort(function(a, b) { 470 return (positions.get(a).x || 0) - (positions.get(b).x || 0); 471 }); 472 473 // Forward pass: push right any node that overlaps its left neighbor 474 for (var i = 1; i < sorted.length; i++) { 475 var prev = positions.get(sorted[i - 1]); 476 var curr = positions.get(sorted[i]); 477 var minX = prev.x + nodeW + C.MIN_H_GAP; 478 if (curr.x < minX) { 479 curr.x = minX; 480 } 481 } 482 483 // Check if group exceeds canvas right bound 484 var lastPos = positions.get(sorted[sorted.length - 1]); 485 var overflow = (lastPos.x + nodeW + C.MARGIN_X) - C.CANVAS_W; 486 if (overflow > 0) { 487 var maxShift = positions.get(sorted[0]).x - (C.MARGIN_X + 40); 488 var shiftLeft = Math.min(overflow, Math.max(0, maxShift)); 489 sorted.forEach(function(id) { 490 positions.get(id).x -= shiftLeft; 491 }); 492 } 493 }); 494 } 495 496 // ===== Horizontal layout helpers ===== 497 498 /** 499 * Place a column of nodes evenly centered vertically. 500 * Caller is responsible for ordering ids. 501 */ 502 function placeColumn(ids, centerX, nodeW, nodeH, positions) { 503 if (ids.length === 0) return; 504 var n = ids.length; 505 var totalH = n * nodeH + (n - 1) * C.MIN_H_GAP; 506 var startY = Math.max(C.MARGIN_Y + 40, (C.CANVAS_H - totalH) / 2); 507 508 ids.forEach(function(id, i) { 509 positions.set(id, { 510 x: centerX - nodeW / 2, 511 y: startY + i * (nodeH + C.MIN_H_GAP), 512 w: nodeW, 513 h: nodeH 514 }); 515 }); 516 } 517 518 /** 519 * One pass of barycenter heuristic (horizontal: optimizes Y). 520 * Uses variable spacing â places nodes at ideal Y, enforcing minimum gaps. 521 */ 522 function barycenterPassH(positions, molecules, reactions, edges, startingIds, bandNodes) { 523 var neighbors = buildNeighbors(edges); 524 525 var groups = []; 526 groups.push({ ids: startingIds, nodeH: C.MOL_H }); 527 BANDS.forEach(function(band) { 528 var bn = bandNodes[band]; 529 groups.push({ ids: bn.mols, nodeH: C.MOL_H }); 530 groups.push({ ids: bn.rxns, nodeH: C.RXN_H }); 531 }); 532 533 groups.forEach(function(group) { 534 var ids = group.ids; 535 var nodeH = group.nodeH; 536 if (ids.length <= 1) return; 537 538 var ideals = ids.map(function(id) { 539 var nbrs = neighbors.get(id) || []; 540 var pos = positions.get(id); 541 if (!pos || nbrs.length === 0) return { id: id, idealY: pos ? pos.y : 0 }; 542 543 var sum = 0; 544 var count = 0; 545 nbrs.forEach(function(nbId) { 546 var npos = positions.get(nbId); 547 if (npos) { 548 sum += npos.y + npos.h / 2; 549 count++; 550 } 551 }); 552 var avgY = count > 0 ? (sum / count) - nodeH / 2 : pos.y; 553 return { id: id, idealY: avgY }; 554 }); 555 556 ideals.sort(function(a, b) { return a.idealY - b.idealY; }); 557 558 var n = ideals.length; 559 if (n === 0) return; 560 561 // Variable spacing: place at ideal positions, enforce minimum gaps 562 var placed = [ideals[0].idealY]; 563 for (var i = 1; i < n; i++) { 564 var minAllowed = placed[i - 1] + nodeH + C.MIN_H_GAP; 565 placed.push(Math.max(ideals[i].idealY, minAllowed)); 566 } 567 568 // Shift group to stay within canvas bounds 569 var groupTop = placed[0]; 570 var groupBottom = placed[n - 1] + nodeH; 571 var shift = 0; 572 if (groupTop < C.MARGIN_Y + 40) { 573 shift = (C.MARGIN_Y + 40) - groupTop; 574 } else if (groupBottom > C.CANVAS_H - C.MARGIN_Y) { 575 shift = (C.CANVAS_H - C.MARGIN_Y) - groupBottom; 576 } 577
578 ideals.forEach(function(item, i) { 579 var pos = positions.get(item.id); 580 if (pos) { 581 pos.y = placed[i] + shift; 582 } 583 }); 584 }); 585 } 586 587 /** 588 * Resolve overlaps (horizontal): ensure minimum gaps between nodes on Y axis. 589 * Preserves relative order and variable spacing from barycenter. 590 */ 591 function resolveOverlapsH(positions, startingIds, bandNodes) { 592 var groups = []; 593 groups.push({ ids: startingIds, nodeH: C.MOL_H }); 594 BANDS.forEach(function(band) { 595 var bn = bandNodes[band]; 596 groups.push({ ids: bn.mols, nodeH: C.MOL_H }); 597 groups.push({ ids: bn.rxns, nodeH: C.RXN_H }); 598 }); 599 600 groups.forEach(function(group) { 601 var ids = group.ids; 602 var nodeH = group.nodeH; 603 if (ids.length <= 1) return; 604 605 var sorted = ids.slice().sort(function(a, b) { 606 return (positions.get(a).y || 0) - (positions.get(b).y || 0); 607 }); 608 609 // Forward pass: push down any node that overlaps its upper neighbor 610 for (var i = 1; i < sorted.length; i++) { 611 var prev = positions.get(sorted[i - 1]); 612 var curr = positions.get(sorted[i]); 613 var minY = prev.y + nodeH + C.MIN_H_GAP; 614 if (curr.y < minY) { 615 curr.y = minY; 616 } 617 } 618 619 // Check if group exceeds canvas bottom bound 620 var lastPos = positions.get(sorted[sorted.length - 1]); 621 var overflow = (lastPos.y + nodeH + C.MARGIN_Y) - C.CANVAS_H; 622 if (overflow > 0) { 623 var maxShift = positions.get(sorted[0]).y - (C.MARGIN_Y + 40); 624 var shiftUp = Math.min(overflow, Math.max(0, maxShift)); 625 sorted.forEach(function(id) { 626 positions.get(id).y -= shiftUp; 627 }); 628 } 629 }); 630 } 631 632 // ===== Shared helpers ===== 633 634 function buildNeighbors(edges) { 635 var neighbors = new Map();
636 edges.forEach(function(e) { 637 if (!neighbors.has(e.sourceId)) neighbors.set(e.sourceId, []); 638 if (!neighbors.has(e.targetId)) neighbors.set(e.targetId, []); 639 neighbors.get(e.sourceId).push(e.targetId); 640 neighbors.get(e.targetId).push(e.sourceId); 641 }); 642 return neighbors; 643 } 644 645})();
Line numbers count LF bytes from the start of the resource, as the search results do. Vendor segments are library code the classifier recognised; they are stored but not indexed. Bytes are shown as Latin1 characters, one per byte.