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/filtered_graph.hpp (5402B)

#ifndef OSRM_UTIL_FILTERED_GRAPH_HPP
#define OSRM_UTIL_FILTERED_GRAPH_HPP

#include "storage/shared_memory_ownership.hpp"

#include "util/dynamic_graph.hpp"
#include "util/filtered_integer_range.hpp"
#include "util/static_graph.hpp"
#include "util/vector_view.hpp"

namespace osrm::util
{
namespace detail
{
template <typename GraphT, storage::Ownership Ownership> class FilteredGraphImpl;

// For static graphs we can save the filters as a static vector since
// we don't modify the structure of the graph. This also makes it easy to
// swap out the filter.
template <typename EdgeDataT, storage::Ownership Ownership>
class FilteredGraphImpl<util::StaticGraph<EdgeDataT, Ownership>, Ownership>
{
    template <typename T> using Vector = util::ViewOrVector<T, Ownership>;

public:
    using Graph = util::StaticGraph<EdgeDataT, Ownership>;
    using EdgeIterator = typename Graph::EdgeIterator;
    using NodeIterator = typename Graph::NodeIterator;
    using NodeArrayEntry = typename Graph::NodeArrayEntry;
    using EdgeArrayEntry = typename Graph::EdgeArrayEntry;
    using EdgeRange = util::filtered_range<EdgeIterator, Vector<bool>>;

unsigned GetNumberOfNodes() const { return graph.GetNumberOfNodes(); }

unsigned GetNumberOfEdges() const { return graph.GetNumberOfEdges(); }

unsigned GetOutDegree(const NodeIterator n) const
    {
        auto range = graph.GetAdjacentEdgeRange(n);
        return std::count_if(range.begin(), range.end(), [this](const EdgeIterator edge) {
            return edge_filter[edge];
        });
    }

inline NodeIterator GetTarget(const EdgeIterator e) const
    {
        BOOST_ASSERT(edge_filter[e]);
        return graph.GetTarget(e);
    }

auto &GetEdgeData(const EdgeIterator e)
    {
        BOOST_ASSERT(edge_filter[e]);
        return graph.GetEdgeData(e);
    }

const auto &GetEdgeData(const EdgeIterator e) const
    {
        BOOST_ASSERT(edge_filter[e]);
        return graph.GetEdgeData(e);
    }

auto GetAdjacentEdgeRange(const NodeIterator n) const
    {
        return EdgeRange{graph.BeginEdges(n), graph.EndEdges(n), edge_filter};
    }

// searches for a specific edge
    EdgeIterator FindEdge(const NodeIterator from, const NodeIterator to) const
    {
        for (const auto edge : GetAdjacentEdgeRange(from))
        {
            if (to == GetTarget(edge))
            {
                return edge;
            }
        }
        return SPECIAL_EDGEID;
    }

template <typename FilterFunction>
    EdgeIterator
    FindSmallestEdge(const NodeIterator from, const NodeIterator to, FilterFunction &&filter) const
    {
        static_assert(traits::HasDataMember<typename Graph::EdgeArrayEntry>::value,
                      "Filtering on .data not possible without .data member attribute");

EdgeIterator smallest_edge = SPECIAL_EDGEID;
        EdgeWeight smallest_weight = INVALID_EDGE_WEIGHT;
        for (auto edge : GetAdjacentEdgeRange(from))
        {
            const NodeID target = GetTarget(edge);
            const auto &data = GetEdgeData(edge);
            if (target == to && data.weight < smallest_weight &&
                std::forward<FilterFunction>(filter)(data))
            {
                smallest_edge = edge;
                smallest_weight = data.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;
    }

FilteredGraphImpl() = default;

FilteredGraphImpl(Graph graph_, Vector<bool> edge_filter_)
        : graph(std::move(graph_)), edge_filter(std::move(edge_filter_))
    {
        BOOST_ASSERT(edge_filter.empty() || edge_filter.size() == graph.GetNumberOfEdges());
    }

// Takes a graph and a function that maps EdgeID to true
    // if the edge should be included in the graph.
    template <typename Pred>
    FilteredGraphImpl(Graph graph, Pred filter)
        : graph(std::move(graph)), edge_filter(graph.GetNumberOfEdges())
    {
        auto edge_ids = util::irange<EdgeID>(0, graph.GetNumberOfEdges());
        std::transform(edge_ids.begin(), edge_ids.end(), edge_filter.begin(), filter);
    }

void Renumber(const std::vector<NodeID> &old_to_new_node)
    {
        graph.Renumber(old_to_new_node);
        // FIXME the edge filter needs to be renumbered with a different permutation
        // util::inplacePermutation(edge_filter.begin(), edge_filter.end(), old_to_new_node);
    }

private:
    Graph graph;
    Vector<bool> edge_filter;
};
} // namespace detail

template <typename GraphT>
using FilteredGraphContainer = detail::FilteredGraphImpl<GraphT, storage::Ownership::Container>;
template <typename GraphT>
using FilteredGraphView = detail::FilteredGraphImpl<GraphT, storage::Ownership::View>;
} // namespace osrm::util

#endif

cmd: