Function IsNodeIndependent

src/contractor/graph_contractor.cpp:466–501

* @brief Test if a node is independent. * * Two independent nodes can be contracted in parallel without influencing each other. * * A node is independent if there is no node with a lower priority less than 3 hops away * from it. (In case of equal priorities the node id is used as tie breaker.) The * next-nearest independent node must be at least 3 hops away: they can be processed at * the s

 * @return bool true if the node is independent.
 */
bool IsNodeIndependent(const ContractorGraph &graph,
                       const NodeID v,
                       const std::vector<float> &priorities)
{
    const float priority = priorities[v];
    BOOST_ASSERT(priority >= 0);

    for (const NodeID hop1 : GetNeighbours(graph, v))
    {
        // 1 hop away
        const float hop1_priority = priorities[hop1];
        BOOST_ASSERT(hop1_priority >= 0);

        if (hop1_priority < priority || (hop1_priority == priority && hop1 < v))
        {
            return false;
        }

        for (auto e : graph.GetAdjacentEdgeRange(hop1))
        {
            // 2 hops away
            const NodeID hop2 = graph.GetTarget(e);
            // it is cheaper to evaluate a node twice than to do an expensive test here
            if (hop2 == v)
                continue;
            const float hop2_priority = priorities[hop2];
            BOOST_ASSERT(hop2_priority >= 0);

            if (hop2_priority < priority || (hop2_priority == priority && hop2 < v))
            {
                return false;
            }
        }
    }
    return true;
}

} // namespace