21120124705

Committed 18 Jan 2026 11:02PM UTC coverage: 88.936% (-1.0%) from 89.943%

Build # 21120124705

Build Type

Pull #4

github

Committed by

web-flow

Commit Message

Merge 105737a80 into df283e449

Pull Request Pull Request #4: Add setting for arrow shapes

Run Details

14 of 26 new or added lines in 4 files covered. (53.85%)

4 existing lines in 1 file now uncovered.

1262 of 1419 relevant lines covered (88.94%)

5224.09 hits per line

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

93.41

/src/directed/cross_minimization.cpp

#include "directed/cross_minimization.h"

#include <ranges>
#include <set>
#include <algorithm>
using namespace std;
using namespace graph_layout;

void SPLayering::initializeMapping() {
    const int numLayers = static_cast<int>(orders.size());
    positions.resize(numLayers);
    idToLayer.clear();
    for (int i = 0; i < numLayers; i++) {
        for (int j = 0; j < static_cast<int>(orders[i].size()); ++j) {
            positions[i][orders[i][j]] = j;
            idToLayer[orders[i][j]] = i;
        }
    }
}

CrossMinimization::CrossMinimization(const CrossMinimizationMethod method) : _method(method) {
}


void CrossMinimization::setMethod(const CrossMinimizationMethod method) {
    _method = method;
}

pair<SPLayering, vector<SPVirtualEdge>> CrossMinimization::reduceNumCross(SPDirectedGraph& graph, vector<int>& ranks) const {
    auto [layering, virtualEdges] = addVirtualEdges(graph, ranks);
    switch (_method) {
        case CrossMinimizationMethod::BARYCENTER:
            reduceNumCrossWithBaryCenterHeuristic(graph, layering);
            break;
        case CrossMinimizationMethod::MEDIAN:
            reduceNumCrossWithMedianHeuristic(graph, layering);
            break;
        case CrossMinimizationMethod::PAIRWISE_SWITCH:
            reduceNumCrossWithPairwiseSwitchHeuristic(graph, layering);
            break;
    }
    layering.initializeMapping();
    return {layering, virtualEdges};
}

pair<SPLayering, vector<SPVirtualEdge>> CrossMinimization::addVirtualEdges(SPDirectedGraph& graph, vector<int>& ranks) {
    SPLayering layering;
    auto& discreteRanks = layering.layerRanks;
    auto& orders = layering.orders;
    discreteRanks = vector(ranks);
    ranges::sort(discreteRanks);
    discreteRanks.erase(ranges::unique(discreteRanks).begin(), discreteRanks.end());
    unordered_map<int, int> rankToIndex;
    for (int i = 0; i < static_cast<int>(discreteRanks.size()); i++) {
        rankToIndex[discreteRanks[i]] = i;
    }
    orders.resize(discreteRanks.size());
    for (int i = 0; i < static_cast<int>(ranks.size()); ++i) {
        orders[rankToIndex[ranks[i]]].emplace_back(i);
    }

    int n = static_cast<int>(graph.numVertices());
    vector<SPVirtualEdge> virtualEdges;
    for (const auto& edge : graph.edges()) {
        if (rankToIndex[ranks[edge.v]] - rankToIndex[ranks[edge.u]] > 1) {
            virtualEdges.emplace_back(edge);
        }
    }
    int numNewNodes = 0;
    for (const auto& [edge, edgeId] : virtualEdges) {
        graph.removeEdge(edge.id);
        numNewNodes += rankToIndex[ranks[edge.v]] - rankToIndex[ranks[edge.u]] - 1;
    }
    graph.updateNumVertices(n + numNewNodes);
    int edgeId = VIRTUAL_EDGE_ID_OFFSET;
    for (auto& [originalEdge, virtualEdgeIds] : virtualEdges) {
        const int u = originalEdge.u;
        const int v = originalEdge.v;
        int last = u;
        for (int rankIndex = rankToIndex[ranks[u]] + 1; rankIndex < rankToIndex[ranks[v]]; ++rankIndex) {
            graph.addEdge(SPEdge(edgeId, last, n));
            virtualEdgeIds.emplace_back(edgeId++);
            ranks.emplace_back(discreteRanks[rankIndex]);
            orders[rankIndex].emplace_back(n);
            last = n++;
        }
        graph.addEdge(SPEdge(edgeId, last, v));
        virtualEdgeIds.emplace_back(edgeId++);
    }

    layering.width = 0;
    for (const auto& order : orders) {
        layering.width = max(layering.width, order.size());
    }
    layering.initializeMapping();
    return {layering, virtualEdges};
}

/** Compute the number of crossings between two adjacent layers.
 *
 * We iterate over the vertices in the second layer backwards.
 * Suppose there is an edge connecting u in the second layer to v in the first layer,
 * this edge crosses all edges for which `position[v']` < `position[v]` (the prefix sum of existing edges).
 * We use a binary indexed tree to maintain the prefix sums.
 *
 * @param graph A DAG.
 * @param bit An initialized binary indexed tree.
 * @param order1 Orders in the first layer.
 * @param order2 Orders in the second layer.
 * @param forward Whether it is from low rank to high rank.
 * @return Number of crossings.
 */
long long CrossMinimization::computeNumCross(
    SPDirectedGraph& graph,
    BinaryIndexedTree &bit,
    const vector<int> &order1,
    const vector<int> &order2,
    const bool forward) {
    bit.clear(order1.size());
    unordered_map<int, int> positions;
    for (int i = 0; i < static_cast<int>(order1.size()); ++i) {
        positions[order1[i]] = i;
    }
    long long numCross = 0;
    if (forward) {
        for (const int v : views::reverse(order2)) {
            for (const auto& edge : graph.getInEdges(v)) {
                const int u = edge.u;
                if (const auto it = positions.find(u); it != positions.end()) {
                    numCross += bit.prefixSum(it->second - 1);
                }
            }
            for (const auto& edge : graph.getInEdges(v)) {
                const int u = edge.u;
                if (const auto it = positions.find(u); it != positions.end()) {
                    bit.add(it->second);
                }
            }
        }
    } else {
        for (const int v : views::reverse(order2)) {
            for (const auto& edge : graph.getOutEdges(v)) {
                const int u = edge.v;
                if (const auto it = positions.find(u); it != positions.end()) {
                    numCross += bit.prefixSum(it->second - 1);
                }
            }
            for (const auto& edge : graph.getOutEdges(v)) {
                const int u = edge.v;
                if (const auto it = positions.find(u); it != positions.end()) {
                    bit.add(it->second);
                }
            }
        }
    }
    return numCross;
}

long long CrossMinimization::computeNumCross(SPDirectedGraph& graph, const SPLayering& layering) {
    const auto& orders = layering.orders;
    BinaryIndexedTree bit(layering.width);
    long long numCross = 0;
    for (size_t i = 1; i < orders.size(); ++i) {
        numCross += computeNumCross(graph, bit, orders[i - 1], orders[i], true);
    }
    return numCross;
}

/** Reduce the number of crossings using a weighting heuristic.
 *
 * The algorithm goes through several rounds of scanning.
 * In each round, it first optimizes from lower ranks to higher ranks, then from higher ranks to lower ranks.
 * During each optimization, the order of the previous layer is fixed,
 * and heuristic methods are used to optimize the ordering of the current layer.
 *
 * @param graph A DAG.
 * @param layering A cross minimization result.
 * @param weighting A weighting function.
 */
void CrossMinimization::reduceNumCrossWithWeightingHeuristic(
    SPDirectedGraph& graph,
    SPLayering& layering,
    const function<double(SPDirectedGraph&, const unordered_map<int, int>&, int, bool)> &weighting) {
    constexpr int NUM_REPEAT = 2;

    auto& orders = layering.orders;
    const int numLayers = static_cast<int>(orders.size());

    vector<pair<double, pair<int, int>>> weights(layering.width);

    SPLayering bestLayeredOrder(layering);
    long long bestNumCross = computeNumCross(graph, layering);
    bool lastIsBest = false, hasUpdate = false;
    unordered_map<int, int> positions;
    for (int repeatIndex = 0; repeatIndex < NUM_REPEAT; ++repeatIndex) {
        hasUpdate = false;
        for (int layerIndex = 1; layerIndex < numLayers; ++layerIndex) {
            positions.clear();
            for (int i = 0; i < static_cast<int>(orders[layerIndex - 1].size()); ++i) {
                positions[orders[layerIndex - 1][i]] = i;
            }
            const int n = static_cast<int>(orders[layerIndex].size());
            for (int i = 0; i < n; ++i) {
                const int v = orders[layerIndex][i];
                weights[i] = {weighting(graph, positions, v, true), {i, v}};
            }
            sort(weights.begin(), weights.begin() + n);
            for (int i = 0; i < n; ++i) {
                const int v = weights[i].second.second;
                if (orders[layerIndex][i] != v) {
                    hasUpdate = true;
                }
                orders[layerIndex][i] = v;
            }
        }
        if (const long long numCross = computeNumCross(graph, layering); numCross < bestNumCross) {
            bestLayeredOrder = layering;
            bestNumCross = numCross;
        }

        for (int layerIndex = numLayers - 2; layerIndex >= 0; --layerIndex) {
            positions.clear();
            for (int i = 0; i < static_cast<int>(orders[layerIndex + 1].size()); ++i) {
                positions[orders[layerIndex + 1][i]] = i;
            }
            const int n = static_cast<int>(orders[layerIndex].size());
            for (int i = 0; i < n; ++i) {
                const int u = orders[layerIndex][i];
                weights[i] = {weighting(graph, positions, u, false), {i, u}};
            }
            sort(weights.begin(), weights.begin() + n);
            for (int i = 0; i < n; ++i) {
                orders[layerIndex][i] = weights[i].second.second;
            }
            for (int i = 0; i < n; ++i) {
                const int u = weights[i].second.second;
                if (orders[layerIndex][i] != u) {
                    hasUpdate = true;
                }
                orders[layerIndex][i] = u;
            }

            if (!hasUpdate) {
                break;
            }
        }
        lastIsBest = false;
        if (const long long numCross = computeNumCross(graph, layering); numCross < bestNumCross) {
            if (repeatIndex + 1 != NUM_REPEAT) {
                bestLayeredOrder = layering;
            }
            bestNumCross = numCross;
            lastIsBest = true;
        }
    }
    if (bestLayeredOrder.width > 0 && !lastIsBest) {
        layering = bestLayeredOrder;
    }
}

