21103632348

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

Build # 21103632348

Build Type

push

github

Committed by

web-flow

Commit Message

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

Coverage Stats

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

#include "graph_layout.h"

#include <format>
#include <fstream>
#include <cmath>
#include <ranges>
#include <algorithm>

#include "svg_diagram.h"
using namespace std;
using namespace svg_diagram;
using namespace graph_layout;

DirectedGraphHierarchicalLayout::DirectedGraphHierarchicalLayout() = default;

shared_ptr<SPDirectedGraph> DirectedGraphHierarchicalLayout::createGraph(const size_t numVertices) {
    _initialNumVertices = static_cast<int>(numVertices);
    _graph = make_shared<SPDirectedGraph>(numVertices);
    return _graph;
}

void DirectedGraphHierarchicalLayout::setGraph(const shared_ptr<SPDirectedGraph>& graph) {
    _initialNumVertices = static_cast<int>(graph->numVertices());
    _graph = graph;
}

shared_ptr<SPDirectedGraph> DirectedGraphHierarchicalLayout::graph() const {
    return _graph;
}

Attributes & DirectedGraphHierarchicalLayout::attributes() {
    return _attributes;
}

void DirectedGraphHierarchicalLayout::setFeedbackArcsMethod(const FeedbackArcsMethod method) {
    _feedbackArcsFinder.setMethod(method);
}

void DirectedGraphHierarchicalLayout::setLayerAssignmentMethod(const LayerAssignmentMethod method) {
    _layerAssignment.setMethod(method);
}

void DirectedGraphHierarchicalLayout::setCrossMinimizationMethod(const CrossMinimizationMethod method) {
    _crossMinimization.setMethod(method);
}

void DirectedGraphHierarchicalLayout::setVertexPositioningMethod(const VertexPositioningMethod method) {
    _vertexPositioning.setMethod(method);
}

void DirectedGraphHierarchicalLayout::setLayerMargin(const double margin) {
    _vertexPositioning.setLayerMargin(margin);
}

