FM / util

/srv/osrm/osrm-backend/include/util

Name	Size	Mode	Actions
guidance/	-	0755	rm
alias.hpp	6870	0644	edit dl rm
assert.hpp	1964	0644	edit dl rm
attributes.hpp	357	0644	edit dl rm
bearing.hpp	3964	0644	edit dl rm
bit_range.hpp	2950	0644	edit dl rm
cheap_ruler.hpp	2124	0644	edit dl rm
concurrent_id_map.hpp	2148	0644	edit dl rm
conditional_restrictions.hpp	627	0644	edit dl rm
connectivity_checksum.hpp	1931	0644	edit dl rm
coordinate.hpp	9244	0644	edit dl rm
coordinate_calculation.hpp	16297	0644	edit dl rm
deallocating_vector.hpp	11205	0644	edit dl rm
debug.hpp	5958	0644	edit dl rm
dist_table_wrapper.hpp	2299	0644	edit dl rm
dynamic_graph.hpp	15951	0644	edit dl rm
exception.hpp	5126	0644	edit dl rm
exception_utils.hpp	609	0644	edit dl rm
exclude_flag.hpp	975	0644	edit dl rm
filtered_graph.hpp	5402	0644	edit dl rm
filtered_integer_range.hpp	3097	0644	edit dl rm
fingerprint.hpp	1166	0644	edit dl rm
for_each_indexed.hpp	634	0644	edit dl rm
for_each_pair.hpp	990	0644	edit dl rm
for_each_range.hpp	477	0644	edit dl rm
geojson_debug_logger.hpp	6330	0644	edit dl rm
geojson_debug_policies.hpp	1810	0644	edit dl rm
geojson_debug_policy_toolkit.hpp	3258	0644	edit dl rm
geojson_validation.hpp	2899	0644	edit dl rm
graph_traits.hpp	1245	0644	edit dl rm
graph_utils.hpp	3141	0644	edit dl rm
group_by.hpp	722	0644	edit dl rm
hilbert_value.hpp	3010	0644	edit dl rm
indexed_data.hpp	15039	0644	edit dl rm
integer_range.hpp	3286	0644	edit dl rm
isatty.hpp	610	0644	edit dl rm
json_container.hpp	3181	0644	edit dl rm
json_deep_compare.hpp	4732	0644	edit dl rm
json_renderer.hpp	4160	0644	edit dl rm
json_util.hpp	544	0644	edit dl rm
log.hpp	2187	0644	edit dl rm
lua_util.hpp	891	0644	edit dl rm
matrix_graph_wrapper.hpp	1294	0644	edit dl rm
meminfo.hpp	660	0644	edit dl rm
mmap_file.hpp	2776	0644	edit dl rm
mmap_tar.hpp	1007	0644	edit dl rm
msb.hpp	1178	0644	edit dl rm
node_based_graph.hpp	3530	0644	edit dl rm
opening_hours.hpp	8338	0644	edit dl rm
packed_vector.hpp	21691	0644	edit dl rm
percent.hpp	2106	0644	edit dl rm
permutation.hpp	1991	0644	edit dl rm
query_heap.hpp	10205	0644	edit dl rm
range_table.hpp	7119	0644	edit dl rm
rectangle.hpp	5900	0644	edit dl rm
serialization.hpp	5902	0644	edit dl rm
static_assert.hpp	640	0644	edit dl rm
static_graph.hpp	10702	0644	edit dl rm
static_rtree.hpp	34147	0644	edit dl rm
std_hash.hpp	1035	0644	edit dl rm
string_util.hpp	3400	0644	edit dl rm
tarjan_scc.hpp	6646	0644	edit dl rm
timed_histogram.hpp	2576	0644	edit dl rm
timezones.hpp	1417	0644	edit dl rm
timing_util.hpp	1485	0644	edit dl rm
to_osm_link.hpp	694	0644	edit dl rm
trigonometry_table.hpp	35906	0644	edit dl rm
typedefs.hpp	7627	0644	edit dl rm
vector_tile.hpp	303	0644	edit dl rm
vector_view.hpp	8000	0644	edit dl rm
version.hpp.in	406	0644	edit dl rm
viewport.hpp	1579	0644	edit dl rm
web_mercator.hpp	6480	0644	edit dl rm
xor_fast_hash.hpp	1797	0644	edit dl rm
xor_fast_hash_storage.hpp	2195	0644	edit dl rm

