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/graph_utils.hpp (3141B)

#ifndef GRAPH_UTILS_HPP
#define GRAPH_UTILS_HPP

#include "util/typedefs.hpp"

#include <boost/assert.hpp>
#include <vector>

namespace osrm::util
{

/// This function checks if the graph (consisting of directed edges) is undirected
template <typename GraphT> bool isUndirectedGraph(const GraphT &graph)
{
    for (auto source = 0u; source < graph.GetNumberOfNodes(); ++source)
    {
        for (auto edge = graph.BeginEdges(source); edge < graph.EndEdges(source); ++edge)
        {
            const auto &data = graph.GetEdgeData(edge);

auto target = graph.GetTarget(edge);
            BOOST_ASSERT(target != SPECIAL_NODEID);

bool found_reverse = false;
            for (auto rev_edge = graph.BeginEdges(target); rev_edge < graph.EndEdges(target);
                 ++rev_edge)
            {
                auto rev_target = graph.GetTarget(rev_edge);
                BOOST_ASSERT(rev_target != SPECIAL_NODEID);

if (rev_target != source)
                {
                    continue;
                }

BOOST_ASSERT_MSG(!found_reverse, "Found more than one reverse edge");
                found_reverse = true;
            }

if (!found_reverse)
            {
                return false;
            }
        }
    }

return true;
}

/// Since DynamicGraph assumes directed edges we have to make sure we transformed
/// the compressed edge format into single directed edges. We do this to make sure
/// every node also knows its incoming edges, not only its outgoing edges and use the reversed=true
/// flag to indicate which is which.
///
/// We do the transformation in the following way:
///
/// if the edge (a, b) is split:
///   1. this edge must be in only one direction, so its a --> b
///   2. there must be another directed edge b --> a somewhere in the data
/// if the edge (a, b) is not split:
///   1. this edge be on of a --> b od a <-> b
///      (a <-- b gets reducted to b --> a)
///   2. a --> b will be transformed to a --> b and b <-- a
///   3. a <-> b will be transformed to a --> b and b --> a
template <typename OutputEdgeT, typename InputEdgeT, typename FunctorT>
std::vector<OutputEdgeT> directedEdgesFromCompressed(const std::vector<InputEdgeT> &input_edge_list,
                                                     FunctorT copy_data)
{
    std::vector<OutputEdgeT> output_edge_list;

OutputEdgeT edge;
    for (const auto &input_edge : input_edge_list)
    {
        // edges that are not forward get converted by flipping the end points
        BOOST_ASSERT(input_edge.flags.forward);

edge.source = input_edge.source;
        edge.target = input_edge.target;
        edge.data.reversed = false;

BOOST_ASSERT(edge.source != edge.target);

copy_data(edge, input_edge);

output_edge_list.push_back(edge);

if (!input_edge.flags.is_split)
        {
            std::swap(edge.source, edge.target);
            edge.data.reversed = !input_edge.flags.backward;
            output_edge_list.push_back(edge);
        }
    }

return output_edge_list;
}
} // namespace osrm::util

#endif

cmd: