data/RelationGraphTree.cpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #include "RelationGraphTree.h" | ||
| 2 | |||
| 3 | #include "RelationGraphFamilies.h" | ||
| 4 | #include "RelationVocabulary.h" | ||
| 5 | |||
| 6 | #include <QHash> | ||
| 7 | #include <QSet> | ||
| 8 | #include <algorithm> | ||
| 9 | |||
| 10 | namespace RelationGraph { | ||
| 11 | |||
| 12 | namespace { | ||
| 13 | |||
| 14 | struct Step { | ||
| 15 | const char *type; | ||
| 16 | int generations; | ||
| 17 | }; | ||
| 18 | |||
| 19 | const Step kSteps[] = {{"parent", 1}, {"grandparent", 2}, {"aunt-uncle", 1}, {"parent-in-law", 1}, | ||
| 20 | {"child", -1}, {"grandchild", -2}, {"niece-nephew", -1}, {"child-in-law", -1}, | ||
| 21 | {"sibling", 0}, {"spouse", 0}, {"ex-partner", 0}, {"cousin", 0}, | ||
| 22 | {"kin", 0}, {"sibling-in-law", 0}, {"great-grandparent", 3}, | ||
| 23 | {"great-grandchild", -3}, {"great-aunt-uncle", 2}, {"grand-niece-nephew", -2}}; | ||
| 24 | |||
| 25 | 494 | bool countsAsFamily(const StoredEdge &e) { | |
| 26 | 494 | int step = 0; | |
| 27 |
4/4✓ Branch 7 → 8 taken 174 times.
✓ Branch 7 → 13 taken 18 times.
✓ Branch 8 → 9 taken 470 times.
✓ Branch 8 → 13 taken 6 times.
|
1482 | return (e.role == QLatin1String("relation") || e.role == QLatin1String("inferred")) && e.toCardId > 0 && |
| 28 |
6/7✓ Branch 4 → 5 taken 192 times.
✓ Branch 4 → 8 taken 302 times.
✓ Branch 9 → 10 taken 470 times.
✗ Branch 9 → 13 not taken.
✓ Branch 10 → 11 taken 470 times.
✓ Branch 11 → 12 taken 344 times.
✓ Branch 11 → 13 taken 126 times.
|
1482 | e.fromCardId != e.toCardId && generationStep(e.type, &step); |
| 29 | } | ||
| 30 | |||
| 31 | } // namespace | ||
| 32 | |||
| 33 | 26313 | bool generationStep(const QString &type, int *step) { | |
| 34 |
1/1✓ Branch 2 → 3 taken 26313 times.
|
26313 | const QString known = RelationVocabulary::canonical(type); |
| 35 |
2/2✓ Branch 9 → 4 taken 235254 times.
✓ Branch 9 → 10 taken 7101 times.
|
242355 | for (const Step &s : kSteps) |
| 36 |
2/2✓ Branch 6 → 7 taken 19212 times.
✓ Branch 6 → 8 taken 216042 times.
|
235254 | if (known == QLatin1String(s.type)) { |
| 37 | 19212 | *step = s.generations; | |
| 38 | 19212 | return true; | |
| 39 | } | ||
| 40 | 7101 | return false; | |
| 41 | 26313 | } | |
| 42 | |||
| 43 | 11175 | bool isDescent(const QString &type) { | |
| 44 |
1/1✓ Branch 2 → 3 taken 11175 times.
|
11175 | const QString known = RelationVocabulary::canonical(type); |
| 45 |
4/4✓ Branch 8 → 9 taken 5156 times.
✓ Branch 8 → 21 taken 344 times.
✓ Branch 11 → 12 taken 4452 times.
✓ Branch 11 → 21 taken 704 times.
|
21831 | return known == QLatin1String("parent") || known == QLatin1String("child") || |
| 46 |
4/4✓ Branch 14 → 15 taken 4320 times.
✓ Branch 14 → 21 taken 132 times.
✓ Branch 17 → 18 taken 4236 times.
✓ Branch 17 → 21 taken 84 times.
|
13928 | known == QLatin1String("grandparent") || known == QLatin1String("grandchild") || |
| 47 |
3/4✓ Branch 5 → 6 taken 5500 times.
✓ Branch 5 → 21 taken 5675 times.
✗ Branch 20 → 21 not taken.
✓ Branch 20 → 22 taken 4236 times.
|
32170 | known == QLatin1String("great-grandparent") || known == QLatin1String("great-grandchild"); |
| 48 | 11175 | } | |
| 49 | |||
| 50 | 7 | Graph familyTree(const Input &input, qint64 centerCardId, int maxSteps) { | |
| 51 | 7 | Graph graph; | |
| 52 | 7 | QHash<qint64, const Person *> people; | |
| 53 |
2/2✓ Branch 8 → 4 taken 503 times.
✓ Branch 8 → 9 taken 7 times.
|
510 | for (const Person &p : input.people) |
| 54 |
1/1✓ Branch 5 → 6 taken 503 times.
|
503 | people.insert(p.cardId, &p); |
| 55 |
1/2✗ Branch 10 → 11 not taken.
✓ Branch 10 → 12 taken 7 times.
|
7 | if (!people.contains(centerCardId)) |
| 56 | ✗ | return graph; | |
| 57 | // Breadth first over family relationships; a person's generation is the | ||
| 58 | // first one found (the nearest path wins). | ||
| 59 | 7 | QHash<qint64, QList<int>> edgesOf; | |
| 60 |
2/2✓ Branch 33 → 13 taken 256 times.
✓ Branch 33 → 34 taken 7 times.
|
263 | for (int i = 0; i < input.edges.size(); ++i) |
| 61 |
7/9✓ Branch 14 → 15 taken 256 times.
✓ Branch 15 → 16 taken 172 times.
✓ Branch 15 → 23 taken 84 times.
✓ Branch 18 → 19 taken 172 times.
✗ Branch 18 → 23 not taken.
✓ Branch 21 → 22 taken 172 times.
✗ Branch 21 → 23 not taken.
✓ Branch 24 → 25 taken 172 times.
✓ Branch 24 → 31 taken 84 times.
|
428 | if (countsAsFamily(input.edges.at(i)) && people.contains(input.edges.at(i).fromCardId) && |
| 62 | 172 | people.contains(input.edges.at(i).toCardId)) { | |
| 63 |
2/2✓ Branch 26 → 27 taken 172 times.
✓ Branch 27 → 28 taken 172 times.
|
172 | edgesOf[input.edges.at(i).fromCardId].append(i); |
| 64 |
2/2✓ Branch 29 → 30 taken 172 times.
✓ Branch 30 → 31 taken 172 times.
|
172 | edgesOf[input.edges.at(i).toCardId].append(i); |
| 65 | } | ||
| 66 |
1/1✓ Branch 35 → 36 taken 7 times.
|
7 | QHash<qint64, int> generation{{centerCardId, 0}}; |
| 67 |
1/1✓ Branch 37 → 38 taken 7 times.
|
7 | QHash<qint64, int> distance{{centerCardId, 0}}; |
| 68 |
1/1✓ Branch 38 → 39 taken 7 times.
|
7 | QList<qint64> order{centerCardId}; |
| 69 |
2/2✓ Branch 78 → 40 taken 47 times.
✓ Branch 78 → 79 taken 7 times.
|
54 | for (int head = 0; head < order.size(); ++head) { |
| 70 | 47 | const qint64 card = order.at(head); | |
| 71 |
3/6✓ Branch 42 → 43 taken 47 times.
✗ Branch 42 → 45 not taken.
✗ Branch 44 → 45 not taken.
✓ Branch 44 → 46 taken 47 times.
✗ Branch 47 → 48 not taken.
✓ Branch 47 → 49 taken 47 times.
|
47 | if (distance.value(card) >= maxSteps || order.size() >= MaxEgoNodes) |
| 72 | ✗ | continue; | |
| 73 |
4/4✓ Branch 50 → 51 taken 47 times.
✓ Branch 51 → 52 taken 47 times.
✓ Branch 73 → 53 taken 242 times.
✓ Branch 73 → 74 taken 47 times.
|
289 | for (int index : edgesOf.value(card)) { |
| 74 | 242 | const StoredEdge &e = input.edges.at(index); | |
| 75 | 242 | int step = 0; | |
| 76 |
1/1✓ Branch 55 → 56 taken 242 times.
|
242 | generationStep(e.type, &step); |
| 77 | 242 | const bool forward = e.fromCardId == card; // "to is from's type": to sits `step` above from | |
| 78 |
2/2✓ Branch 56 → 57 taken 121 times.
✓ Branch 56 → 58 taken 121 times.
|
242 | const qint64 other = forward ? e.toCardId : e.fromCardId; |
| 79 |
2/2✓ Branch 60 → 61 taken 202 times.
✓ Branch 60 → 62 taken 40 times.
|
242 | if (distance.contains(other)) |
| 80 | 202 | continue; | |
| 81 |
3/3✓ Branch 63 → 64 taken 30 times.
✓ Branch 63 → 65 taken 10 times.
✓ Branch 66 → 67 taken 40 times.
|
40 | generation.insert(other, generation.value(card) + (forward ? step : -step)); |
| 82 |
1/1✓ Branch 68 → 69 taken 40 times.
|
40 | distance.insert(other, distance.value(card) + 1); |
| 83 |
1/1✓ Branch 69 → 70 taken 40 times.
|
40 | order.append(other); |
| 84 | 47 | } | |
| 85 | } | ||
| 86 |
2/2✓ Branch 103 → 82 taken 47 times.
✓ Branch 103 → 104 taken 7 times.
|
54 | for (qint64 card : std::as_const(order)) { |
| 87 | 47 | const Person *p = people.value(card); | |
| 88 | 47 | Node node; | |
| 89 | 47 | node.cardId = p->cardId; | |
| 90 | 47 | node.key = p->key; | |
| 91 | 47 | node.name = p->name; | |
| 92 | 47 | node.gender = p->gender; | |
| 93 | 47 | node.inScope = p->inScope; | |
| 94 | 47 | node.me = p->me; | |
| 95 | 47 | node.birthday = p->birthday; | |
| 96 | 47 | node.center = card == centerCardId; | |
| 97 | 47 | node.depth = distance.value(card); | |
| 98 | 47 | node.sector = QStringLiteral("family"); | |
| 99 | 47 | node.degree = int(edgesOf.value(card).size()); | |
| 100 | 47 | node.generation = generation.value(card); | |
| 101 |
1/1✓ Branch 99 → 100 taken 47 times.
|
47 | graph.nodes.append(node); |
| 102 | 47 | } | |
| 103 | // One edge per pair: a stored relationship before an inferred one. | ||
| 104 | 7 | QSet<QPair<int, int>> drawn; | |
| 105 |
2/2✓ Branch 185 → 115 taken 14 times.
✓ Branch 185 → 186 taken 7 times.
|
49 | for (const QString role : {QStringLiteral("relation"), QStringLiteral("inferred")}) |
| 106 |
2/2✓ Branch 182 → 118 taken 512 times.
✓ Branch 182 → 183 taken 14 times.
|
526 | for (const StoredEdge &e : input.edges) { |
| 107 |
7/7✓ Branch 120 → 121 taken 238 times.
✓ Branch 120 → 123 taken 274 times.
✓ Branch 121 → 122 taken 238 times.
✓ Branch 122 → 123 taken 66 times.
✓ Branch 122 → 124 taken 172 times.
✓ Branch 125 → 126 taken 340 times.
✓ Branch 125 → 127 taken 172 times.
|
512 | if (e.role != role || !countsAsFamily(e)) |
| 108 | 441 | continue; | |
| 109 |
2/2✓ Branch 127 → 128 taken 172 times.
✓ Branch 128 → 129 taken 172 times.
|
172 | const int from = graph.indexOf(e.fromCardId), to = graph.indexOf(e.toCardId); |
| 110 |
6/8✓ Branch 129 → 130 taken 121 times.
✓ Branch 129 → 136 taken 51 times.
✓ Branch 130 → 131 taken 121 times.
✗ Branch 130 → 136 not taken.
✗ Branch 135 → 136 not taken.
✓ Branch 135 → 137 taken 121 times.
✓ Branch 138 → 139 taken 51 times.
✓ Branch 138 → 140 taken 121 times.
|
172 | if (from < 0 || to < 0 || drawn.contains({std::min(from, to), std::max(from, to)})) |
| 111 | 51 | continue; | |
| 112 | // An inferred aunt, cousin or in-law follows from the tree itself; only inferred parents are drawn. | ||
| 113 |
1/1✓ Branch 140 → 141 taken 121 times.
|
121 | const QString type = RelationVocabulary::canonical(e.type); |
| 114 |
8/8✓ Branch 143 → 144 taken 66 times.
✓ Branch 143 → 151 taken 55 times.
✓ Branch 146 → 147 taken 54 times.
✓ Branch 146 → 151 taken 12 times.
✓ Branch 149 → 150 taken 50 times.
✓ Branch 149 → 151 taken 4 times.
✓ Branch 152 → 153 taken 50 times.
✓ Branch 152 → 154 taken 71 times.
|
121 | if (role == QLatin1String("inferred") && type != QLatin1String("parent") && type != QLatin1String("child")) |
| 115 | 50 | continue; | |
| 116 |
1/1✓ Branch 157 → 158 taken 71 times.
|
71 | drawn.insert({std::min(from, to), std::max(from, to)}); |
| 117 | 71 | Edge edge; | |
| 118 | 71 | edge.from = from; | |
| 119 | 71 | edge.to = to; | |
| 120 | 71 | edge.kind = role; | |
| 121 | 71 | edge.type = e.type; | |
| 122 | 71 | edge.label = e.label; | |
| 123 | 71 | edge.category = QStringLiteral("family"); | |
| 124 |
2/2✓ Branch 169 → 170 taken 55 times.
✓ Branch 169 → 171 taken 16 times.
|
71 | edge.storedOnCardId = role == QLatin1String("relation") ? e.fromCardId : 0; |
| 125 | 71 | edge.sourceIndex = e.sourceIndex; | |
| 126 |
1/1✓ Branch 172 → 173 taken 71 times.
|
71 | graph.edges.append(edge); |
| 127 | 156 | } | |
| 128 |
2/2✓ Branch 192 → 193 taken 7 times.
✓ Branch 193 → 194 taken 7 times.
|
7 | Families::addAreas(input, Families::of(input), centerCardId, &graph); |
| 129 | 7 | return graph; | |
| 130 | 7 | } | |
| 131 | |||
| 132 | } // namespace RelationGraph | ||
| 133 | |||
| 134 | namespace RelationGraphLayout { | ||
| 135 | |||
| 136 | 6 | QList<QPointF> familyTree(const RelationGraph::Graph &graph) { | |
| 137 |
1/1✓ Branch 3 → 4 taken 6 times.
|
6 | QList<QPointF> positions(graph.nodes.size()); |
| 138 | 6 | QList<int> shown; | |
| 139 | 6 | QHash<int, int> generation; | |
| 140 |
2/2✓ Branch 12 → 5 taken 43 times.
✓ Branch 12 → 13 taken 6 times.
|
49 | for (int i = 0; i < graph.nodes.size(); ++i) |
| 141 |
1/2✓ Branch 6 → 7 taken 43 times.
✗ Branch 6 → 10 not taken.
|
43 | if (!graph.nodes.at(i).family) { // a family card is only its area |
| 142 |
1/1✓ Branch 7 → 8 taken 43 times.
|
43 | shown.append(i); |
| 143 |
1/1✓ Branch 9 → 10 taken 43 times.
|
43 | generation.insert(i, graph.nodes.at(i).generation); |
| 144 | } | ||
| 145 |
1/2✗ Branch 14 → 15 not taken.
✓ Branch 14 → 16 taken 6 times.
|
6 | if (shown.isEmpty()) |
| 146 | ✗ | return positions; | |
| 147 |
1/1✓ Branch 16 → 17 taken 6 times.
|
6 | const QHash<int, QPointF> placed = rows(graph, shown, generation); |
| 148 | 6 | const double originX = placed.value(0).x(); // the centre at (0, 0) | |
| 149 |
2/2✓ Branch 28 → 20 taken 43 times.
✓ Branch 28 → 29 taken 6 times.
|
49 | for (auto it = placed.cbegin(); it != placed.cend(); ++it) |
| 150 |
1/1✓ Branch 24 → 25 taken 43 times.
|
43 | positions[it.key()] = it.value() - QPointF(originX, 0); |
| 151 | 6 | return positions; | |
| 152 | 6 | } | |
| 153 | |||
| 154 | } // namespace RelationGraphLayout | ||
| 155 |