Edit: /srv/osrm/osrm-backend/include/util/dynamic_graph.hpp (15951B)

#ifndef DYNAMICGRAPH_HPP
#define DYNAMICGRAPH_HPP

#include "util/deallocating_vector.hpp"
#include "util/exception.hpp"
#include "util/exception_utils.hpp"
#include "util/integer_range.hpp"
#include "util/permutation.hpp"
#include "util/typedefs.hpp"

#include <boost/assert.hpp>

#include <cstdint>

#include <algorithm>
#include <atomic>
#include <limits>
#include <tuple>
#include <vector>

namespace osrm::util
{
namespace detail
{
// These types need to live outside of DynamicGraph
// to be not dependable. We need this for transforming graphs
// with different data.

template <typename EdgeIterator> struct DynamicNode
{
    // index of the first edge
    EdgeIterator first_edge;
    // amount of edges
    unsigned edges;
};

template <typename NodeIterator, typename EdgeDataT> struct DynamicEdge
{
    NodeIterator target;
    EdgeDataT data;
};
} // namespace detail

template <typename EdgeDataT> class DynamicGraph
{
  public:
    using EdgeData = EdgeDataT;
    using NodeIterator = std::uint32_t;
    using EdgeIterator = std::uint32_t;
    using EdgeRange = range<EdgeIterator>;

using Node = detail::DynamicNode<EdgeIterator>;
    using Edge = detail::DynamicEdge<NodeIterator, EdgeDataT>;

template <typename E> friend class DynamicGraph;

class InputEdge
    {
      public:
        NodeIterator source;
        NodeIterator target;
        EdgeDataT data;

InputEdge()
            : source(std::numeric_limits<NodeIterator>::max()),
              target(std::numeric_limits<NodeIterator>::max())
        {
        }

template <typename... Ts>
        InputEdge(NodeIterator source, NodeIterator target, Ts &&... data)
            : source(source), target(target), data(std::forward<Ts>(data)...)
        {
        }

bool operator<(const InputEdge &rhs) const
        {
            return std::tie(source, target) < std::tie(rhs.source, rhs.target);
        }
    };

DynamicGraph() : DynamicGraph(0) {}

// Constructs an empty graph with a given number of nodes.
    explicit DynamicGraph(NodeIterator nodes) : number_of_nodes(nodes), number_of_edges(0)
    {
        node_array.reserve(number_of_nodes);
        node_array.resize(number_of_nodes);

edge_list.reserve(number_of_nodes * 1.1);
        edge_list.resize(number_of_nodes);
    }

/**
     * Constructs a DynamicGraph from a list of edges sorted by source node id.
     */
    template <class ContainerT> DynamicGraph(const NodeIterator nodes, const ContainerT &graph)
    {
        // we need to cast here because DeallocatingVector does not have a valid const iterator
        BOOST_ASSERT(std::is_sorted(const_cast<ContainerT &>(graph).begin(),
                                    const_cast<ContainerT &>(graph).end()));

number_of_nodes = nodes;
        number_of_edges = static_cast<EdgeIterator>(graph.size());
        node_array.resize(number_of_nodes);
        EdgeIterator edge = 0;
        EdgeIterator position = 0;
        for (const auto node : irange(0u, number_of_nodes))
        {
            EdgeIterator last_edge = edge;
            while (edge < number_of_edges && graph[edge].source == node)
            {
                ++edge;
            }
            node_array[node].first_edge = position;
            node_array[node].edges = edge - last_edge;
            position += node_array[node].edges;
        }
        edge_list.reserve(static_cast<std::size_t>(edge_list.size() * 1.1));
        edge_list.resize(position);
        edge = 0;
        for (const auto node : irange(0u, number_of_nodes))
        {
            for (const auto i : irange(node_array[node].first_edge,
                                       node_array[node].first_edge + node_array[node].edges))
            {
                edge_list[i].target = graph[edge].target;
                BOOST_ASSERT(edge_list[i].target < number_of_nodes);
                edge_list[i].data = graph[edge].data;
                ++edge;
            }
        }

BOOST_ASSERT(node_array.size() == number_of_nodes);
    }

// Copy&move for the same data
    //

DynamicGraph(const DynamicGraph &other)
    {
        number_of_nodes = other.number_of_nodes;
        // atomics can't be moved this is why we need an own constructor
        number_of_edges = static_cast<std::uint32_t>(other.number_of_edges);

node_array = other.node_array;
        edge_list = other.edge_list;
    }

DynamicGraph &operator=(const DynamicGraph &other)
    {
        auto copy_other = other;
        *this = std::move(other);
        return *this;
    }

DynamicGraph(DynamicGraph &&other)
    {
        number_of_nodes = other.number_of_nodes;
        // atomics can't be moved this is why we need an own constructor
        number_of_edges = static_cast<std::uint32_t>(other.number_of_edges);

node_array = std::move(other.node_array);
        edge_list = std::move(other.edge_list);
    }

DynamicGraph &operator=(DynamicGraph &&other)
    {
        number_of_nodes = other.number_of_nodes;
        // atomics can't be moved this is why we need an own constructor
        number_of_edges = static_cast<std::uint32_t>(other.number_of_edges);

node_array = std::move(other.node_array);
        edge_list = std::move(other.edge_list);

return *this;
    }

// Removes all edges to and from nodes for which filter(node_id) returns false
    template <typename Pred> auto Filter(Pred filter) const &
    {
        BOOST_ASSERT(node_array.size() == number_of_nodes);

DynamicGraph other;

other.number_of_nodes = number_of_nodes;
        other.number_of_edges = static_cast<std::uint32_t>(number_of_edges);
        other.edge_list.reserve(edge_list.size());
        other.node_array.resize(node_array.size());

NodeID node_id = 0;
        std::transform(
            node_array.begin(), node_array.end(), other.node_array.begin(), [&](const Node &node) {
                const EdgeIterator first_edge = other.edge_list.size();

BOOST_ASSERT(node_id < number_of_nodes);
                if (filter(node_id++))
                {
                    std::copy_if(edge_list.begin() + node.first_edge,
                                 edge_list.begin() + node.first_edge + node.edges,
                                 std::back_inserter(other.edge_list),
                                 [&](const auto &edge) { return filter(edge.target); });
                    const unsigned num_edges = other.edge_list.size() - first_edge;
                    return Node{first_edge, num_edges};
                }
                else
                {
                    return Node{first_edge, 0};
                }
            });

return other;
    }

unsigned GetNumberOfNodes() const { return number_of_nodes; }

unsigned GetNumberOfEdges() const { return number_of_edges; }
    auto GetEdgeCapacity() const { return edge_list.size(); }

unsigned GetOutDegree(const NodeIterator n) const { return node_array[n].edges; }

unsigned GetDirectedOutDegree(const NodeIterator n) const
    {
        unsigned degree = 0;
        for (const auto edge : irange(BeginEdges(n), EndEdges(n)))
        {
            if (!GetEdgeData(edge).reversed)
            {
                ++degree;
            }
        }
        return degree;
    }

NodeIterator GetTarget(const EdgeIterator e) const { return NodeIterator(edge_list[e].target); }

void SetTarget(const EdgeIterator e, const NodeIterator n) { edge_list[e].target = n; }

EdgeDataT &GetEdgeData(const EdgeIterator e) { return edge_list[e].data; }

const EdgeDataT &GetEdgeData(const EdgeIterator e) const { return edge_list[e].data; }

EdgeIterator BeginEdges(const NodeIterator n) const
    {
        return EdgeIterator(node_array[n].first_edge);
    }

EdgeIterator EndEdges(const NodeIterator n) const
    {
        return EdgeIterator(node_array[n].first_edge + node_array[n].edges);
    }

EdgeRange GetAdjacentEdgeRange(const NodeIterator node) const
    {
        return irange(BeginEdges(node), EndEdges(node));
    }

NodeIterator InsertNode()
    {
        node_array.emplace_back(node_array.back());
        number_of_nodes += 1;

return number_of_nodes;
    }

// adds an edge. Invalidates edge iterators for the source node
    EdgeIterator InsertEdge(const NodeIterator from, const NodeIterator to, const EdgeDataT &data)
    {
        Node &node = node_array[from];
        EdgeIterator one_beyond_last_of_node = node.edges + node.first_edge;
        // if we can't write at the end of this nodes edges
        // that is: the end is the end of the edge_list,
        //          or the beginning of the next nodes edges
        if (one_beyond_last_of_node == edge_list.size() || !isDummy(one_beyond_last_of_node))
        {
            // can we write before this nodes edges?
            if (node.first_edge != 0 && isDummy(node.first_edge - 1))
            {
                node.first_edge--;
                edge_list[node.first_edge] = edge_list[node.first_edge + node.edges];
            }
            else
            {
                // we have to move this nodes edges to the end of the edge_list
                EdgeIterator newFirstEdge = (EdgeIterator)edge_list.size();
                unsigned newSize = node.edges * 1.1 + 2;
                EdgeIterator requiredCapacity = newSize + edge_list.size();
                EdgeIterator oldCapacity = edge_list.capacity();
                // make sure there is enough space at the end
                if (requiredCapacity >= oldCapacity)
                {
                    edge_list.reserve(requiredCapacity * 1.1);
                }
                edge_list.resize(edge_list.size() + newSize);
                // move the edges over and invalidate the old ones
                for (const auto i : irange(0u, node.edges))
                {
                    edge_list[newFirstEdge + i] = edge_list[node.first_edge + i];
                    makeDummy(node.first_edge + i);
                }
                // invalidate until the end of edge_list
                for (const auto i : irange(node.edges + 1, newSize))
                {
                    makeDummy(newFirstEdge + i);
                }
                node.first_edge = newFirstEdge;
            }
        }
        // get the position for the edge that is to be inserted
        // and write it
        Edge &edge = edge_list[node.first_edge + node.edges];
        edge.target = to;
        edge.data = data;
        ++number_of_edges;
        ++node.edges;
        return EdgeIterator(node.first_edge + node.edges);
    }

// removes an edge. Invalidates edge iterators for the source node
    void DeleteEdge(const NodeIterator source, const EdgeIterator e)
    {
        Node &node = node_array[source];
        --number_of_edges;
        --node.edges;
        BOOST_ASSERT(std::numeric_limits<unsigned>::max() != node.edges);
        const unsigned last = node.first_edge + node.edges;
        BOOST_ASSERT(std::numeric_limits<unsigned>::max() != last);
        // swap with last edge
        edge_list[e] = edge_list[last];
        makeDummy(last);
    }

// removes all edges (source,target)
    int32_t DeleteEdgesTo(const NodeIterator source, const NodeIterator target)
    {
        int32_t deleted = 0;
        for (EdgeIterator i = BeginEdges(source), iend = EndEdges(source); i < iend - deleted; ++i)
        {
            if (edge_list[i].target == target)
            {
                do
                {
                    deleted++;
                    edge_list[i] = edge_list[iend - deleted];
                    makeDummy(iend - deleted);
                } while (i < iend - deleted && edge_list[i].target == target);
            }
        }

number_of_edges -= deleted;
        node_array[source].edges -= deleted;

return deleted;
    }

// searches for a specific edge
    EdgeIterator FindEdge(const NodeIterator from, const NodeIterator to) const
    {
        for (const auto i : irange(BeginEdges(from), EndEdges(from)))
        {
            if (to == edge_list[i].target)
            {
                return i;
            }
        }
        return SPECIAL_EDGEID;
    }

// searches for a specific edge
    EdgeIterator FindSmallestEdge(const NodeIterator from, const NodeIterator to) const
    {
        EdgeIterator smallest_edge = SPECIAL_EDGEID;
        EdgeWeight smallest_weight = INVALID_EDGE_WEIGHT;
        for (auto edge : GetAdjacentEdgeRange(from))
        {
            const NodeID target = GetTarget(edge);
            const EdgeWeight weight = GetEdgeData(edge).distance;
            if (target == to && weight < smallest_weight)
            {
                smallest_edge = edge;
                smallest_weight = weight;
            }
        }
        return smallest_edge;
    }

EdgeIterator FindEdgeInEitherDirection(const NodeIterator from, const NodeIterator to) const
    {
        EdgeIterator tmp = FindEdge(from, to);
        return (SPECIAL_NODEID != tmp ? tmp : FindEdge(to, from));
    }

EdgeIterator
    FindEdgeIndicateIfReverse(const NodeIterator from, const NodeIterator to, bool &result) const
    {
        EdgeIterator current_iterator = FindEdge(from, to);
        if (SPECIAL_NODEID == current_iterator)
        {
            current_iterator = FindEdge(to, from);
            if (SPECIAL_NODEID != current_iterator)
            {
                result = true;
            }
        }
        return current_iterator;
    }

void Renumber(const std::vector<NodeID> &old_to_new_node)
    {
        // permutate everything but the sentinel
        util::inplacePermutation(node_array.begin(), node_array.end(), old_to_new_node);

// Build up edge permutation
        if (edge_list.size() >= std::numeric_limits<EdgeID>::max())
        {
            throw util::exception("There are too many edges, OSRM only supports 2^32" + SOURCE_REF);
        }

EdgeID new_edge_index = 0;
        std::vector<EdgeID> old_to_new_edge(edge_list.size(), SPECIAL_EDGEID);
        for (auto node : util::irange<NodeID>(0, number_of_nodes))
        {
            auto new_first_edge = new_edge_index;
            // move all filled edges
            for (auto edge : GetAdjacentEdgeRange(node))
            {
                edge_list[edge].target = old_to_new_node[edge_list[edge].target];
                BOOST_ASSERT(edge_list[edge].target != SPECIAL_NODEID);
                old_to_new_edge[edge] = new_edge_index++;
            }
            node_array[node].first_edge = new_first_edge;
        }
        auto number_of_valid_edges = new_edge_index;

// move all dummy edges to the end of the renumbered range
        for (auto edge : util::irange<NodeID>(0, edge_list.size()))
        {
            if (old_to_new_edge[edge] == SPECIAL_EDGEID)
            {
                BOOST_ASSERT(isDummy(edge));
                old_to_new_edge[edge] = new_edge_index++;
            }
        }
        BOOST_ASSERT(std::find(old_to_new_edge.begin(), old_to_new_edge.end(), SPECIAL_EDGEID) ==
                     old_to_new_edge.end());
        util::inplacePermutation(edge_list.begin(), edge_list.end(), old_to_new_edge);
        // Remove useless dummy nodes at the end
        edge_list.resize(number_of_valid_edges);
        number_of_edges = number_of_valid_edges;
    }

protected:
    bool isDummy(const EdgeIterator edge) const
    {
        return edge_list[edge].target == (std::numeric_limits<NodeIterator>::max)();
    }

void makeDummy(const EdgeIterator edge)
    {
        edge_list[edge].target = (std::numeric_limits<NodeIterator>::max)();
    }

NodeIterator number_of_nodes;
    std::atomic_uint number_of_edges;

std::vector<Node> node_array;
    DeallocatingVector<Edge> edge_list;
};
} // namespace osrm::util

#endif // DYNAMICGRAPH_HPP

cmd: