data/RelationKinship.cpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #include "RelationKinship.h" | ||
| 2 | |||
| 3 | #include "RelationInference.h" | ||
| 4 | #include "RelationVocabulary.h" | ||
| 5 | |||
| 6 | #include <QMultiMap> | ||
| 7 | |||
| 8 | namespace RelationKinship { | ||
| 9 | |||
| 10 | namespace { | ||
| 11 | |||
| 12 | struct Spanned { | ||
| 13 | const char *type; | ||
| 14 | int degree; | ||
| 15 | }; | ||
| 16 | |||
| 17 | // Partners and in-laws; blood relationships come from their kinship vector. | ||
| 18 | const Spanned kNonBlood[] = { | ||
| 19 | {"spouse", 0}, {"ex-partner", 1}, {"parent-in-law", 1}, | ||
| 20 | {"child-in-law", 1}, {"sibling-in-law", 2}, {"kin", UnknownKinDegree}, | ||
| 21 | }; | ||
| 22 | |||
| 23 | 5056 | bool isKinshipEdge(const RelationGraph::StoredEdge &edge) { | |
| 24 |
4/4✓ Branch 7 → 8 taken 1798 times.
✓ Branch 7 → 13 taken 331 times.
✓ Branch 8 → 9 taken 4662 times.
✓ Branch 8 → 13 taken 63 times.
|
15168 | return (edge.role == QLatin1String("relation") || edge.role == QLatin1String("inferred")) && edge.toCardId > 0 && |
| 25 |
6/7✓ Branch 4 → 5 taken 2129 times.
✓ Branch 4 → 8 taken 2927 times.
✓ Branch 9 → 10 taken 4662 times.
✗ Branch 9 → 13 not taken.
✓ Branch 10 → 11 taken 4662 times.
✓ Branch 11 → 12 taken 3334 times.
✓ Branch 11 → 13 taken 1328 times.
|
15168 | edge.fromCardId != edge.toCardId && degreeOf(edge.type) >= 0; |
| 26 | } | ||
| 27 | |||
| 28 | } // namespace | ||
| 29 | |||
| 30 | 8534 | int degreeOf(const QString &type) { | |
| 31 | 8534 | int up = 0, down = 0; | |
| 32 |
3/3✓ Branch 2 → 3 taken 8534 times.
✓ Branch 3 → 4 taken 4759 times.
✓ Branch 3 → 5 taken 3775 times.
|
8534 | if (RelationInference::kinship(type, &up, &down)) |
| 33 | 4759 | return up + down; | |
| 34 |
1/1✓ Branch 5 → 6 taken 3775 times.
|
3775 | const QString known = RelationVocabulary::canonical(type); |
| 35 |
2/2✓ Branch 12 → 7 taken 16261 times.
✓ Branch 12 → 13 taken 1537 times.
|
17798 | for (const Spanned &spanned : kNonBlood) |
| 36 |
2/2✓ Branch 9 → 10 taken 2238 times.
✓ Branch 9 → 11 taken 14023 times.
|
16261 | if (known == QLatin1String(spanned.type)) |
| 37 | 2238 | return spanned.degree; | |
| 38 | 1537 | return -1; | |
| 39 | 3775 | } | |
| 40 | |||
| 41 | 109 | QHash<qint64, int> degrees(const RelationGraph::Input &input, qint64 centerCardId) { | |
| 42 | 109 | QHash<qint64, QList<QPair<qint64, int>>> next; | |
| 43 |
2/2✓ Branch 18 → 4 taken 5056 times.
✓ Branch 18 → 19 taken 109 times.
|
5165 | for (const RelationGraph::StoredEdge &edge : input.edges) { |
| 44 |
3/3✓ Branch 5 → 6 taken 5056 times.
✓ Branch 6 → 7 taken 1722 times.
✓ Branch 6 → 8 taken 3334 times.
|
5056 | if (!isKinshipEdge(edge)) |
| 45 | 1722 | continue; | |
| 46 |
1/1✓ Branch 8 → 9 taken 3334 times.
|
3334 | const int degree = degreeOf(edge.type); |
| 47 |
2/2✓ Branch 9 → 10 taken 3334 times.
✓ Branch 11 → 12 taken 3334 times.
|
3334 | next[edge.fromCardId].append({edge.toCardId, degree}); |
| 48 |
2/2✓ Branch 12 → 13 taken 3334 times.
✓ Branch 14 → 15 taken 3334 times.
|
3334 | next[edge.toCardId].append({edge.fromCardId, degree}); |
| 49 | } | ||
| 50 |
1/1✓ Branch 20 → 21 taken 109 times.
|
109 | QHash<qint64, int> out{{centerCardId, 0}}; |
| 51 | // Dijkstra with an ordered queue; ties by card id keep it deterministic. | ||
| 52 | 109 | QMultiMap<QPair<int, qint64>, bool> queue; | |
| 53 |
1/1✓ Branch 22 → 23 taken 109 times.
|
109 | queue.insert({0, centerCardId}, true); |
| 54 |
3/3✓ Branch 57 → 58 taken 818 times.
✓ Branch 58 → 24 taken 709 times.
✓ Branch 58 → 59 taken 109 times.
|
818 | while (!queue.isEmpty()) { |
| 55 |
1/1✓ Branch 24 → 25 taken 709 times.
|
709 | const auto [distance, card] = queue.firstKey(); |
| 56 |
2/2✓ Branch 27 → 28 taken 709 times.
✓ Branch 29 → 30 taken 709 times.
|
709 | queue.erase(queue.begin()); |
| 57 |
1/2✗ Branch 31 → 32 not taken.
✓ Branch 31 → 33 taken 709 times.
|
709 | if (distance > out.value(card, distance)) |
| 58 | ✗ | continue; | |
| 59 |
4/4✓ Branch 34 → 35 taken 709 times.
✓ Branch 35 → 36 taken 709 times.
✓ Branch 54 → 37 taken 3908 times.
✓ Branch 54 → 55 taken 709 times.
|
4617 | for (const auto &[other, degree] : next.value(card)) { |
| 60 | 3908 | const int reached = distance + degree; | |
| 61 |
5/6✓ Branch 41 → 42 taken 3308 times.
✓ Branch 41 → 45 taken 600 times.
✓ Branch 43 → 44 taken 3308 times.
✗ Branch 43 → 45 not taken.
✓ Branch 46 → 47 taken 3308 times.
✓ Branch 46 → 48 taken 600 times.
|
3908 | if (out.contains(other) && out.value(other) <= reached) |
| 62 | 3308 | continue; | |
| 63 |
1/1✓ Branch 48 → 49 taken 600 times.
|
600 | out.insert(other, reached); |
| 64 |
1/1✓ Branch 50 → 51 taken 600 times.
|
600 | queue.insert({reached, other}, true); |
| 65 | 709 | } | |
| 66 | } | ||
| 67 | 109 | return out; | |
| 68 | 109 | } | |
| 69 | |||
| 70 | 109 | QSet<qint64> otherwiseRelated(const RelationGraph::Input &input, qint64 centerCardId) { | |
| 71 | 109 | QSet<qint64> out; | |
| 72 |
2/2✓ Branch 30 → 5 taken 5056 times.
✓ Branch 30 → 31 taken 109 times.
|
5165 | for (const RelationGraph::StoredEdge &edge : input.edges) { |
| 73 |
6/6✓ Branch 6 → 7 taken 4993 times.
✓ Branch 6 → 9 taken 63 times.
✓ Branch 7 → 8 taken 4490 times.
✓ Branch 7 → 10 taken 503 times.
✓ Branch 8 → 9 taken 4180 times.
✓ Branch 8 → 10 taken 310 times.
|
5056 | if (edge.toCardId <= 0 || (edge.fromCardId != centerCardId && edge.toCardId != centerCardId)) |
| 74 | 4243 | continue; | |
| 75 |
4/4✓ Branch 12 → 13 taken 738 times.
✓ Branch 12 → 20 taken 75 times.
✓ Branch 15 → 16 taken 529 times.
✓ Branch 15 → 21 taken 209 times.
|
2080 | const bool nonKin = edge.role == QLatin1String("via") || |
| 76 |
3/3✓ Branch 16 → 17 taken 529 times.
✓ Branch 17 → 18 taken 207 times.
✓ Branch 17 → 21 taken 322 times.
|
1267 | (edge.role == QLatin1String("relation") && degreeOf(edge.type) < 0 && |
| 77 |
3/3✓ Branch 18 → 19 taken 207 times.
✓ Branch 19 → 20 taken 152 times.
✓ Branch 19 → 21 taken 55 times.
|
207 | RelationVocabulary::categoryOf(edge.type) != RelationVocabulary::Category::Family); |
| 78 |
2/2✓ Branch 22 → 23 taken 227 times.
✓ Branch 22 → 28 taken 586 times.
|
813 | if (nonKin) |
| 79 |
3/3✓ Branch 23 → 24 taken 134 times.
✓ Branch 23 → 25 taken 93 times.
✓ Branch 26 → 27 taken 227 times.
|
227 | out.insert(edge.fromCardId == centerCardId ? edge.toCardId : edge.fromCardId); |
| 80 | } | ||
| 81 | 109 | return out; | |
| 82 | ✗ | } | |
| 83 | |||
| 84 | 16 | RelationGraph::Input withinDegree(const RelationGraph::Input &input, qint64 centerCardId, int limit) { | |
| 85 |
2/2✓ Branch 2 → 3 taken 1 time.
✓ Branch 2 → 4 taken 15 times.
|
16 | if (limit <= 0) |
| 86 | 1 | return input; | |
| 87 |
1/1✓ Branch 4 → 5 taken 15 times.
|
15 | const QHash<qint64, int> degree = degrees(input, centerCardId); |
| 88 |
1/1✓ Branch 5 → 6 taken 15 times.
|
15 | const QSet<qint64> kept = otherwiseRelated(input, centerCardId); |
| 89 | 15 | QSet<qint64> beyond; | |
| 90 |
2/2✓ Branch 24 → 8 taken 106 times.
✓ Branch 24 → 25 taken 15 times.
|
121 | for (auto it = degree.cbegin(); it != degree.cend(); ++it) |
| 91 |
7/8✓ Branch 9 → 10 taken 38 times.
✓ Branch 9 → 16 taken 68 times.
✓ Branch 11 → 12 taken 38 times.
✗ Branch 11 → 16 not taken.
✓ Branch 14 → 15 taken 35 times.
✓ Branch 14 → 16 taken 3 times.
✓ Branch 17 → 18 taken 35 times.
✓ Branch 17 → 21 taken 71 times.
|
106 | if (it.value() > limit && it.key() != centerCardId && !kept.contains(it.key())) |
| 92 |
1/1✓ Branch 19 → 20 taken 35 times.
|
35 | beyond.insert(it.key()); |
| 93 |
1/2✗ Branch 26 → 27 not taken.
✓ Branch 26 → 28 taken 15 times.
|
15 | if (beyond.isEmpty()) |
| 94 | ✗ | return input; | |
| 95 | 15 | RelationGraph::Input out; | |
| 96 |
2/2✓ Branch 36 → 30 taken 1002 times.
✓ Branch 36 → 37 taken 15 times.
|
1017 | for (const RelationGraph::Person &person : input.people) |
| 97 |
2/2✓ Branch 32 → 33 taken 967 times.
✓ Branch 32 → 34 taken 35 times.
|
1002 | if (!beyond.contains(person.cardId)) |
| 98 |
1/1✓ Branch 33 → 34 taken 967 times.
|
967 | out.people.append(person); |
| 99 |
2/2✓ Branch 50 → 39 taken 593 times.
✓ Branch 50 → 51 taken 15 times.
|
608 | for (const RelationGraph::StoredEdge &edge : input.edges) |
| 100 |
6/6✓ Branch 41 → 42 taken 523 times.
✓ Branch 41 → 45 taken 70 times.
✓ Branch 43 → 44 taken 453 times.
✓ Branch 43 → 45 taken 70 times.
✓ Branch 46 → 47 taken 453 times.
✓ Branch 46 → 48 taken 140 times.
|
593 | if (!beyond.contains(edge.fromCardId) && !beyond.contains(edge.toCardId)) |
| 101 |
1/1✓ Branch 47 → 48 taken 453 times.
|
453 | out.edges.append(edge); |
| 102 | 30 | const auto together = [&beyond](const QList<RelationGraph::Together> &pairs) { | |
| 103 | 30 | QList<RelationGraph::Together> kept; | |
| 104 |
1/2✗ Branch 15 → 4 not taken.
✓ Branch 15 → 16 taken 30 times.
|
30 | for (const RelationGraph::Together &pair : pairs) |
| 105 | ✗ | if (!beyond.contains(pair.a) && !beyond.contains(pair.b)) | |
| 106 | ✗ | kept.append(pair); | |
| 107 | 30 | return kept; | |
| 108 | ✗ | }; | |
| 109 |
1/1✓ Branch 51 → 52 taken 15 times.
|
15 | out.sharedEvents = together(input.sharedEvents); |
| 110 |
1/1✓ Branch 54 → 55 taken 15 times.
|
15 | out.suggestions = together(input.suggestions); |
| 111 | 15 | return out; | |
| 112 | 15 | } | |
| 113 | |||
| 114 | } // namespace RelationKinship | ||
| 115 |