void DirectedGraphHierarchicalLayout::layoutGraph() {
    if (_graph == nullptr) {
        return;
    }
    computeVertexSizes();
    const size_t n = _graph->numVertices();
    const auto rankDir = _attributes.rankDir();
    int newVertexIndex = static_cast<int>(n);
    int edgeIndex = CrossMinimization::VIRTUAL_EDGE_ID_OFFSET;
    _graph->disableSelfCycleEdges();
    GraphComponentSplitter splitter;
    const auto feedbackArcs = _feedbackArcsFinder.findFeedbackArcs(*_graph);
    _graph->reverseEdges(feedbackArcs);
    _xs.resize(n);
    _ys.resize(n);
    _virtualEdges.clear();
    double subGraphShift = 0.0;
    auto subGraphs = splitter.splitGraph(*_graph);
    for (int groupIndex = 0; groupIndex < static_cast<int>(subGraphs.size()); ++groupIndex) {
        auto& subGraph = subGraphs[groupIndex];
        const int subN = static_cast<int>(subGraph.numVertices());
        auto ranks = _layerAssignment.rankVertices(subGraph);
        auto [layering, virtualEdges] = _crossMinimization.reduceNumCross(subGraph, ranks);
        auto [subXs, subYs] = _vertexPositioning.assignCoordinates(subGraph, layering);
        double maxLeftVertexSize = 0.0, maxRightVertexSize = 0.0, maxX = 0.0;
        for (int u = 0; u < subN; ++u) {
            if (subXs[u] == 0.0) {
                maxLeftVertexSize = max(maxLeftVertexSize, _vertexPositioning.vertexSizeAt(u));
            }
            if (subXs[u] >= maxX) {
                maxX = subXs[u];
                maxRightVertexSize = max(maxRightVertexSize, _vertexPositioning.vertexSizeAt(u));
            }
        }
        if (groupIndex > 0) {
            subGraphShift += maxLeftVertexSize * 0.5;
        }
        for (const auto& virtualEdge : virtualEdges) {
            SPVirtualEdge newVirtualEdge;
            const auto& originalEdge = virtualEdge.originalEdge;
            newVirtualEdge.originalEdge = originalEdge;
            const auto& edgeIds = virtualEdge.virtualEdgeIds;
            bool isReversed = _graph->isReverseEdge(originalEdge.id);
            bool removeOriginalEdge = false;
            int lastVertex = originalEdge.u;
            vector<int> newEdgeIds;
            for (int i = 0; i + 1 < static_cast<int>(edgeIds.size()); ++i) {
                const auto& inEdge = subGraph.getEdge(edgeIds[i]);
                const auto& outEdge = subGraph.getEdge(edgeIds[i + 1]);
                if (abs(subXs[inEdge.u] - subXs[inEdge.v]) > 1e-8 || abs(subXs[outEdge.u] - subXs[outEdge.v]) > 1e-8) {
                    removeOriginalEdge = true;
                    _graph->updateNumVertices(newVertexIndex + 1);
                    newEdgeIds.push_back(edgeIndex);
                    newVirtualEdge.virtualEdgeIds.emplace_back(edgeIndex);
                    if (!isReversed) {
                        _graph->addEdge({edgeIndex++, lastVertex, newVertexIndex});
                    } else {
                        _graph->addEdge({edgeIndex++, newVertexIndex, lastVertex});
                    }
                    _xs.push_back(subXs[inEdge.v] + subGraphShift);
                    _ys.push_back(subYs[inEdge.v]);
                    lastVertex = newVertexIndex++;
                    if (subXs[inEdge.v] >= maxX) {
                        maxX = subXs[inEdge.v];
                        maxRightVertexSize = max(maxRightVertexSize, _vertexPositioning.vertexSizeAt(inEdge.v));
                    }
                }
            }
            if (removeOriginalEdge) {
                _graph->removeEdge(originalEdge.id);
                newEdgeIds.push_back(edgeIndex);
                newVirtualEdge.virtualEdgeIds.emplace_back(edgeIndex);
                if (!isReversed) {
                    _graph->addEdge({edgeIndex++, lastVertex, originalEdge.v});
                } else {
                    _graph->addEdge({edgeIndex++, originalEdge.v, lastVertex});
                }
                if (isReversed) {
                    swap(newVirtualEdge.originalEdge.u, newVirtualEdge.originalEdge.v);
                    ranges::reverse(newVirtualEdge.virtualEdgeIds);
                }
                _virtualEdges.emplace_back(newVirtualEdge);
            }
        }
        for (int u = 0; u < subN; ++u) {
            _xs[splitter.originalVertexId(groupIndex, u)] = subXs[u] + subGraphShift;
            _ys[splitter.originalVertexId(groupIndex, u)] = subYs[u];
        }
        subGraphShift += maxX + maxRightVertexSize * 0.5;
    }
    _graph->reverseEdgesBack();
    _graph->enableSelfCycleEdges();
    adjustCoordinatesByGraphRank();
}

string DirectedGraphHierarchicalLayout::render() const {
    if (_graph == nullptr) {
        return "";
    }
    const int n = static_cast<int>(_graph->numVertices());
    SVGDiagram diagram;
    if (const auto bgColor = _attributes.graphAttributes(ATTR_KEY_BG_COLOR); !bgColor.empty()) {
        diagram.setBackgroundColor(bgColor);
    }
    unordered_map<int, unordered_set<int>> outEdges;
    const auto rankDir = _attributes.rankDir();
    for (const auto& [id, u, v] : _graph->edges()) {
        outEdges[u].insert(v);
    }
    vector<string> nodeIds(n);
    for (int u = 0; u < n; ++u) {
        nodeIds[u] = format("node{}", u);
        const auto node = diagram.addNode(nodeIds[u]);
        node->setCenter(_xs[u], _ys[u]);
        if (u < _initialNumVertices) {
            node->setShape(_attributes.vertexAttributes(u, ATTR_KEY_SHAPE));
            node->setLabel(_attributes.vertexAttributes(u, ATTR_KEY_LABEL));
            node->setFont(_attributes.vertexAttributes(u, ATTR_KEY_FONT_NAME), stod(_attributes.vertexAttributes(u, ATTR_KEY_FONT_SIZE)));
        } else {
            node->setShape(string("none"));
            node->setMargin(0, 0);
        }
    }
    for (const auto& edge : _graph->edges()) {
        if (isVirtualVertex(edge.u) || isVirtualVertex(edge.v)) {
            continue;
        }
        const auto e = diagram.addEdge(nodeIds[edge.u], nodeIds[edge.v]);
        if (const auto label = _attributes.edgeAttributes(edge.id, ATTR_KEY_LABEL); !label.empty()) {
            e->setLabel(label);
        }
        if (const auto label = _attributes.edgeAttributes(edge.id, ATTR_KEY_TAIL_LABEL); !label.empty()) {
            e->setTailLabel(label);
        }
        if (const auto label = _attributes.edgeAttributes(edge.id, ATTR_KEY_HEAD_LABEL); !label.empty()) {
            e->setHeadLabel(label);
        }
        e->setFont(_attributes.edgeAttributes(edge.id, ATTR_KEY_FONT_NAME), stod(_attributes.edgeAttributes(edge.id, ATTR_KEY_FONT_SIZE)));
        e->setLabelDistance(stod(_attributes.edgeAttributes(edge.id, ATTR_KEY_LABEL_DISTANCE)));
        e->setMargin(2);
        e->setArrowHead();
        if (edge.u != edge.v) {
            if (outEdges[edge.v].contains(edge.u)) {
                // There is a reverse edge
                const auto x1 = _xs[edge.u];
                const auto y1 = _ys[edge.u];
                const auto x2 = _xs[edge.v];
                const auto y2 = _ys[edge.v];
                const double dx = x2 - x1;
                const double dy = y2 - y1;
                const double len = sqrt(dx * dx + dy * dy);
                const double nx = -dy / len;
                const double ny = dx / len;
                const double midX = (x1 + x2) / 2;
                const double midY = (y1 + y2) / 2;
                const double x = midX + nx * 10.0;
                const double y = midY + ny * 10.0;
                e->addConnectionPoint(x, y);
            }
        } else {
            if (rankDir == AttributeRankDir::TOP_TO_BOTTOM) {
                e->setSelfLoopAttributes(180, VertexPositioning::DEFAULT_VERTEX_MARGIN * 0.8, 30);
            } else if (rankDir == AttributeRankDir::BOTTOM_TO_TOP) {
                e->setSelfLoopAttributes(0, VertexPositioning::DEFAULT_VERTEX_MARGIN * 0.8, 30);
            } else if (rankDir == AttributeRankDir::LEFT_TO_RIGHT) {
                e->setSelfLoopAttributes(-90, VertexPositioning::DEFAULT_VERTEX_MARGIN * 0.8, 30);
            } else {
                e->setSelfLoopAttributes(90, VertexPositioning::DEFAULT_VERTEX_MARGIN * 0.8, 30);
            }
        }
    }
    for (const auto& virtualEdge : _virtualEdges) {
        const auto& edgeId = virtualEdge.originalEdge.id;
        const auto& originalEdge = virtualEdge.originalEdge;
        const auto& edgeIds = virtualEdge.virtualEdgeIds;
        const auto e = diagram.addEdge(nodeIds[originalEdge.u], nodeIds[originalEdge.v]);
        if (const auto label = _attributes.edgeAttributes(edgeId, ATTR_KEY_LABEL); !label.empty()) {
            e->setLabel(label);
        }
        if (const auto label = _attributes.edgeAttributes(edgeId, ATTR_KEY_TAIL_LABEL); !label.empty()) {
            e->setTailLabel(label);
        }
        if (const auto label = _attributes.edgeAttributes(edgeId, ATTR_KEY_HEAD_LABEL); !label.empty()) {
            e->setHeadLabel(label);
        }
        e->setFont(_attributes.edgeAttributes(edgeId, ATTR_KEY_FONT_NAME), stod(_attributes.edgeAttributes(edgeId, ATTR_KEY_FONT_SIZE)));
        e->setLabelDistance(stod(_attributes.edgeAttributes(edgeId, ATTR_KEY_LABEL_DISTANCE)));
        e->setSplines(_attributes.edgeAttributes(edgeId, ATTR_KEY_SPLINES));
        e->setArrowHead();
        e->setMargin(2);
        for (int i = 0; i + 1 < static_cast<int>(edgeIds.size()); ++i) {
            const auto& edge = _graph->getEdge(edgeIds[i]);
            e->addConnectionPoint(_xs[edge.v], _ys[edge.v]);
        }
    }
    return diagram.render();
}

void DirectedGraphHierarchicalLayout::render(const string& filePath) const {
    ofstream file(filePath);
    file << render();
    file.close();
}

void DirectedGraphHierarchicalLayout::initVertexLabelsWithNumericalValues(const int start) {
    const int n = _initialNumVertices;
    for (int i = 0; i < n; ++i) {
        _attributes.setVertexAttributes(i, ATTR_KEY_LABEL, format("{}", start + i));
    }
}

void DirectedGraphHierarchicalLayout::setVertexLabels(const vector<string> &vertexLabels) {
    for (int i = 0; i < static_cast<int>(vertexLabels.size()); ++i) {
        _attributes.setVertexAttributes(i, ATTR_KEY_LABEL, vertexLabels[i]);
    }
}

void DirectedGraphHierarchicalLayout::setEdgeLabel(const int edgeId, const string& label) {
    _attributes.setEdgeAttributes(edgeId, ATTR_KEY_LABEL, label);
}

/** A vertex is virtual if the vertex ID is greater than the maximum vertex ID in the beginning graph.
 *
 * @param u A vertex ID.
 * @return Whether the vertex is virtual.
 */
bool DirectedGraphHierarchicalLayout::isVirtualVertex(const int u) const {
    return u >= _initialNumVertices;
}

/** Adjust the coordinates by `_graphAttributes.rank`.
 * The default rank is top to bottom.
 */
void DirectedGraphHierarchicalLayout::adjustCoordinatesByGraphRank() {
    const auto rankDir = _attributes.rankDir();
    if (rankDir == AttributeRankDir::TOP_TO_BOTTOM) {
        return;
    }
    if (rankDir == AttributeRankDir::BOTTOM_TO_TOP || rankDir == AttributeRankDir::RIGHT_TO_LEFT) {
        const auto yMin = ranges::min(_ys);
        const auto yMax = ranges::max(_ys);
        for (auto& y : _ys) {
            y = yMax - y + yMin;
        }
    }
    if (rankDir == AttributeRankDir::LEFT_TO_RIGHT || rankDir == AttributeRankDir::RIGHT_TO_LEFT) {
        swap_ranges(_xs.begin(), _xs.end(), _ys.begin());
    }
}

void DirectedGraphHierarchicalLayout::computeVertexSizes() {
    const int n = static_cast<int>(_graph->numVertices());
    const auto rankDir = _attributes.rankDir();
    double layerMargin = VertexPositioning::DEFAULT_LAYER_MARGIN;
    vector vertexSizes(n, VertexPositioning::DEFAULT_VERTEX_SIZE);
    for (int u = 0; u < n; ++u) {
        SVGNode node;
        node.setShape(_attributes.vertexAttributes(u, ATTR_KEY_SHAPE));
        node.setLabel(_attributes.vertexAttributes(u, ATTR_KEY_LABEL));
        node.setFontName(_attributes.vertexAttributes(u, ATTR_KEY_FONT_NAME));
        node.setFontSize(stod(_attributes.vertexAttributes(u, ATTR_KEY_FONT_SIZE)));
        node.adjustNodeSize();
        const auto width = node.width();
        const auto height = node.height();
        vertexSizes[u] = max(vertexSizes[u], max(width, height));
        if (rankDir == AttributeRankDir::TOP_TO_BOTTOM || rankDir == AttributeRankDir::BOTTOM_TO_TOP) {
            layerMargin = max(layerMargin, height);
        } else {
            layerMargin = max(layerMargin, width);
        }
    }
    _vertexPositioning.setVertexSizes(std::move(vertexSizes));
    _vertexPositioning.setVertexMargin(VertexPositioning::DEFAULT_VERTEX_MARGIN);
    _vertexPositioning.setLayerMargin(layerMargin);
}

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✔

CyberZHG / GraphLayout / 21103632348

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

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