NBAlgorithms.h

Go to the documentation of this file.

/****************************************************************************/
// Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
// Copyright (C) 2012-2026 German Aerospace Center (DLR) and others.
// This program and the accompanying materials are made available under the
// terms of the Eclipse Public License 2.0 which is available at
// https://www.eclipse.org/legal/epl-2.0/
// This Source Code may also be made available under the following Secondary
// Licenses when the conditions for such availability set forth in the Eclipse
// Public License 2.0 are satisfied: GNU General Public License, version 2
// or later which is available at
// https://www.gnu.org/licenses/old-licenses/gpl-2.0-standalone.html
// SPDX-License-Identifier: EPL-2.0 OR GPL-2.0-or-later
/****************************************************************************/
// Algorithms for network computation
/****************************************************************************/
#pragma once
#include <config.h>
 
#include <map>
#include "NBEdgeCont.h"
#include "NBNodeCont.h"
 
// ===========================================================================
// class declarations
// ===========================================================================
class NBEdge;
class NBNode;
 
// ===========================================================================
// class definitions
// ===========================================================================
// ---------------------------------------------------------------------------
// NBTurningDirectionsComputer
// ---------------------------------------------------------------------------
/* @class NBTurningDirectionsComputer
 * @brief Computes turnaround destinations for all edges (if exist)
 */
class NBTurningDirectionsComputer {
public:
    static void computeTurnDirections(NBNodeCont& nc, bool warn = true);
 
    static void computeTurnDirectionsForNode(NBNode* node, bool warn);
 
    static double getFarAngleAtNode(const NBEdge* e, const NBNode* n, double dist = 50);
 
private:
    struct Combination {
        NBEdge* from;
        NBEdge* to;
        double angle;
    };
 
 
    class combination_by_angle_sorter {
    public:
        explicit combination_by_angle_sorter() { }
        int operator()(const Combination& c1, const Combination& c2) const {
            if (c1.angle != c2.angle) {
                return c1.angle > c2.angle;
            }
            if (c1.from != c2.from) {
                if (c1.to == c2.to && c1.from->getPermissions() != c2.from->getPermissions()) {
                    if (c1.from->getPermissions() == c1.to->getPermissions()) {
                        return true;
                    } else if (c2.from->getPermissions() == c1.to->getPermissions()) {
                        return false;
                    }
                }
                return c1.from->getID() < c2.from->getID();
            }
            if (c1.to->getPermissions() != c2.to->getPermissions()) {
                if (c1.to->getPermissions() == c1.from->getPermissions()) {
                    return true;
                } else if (c2.to->getPermissions() == c1.from->getPermissions()) {
                    return false;
                }
            }
            return c1.to->getID() < c2.to->getID();
        }
    };
};
 
 
 
// ---------------------------------------------------------------------------
// NBNodesEdgesSorter
// ---------------------------------------------------------------------------
/* @class NBNodesEdgesSorter
 * @brief Sorts a node's edges clockwise regarding driving direction
 */
class NBNodesEdgesSorter {
public:
    static void sortNodesEdges(NBNodeCont& nc, bool useNodeShape = false);
 
    class crossing_by_junction_angle_sorter {
    public:
        explicit crossing_by_junction_angle_sorter(const NBNode* node, const EdgeVector& ordering);
 
        int operator()(const std::unique_ptr<NBNode::Crossing>& c1, const std::unique_ptr<NBNode::Crossing>& c2) const {
            const int r1 = getMinRank(c1->edges);
            const int r2 = getMinRank(c2->edges);
            if (r1 == r2) {
                return c1->edges.size() > c2->edges.size();
            } else {
                return (int)(r1 < r2);
            }
        }
 
    private:
        int getMinRank(const EdgeVector& e) const {
            int result = (int)myOrdering.size();
            for (EdgeVector::const_iterator it = e.begin(); it != e.end(); ++it) {
                int rank = (int)std::distance(myOrdering.begin(), std::find(myOrdering.begin(), myOrdering.end(), *it));
                result = MIN2(result, rank);
            }
            return result;
        }
 
    private:
        EdgeVector myOrdering;
    };
 
    static void swapWhenReversed(const NBNode* const n,
                                 const std::vector<NBEdge*>::iterator& i1,
                                 const std::vector<NBEdge*>::iterator& i2);
 
 
    class edge_by_junction_angle_sorter {
    public:
        explicit edge_by_junction_angle_sorter(NBNode* n) : myNode(n) {}
        int operator()(NBEdge* e1, NBEdge* e2) const {
            const double a1 = e1->getAngleAtNodeNormalized(myNode);
            const double a2 = e2->getAngleAtNodeNormalized(myNode);
            return a1 < a2 || (a1 == a2 && e1->getNumericalID() < e2->getNumericalID());
        }
 
    private:
        NBNode* myNode;
 
    };
 
};
 
 
 
// ---------------------------------------------------------------------------
// NBNodeTypeComputer
// ---------------------------------------------------------------------------
/* @class NBNodeTypeComputer
 * @brief Computes node types
 */
class NBNodeTypeComputer {
public:
    static void computeNodeTypes(NBNodeCont& nc, NBTrafficLightLogicCont& tlc);
 
    static void validateRailCrossings(NBNodeCont& nc, NBTrafficLightLogicCont& tlc);
 
    static bool isRailwayNode(const NBNode* n);
};
 
 
 
// ---------------------------------------------------------------------------
// NBEdgePriorityComputer
// ---------------------------------------------------------------------------
/* @class NBEdgePriorityComputer
 * @brief Computes edge priorities within a node
 */
class NBEdgePriorityComputer {
public:
    static void computeEdgePriorities(NBNodeCont& nc);
 
private:
    static void setPriorityJunctionPriorities(NBNode& n, bool forceStraight = false);
 
    static double getScore(const NBEdge* e1, const NBEdge* e2, int minPrio, int maxPrio, int maxNumLanes, double maxSpeed, SVCPermissions permissions);
 
    static void markBestParallel(const NBNode& n, NBEdge* bestFirst, NBEdge* bestSecond);
 
    static NBEdge* extractAndMarkFirst(NBNode& n, std::vector<NBEdge*>& s, int prio = 1);
 
    static bool samePriority(const NBEdge* const e1, const NBEdge* const e2, SVCPermissions permissions);
 
    static bool hasDifferentPriorities(const EdgeVector& edges, const NBEdge* excluded);
 
};