/** Reduce the number of crossings using the Barycenter heuristic.
 *
 * The Barycenter is the average of the positions of all vertices in the previous layer
 * that are connected to the current vertex.
 *
 * @param graph A DAG.
 * @param layering A cross minimization result.
 */
void CrossMinimization::reduceNumCrossWithBaryCenterHeuristic(SPDirectedGraph& graph, SPLayering& layering) {
    auto weighting = [](SPDirectedGraph& _graph, const unordered_map<int, int>& positions, const int u, const bool forward) {
        double weight = 0.0;
        if (forward) {
            for (const auto& edge : _graph.getInEdges(u)) {
                weight += positions.find(edge.u)->second;
            }
            if (const auto degree = _graph.getInDegrees()[u]; degree > 0) {
                weight /= degree;
            }
        } else {
            for (const auto& edge : _graph.getOutEdges(u)) {
                weight += positions.find(edge.v)->second;
            }
            if (const auto degree = _graph.getOutDegrees()[u]; degree > 0) {
                weight /= degree;
            }
        }
        return weight;
    };
    reduceNumCrossWithWeightingHeuristic(graph, layering, weighting);
}

/** Reduce the number of crossings using the median heuristic.
 *
 * The median positions of all vertices in the previous layer that are connected to the current vertex.
 *
 * @param graph A DAG.
 * @param layering A cross minimization result.
 */
void CrossMinimization::reduceNumCrossWithMedianHeuristic(SPDirectedGraph& graph, SPLayering& layering) {
    auto weighting = [](SPDirectedGraph& _graph, const unordered_map<int, int>& positions, const int u, const bool forward) {
        vector<int> adjPositions;
        if (forward) {
            for (const auto& edge : _graph.getInEdges(u)) {
                adjPositions.emplace_back(positions.find(edge.u)->second);
            }
        } else {
            for (const auto& edge : _graph.getOutEdges(u)) {
                adjPositions.emplace_back(positions.find(edge.v)->second);
            }
        }
        const int n = static_cast<int>(adjPositions.size());
        if (n == 0) {
            return 0.0;
        }
        const auto mid = adjPositions.begin() + n / 2;
        ranges::nth_element(adjPositions, mid);
        double weight = *mid;
        if (n % 2 == 0) {
            const double weight2 = *max_element(adjPositions.begin(), mid);
            weight = (weight + weight2) * 0.5;
        }
        return weight;
    };
    reduceNumCrossWithWeightingHeuristic(graph, layering, weighting);
}

/** Compute the number of crossings between two vertices in one direction.
 *
 * Equivalent to counting inversions, which is solved here using merge sort.
 *
 * @param graph A DAG.
 * @param positions Mapping from a vertex ID to its index in the corresponding layer.
 * @param adjPositionsU All positions of the vertices connected to the first vertex.
 * @param adjPositionsV All positions of the vertices connected to the second vertex.
 * @param layerIndex Index of the layer that contains the two vertices.
 * @param u ID of the fist vertex.
 * @param v ID of the second vertex.
 * @param forward Whether it is from low rank to high rank.
 * @return Number of crossings.
 */
long long CrossMinimization::computeNumCross(SPDirectedGraph& graph,
                                             const vector<unordered_map<int, int>>& positions,
                                             vector<int>& adjPositionsU,
                                             vector<int>& adjPositionsV,
                                             const int layerIndex, const int u, const int v, const bool forward) {
    const int numLayers = static_cast<int>(positions.size());
    const int adjLayerIndex = forward ? layerIndex + 1 : layerIndex - 1;
    if (adjLayerIndex < 0 || adjLayerIndex >= numLayers) {
        return 0;
    }
    const auto& edgesU = forward ? graph.getOutEdges(u) : graph.getInEdges(u);
    const auto& edgesV = forward ? graph.getOutEdges(v) : graph.getInEdges(v);
    int degU = 0, degV = 0;
    for (const auto& edge : edgesU) {
        adjPositionsU[degU++] = positions[adjLayerIndex].find(edge.u == u ? edge.v : edge.u)->second;
    }
    for (const auto& edge : edgesV) {
        adjPositionsV[degV++] = positions[adjLayerIndex].find(edge.u == v ? edge.v : edge.u)->second;
    }
    sort(adjPositionsU.begin(), adjPositionsU.begin() + degU);
    sort(adjPositionsV.begin(), adjPositionsV.begin() + degV);
    long long numCross = 0;
    for (int indexU = 0, indexV = 0; indexU < degU && indexV < degV;) {
        if (adjPositionsU[indexU] <= adjPositionsV[indexV]) {
            ++indexU;
        } else {
            ++indexV;
            numCross += degU - indexU;
        }
    }
    return numCross;
}

