236 {
237 graph = SegmentEdgeGraph{};
238 graph.segments.reserve(segments.
size());
240
241
243
244
245
246
247
248
249
250 std::map<SegmentBucketKey, std::vector<const xAOD::MuonSegment*>>
251 segmentsByBucket;
253 segmentsByBucket[segmentBucketKey(*segment)].push_back(segment);
254 }
255
256 const InferenceUtils::SegmentQualityOrder betterSegment{};
257
258 std::unordered_set<const xAOD::MuonSegment*> retainedSegments;
259 retainedSegments.reserve(segments.size());
260 for (auto& [_, bucketSegments] : segmentsByBucket) {
261 std::ranges::sort(bucketSegments, betterSegment);
263 ? bucketSegments.size()
264 : std::min<std::size_t>(
265 bucketSegments.size(),
267 retainedSegments.insert(bucketSegments.begin(),
268 bucketSegments.begin() + nKeep);
269 }
270
271 std::vector<Amg::Vector3D>
pos;
272 std::vector<Amg::Vector3D>
dir;
273 std::vector<BucketSegmentFeatures> bucket;
274 pos.reserve(retainedSegments.size());
275 dir.reserve(retainedSegments.size());
276 bucket.reserve(retainedSegments.size());
277
279 if (!retainedSegments.contains(segment)) continue;
280
283 const SegmentBucketKey
key = segmentBucketKey(*segment);
284 const auto bucketIt = segmentsByBucket.find(key);
285 const int multiplicity =
286 bucketIt == segmentsByBucket.end()
287 ? 1
288 : static_cast<int>(bucketIt->second.size());
289
290 const int chamberIndex = static_cast<int>(segment->chamberIndex());
292 const int sector = segment->sector();
293
294 graph.segments.push_back(segment);
295 pos.emplace_back(position / Gaudi::Units::m);
296 dir.emplace_back(direction);
297 bucket.emplace_back(BucketSegmentFeatures{
298 chamberIndex,
layers, sector, multiplicity});
300 graph.nodeFeatures.push_back(
301 nodeFeatureValue(featureId,
pos.back(),
dir.back(), bucket.back()));
302 }
303 }
304 graph.nNodes = graph.segments.size();
305
306 if (
pos.size() != graph.nNodes ||
dir.size() != graph.nNodes ||
307 bucket.size() != graph.nNodes) {
308 ATH_MSG_ERROR(
"Inconsistent vector sizes during graph building: nodes="
309 << graph.nNodes <<
", pos=" <<
pos.size()
310 <<
", dir=" <<
dir.size() <<
", bucket=" << bucket.size());
311 return StatusCode::FAILURE;
312 }
313
314 if (graph.nNodes < 2) {
315 graph.nEdges = 0;
317 return StatusCode::SUCCESS;
318 }
319
320 const auto wrapRegularSector = [&](int sector) {
321
322
326 }
327 return sector;
328 };
329
330
331
332
333
334
335 std::unordered_map<int, std::vector<std::size_t>> nodesBySector;
336 nodesBySector.reserve(graph.nNodes);
337 for (std::size_t node = 0; node < graph.nNodes; ++node) {
338 nodesBySector[wrapRegularSector(bucket[node].sector)].push_back(node);
339 }
340
341 std::unordered_map<int, std::vector<int>> targetSectorsBySourceSector;
342 targetSectorsBySourceSector.reserve(nodesBySector.size());
343 std::size_t sectorLocalEdgeUpperBound = 0;
344 for (const auto& [sourceSector, sourceNodes] : nodesBySector) {
345 std::vector<int> targetSectors;
349 targetSectors.push_back(wrapRegularSector(sourceSector + delta));
350 }
351 for (const int targetSector : targetSectors) {
352 const auto found = nodesBySector.find(targetSector);
353 if (found == nodesBySector.end()) continue;
354 sectorLocalEdgeUpperBound += sourceNodes.size() *
found->second.size();
355 if (targetSector == sourceSector) {
356 sectorLocalEdgeUpperBound -= sourceNodes.size();
357 }
358 }
359 targetSectorsBySourceSector.emplace(sourceSector,
360 std::move(targetSectors));
361 }
362
363
364
365
366
367
368
369
370 struct UndirectedEdge {
371 std::size_t
first{0};
375 float dz{0.f};
377 float cosAngle{0.f};
378 };
379 const auto betterEdge = [](
const UndirectedEdge&
first,
380 const UndirectedEdge&
second) {
383 if (cosOrder != 0) {
384 return cosOrder < 0;
385 }
386
387 const int distanceOrder =
389 if (distanceOrder != 0) {
390 return distanceOrder < 0;
391 }
394 };
395 const auto edgeKey = [](const UndirectedEdge& edge) {
396 return (static_cast<std::uint64_t>(edge.first) << 32) |
397 static_cast<std::uint64_t>(edge.second);
398 };
399
400 const unsigned int maxEdgesPerNode =
402 const unsigned int maxEdgesPerTargetChamber =
404 const bool usePreInferenceSelection =
405 maxEdgesPerNode != 0 || maxEdgesPerTargetChamber != 0;
406 std::vector<std::vector<UndirectedEdge>> bestEdgesByNode;
407 if (usePreInferenceSelection) {
408 bestEdgesByNode.resize(graph.nNodes);
409 const unsigned int reservePerNode =
410 maxEdgesPerNode != 0 ? maxEdgesPerNode : maxEdgesPerTargetChamber;
411 for (std::vector<UndirectedEdge>& edges : bestEdgesByNode) {
412 edges.reserve(reservePerNode);
413 }
414 } else {
415 graph.edgeIndex.reserve(2 * sectorLocalEdgeUpperBound);
417 }
418 const auto appendDirectedPair = [&](const UndirectedEdge& edge) {
419 graph.edgeIndex.push_back(static_cast<int64_t>(edge.first));
420 graph.edgeIndex.push_back(static_cast<int64_t>(edge.second));
421 graph.edgeFeatures.insert(
422 graph.edgeFeatures.end(),
423 {edge.dx, edge.dy, edge.dz, edge.distance, edge.cosAngle,
424 float(bucket[edge.first].chamberIndex ==
425 bucket[edge.second].chamberIndex),
426 float(bucket[edge.first].sector == bucket[edge.second].sector)});
427
428 graph.edgeIndex.push_back(static_cast<int64_t>(edge.second));
429 graph.edgeIndex.push_back(static_cast<int64_t>(edge.first));
430 graph.edgeFeatures.insert(
431 graph.edgeFeatures.end(),
432 {-edge.dx, -edge.dy, -edge.dz, edge.distance, edge.cosAngle,
433 float(bucket[edge.first].chamberIndex ==
434 bucket[edge.second].chamberIndex),
435 float(bucket[edge.first].sector == bucket[edge.second].sector)});
436 };
437
438 const auto retainForNode = [&](std::size_t node,
439 const UndirectedEdge& candidate) {
440 std::vector<UndirectedEdge>& retained = bestEdgesByNode[node];
441 const std::size_t
other = candidate.first == node ? candidate.second
442 : candidate.first;
443 const int targetChamber = bucket[
other].chamberIndex;
444
445 if (maxEdgesPerTargetChamber != 0) {
446 unsigned int sameChamberCount = 0;
447 auto worstSameChamber = retained.end();
448 for (auto it = retained.begin(); it != retained.end(); ++it) {
449 const std::size_t retainedOther =
450 it->first == node ?
it->second :
it->first;
451 if (bucket[retainedOther].chamberIndex != targetChamber) continue;
452 ++sameChamberCount;
453 if (worstSameChamber == retained.end() ||
454 betterEdge(*worstSameChamber, *it)) {
455 worstSameChamber =
it;
456 }
457 }
458 if (sameChamberCount >= maxEdgesPerTargetChamber) {
459 if (!betterEdge(candidate, *worstSameChamber)) return;
460 *worstSameChamber = candidate;
461 } else {
462 retained.push_back(candidate);
463 }
464 } else {
465 retained.push_back(candidate);
466 }
467
468 if (maxEdgesPerNode != 0 && retained.size() > maxEdgesPerNode) {
469 auto worst = retained.begin();
470 for (auto it = std::next(retained.begin()); it != retained.end(); ++it) {
471 if (betterEdge(*worst, *it))
worst =
it;
472 }
473 retained.erase(worst);
474 }
475 };
476
477 std::size_t candidatePairs = 0;
478 for (std::size_t first = 0;
first < graph.nNodes; ++
first) {
479 const auto sectorsIt =
480 targetSectorsBySourceSector.find(wrapRegularSector(bucket[first].sector));
481 if (sectorsIt == targetSectorsBySourceSector.end()) continue;
482 for (const int sector : sectorsIt->second) {
483 const auto targetIt = nodesBySector.find(sector);
484 if (targetIt == nodesBySector.end()) continue;
485
486 for (const std::size_t second : targetIt->second) {
487
488 if (second <= first) continue;
489 if (sectorDistance(bucket[first].sector, bucket[second].sector,
492 continue;
493 }
495 bucket[first].chamberIndex == bucket[second].chamberIndex) {
496 continue;
497 }
498 const float cosAngle =
static_cast<float>(
dir[
first].dot(dir[second]));
500
502 const UndirectedEdge candidate{
505 static_cast<float>(delta.x()),
506 static_cast<float>(delta.y()),
507 static_cast<float>(delta.z()),
508 static_cast<float>(delta.mag()),
509 cosAngle};
510 ++candidatePairs;
511
512 if (!usePreInferenceSelection) {
513 appendDirectedPair(candidate);
514 } else {
515 retainForNode(first, candidate);
516 retainForNode(second, candidate);
517 }
518 }
519 }
520 }
521 std::size_t retainedPairs = candidatePairs;
522 if (usePreInferenceSelection) {
523 const unsigned int selectedReservePerNode =
524 maxEdgesPerNode != 0 ? maxEdgesPerNode : maxEdgesPerTargetChamber;
525 std::unordered_set<std::uint64_t> selectedKeys;
526 selectedKeys.reserve(graph.nNodes * selectedReservePerNode);
527 std::vector<UndirectedEdge> selectedEdges;
528 selectedEdges.reserve(graph.nNodes * selectedReservePerNode);
529
530 for (const std::vector<UndirectedEdge>& nodeEdges : bestEdgesByNode) {
531 for (const UndirectedEdge& edge : nodeEdges) {
532 if (selectedKeys.insert(edgeKey(edge)).second) {
533 selectedEdges.push_back(edge);
534 }
535 }
536 }
537 std::sort(selectedEdges.begin(), selectedEdges.end(),
538 [](const UndirectedEdge& first,
539 const UndirectedEdge& second) {
540 if (first.first != second.first) {
541 return first.first < second.first;
542 }
544 });
545
546 retainedPairs = selectedEdges.size();
547 graph.edgeIndex.reserve(4 * retainedPairs);
549 for (const UndirectedEdge& edge : selectedEdges) {
550 appendDirectedPair(edge);
551 }
552 }
553 graph.nEdges = graph.edgeIndex.size() / 2;
554 const std::size_t nodesBeforeIsolatedNodeDrop = graph.nNodes;
556 std::vector<unsigned char>
active(graph.nNodes, 0);
557 for (const int64_t index : graph.edgeIndex) {
559 }
560 const std::size_t activeNodes =
561 std::count(
active.begin(),
active.end(),
static_cast<unsigned char>(1));
562 if (activeNodes != graph.nNodes) {
563 std::vector<std::size_t> oldToNew(graph.nNodes, graph.nNodes);
564 std::vector<const xAOD::MuonSegment*> compactedSegments;
565 std::vector<float> compactedNodeFeatures;
566 compactedSegments.reserve(activeNodes);
568 for (std::size_t oldNode = 0; oldNode < graph.nNodes; ++oldNode) {
569 if (!active[oldNode]) continue;
570 oldToNew[oldNode] = compactedSegments.size();
571 compactedSegments.push_back(graph.segments[oldNode]);
572 const auto featureBegin = graph.nodeFeatures.begin() +
574 compactedNodeFeatures.insert(compactedNodeFeatures.end(),
575 featureBegin,
577 }
578 for (int64_t& index : graph.edgeIndex) {
579 index =
static_cast<int64_t
>(oldToNew[
static_cast<std::size_t
>(
index)]);
580 }
581 graph.segments = std::move(compactedSegments);
582 graph.nodeFeatures = std::move(compactedNodeFeatures);
583 graph.nNodes = activeNodes;
584 }
585 }
587 ATH_MSG_DEBUG(
"buildGraph: input segments=" << segments.size()
588 << ", kept nodes=" << graph.nNodes
589 << ", nodes before isolated-node drop=" << nodesBeforeIsolatedNodeDrop
591 << ", candidate pairs=" << candidatePairs
592 << ", retained pairs=" << retainedPairs
593 << ", built directed edges=" << graph.nEdges
595 << ", per-target-chamber cap=" << maxEdgesPerTargetChamber
598 << ", sector-local reserve=" << sectorLocalEdgeUpperBound);
599
600
601 if (msgLvl(MSG::DEBUG)) {
607 }
608 return StatusCode::SUCCESS;
609}
const SpacePointBucket * parentBucket() const
Returns the bucket out of which the seed was formed.
const SegmentSeed * parent() const
Returns the seed out of which the segment was built.
float distance(const Amg::Vector3D &p1, const Amg::Vector3D &p2)
calculates the distance between two point in 3D space
Eigen::Matrix< double, 3, 1 > Vector3D
int compareFloat(float first, float second)
Three-way float comparison which orders NaN after all numeric values.
int compareFloatDescending(float first, float second)
Three-way descending comparison which also orders NaN last.
SegmentNodeFeatureId
Identifier for each node feature in segment-based GNNs.
const Segment * detailedSegment(const xAOD::MuonSegment &seg)
Helper function to navigate from the xAOD::MuonSegment to the MuonR4::Segment.
const Amg::Vector3D & direction() const
Method to retrieve the direction at the Intersection.
const Amg::Vector3D & position() const
Method to retrieve the position of the Intersection.
void sort(typename DataModel_detail::iterator< DVL > beg, typename DataModel_detail::iterator< DVL > end)
Specialization of sort for DataVector/List.
MuonSegment_v1 MuonSegment
Reference the current persistent version: