• Home
  • Features
  • Pricing
  • Docs
  • Announcements
  • Sign In

CyberZHG / GraphLayout / 21103632348

18 Jan 2026 01:03AM UTC coverage: 89.943% (-0.5%) from 90.404%
21103632348

push

github

web-flow
Fix head & tail labels for virtual edges (#3)

* Update SVGDiagram to 1.7.0

* Fix head & tail labels for virtual edges

* Fix font & distance

* Update self loop height

* Restore self loop height

* Add config for splines

11 of 19 new or added lines in 2 files covered. (57.89%)

1261 of 1402 relevant lines covered (89.94%)

6747.57 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

92.83
/src/graph_layout.cpp
1
#include "graph_layout.h"
2

3
#include <format>
4
#include <fstream>
5
#include <cmath>
6
#include <ranges>
7
#include <algorithm>
8

9
#include "svg_diagram.h"
10
using namespace std;
11
using namespace svg_diagram;
12
using namespace graph_layout;
13

14
DirectedGraphHierarchicalLayout::DirectedGraphHierarchicalLayout() = default;
21 ✔
15

16
shared_ptr<SPDirectedGraph> DirectedGraphHierarchicalLayout::createGraph(const size_t numVertices) {
8 ✔
17
    _initialNumVertices = static_cast<int>(numVertices);
8 ✔
18
    _graph = make_shared<SPDirectedGraph>(numVertices);
8 ✔
19
    return _graph;
8 ✔
20
}
21

22
void DirectedGraphHierarchicalLayout::setGraph(const shared_ptr<SPDirectedGraph>& graph) {
13 ✔
23
    _initialNumVertices = static_cast<int>(graph->numVertices());
13 ✔
24
    _graph = graph;
13 ✔
25
}
13 ✔
26

27
shared_ptr<SPDirectedGraph> DirectedGraphHierarchicalLayout::graph() const {
×
28
    return _graph;
×
29
}
30

31
Attributes & DirectedGraphHierarchicalLayout::attributes() {
129 ✔
32
    return _attributes;
129 ✔
33
}
34

35
void DirectedGraphHierarchicalLayout::setFeedbackArcsMethod(const FeedbackArcsMethod method) {
5 ✔
36
    _feedbackArcsFinder.setMethod(method);
5 ✔
37
}
5 ✔
38

39
void DirectedGraphHierarchicalLayout::setLayerAssignmentMethod(const LayerAssignmentMethod method) {
×
40
    _layerAssignment.setMethod(method);
×
41
}
×
42

43
void DirectedGraphHierarchicalLayout::setCrossMinimizationMethod(const CrossMinimizationMethod method) {
×
44
    _crossMinimization.setMethod(method);
×
45
}
×
46

47
void DirectedGraphHierarchicalLayout::setVertexPositioningMethod(const VertexPositioningMethod method) {
×
48
    _vertexPositioning.setMethod(method);
×
49
}
×
50

51
void DirectedGraphHierarchicalLayout::setLayerMargin(const double margin) {
×
52
    _vertexPositioning.setLayerMargin(margin);
×
53
}
×
54

55
void DirectedGraphHierarchicalLayout::layoutGraph() {
21 ✔
56
    if (_graph == nullptr) {
21 ✔
57
        return;
×
58
    }
59
    computeVertexSizes();
21 ✔
60
    const size_t n = _graph->numVertices();
21 ✔
61
    const auto rankDir = _attributes.rankDir();
21 ✔
62
    int newVertexIndex = static_cast<int>(n);
21 ✔
63
    int edgeIndex = CrossMinimization::VIRTUAL_EDGE_ID_OFFSET;
21 ✔
64
    _graph->disableSelfCycleEdges();
21 ✔
65
    GraphComponentSplitter splitter;
21 ✔
66
    const auto feedbackArcs = _feedbackArcsFinder.findFeedbackArcs(*_graph);
21 ✔
67
    _graph->reverseEdges(feedbackArcs);
21 ✔
68
    _xs.resize(n);
21 ✔
69
    _ys.resize(n);
21 ✔
70
    _virtualEdges.clear();
21 ✔
71
    double subGraphShift = 0.0;
21 ✔
72
    auto subGraphs = splitter.splitGraph(*_graph);
21 ✔
73
    for (int groupIndex = 0; groupIndex < static_cast<int>(subGraphs.size()); ++groupIndex) {
45 ✔
74
        auto& subGraph = subGraphs[groupIndex];
24 ✔
75
        const int subN = static_cast<int>(subGraph.numVertices());
24 ✔
76
        auto ranks = _layerAssignment.rankVertices(subGraph);
24 ✔
77
        auto [layering, virtualEdges] = _crossMinimization.reduceNumCross(subGraph, ranks);
24 ✔
78
        auto [subXs, subYs] = _vertexPositioning.assignCoordinates(subGraph, layering);
24 ✔
79
        double maxLeftVertexSize = 0.0, maxRightVertexSize = 0.0, maxX = 0.0;
24 ✔
80
        for (int u = 0; u < subN; ++u) {
226 ✔
81
            if (subXs[u] == 0.0) {
202 ✔
82
                maxLeftVertexSize = max(maxLeftVertexSize, _vertexPositioning.vertexSizeAt(u));
59 ✔
83
            }
84
            if (subXs[u] >= maxX) {
202 ✔
85
                maxX = subXs[u];
79 ✔
86
                maxRightVertexSize = max(maxRightVertexSize, _vertexPositioning.vertexSizeAt(u));
79 ✔
87
            }
88
        }
89
        if (groupIndex > 0) {
24 ✔
90
            subGraphShift += maxLeftVertexSize * 0.5;
4 ✔
91
        }
92
        for (const auto& virtualEdge : virtualEdges) {
71 ✔
93
            SPVirtualEdge newVirtualEdge;
47 ✔
94
            const auto& originalEdge = virtualEdge.originalEdge;
47 ✔
95
            newVirtualEdge.originalEdge = originalEdge;
47 ✔
96
            const auto& edgeIds = virtualEdge.virtualEdgeIds;
47 ✔
97
            bool isReversed = _graph->isReverseEdge(originalEdge.id);
47 ✔
98
            bool removeOriginalEdge = false;
47 ✔
99
            int lastVertex = originalEdge.u;
47 ✔
100
            vector<int> newEdgeIds;
47 ✔
101
            for (int i = 0; i + 1 < static_cast<int>(edgeIds.size()); ++i) {
188 ✔
102
                const auto& inEdge = subGraph.getEdge(edgeIds[i]);
141 ✔
103
                const auto& outEdge = subGraph.getEdge(edgeIds[i + 1]);
141 ✔
104
                if (abs(subXs[inEdge.u] - subXs[inEdge.v]) > 1e-8 || abs(subXs[outEdge.u] - subXs[outEdge.v]) > 1e-8) {
141 ✔
105
                    removeOriginalEdge = true;
54 ✔
106
                    _graph->updateNumVertices(newVertexIndex + 1);
54 ✔
107
                    newEdgeIds.push_back(edgeIndex);
54 ✔
108
                    newVirtualEdge.virtualEdgeIds.emplace_back(edgeIndex);
54 ✔
109
                    if (!isReversed) {
54 ✔
110
                        _graph->addEdge({edgeIndex++, lastVertex, newVertexIndex});
38 ✔
111
                    } else {
112
                        _graph->addEdge({edgeIndex++, newVertexIndex, lastVertex});
16 ✔
113
                    }
114
                    _xs.push_back(subXs[inEdge.v] + subGraphShift);
54 ✔
115
                    _ys.push_back(subYs[inEdge.v]);
54 ✔
116
                    lastVertex = newVertexIndex++;
54 ✔
117
                    if (subXs[inEdge.v] >= maxX) {
54 ✔
118
                        maxX = subXs[inEdge.v];
31 ✔
119
                        maxRightVertexSize = max(maxRightVertexSize, _vertexPositioning.vertexSizeAt(inEdge.v));
31 ✔
120
                    }
121
                }
122
            }
123
            if (removeOriginalEdge) {
47 ✔
124
                _graph->removeEdge(originalEdge.id);
39 ✔
125
                newEdgeIds.push_back(edgeIndex);
39 ✔
126
                newVirtualEdge.virtualEdgeIds.emplace_back(edgeIndex);
39 ✔
127
                if (!isReversed) {
39 ✔
128
                    _graph->addEdge({edgeIndex++, lastVertex, originalEdge.v});
29 ✔
129
                } else {
130
                    _graph->addEdge({edgeIndex++, originalEdge.v, lastVertex});
10 ✔
131
                }
132
                if (isReversed) {
39 ✔
133
                    swap(newVirtualEdge.originalEdge.u, newVirtualEdge.originalEdge.v);
10 ✔
134
                    ranges::reverse(newVirtualEdge.virtualEdgeIds);
10 ✔
135
                }
136
                _virtualEdges.emplace_back(newVirtualEdge);
39 ✔
137
            }
138
        }
47 ✔
139
        for (int u = 0; u < subN; ++u) {
226 ✔
140
            _xs[splitter.originalVertexId(groupIndex, u)] = subXs[u] + subGraphShift;
202 ✔
141
            _ys[splitter.originalVertexId(groupIndex, u)] = subYs[u];
202 ✔
142
        }
143
        subGraphShift += maxX + maxRightVertexSize * 0.5;
24 ✔
144
    }
24 ✔
145
    _graph->reverseEdgesBack();
21 ✔
146
    _graph->enableSelfCycleEdges();
21 ✔
147
    adjustCoordinatesByGraphRank();
21 ✔
148
}
21 ✔
149

150
string DirectedGraphHierarchicalLayout::render() const {
19 ✔
151
    if (_graph == nullptr) {
19 ✔
152
        return "";
×
153
    }
154
    const int n = static_cast<int>(_graph->numVertices());
19 ✔
155
    SVGDiagram diagram;
19 ✔
156
    if (const auto bgColor = _attributes.graphAttributes(ATTR_KEY_BG_COLOR); !bgColor.empty()) {
19 ✔
157
        diagram.setBackgroundColor(bgColor);
19 ✔
158
    }
19 ✔
159
    unordered_map<int, unordered_set<int>> outEdges;
19 ✔
160
    const auto rankDir = _attributes.rankDir();
19 ✔
161
    for (const auto& [id, u, v] : _graph->edges()) {
357 ✔
162
        outEdges[u].insert(v);
338 ✔
163
    }
164
    vector<string> nodeIds(n);
19 ✔
165
    for (int u = 0; u < n; ++u) {
274 ✔
166
        nodeIds[u] = format("node{}", u);
255 ✔
167
        const auto node = diagram.addNode(nodeIds[u]);
255 ✔
168
        node->setCenter(_xs[u], _ys[u]);
255 ✔
169
        if (u < _initialNumVertices) {
255 ✔
170
            node->setShape(_attributes.vertexAttributes(u, ATTR_KEY_SHAPE));
201 ✔
171
            node->setLabel(_attributes.vertexAttributes(u, ATTR_KEY_LABEL));
201 ✔
172
            node->setFont(_attributes.vertexAttributes(u, ATTR_KEY_FONT_NAME), stod(_attributes.vertexAttributes(u, ATTR_KEY_FONT_SIZE)));
201 ✔
173
        } else {
174
            node->setShape(string("none"));
108 ✔
175
            node->setMargin(0, 0);
54 ✔
176
        }
177
    }
255 ✔
178
    for (const auto& edge : _graph->edges()) {
357 ✔
179
        if (isVirtualVertex(edge.u) || isVirtualVertex(edge.v)) {
338 ✔
180
            continue;
93 ✔
181
        }
182
        const auto e = diagram.addEdge(nodeIds[edge.u], nodeIds[edge.v]);
245 ✔
183
        if (const auto label = _attributes.edgeAttributes(edge.id, ATTR_KEY_LABEL); !label.empty()) {
245 ✔
184
            e->setLabel(label);
33 ✔
185
        }
245 ✔
186
        if (const auto label = _attributes.edgeAttributes(edge.id, ATTR_KEY_TAIL_LABEL); !label.empty()) {
245 ✔
187
            e->setTailLabel(label);
1 ✔
188
        }
245 ✔
189
        if (const auto label = _attributes.edgeAttributes(edge.id, ATTR_KEY_HEAD_LABEL); !label.empty()) {
245 ✔
190
            e->setHeadLabel(label);
1 ✔
191
        }
245 ✔
192
        e->setFont(_attributes.edgeAttributes(edge.id, ATTR_KEY_FONT_NAME), stod(_attributes.edgeAttributes(edge.id, ATTR_KEY_FONT_SIZE)));
245 ✔
193
        e->setLabelDistance(stod(_attributes.edgeAttributes(edge.id, ATTR_KEY_LABEL_DISTANCE)));
245 ✔
194
        e->setMargin(2);
245 ✔
195
        e->setArrowHead();
245 ✔
196
        if (edge.u != edge.v) {
245 ✔
197
            if (outEdges[edge.v].contains(edge.u)) {
228 ✔
198
                // There is a reverse edge
199
                const auto x1 = _xs[edge.u];
18 ✔
200
                const auto y1 = _ys[edge.u];
18 ✔
201
                const auto x2 = _xs[edge.v];
18 ✔
202
                const auto y2 = _ys[edge.v];
18 ✔
203
                const double dx = x2 - x1;
18 ✔
204
                const double dy = y2 - y1;
18 ✔
205
                const double len = sqrt(dx * dx + dy * dy);
18 ✔
206
                const double nx = -dy / len;
18 ✔
207
                const double ny = dx / len;
18 ✔
208
                const double midX = (x1 + x2) / 2;
18 ✔
209
                const double midY = (y1 + y2) / 2;
18 ✔
210
                const double x = midX + nx * 10.0;
18 ✔
211
                const double y = midY + ny * 10.0;
18 ✔
212
                e->addConnectionPoint(x, y);
18 ✔
213
            }
214
        } else {
215
            if (rankDir == AttributeRankDir::TOP_TO_BOTTOM) {
17 ✔
216
                e->setSelfLoopAttributes(180, VertexPositioning::DEFAULT_VERTEX_MARGIN * 0.8, 30);
4 ✔
217
            } else if (rankDir == AttributeRankDir::BOTTOM_TO_TOP) {
13 ✔
218
                e->setSelfLoopAttributes(0, VertexPositioning::DEFAULT_VERTEX_MARGIN * 0.8, 30);
4 ✔
219
            } else if (rankDir == AttributeRankDir::LEFT_TO_RIGHT) {
9 ✔
220
                e->setSelfLoopAttributes(-90, VertexPositioning::DEFAULT_VERTEX_MARGIN * 0.8, 30);
5 ✔
221
            } else {
222
                e->setSelfLoopAttributes(90, VertexPositioning::DEFAULT_VERTEX_MARGIN * 0.8, 30);
4 ✔
223
            }
224
        }
225
    }
245 ✔
226
    for (const auto& virtualEdge : _virtualEdges) {
58 ✔
227
        const auto& edgeId = virtualEdge.originalEdge.id;
39 ✔
228
        const auto& originalEdge = virtualEdge.originalEdge;
39 ✔
229
        const auto& edgeIds = virtualEdge.virtualEdgeIds;
39 ✔
230
        const auto e = diagram.addEdge(nodeIds[originalEdge.u], nodeIds[originalEdge.v]);
39 ✔
231
        if (const auto label = _attributes.edgeAttributes(edgeId, ATTR_KEY_LABEL); !label.empty()) {
39 ✔
232
            e->setLabel(label);
4 ✔
233
        }
39 ✔
234
        if (const auto label = _attributes.edgeAttributes(edgeId, ATTR_KEY_TAIL_LABEL); !label.empty()) {
39 ✔
NEW
235
            e->setTailLabel(label);
×
236
        }
39 ✔
237
        if (const auto label = _attributes.edgeAttributes(edgeId, ATTR_KEY_HEAD_LABEL); !label.empty()) {
39 ✔
NEW
238
            e->setHeadLabel(label);
×
239
        }
39 ✔
240
        e->setFont(_attributes.edgeAttributes(edgeId, ATTR_KEY_FONT_NAME), stod(_attributes.edgeAttributes(edgeId, ATTR_KEY_FONT_SIZE)));
39 ✔
241
        e->setLabelDistance(stod(_attributes.edgeAttributes(edgeId, ATTR_KEY_LABEL_DISTANCE)));
39 ✔
242
        e->setSplines(_attributes.edgeAttributes(edgeId, ATTR_KEY_SPLINES));
39 ✔
243
        e->setArrowHead();
39 ✔
244
        e->setMargin(2);
39 ✔
245
        for (int i = 0; i + 1 < static_cast<int>(edgeIds.size()); ++i) {
93 ✔
246
            const auto& edge = _graph->getEdge(edgeIds[i]);
54 ✔
247
            e->addConnectionPoint(_xs[edge.v], _ys[edge.v]);
54 ✔
248
        }
249
    }
39 ✔
250
    return diagram.render();
19 ✔
251
}
19 ✔
252

253
void DirectedGraphHierarchicalLayout::render(const string& filePath) const {
19 ✔
254
    ofstream file(filePath);
19 ✔
255
    file << render();
19 ✔
256
    file.close();
19 ✔
257
}
19 ✔
258

259
void DirectedGraphHierarchicalLayout::initVertexLabelsWithNumericalValues(const int start) {
11 ✔
260
    const int n = _initialNumVertices;
11 ✔
261
    for (int i = 0; i < n; ++i) {
169 ✔
262
        _attributes.setVertexAttributes(i, ATTR_KEY_LABEL, format("{}", start + i));
158 ✔
263
    }
264
}
11 ✔
265

266
void DirectedGraphHierarchicalLayout::setVertexLabels(const vector<string> &vertexLabels) {
3 ✔
267
    for (int i = 0; i < static_cast<int>(vertexLabels.size()); ++i) {
14 ✔
268
        _attributes.setVertexAttributes(i, ATTR_KEY_LABEL, vertexLabels[i]);
11 ✔
269
    }
270
}
3 ✔
271

272
void DirectedGraphHierarchicalLayout::setEdgeLabel(const int edgeId, const string& label) {
3 ✔
273
    _attributes.setEdgeAttributes(edgeId, ATTR_KEY_LABEL, label);
3 ✔
274
}
3 ✔
275

276
/** A vertex is virtual if the vertex ID is greater than the maximum vertex ID in the beginning graph.
277
 *
278
 * @param u A vertex ID.
279
 * @return Whether the vertex is virtual.
280
 */
281
bool DirectedGraphHierarchicalLayout::isVirtualVertex(const int u) const {
622 ✔
282
    return u >= _initialNumVertices;
622 ✔
283
}
284

285
/** Adjust the coordinates by `_graphAttributes.rank`.
286
 * The default rank is top to bottom.
287
 */
288
void DirectedGraphHierarchicalLayout::adjustCoordinatesByGraphRank() {
21 ✔
289
    const auto rankDir = _attributes.rankDir();
21 ✔
290
    if (rankDir == AttributeRankDir::TOP_TO_BOTTOM) {
21 ✔
291
        return;
8 ✔
292
    }
293
    if (rankDir == AttributeRankDir::BOTTOM_TO_TOP || rankDir == AttributeRankDir::RIGHT_TO_LEFT) {
13 ✔
294
        const auto yMin = ranges::min(_ys);
6 ✔
295
        const auto yMax = ranges::max(_ys);
6 ✔
296
        for (auto& y : _ys) {
108 ✔
297
            y = yMax - y + yMin;
102 ✔
298
        }
299
    }
300
    if (rankDir == AttributeRankDir::LEFT_TO_RIGHT || rankDir == AttributeRankDir::RIGHT_TO_LEFT) {
13 ✔
301
        swap_ranges(_xs.begin(), _xs.end(), _ys.begin());
10 ✔
302
    }
303
}
21 ✔
304

305
void DirectedGraphHierarchicalLayout::computeVertexSizes() {
21 ✔
306
    const int n = static_cast<int>(_graph->numVertices());
21 ✔
307
    const auto rankDir = _attributes.rankDir();
21 ✔
308
    double layerMargin = VertexPositioning::DEFAULT_LAYER_MARGIN;
21 ✔
309
    vector vertexSizes(n, VertexPositioning::DEFAULT_VERTEX_SIZE);
21 ✔
310
    for (int u = 0; u < n; ++u) {
223 ✔
311
        SVGNode node;
202 ✔
312
        node.setShape(_attributes.vertexAttributes(u, ATTR_KEY_SHAPE));
202 ✔
313
        node.setLabel(_attributes.vertexAttributes(u, ATTR_KEY_LABEL));
202 ✔
314
        node.setFontName(_attributes.vertexAttributes(u, ATTR_KEY_FONT_NAME));
202 ✔
315
        node.setFontSize(stod(_attributes.vertexAttributes(u, ATTR_KEY_FONT_SIZE)));
202 ✔
316
        node.adjustNodeSize();
202 ✔
317
        const auto width = node.width();
202 ✔
318
        const auto height = node.height();
202 ✔
319
        vertexSizes[u] = max(vertexSizes[u], max(width, height));
202 ✔
320
        if (rankDir == AttributeRankDir::TOP_TO_BOTTOM || rankDir == AttributeRankDir::BOTTOM_TO_TOP) {
202 ✔
321
            layerMargin = max(layerMargin, height);
99 ✔
322
        } else {
323
            layerMargin = max(layerMargin, width);
103 ✔
324
        }
325
    }
202 ✔
326
    _vertexPositioning.setVertexSizes(std::move(vertexSizes));
21 ✔
327
    _vertexPositioning.setVertexMargin(VertexPositioning::DEFAULT_VERTEX_MARGIN);
21 ✔
328
    _vertexPositioning.setLayerMargin(layerMargin);
21 ✔
329
}
21 ✔
STATUS · Troubleshooting · Open an Issue · Sales · Support · CAREERS · ENTERPRISE · START FREE TRIAL · SCHEDULE DEMO
ANNOUNCEMENTS · TWITTER · TOS & SLA · Supported CI Services · What's a CI service? · Automated Testing

© 2026 Coveralls, Inc