/** Compute the number of crossings between two vertices in one direction.
 *
 * Equivalent to counting inversions, which is solved here using merge sort.
 *
 * @param graph A DAG.
 * @param positions Mapping from a vertex ID to its index in the corresponding layer.
 * @param adjPositionsU All positions of the vertices connected to the first vertex.
 * @param adjPositionsV All positions of the vertices connected to the second vertex.
 * @param layerIndex Index of the layer that contains the two vertices.
 * @param u ID of the fist vertex.
 * @param v ID of the second vertex.
 * @return Number of crossings.
 */
long long CrossMinimization::computeNumCross(SPDirectedGraph& graph,
                                             const vector<unordered_map<int, int>>& positions,
                                             vector<int>& adjPositionsU,
                                             vector<int>& adjPositionsV,
                                             const int layerIndex, const int u, const int v) {
    const long long numCrossForward = computeNumCross(graph, positions, adjPositionsU, adjPositionsV, layerIndex, u, v, true);
    const long long numCrossBackward = computeNumCross(graph, positions, adjPositionsU, adjPositionsV, layerIndex, u, v, false);
    return numCrossForward + numCrossBackward;
}

/** Reduce the number of crossings by switching the positions of two adjacent vertices.
 *
 * @param graph  A connected DAG.
 * @param layering A cross minimization result.
 */
void CrossMinimization::reduceNumCrossWithPairwiseSwitchHeuristic(SPDirectedGraph& graph, SPLayering& layering) {
    constexpr int NUM_REPEAT = 2;

    auto& orders = layering.orders;
    const int numLayers = static_cast<int>(orders.size());

    vector<unordered_map<int, int>> positions(numLayers);
    for (int layerIndex = 0; layerIndex < numLayers; layerIndex++) {
        for (int i = 0; i < static_cast<int>(orders[layerIndex].size()); i++) {
            positions[layerIndex][orders[layerIndex][i]] = i;
        }
    }

    int maxDegree = 0;
    for (const auto& order : orders) {
        for (const auto& u : order) {
            maxDegree = max(maxDegree, max(graph.getInDegrees()[u], graph.getOutDegrees()[u]));
        }
    }
    vector<int> adjPositions1(maxDegree), adjPositions2(maxDegree);

    bool hasUpdate = false;
    const auto swapIfLessNumCross = [&](const int layerIndex, const int index) {
        const int u = orders[layerIndex][index];
        const int v = orders[layerIndex][index + 1];
        const long long currentNumCross = computeNumCross(graph, positions, adjPositions1, adjPositions2, layerIndex, u, v);
        const long long newNumCross = computeNumCross(graph, positions, adjPositions1, adjPositions2, layerIndex, v, u);
        if (currentNumCross > newNumCross) {
            hasUpdate = true;
            swap(orders[layerIndex][index], orders[layerIndex][index + 1]);
            swap(positions[layerIndex][u], positions[layerIndex][v]);
        }
    };

    for (int repeatIndex = 0; repeatIndex < NUM_REPEAT; ++repeatIndex) {
        hasUpdate = false;
        for (int layerIndex = 0; layerIndex < numLayers; ++layerIndex) {
            for (int i = 0; i + 1 < static_cast<int>(orders[layerIndex].size()); ++i) {
                swapIfLessNumCross(layerIndex, i);
            }
        }
        if (!hasUpdate) {
            break;
        }

        hasUpdate = false;
        for (int layerIndex = numLayers - 1; layerIndex >= 0; --layerIndex) {
            for (int i = 0; i + 1 < static_cast<int>(orders[layerIndex].size()); ++i) {
                swapIfLessNumCross(layerIndex, i);
            }
        }
    }
}

