↰ Return to documentation for file (include/networkit/planarity/LeftRightPlanarityCheckImpl.hpp)
/* LeftRightPlanarityCheckImpl.hpp
*
* Created on: 03.01.2025
* Authors: Andreas Scharf (andreas.b.scharf@gmail.com)
*
*/
#ifndef NETWORKIT_PLANARITY_LEFT_RIGHT_PLANARITY_CHECK_IMPL_HPP_
#define NETWORKIT_PLANARITY_LEFT_RIGHT_PLANARITY_CHECK_IMPL_HPP_
#include <algorithm>
#include <ranges>
#include <stdexcept>
namespace NetworKit {
template <typename GraphT>
GenericLeftRightPlanarityCheck<GraphT>::GenericLeftRightPlanarityCheck(const GraphT &G)
: graph(&G) {
if (G.isDirected()) {
throw std::runtime_error("The graph is not an undirected graph.");
}
if (!G.hasEdgeIds()) {
throw std::runtime_error("The graph has no edge IDs.");
}
numberOfEdges = graph->numberOfEdges();
nestingDepth.resize(numberOfEdges, none);
lowestPointEdge.resize(numberOfEdges, nullEdgeId);
secondLowestPoint.resize(numberOfEdges, none);
ref.resize(numberOfEdges, nullEdgeId);
stackBottom.resize(numberOfEdges, {});
lowestPoint.resize(numberOfEdges, none);
// dfsGraph: directed view of DFS tree + back edges
dfsGraph = GraphT(graph->numberOfNodes(), false, true, false);
}
template <typename GraphT>
void GenericLeftRightPlanarityCheck<GraphT>::run() {
// Euler-criterion: non-planar if m > 3n - 6 for n > 2
if (graph->numberOfNodes() > 2 && graph->numberOfEdges() > 3 * graph->numberOfNodes() - 6) {
hasRun = true;
isGraphPlanar = false;
return;
}
heights.assign(graph->upperNodeIdBound(), noneHeight);
parentEdgeIds.assign(graph->upperNodeIdBound(), nullEdgeId);
parentNodes.assign(graph->upperNodeIdBound(), NullNodeId<NodeT>);
edgeEndpoints.assign(graph->upperEdgeIdBound(), NullNodeId<NodeT>);
// DFS orientation
graph->forNodes([&](NodeT currentNode) {
if (heights[currentNode] == noneHeight) {
heights[currentNode] = 0;
roots.push_back(currentNode);
this->dfsOrientation(currentNode);
}
});
// Sort DFS adjacency by nesting depth
sortAdjacencyListByNestingDepth();
// Planarity testing DFS
isGraphPlanar =
std::ranges::all_of(roots, [this](NodeT rootNode) { return dfsTesting(rootNode); });
hasRun = true;
}
template <typename GraphT>
void GenericLeftRightPlanarityCheck<GraphT>::sortAdjacencyListByNestingDepth() {
dfsGraph.forNodes([&](NodeT currentNode) {
dfsGraph.sortNeighbors(currentNode, [&](NodeT neighbor1, NodeT neighbor2) {
const edgeid e1 = graph->edgeId(currentNode, neighbor1);
const edgeid e2 = graph->edgeId(currentNode, neighbor2);
return nestingDepth[e1] < nestingDepth[e2];
});
});
}
template <typename GraphT>
bool GenericLeftRightPlanarityCheck<GraphT>::conflicting(const Interval &interval, edgeid edgeId) {
if (interval.isEmpty()) {
return false;
}
auto iteratorHigh = lowestPoint[interval.high];
auto iteratorEdge = lowestPoint[edgeId];
return !interval.isEmpty() && iteratorHigh != none && iteratorEdge != none
&& iteratorHigh > iteratorEdge;
}
template <typename GraphT>
bool GenericLeftRightPlanarityCheck<GraphT>::applyConstraints(const edgeid edgeId,
const edgeid parentEdgeId) {
ConflictPair tmpConflictPair{};
// First phase: pop until stackBottom[edgeId], merging intervals on the right side.
do {
ConflictPair currentConflictPair = stack.top();
stack.pop();
if (!currentConflictPair.left.isEmpty()) {
currentConflictPair.swap();
}
if (!currentConflictPair.left.isEmpty()) {
return false;
}
auto rightLowIterator = lowestPoint[currentConflictPair.right.low];
auto parentEdgeIterator = lowestPoint[parentEdgeId];
if (rightLowIterator != none && parentEdgeIterator != none
&& rightLowIterator > parentEdgeIterator) {
if (tmpConflictPair.right.isEmpty()) {
tmpConflictPair.right = currentConflictPair.right;
} else {
ref[tmpConflictPair.right.low] = currentConflictPair.right.high;
}
tmpConflictPair.right.low = currentConflictPair.right.low;
} else {
ref[currentConflictPair.right.low] = lowestPointEdge[parentEdgeId];
}
} while (!stack.empty() && (stack.top() != stackBottom[edgeId]));
// Second phase: pop while there are conflicts with edgeId, merging left/right intervals.
while (!stack.empty()
&& (conflicting(stack.top().left, edgeId) || conflicting(stack.top().right, edgeId))) {
auto currentConflictPair = stack.top();
stack.pop();
if (conflicting(currentConflictPair.right, edgeId)) {
currentConflictPair.swap();
}
if (conflicting(currentConflictPair.right, edgeId)) {
// Still conflicting after swap -> non-planar
return false;
}
ref[tmpConflictPair.right.low] = currentConflictPair.right.high;
if (currentConflictPair.right.low != nullEdgeId) {
tmpConflictPair.right = currentConflictPair.right;
}
if (tmpConflictPair.left.isEmpty()) {
tmpConflictPair.left = currentConflictPair.left;
} else {
ref[tmpConflictPair.left.low] = currentConflictPair.left.high;
}
tmpConflictPair.left.low = currentConflictPair.left.low;
}
if (!tmpConflictPair.left.isEmpty() || !tmpConflictPair.right.isEmpty()) {
stack.push(tmpConflictPair);
}
return true;
}
template <typename GraphT>
count GenericLeftRightPlanarityCheck<GraphT>::getLowestLowPoint(const ConflictPair &conflictPair) {
if (conflictPair.left.isEmpty()) {
return lowestPoint[conflictPair.right.low];
}
if (conflictPair.right.isEmpty()) {
return lowestPoint[conflictPair.left.low];
}
return std::min(lowestPoint[conflictPair.right.low], lowestPoint[conflictPair.left.low]);
}
template <typename GraphT>
void GenericLeftRightPlanarityCheck<GraphT>::removeBackEdges(const edgeid edgeId,
const NodeT parentNode) {
while (!stack.empty() && getLowestLowPoint(stack.top()) == heights[parentNode]) {
stack.pop();
}
if (!stack.empty()) {
auto conflictPair = stack.top();
stack.pop();
// Reduce left interval
while (conflictPair.left.high != nullEdgeId
&& edgeEndpoints[conflictPair.left.high] == parentNode) {
auto tmpEdgeId = ref[conflictPair.left.high];
conflictPair.left.high = (tmpEdgeId != nullEdgeId) ? tmpEdgeId : nullEdgeId;
}
if (conflictPair.left.high == nullEdgeId && conflictPair.left.low != nullEdgeId) {
ref[conflictPair.left.low] = conflictPair.right.low;
conflictPair.left.low = nullEdgeId;
}
// Reduce right interval
while (conflictPair.right.high != nullEdgeId
&& edgeEndpoints[conflictPair.right.high] == parentNode) {
auto tmpEdgeId = ref[conflictPair.right.high];
conflictPair.right.high = (tmpEdgeId != nullEdgeId) ? tmpEdgeId : nullEdgeId;
}
if (conflictPair.right.high == nullEdgeId && conflictPair.right.low != nullEdgeId) {
ref[conflictPair.right.low] = conflictPair.left.low;
conflictPair.right.low = nullEdgeId;
}
stack.push(conflictPair);
}
if (!stack.empty() && lowestPoint[edgeId] < heights[parentNode]) {
const edgeid highestReturnEdgeLeft = stack.top().left.high;
const edgeid highestReturnEdgeRight = stack.top().right.high;
if (highestReturnEdgeLeft != nullEdgeId
&& (highestReturnEdgeRight == nullEdgeId
|| lowestPoint[highestReturnEdgeLeft] > lowestPoint[highestReturnEdgeRight])) {
ref[edgeId] = highestReturnEdgeLeft;
} else {
ref[edgeId] = highestReturnEdgeRight;
}
}
}
template <typename GraphT>
bool GenericLeftRightPlanarityCheck<GraphT>::dfsTesting(NodeT startNode) {
std::stack<NodeT> dfsStack;
dfsStack.push(startNode);
// Per-vertex neighbor iterators in DFS graph
using NeighborIterator = decltype(dfsGraph.neighborRange(static_cast<NodeT>(0)).begin());
std::vector<NeighborIterator> neighborIterators(dfsGraph.upperNodeIdBound());
std::vector<bool> neighborInitialized(dfsGraph.upperNodeIdBound(), false);
std::vector<edgeid> preprocessedEdges(numberOfEdges, nullEdgeId);
auto processNeighborEdges = [&](NodeT currentNode, bool &callRemoveBackEdges) -> bool {
auto range = dfsGraph.neighborRange(currentNode);
auto &neighborIterator = neighborIterators[currentNode];
while (neighborIterator != range.end()) {
const NodeT neighbor = *neighborIterator;
const edgeid currentEdgeId = graph->edgeId(currentNode, neighbor);
assert(currentEdgeId != nullEdgeId);
if (preprocessedEdges[currentEdgeId] == nullEdgeId) {
stackBottom[currentEdgeId] = stack.empty() ? NoneConflictPair : stack.top();
if (currentEdgeId == parentEdgeIds[neighbor]) {
// Tree edge: go deeper
dfsStack.push(currentNode);
dfsStack.push(neighbor);
preprocessedEdges[currentEdgeId] = currentEdgeId;
callRemoveBackEdges = false;
return true; // more work later
}
lowestPointEdge[currentEdgeId] = currentEdgeId;
stack.emplace(Interval{}, Interval(currentEdgeId, currentEdgeId));
}
auto currentEdgeIterator = lowestPoint[currentEdgeId];
if (currentEdgeIterator != none && currentEdgeIterator < heights[currentNode]) {
if (neighbor == *dfsGraph.neighborRange(currentNode).begin()) {
// First neighbor: propagate lowestPointEdge to parent edge
lowestPointEdge[parentEdgeIds[currentNode]] = lowestPointEdge[currentEdgeId];
} else if (!applyConstraints(currentEdgeId, parentEdgeIds[currentNode])) {
return false;
}
}
++neighborIterator;
}
return true;
};
// Main DFS loop
do {
const NodeT currentNode = dfsStack.top();
dfsStack.pop();
const edgeid parentEid = parentEdgeIds[currentNode];
bool callRemoveBackEdges{true};
if (!neighborInitialized[currentNode]) {
neighborIterators[currentNode] = dfsGraph.neighborRange(currentNode).begin();
neighborInitialized[currentNode] = true;
}
if (!processNeighborEdges(currentNode, callRemoveBackEdges)) {
return false;
}
if (callRemoveBackEdges && parentEid != nullEdgeId) {
removeBackEdges(parentEid, parentNodes[currentNode]);
}
} while (!dfsStack.empty());
return true;
}
template <typename GraphT>
void GenericLeftRightPlanarityCheck<GraphT>::dfsOrientation(NodeT startNode) {
std::stack<NodeT> dfsStack;
dfsStack.push(startNode);
std::vector<edgeid> preprocessedEdges(numberOfEdges, nullEdgeId);
do {
const NodeT currentNode = dfsStack.top();
dfsStack.pop();
const edgeid parentEdgeId = parentEdgeIds[currentNode];
for (NodeT neighbor : graph->neighborRange(currentNode)) {
const edgeid edgeId = graph->edgeId(currentNode, neighbor);
if (preprocessedEdges[edgeId] == nullEdgeId) {
if (dfsGraph.hasEdge(currentNode, neighbor)
|| dfsGraph.hasEdge(neighbor, currentNode)) {
continue;
}
dfsGraph.addEdge(currentNode, neighbor);
edgeEndpoints[edgeId] = neighbor;
lowestPoint[edgeId] = heights[currentNode];
secondLowestPoint[edgeId] = heights[currentNode];
if (heights[neighbor] == noneHeight) {
// Tree edge
parentEdgeIds[neighbor] = edgeId;
parentNodes[neighbor] = currentNode;
heights[neighbor] = heights[currentNode] + 1;
dfsStack.push(currentNode);
dfsStack.push(neighbor);
preprocessedEdges[edgeId] = edgeId;
break;
}
// Back edge: lowpoint is ancestor's height
lowestPoint[edgeId] = heights[neighbor];
}
nestingDepth[edgeId] = 2 * lowestPoint[edgeId];
if (secondLowestPoint[edgeId] < heights[currentNode]) {
nestingDepth[edgeId] += 1;
}
if (parentEdgeId != nullEdgeId) {
if (lowestPoint[edgeId] < lowestPoint[parentEdgeId]) {
secondLowestPoint[parentEdgeId] =
std::min(lowestPoint[parentEdgeId], secondLowestPoint[edgeId]);
lowestPoint[parentEdgeId] = lowestPoint[edgeId];
} else if (lowestPoint[edgeId] > lowestPoint[parentEdgeId]) {
secondLowestPoint[parentEdgeId] =
std::min(secondLowestPoint[parentEdgeId], lowestPoint[edgeId]);
} else {
secondLowestPoint[parentEdgeId] =
std::min(secondLowestPoint[parentEdgeId], secondLowestPoint[edgeId]);
}
}
}
} while (!dfsStack.empty());
}
} // namespace NetworKit
#endif // NETWORKIT_PLANARITY_LEFT_RIGHT_PLANARITY_CHECK_IMPL_HPP_