Program Listing for File LeftRightPlanarityCheck.hpp¶

/*  LeftRightPlanarityCheck.hpp
 *
 *  Created on: 03.01.2025
 *  Authors: Andreas Scharf (andreas.b.scharf@gmail.com)
 *
 */

#ifndef NETWORKIT_PLANARITY_LEFT_RIGHT_PLANARITY_CHECK_HPP_
#define NETWORKIT_PLANARITY_LEFT_RIGHT_PLANARITY_CHECK_HPP_

#include <limits>
#include <stack>
#include <vector>

#include <networkit/base/Algorithm.hpp>
#include <networkit/graph/Graph.hpp>

namespace NetworKit {

template <typename GraphT>
class GenericLeftRightPlanarityCheck final : public Algorithm {

public:
    using NodeT = typename GraphT::NodeT;
    using EdgeWeightT = typename GraphT::EdgeWeightT;

    GenericLeftRightPlanarityCheck(const GraphT &G);

    void run() override;

    bool isPlanar() const {
        assureFinished();
        return isGraphPlanar;
    }

private:
    count numberOfEdges;
    static constexpr count noneHeight{std::numeric_limits<count>::max()};

    struct Interval {
        edgeid low{nullEdgeId};
        edgeid high{nullEdgeId};

        Interval() = default;
        Interval(edgeid lowId, edgeid highId) : low(lowId), high(highId) {}

        bool isEmpty() const { return low == nullEdgeId && high == nullEdgeId; }

        friend bool operator==(const Interval &lhs, const Interval &rhs) {
            return lhs.low == rhs.low && lhs.high == rhs.high;
        }
    };

    struct ConflictPair {
        Interval left{};
        Interval right{};

        ConflictPair() = default;
        ConflictPair(const Interval &left, const Interval &right) : left(left), right(right) {}

        void swap() { std::swap(left, right); }

        friend bool operator==(const ConflictPair &lhs, const ConflictPair &rhs) {
            return lhs.left == rhs.left && lhs.right == rhs.right;
        }
    };

    const ConflictPair NoneConflictPair{Interval{}, Interval{}};

    const GraphT *graph;
    bool isGraphPlanar{false};

    void dfsOrientation(NodeT startNode);
    bool dfsTesting(NodeT startNode);

    bool applyConstraints(edgeid edgeId, edgeid parentEdgeId);
    void removeBackEdges(edgeid edgeId, NodeT parentNode);
    void sortAdjacencyListByNestingDepth();
    bool conflicting(const Interval &interval, edgeid edgeId);
    count getLowestLowPoint(const ConflictPair &conflictPair);

    // DFS / lowpoint state
    std::vector<count> heights; // per vertex
    std::vector<NodeT> roots;   // roots of DFS forest

    std::vector<count> lowestPoint;
    std::vector<count> secondLowestPoint;
    std::vector<edgeid> ref;
    std::vector<edgeid> lowestPointEdge;
    std::vector<count> nestingDepth;
    std::vector<ConflictPair> stackBottom;

    // Per-vertex parent edge + parent vertex in DFS tree
    std::vector<edgeid> parentEdgeIds; // parent edge for each vertex (nullEdgeId if root)
    std::vector<NodeT> parentNodes;    // parent vertex for each vertex (NullNodeId<NodeT> if root)

    // For each *underlying* edge ID, remember the DFS orientation's head (v)
    std::vector<NodeT> edgeEndpoints; // edgeEndpoints[eid] = v in oriented DFS edge (u -> v)

    // Conflict stack
    std::stack<ConflictPair> stack;
    // DFS graph with tree/back orientation
    GraphT dfsGraph;
};

using LeftRightPlanarityCheck = GenericLeftRightPlanarityCheck<Graph>;

} // namespace NetworKit

#include <networkit/planarity/LeftRightPlanarityCheckImpl.hpp>

#endif // NETWORKIT_PLANARITY_LEFT_RIGHT_PLANARITY_CHECK_HPP_