1	#include "directed/cross_minimization.h"
2
3	#include <ranges>
4	#include <set>
5	#include <algorithm>
6	using namespace std;
7	using namespace graph_layout;
8
9	void SPLayering::initializeMapping() {	81✔
10	const int numLayers = static_cast<int>(orders.size());	81✔
11	positions.resize(numLayers);	81✔
12	idToLayer.clear();	81✔
13	for (int i = 0; i < numLayers; i++) {	427✔
14	for (int j = 0; j < static_cast<int>(orders[i].size()); ++j) {	1,254✔
15	positions[i][orders[i][j]] = j;	908✔
16	idToLayer[orders[i][j]] = i;	908✔
17	}
18	}
19	}	81✔
20
21	CrossMinimization::CrossMinimization(const CrossMinimizationMethod method) : _method(method) {	29✔
22	}	29✔
23
24
25	void CrossMinimization::setMethod(const CrossMinimizationMethod method) {	×
26	_method = method;	×
27	}	×
28
29	pair<SPLayering, vector<SPVirtualEdge>> CrossMinimization::reduceNumCross(SPDirectedGraph& graph, vector<int>& ranks) const {	32✔
30	auto [layering, virtualEdges] = addVirtualEdges(graph, ranks);	32✔
31	switch (_method) {	32✔
32	case CrossMinimizationMethod::BARYCENTER:	26✔
33	reduceNumCrossWithBaryCenterHeuristic(graph, layering);	26✔
34	break;	26✔
35	case CrossMinimizationMethod::MEDIAN:	3✔
36	reduceNumCrossWithMedianHeuristic(graph, layering);	3✔
37	break;	3✔
38	case CrossMinimizationMethod::PAIRWISE_SWITCH:	3✔
39	reduceNumCrossWithPairwiseSwitchHeuristic(graph, layering);	3✔
40	break;	3✔
41	}
42	layering.initializeMapping();	32✔
43	return {layering, virtualEdges};	64✔
44	}	32✔
45
46	pair<SPLayering, vector<SPVirtualEdge>> CrossMinimization::addVirtualEdges(SPDirectedGraph& graph, vector<int>& ranks) {	45✔
47	SPLayering layering;	45✔
48	auto& discreteRanks = layering.layerRanks;	45✔
49	auto& orders = layering.orders;	45✔
50	discreteRanks = vector(ranks);	45✔
51	ranges::sort(discreteRanks);	45✔
52	discreteRanks.erase(ranges::unique(discreteRanks).begin(), discreteRanks.end());	45✔
53	unordered_map<int, int> rankToIndex;	45✔
54	for (int i = 0; i < static_cast<int>(discreteRanks.size()); i++) {	232✔
55	rankToIndex[discreteRanks[i]] = i;	187✔
56	}
57	orders.resize(discreteRanks.size());	45✔
58	for (int i = 0; i < static_cast<int>(ranks.size()); ++i) {	377✔
59	orders[rankToIndex[ranks[i]]].emplace_back(i);	332✔
60	}
61
62	int n = static_cast<int>(graph.numVertices());	45✔
63	vector<SPVirtualEdge> virtualEdges;	45✔
64	for (const auto& edge : graph.edges()) {	420✔
65	if (rankToIndex[ranks[edge.v]] - rankToIndex[ranks[edge.u]] > 1) {	375✔
66	virtualEdges.emplace_back(edge);	55✔
67	}
68	}
69	int numNewNodes = 0;	45✔
70	for (const auto& [edge, edgeId] : virtualEdges) {	100✔
71	graph.removeEdge(edge.id);	55✔
72	numNewNodes += rankToIndex[ranks[edge.v]] - rankToIndex[ranks[edge.u]] - 1;	55✔
73	}
74	graph.updateNumVertices(n + numNewNodes);	45✔
75	int edgeId = VIRTUAL_EDGE_ID_OFFSET;	45✔
76	for (auto& [originalEdge, virtualEdgeIds] : virtualEdges) {	100✔
77	const int u = originalEdge.u;	55✔
78	const int v = originalEdge.v;	55✔
79	int last = u;	55✔
80	for (int rankIndex = rankToIndex[ranks[u]] + 1; rankIndex < rankToIndex[ranks[v]]; ++rankIndex) {	221✔
81	graph.addEdge(SPEdge(edgeId, last, n));	166✔
82	virtualEdgeIds.emplace_back(edgeId++);	166✔
83	ranks.emplace_back(discreteRanks[rankIndex]);	166✔
84	orders[rankIndex].emplace_back(n);	166✔
85	last = n++;	166✔
86	}
87	graph.addEdge(SPEdge(edgeId, last, v));	55✔
88	virtualEdgeIds.emplace_back(edgeId++);	55✔
89	}
90
91	layering.width = 0;	45✔
92	for (const auto& order : orders) {	232✔
93	layering.width = max(layering.width, order.size());	187✔
94	}
95	layering.initializeMapping();	45✔
96	return {layering, virtualEdges};	90✔
97	}	45✔
98
99	/** Compute the number of crossings between two adjacent layers.
100	*
101	* We iterate over the vertices in the second layer backwards.
102	* Suppose there is an edge connecting u in the second layer to v in the first layer,
103	* this edge crosses all edges for which `position[v']` < `position[v]` (the prefix sum of existing edges).
104	* We use a binary indexed tree to maintain the prefix sums.
105	*
106	* @param graph A DAG.
107	* @param bit An initialized binary indexed tree.
108	* @param order1 Orders in the first layer.
109	* @param order2 Orders in the second layer.
110	* @param forward Whether it is from low rank to high rank.
111	* @return Number of crossings.
112	*/
113	long long CrossMinimization::computeNumCross(	725✔
114	SPDirectedGraph& graph,
115	BinaryIndexedTree &bit,
116	const vector<int> &order1,
117	const vector<int> &order2,
118	const bool forward) {
119	bit.clear(order1.size());	725✔
120	unordered_map<int, int> positions;	725✔
121	for (int i = 0; i < static_cast<int>(order1.size()); ++i) {	6,491✔
122	positions[order1[i]] = i;	5,766✔
123	}
124	long long numCross = 0;	725✔
125	if (forward) {	725✔
126	for (const int v : views::reverse(order2)) {	6,457✔
127	for (const auto& edge : graph.getInEdges(v)) {	14,954✔
128	const int u = edge.u;	9,222✔
129	if (const auto it = positions.find(u); it != positions.end()) {	9,222✔
130	numCross += bit.prefixSum(it->second - 1);	9,222✔
131	}
132	}
133	for (const auto& edge : graph.getInEdges(v)) {	14,954✔
134	const int u = edge.u;	9,222✔
135	if (const auto it = positions.find(u); it != positions.end()) {	9,222✔
136	bit.add(it->second);	9,222✔
137	}
138	}
139	}
140	} else {
141	for (const int v : views::reverse(order2)) {	×
142	for (const auto& edge : graph.getOutEdges(v)) {	×
143	const int u = edge.v;	×
144	if (const auto it = positions.find(u); it != positions.end()) {	×
145	numCross += bit.prefixSum(it->second - 1);	×
146	}
147	}
148	for (const auto& edge : graph.getOutEdges(v)) {	×
149	const int u = edge.v;	×
150	if (const auto it = positions.find(u); it != positions.end()) {	×
151	bit.add(it->second);	×
152	}
153	}
154	}
155	}
156	return numCross;	725✔
157	}	725✔
158
159	long long CrossMinimization::computeNumCross(SPDirectedGraph& graph, const SPLayering& layering) {	305✔
160	const auto& orders = layering.orders;	305✔
161	BinaryIndexedTree bit(layering.width);	305✔
162	long long numCross = 0;	305✔
163	for (size_t i = 1; i < orders.size(); ++i) {	1,030✔
164	numCross += computeNumCross(graph, bit, orders[i - 1], orders[i], true);	725✔
165	}
166	return numCross;	305✔
167	}	305✔
168
169	/** Reduce the number of crossings using a weighting heuristic.
170	*
171	* The algorithm goes through several rounds of scanning.
172	* In each round, it first optimizes from lower ranks to higher ranks, then from higher ranks to lower ranks.
173	* During each optimization, the order of the previous layer is fixed,
174	* and heuristic methods are used to optimize the ordering of the current layer.
175	*
176	* @param graph A DAG.
177	* @param layering A cross minimization result.
178	* @param weighting A weighting function.
179	*/
180	void CrossMinimization::reduceNumCrossWithWeightingHeuristic(	29✔
181	SPDirectedGraph& graph,
182	SPLayering& layering,
183	const function<double(SPDirectedGraph&, const unordered_map<int, int>&, int, bool)> &weighting) {
184	constexpr int NUM_REPEAT = 2;	29✔
185
186	auto& orders = layering.orders;	29✔
187	const int numLayers = static_cast<int>(orders.size());	29✔
188
189	vector<pair<double, pair<int, int>>> weights(layering.width);	29✔
190
191	SPLayering bestLayeredOrder(layering);	29✔
192	long long bestNumCross = computeNumCross(graph, layering);	29✔
193	bool lastIsBest = false, hasUpdate = false;	29✔
194	unordered_map<int, int> positions;	29✔
195	for (int repeatIndex = 0; repeatIndex < NUM_REPEAT; ++repeatIndex) {	87✔
196	hasUpdate = false;	58✔
197	for (int layerIndex = 1; layerIndex < numLayers; ++layerIndex) {	280✔
198	positions.clear();	222✔
199	for (int i = 0; i < static_cast<int>(orders[layerIndex - 1].size()); ++i) {	898✔
200	positions[orders[layerIndex - 1][i]] = i;	676✔
201	}
202	const int n = static_cast<int>(orders[layerIndex].size());	222✔
203	for (int i = 0; i < n; ++i) {	888✔
204	const int v = orders[layerIndex][i];	666✔
205	weights[i] = {weighting(graph, positions, v, true), {i, v}};	666✔
206	}
207	sort(weights.begin(), weights.begin() + n);	222✔
208	for (int i = 0; i < n; ++i) {	888✔
209	const int v = weights[i].second.second;	666✔
210	if (orders[layerIndex][i] != v) {	666✔
211	hasUpdate = true;	257✔
212	}
213	orders[layerIndex][i] = v;	666✔
214	}
215	}
216	if (const long long numCross = computeNumCross(graph, layering); numCross < bestNumCross) {	58✔
217	bestLayeredOrder = layering;	18✔
218	bestNumCross = numCross;	18✔
219	}
220
221	for (int layerIndex = numLayers - 2; layerIndex >= 0; --layerIndex) {	171✔
222	positions.clear();	150✔
223	for (int i = 0; i < static_cast<int>(orders[layerIndex + 1].size()); ++i) {	655✔
224	positions[orders[layerIndex + 1][i]] = i;	505✔
225	}
226	const int n = static_cast<int>(orders[layerIndex].size());	150✔
227	for (int i = 0; i < n; ++i) {	711✔
228	const int u = orders[layerIndex][i];	561✔
229	weights[i] = {weighting(graph, positions, u, false), {i, u}};	561✔
230	}
231	sort(weights.begin(), weights.begin() + n);	150✔
232	for (int i = 0; i < n; ++i) {	711✔
233	orders[layerIndex][i] = weights[i].second.second;	561✔
234	}
235	for (int i = 0; i < n; ++i) {	711✔
236	const int u = weights[i].second.second;	561✔
237	if (orders[layerIndex][i] != u) {	561✔
238	hasUpdate = true;	×
239	}
240	orders[layerIndex][i] = u;	561✔
241	}
242
243	if (!hasUpdate) {	150✔
244	break;	37✔
245	}
246	}
247	lastIsBest = false;	58✔
248	if (const long long numCross = computeNumCross(graph, layering); numCross < bestNumCross) {	58✔
UNCOV 249	if (repeatIndex + 1 != NUM_REPEAT) {	×
UNCOV 250	bestLayeredOrder = layering;	×
251	}
UNCOV 252	bestNumCross = numCross;	×
UNCOV 253	lastIsBest = true;	×
254	}
255	}
256	if (bestLayeredOrder.width > 0 && !lastIsBest) {	29✔
257	layering = bestLayeredOrder;	29✔
258	}
259	}	29✔
260
261	/** Reduce the number of crossings using the Barycenter heuristic.
262	*
263	* The Barycenter is the average of the positions of all vertices in the previous layer
264	* that are connected to the current vertex.
265	*
266	* @param graph A DAG.
267	* @param layering A cross minimization result.
268	*/
269	void CrossMinimization::reduceNumCrossWithBaryCenterHeuristic(SPDirectedGraph& graph, SPLayering& layering) {	26✔
270	auto weighting = [](SPDirectedGraph& _graph, const unordered_map<int, int>& positions, const int u, const bool forward) {	1,176✔
271	double weight = 0.0;	1,176✔
272	if (forward) {	1,176✔
273	for (const auto& edge : _graph.getInEdges(u)) {	1,464✔
274	weight += positions.find(edge.u)->second;	826✔
275	}
276	if (const auto degree = _graph.getInDegrees()[u]; degree > 0) {	638✔
277	weight /= degree;	630✔
278	}
279	} else {
280	for (const auto& edge : _graph.getOutEdges(u)) {	1,193✔
281	weight += positions.find(edge.v)->second;	655✔
282	}
283	if (const auto degree = _graph.getOutDegrees()[u]; degree > 0) {	538✔
284	weight /= degree;	514✔
285	}
286	}
287	return weight;	1,176✔
288	};
289	reduceNumCrossWithWeightingHeuristic(graph, layering, weighting);	26✔
290	}	26✔
291
292	/** Reduce the number of crossings using the median heuristic.
293	*
294	* The median positions of all vertices in the previous layer that are connected to the current vertex.
295	*
296	* @param graph A DAG.
297	* @param layering A cross minimization result.
298	*/
299	void CrossMinimization::reduceNumCrossWithMedianHeuristic(SPDirectedGraph& graph, SPLayering& layering) {	3✔
300	auto weighting = [](SPDirectedGraph& _graph, const unordered_map<int, int>& positions, const int u, const bool forward) {	51✔
301	vector<int> adjPositions;	51✔
302	if (forward) {	51✔
303	for (const auto& edge : _graph.getInEdges(u)) {	58✔
304	adjPositions.emplace_back(positions.find(edge.u)->second);	30✔
305	}
306	} else {
307	for (const auto& edge : _graph.getOutEdges(u)) {	45✔
308	adjPositions.emplace_back(positions.find(edge.v)->second);	22✔
309	}
310	}
311	const int n = static_cast<int>(adjPositions.size());	51✔
312	if (n == 0) {	51✔
313	return 0.0;	11✔
314	}
315	const auto mid = adjPositions.begin() + n / 2;	40✔
316	ranges::nth_element(adjPositions, mid);	40✔
317	double weight = *mid;	40✔
318	if (n % 2 == 0) {	40✔
319	const double weight2 = *max_element(adjPositions.begin(), mid);	6✔
320	weight = (weight + weight2) * 0.5;	6✔
321	}
322	return weight;	40✔
323	};	51✔
324	reduceNumCrossWithWeightingHeuristic(graph, layering, weighting);	3✔
325	}	3✔
326
327	/** Compute the number of crossings between two vertices in one direction.
328	*
329	* Equivalent to counting inversions, which is solved here using merge sort.
330	*
331	* @param graph A DAG.
332	* @param positions Mapping from a vertex ID to its index in the corresponding layer.
333	* @param adjPositionsU All positions of the vertices connected to the first vertex.
334	* @param adjPositionsV All positions of the vertices connected to the second vertex.
335	* @param layerIndex Index of the layer that contains the two vertices.
336	* @param u ID of the fist vertex.
337	* @param v ID of the second vertex.
338	* @param forward Whether it is from low rank to high rank.
339	* @return Number of crossings.
340	*/
341	long long CrossMinimization::computeNumCross(SPDirectedGraph& graph,	88✔
342	const vector<unordered_map<int, int>>& positions,
343	vector<int>& adjPositionsU,
344	vector<int>& adjPositionsV,
345	const int layerIndex, const int u, const int v, const bool forward) {
346	const int numLayers = static_cast<int>(positions.size());	88✔
347	const int adjLayerIndex = forward ? layerIndex + 1 : layerIndex - 1;	88✔
348	if (adjLayerIndex < 0 \|\| adjLayerIndex >= numLayers) {	88✔
349	return 0;	32✔
350	}
351	const auto& edgesU = forward ? graph.getOutEdges(u) : graph.getInEdges(u);	56✔
352	const auto& edgesV = forward ? graph.getOutEdges(v) : graph.getInEdges(v);	56✔
353	int degU = 0, degV = 0;	56✔
354	for (const auto& edge : edgesU) {	114✔
355	adjPositionsU[degU++] = positions[adjLayerIndex].find(edge.u == u ? edge.v : edge.u)->second;	58✔
356	}
357	for (const auto& edge : edgesV) {	114✔
358	adjPositionsV[degV++] = positions[adjLayerIndex].find(edge.u == v ? edge.v : edge.u)->second;	58✔
359	}
360	sort(adjPositionsU.begin(), adjPositionsU.begin() + degU);	56✔
361	sort(adjPositionsV.begin(), adjPositionsV.begin() + degV);	56✔
362	long long numCross = 0;	56✔
363	for (int indexU = 0, indexV = 0; indexU < degU && indexV < degV;) {	110✔
364	if (adjPositionsU[indexU] <= adjPositionsV[indexV]) {	54✔
365	++indexU;	33✔
366	} else {
367	++indexV;	21✔
368	numCross += degU - indexU;	21✔
369	}
370	}
371	return numCross;	56✔
372	}
373
374	/** Compute the number of crossings between two vertices in one direction.
375	*
376	* Equivalent to counting inversions, which is solved here using merge sort.
377	*
378	* @param graph A DAG.
379	* @param positions Mapping from a vertex ID to its index in the corresponding layer.
380	* @param adjPositionsU All positions of the vertices connected to the first vertex.
381	* @param adjPositionsV All positions of the vertices connected to the second vertex.
382	* @param layerIndex Index of the layer that contains the two vertices.
383	* @param u ID of the fist vertex.
384	* @param v ID of the second vertex.
385	* @return Number of crossings.
386	*/
387	long long CrossMinimization::computeNumCross(SPDirectedGraph& graph,	44✔
388	const vector<unordered_map<int, int>>& positions,
389	vector<int>& adjPositionsU,
390	vector<int>& adjPositionsV,
391	const int layerIndex, const int u, const int v) {
392	const long long numCrossForward = computeNumCross(graph, positions, adjPositionsU, adjPositionsV, layerIndex, u, v, true);	44✔
393	const long long numCrossBackward = computeNumCross(graph, positions, adjPositionsU, adjPositionsV, layerIndex, u, v, false);	44✔
394	return numCrossForward + numCrossBackward;	44✔
395	}
396
397	/** Reduce the number of crossings by switching the positions of two adjacent vertices.
398	*
399	* @param graph A connected DAG.
400	* @param layering A cross minimization result.
401	*/
402	void CrossMinimization::reduceNumCrossWithPairwiseSwitchHeuristic(SPDirectedGraph& graph, SPLayering& layering) {	3✔
403	constexpr int NUM_REPEAT = 2;	3✔
404
405	auto& orders = layering.orders;	3✔
406	const int numLayers = static_cast<int>(orders.size());	3✔
407
408	vector<unordered_map<int, int>> positions(numLayers);	3✔
409	for (int layerIndex = 0; layerIndex < numLayers; layerIndex++) {	11✔
410	for (int i = 0; i < static_cast<int>(orders[layerIndex].size()); i++) {	28✔
411	positions[layerIndex][orders[layerIndex][i]] = i;	20✔
412	}
413	}
414
415	int maxDegree = 0;	3✔
416	for (const auto& order : orders) {	11✔
417	for (const auto& u : order) {	28✔
418	maxDegree = max(maxDegree, max(graph.getInDegrees()[u], graph.getOutDegrees()[u]));	20✔
419	}
420	}
421	vector<int> adjPositions1(maxDegree), adjPositions2(maxDegree);	9✔
422
423	bool hasUpdate = false;	3✔
424	const auto swapIfLessNumCross = [&](const int layerIndex, const int index) {	22✔
425	const int u = orders[layerIndex][index];	22✔
426	const int v = orders[layerIndex][index + 1];	22✔
427	const long long currentNumCross = computeNumCross(graph, positions, adjPositions1, adjPositions2, layerIndex, u, v);	22✔
428	const long long newNumCross = computeNumCross(graph, positions, adjPositions1, adjPositions2, layerIndex, v, u);	22✔
429	if (currentNumCross > newNumCross) {	22✔
430	hasUpdate = true;	3✔
431	swap(orders[layerIndex][index], orders[layerIndex][index + 1]);	3✔
432	swap(positions[layerIndex][u], positions[layerIndex][v]);	3✔
433	}
434	};	22✔
435
436	for (int repeatIndex = 0; repeatIndex < NUM_REPEAT; ++repeatIndex) {	5✔
437	hasUpdate = false;	5✔
438	for (int layerIndex = 0; layerIndex < numLayers; ++layerIndex) {	17✔
439	for (int i = 0; i + 1 < static_cast<int>(orders[layerIndex].size()); ++i) {	29✔
440	swapIfLessNumCross(layerIndex, i);	17✔
441	}
442	}
443	if (!hasUpdate) {	5✔
444	break;	3✔
445	}
446
447	hasUpdate = false;	2✔
448	for (int layerIndex = numLayers - 1; layerIndex >= 0; --layerIndex) {	6✔
449	for (int i = 0; i + 1 < static_cast<int>(orders[layerIndex].size()); ++i) {	9✔
450	swapIfLessNumCross(layerIndex, i);	5✔
451	}
452	}
453	}
454	}	3✔

CyberZHG / GraphLayout / 21120124705

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