Distance Functions

Distance functions compute (an approximation for) the distance between two coordinates.

Header: fiction/algorithms/path_finding/distance.hpp

template<typename Lyt, typename Dist = uint64_t>
constexpr Dist fiction::manhattan_distance([[maybe_unused]] const Lyt &lyt, const coordinate<Lyt> &source, const coordinate<Lyt> &target) noexcept

The Manhattan distance \(D\) between two layout coordinates \((x_1, y_1)\) and \((x_2, y_2)\) given by

\(D = |x_1 - x_2| + |y_1 - y_2|\)

Template Parameters:

  • Lyt – Coordinate layout type.

  • Dist – Integral type for the distance.

Parameters:

  • lyt – Layout.

  • source – Source coordinate.

  • target – Target coordinate.

Returns:

Manhattan distance between source and target.

template<typename Lyt, typename Dist = double>
constexpr Dist fiction::euclidean_distance([[maybe_unused]] const Lyt &lyt, const coordinate<Lyt> &source, const coordinate<Lyt> &target) noexcept

The Euclidean distance \(D\) between two layout coordinates \((x_1, y_1)\) and \((x_2, y_2)\) given by

\(D = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}\)

Template Parameters:

  • Lyt – Coordinate layout type.

  • Dist – Floating-point type for the distance.

Parameters:

  • lyt – Layout.

  • source – Source coordinate.

  • target – Target coordinate.

Returns:

Euclidean distance between source and target.

template<typename Lyt, typename Dist = uint64_t>
constexpr Dist fiction::twoddwave_distance([[maybe_unused]] const Lyt &lyt, const coordinate<Lyt> &source, const coordinate<Lyt> &target) noexcept

The 2DDWave distance \(D\) between two layout coordinates \(s = (x_1, y_1)\) and \(t = (x_2, y_2)\) given by

\(D = |x_1 - x_2| + |y_1 - y_2|\) iff \(s \leq t\) and \(\infty\), otherwise.

Thereby, \(s \leq t\) iff \(x_1 \leq x_2\) and \(y_1 \leq y_2\).

Note

To represent \(\infty\), std::numeric_limits<uint32_t>::max() is returned for distances of infinite length. We are using uint32_t to prevent overflows when adding distances in the default uint64_t number range.

Template Parameters:

  • Lyt – Coordinate layout type.

  • Dist – Integral type for the distance.

Parameters:

  • lyt – Layout.

  • source – Source coordinate.

  • target – Target coordinate.

Returns:

2DDWave distance between source and target.

template<typename Lyt, typename Dist>
class distance_functor

A functor that computes distances between coordinates and can be passed as an object to, e.g., path finding algorithms with a standardized signature. This class is intended to be instantiated with concrete distance functions passed to the constructor.

Template Parameters:

  • Lyt – Coordinate layout type.

  • Dist – Distance value type.

Subclassed by fiction::distance_map_functor< Lyt, Dist >, fiction::smart_distance_cache_functor< Lyt, Dist >, fiction::sparse_distance_map_functor< Lyt, Dist >

Public Functions

inline explicit distance_functor(const std::function<Dist(const Lyt&, const coordinate<Lyt>&, const coordinate<Lyt>&)> &dist_fn)

Standard constructor that instantiates the distance function.

Parameters:

dist_fn – A function that maps from layout coordinates to a distance value.

virtual ~distance_functor() = default

Destructor.

inline virtual Dist operator()(const Lyt &lyt, const coordinate<Lyt> &source, const coordinate<Lyt> &target) const

Operator to call the distance function.

Parameters:

  • lyt – Layout.

  • source – Source coordinate.

  • target – Target coordinate.

Returns:

Distance between source and target.

template<typename Lyt, typename Dist = uint64_t>
class manhattan_distance_functor : public fiction::distance_functor<Lyt, uint64_t>

A pre-defined distance functor that uses the Manhattan distance.

Template Parameters:

  • Lyt – Coordinate layout type.

  • Dist – Integral distance type.

template<typename Lyt, typename Dist = double>
class euclidean_distance_functor : public fiction::distance_functor<Lyt, double>

A pre-defined distance functor that uses the Euclidean distance.

Template Parameters:

  • Lyt – Coordinate layout type.

  • Dist – Floating-point distance type.

template<typename Lyt, typename Dist = uint64_t>
class twoddwave_distance_functor : public fiction::distance_functor<Lyt, uint64_t>

A pre-defined distance functor that uses the 2DDWave distance.

Template Parameters:

  • Lyt – Coordinate layout type.

  • Dist – Integral distance type.

Distance Maps

Distance maps can store the distance from a coordinate to all other coordinates. They are particularly useful when repeatedly calling complex distance functions that are expensive to evaluate. The distance maps can serve as a lookup-table for these cases.

Header: fiction/algorithms/path_finding/distance_map.hpp

template<typename Dist>
using fiction::distance_map = std::vector<std::vector<Dist>>

A distance map is a two-dimensional array of distances between coordinates. The distance map is accessed via the indices of the coordinates in the associated layout. A coordinate index \(i\) is calculated as follows: \(i = y \cdot W + x\), with \(W\) being the width of the layout. As an example, in a layout of size \(3 \times 3\), the coordinate index of the coordinate \((2, 1)\) has index \(1 \cdot 3 + 2 = 5\).

The distance_map is to be preferred over the sparse_distance_map in most cases when performance is the main goal.

template<typename Lyt, typename Dist>
using fiction::sparse_distance_map = phmap::parallel_flat_hash_map<std::pair<coordinate<Lyt>, coordinate<Lyt>>, Dist>

A sparse distance map is a flat hash map of distances between coordinates. The sparse distance map is accessed via coordinate pairs. The sparse distance map is to be preferred over the distance map if only a small subset of the distances between coordinates is to be stored.

The distance_map is to be preferred over the sparse_distance_map in most cases when performance is the main goal.

template<typename Lyt, typename Dist>
distance_map<Dist> fiction::initialize_distance_map(const Lyt &lyt, const distance_functor<Lyt, Dist> &dist_fn) noexcept

This function fully initializes a distance_map for a given layout and distance functor. It computes the distances between all pairs of coordinates in the layout and stores them in the distance map for quick subsequent access.

This function performs \(\mathcal{O}(|L|^2)\) distance computations, where \(|L|\) is the number of coordinates in the layout.

Template Parameters:

  • Lyt – Coordinate layout type.

  • Dist – Distance type.

Parameters:

  • lyt – Layout to compute distances for.

  • dist_fn – Distance functor to apply to all pairs of coordinates in lyt.

Returns:

Fully initialized distance_map for lyt.

template<typename Lyt, typename Dist>
sparse_distance_map<Lyt, Dist> fiction::initialize_sparse_distance_map(const Lyt &lyt, const distance_functor<Lyt, Dist> &dist_fn) noexcept

This function fully initializes a sparse_distance_map for a given layout and distance functor. It computes the distances between all pairs of coordinates in the layout and stores them in the distance map for quick subsequent access.

This function performs \(\mathcal{O}(|L|^2)\) distance computations, where \(|L|\) is the number of coordinates in the layout.

Template Parameters:

  • Lyt – Coordinate layout type.

  • Dist – Distance type.

Parameters:

  • lyt – Layout to compute distances for.

  • dist_fn – Distance functor to apply to all pairs of coordinates in lyt.

Returns:

Fully initialized sparse_distance_map for lyt.

template<typename Lyt, typename Dist>
class distance_map_functor : public fiction::distance_functor<Lyt, Dist>

A distance functor that uses a fully precomputed distance_map to determine distances between coordinates. It can be used as a drop-in replacement for any other distance functor in path-finding algorithms.

Template Parameters:

  • Lyt – Coordinate layout type.

  • Dist – Distance type.

Public Functions

inline explicit distance_map_functor(const distance_map<Dist> &dm)

Construct the distance functor from a distance_map.

Parameters:

dm – Distance map.

inline virtual Dist operator()(const Lyt &lyt, const coordinate<Lyt> &source, const coordinate<Lyt> &target) const override

Override the call operator to query the distance map instead of the distance function.

Note

This function will throw an exception if the queried distance is not stored in the distance map.

Parameters:

  • lyt – Layout.

  • source – Source coordinate.

  • target – Target coordinate.

Returns:

Distance between source and target according to the stored distance map.

template<typename Lyt, typename Dist>
class sparse_distance_map_functor : public fiction::distance_functor<Lyt, Dist>

A distance functor that uses a fully precomputed sparse_distance_map to determine distances between coordinates. It can be used as a drop-in replacement for any other distance functor in path-finding algorithms.

Template Parameters:

  • Lyt – Coordinate layout type.

  • Dist – Distance type.

Public Functions

inline explicit sparse_distance_map_functor(const sparse_distance_map<Lyt, Dist> &sdm)

Construct the distance functor from a sparse distance map.

Parameters:

sdm – Sparse distance map.

inline virtual Dist operator()(const Lyt&, const coordinate<Lyt> &source, const coordinate<Lyt> &target) const override

Override the call operator to query the sparse distance map instead of the distance function.

Note

This function will throw an exception if the queried distance is not stored in the sparse distance map.

Parameters:

  • lyt – Layout.

  • source – Source coordinate.

  • target – Target coordinate.

Returns:

Distance between source and target according to the stored sparse distance map.

template<typename Lyt, typename Dist>
class smart_distance_cache_functor : public fiction::distance_functor<Lyt, Dist>

A distance functor that internally uses a sparse_distance_map as a cache to prevent re-computing distances that have already been evaluated. In contrast to distance_map_functor and sparse_distance_map_functor, this functor does not require a pre-computed distance map upon construction, but instead will gradually build up its own cache when queried multiple times. It can be used as a drop-in replacement for any other distance functor in path-finding algorithms.

Template Parameters:

  • Lyt – Coordinate layout type.

  • Dist – Distance type.

Public Functions

inline explicit smart_distance_cache_functor(const Lyt &lyt, const std::function<Dist(const Lyt&, const coordinate<Lyt>&, const coordinate<Lyt>&)> &dist_fn)

Construct a distance functor from a layout and a distance function.

The internal cache will be initialized empty. Distances will be computed on the fly and stored in the cache whenever they are queried.

Parameters:

  • lyt – Layout.

  • dist_fn – Distance function.

inline virtual Dist operator()(const Lyt &lyt, const coordinate<Lyt> &source, const coordinate<Lyt> &target) const override

Override the call operator to first query the cache instead of the distance function. Only on a cache miss, the distance function will be called and the result will be stored in the cache.

Parameters:

  • lyt – Layout.

  • source – Source coordinate.

  • target – Target coordinate.

Returns:

Distance between source and target according to the cache or the distance function.

Cost Functions

Cost functions compute the cost to move from one coordinate to another (adjacent) one.

Header: fiction/algorithms/path_finding/cost.hpp

template<typename Lyt, typename Cost = uint8_t>
constexpr Cost fiction::unit_cost([[maybe_unused]] const coordinate<Lyt> &source, [[maybe_unused]] const coordinate<Lyt> &target) noexcept

Unit cost between two layout coordinates that always returns 1.

Template Parameters:

  • Lyt – Coordinate layout type.

  • Cost – Integral type for the cost.

Parameters:

  • source – Source coordinate.

  • target – Target coordinate.

Returns:

Unit cost between source and target, i.e., 1.

template<typename Lyt, typename Cost = double>
Cost fiction::random_cost([[maybe_unused]] const coordinate<Lyt> &source, [[maybe_unused]] const coordinate<Lyt> &target) noexcept

Random cost between two layout coordinates that returns a random value between 0 and 1.

Template Parameters:

  • Lyt – Coordinate layout type.

  • Cost – Floating-point type for the cost.

Parameters:

  • source – Source coordinate.

  • target – Target coordinate.

Returns:

Random cost between source and target, i.e., a random number between 0 and 1.

template<typename Lyt, typename Cost>
class cost_functor

A functor that computes costs between coordinates and can be passed as an object to, e.g., path finding algorithms with a standardized signature. This class is intended to be instantiated with concrete cost functions passed to the constructor.

Template Parameters:

  • Lyt – Coordinate layout type.

  • Cost – Cost value type.

Public Functions

inline explicit cost_functor(const std::function<Cost(const coordinate<Lyt>&, const coordinate<Lyt>&)> &cost_fn)

Standard constructor that instantiates the cost function.

Parameters:

cost_fn – A function that maps from layout coordinates to a cost value.

virtual ~cost_functor() = default

Destructor.

inline virtual Cost operator()(const coordinate<Lyt> &source, const coordinate<Lyt> &target) const

Operator to call the cost function.

Parameters:

  • source – Source coordinate.

  • target – Target coordinate.

Returns:

Cost between source and target.

template<typename Lyt, typename Cost = uint8_t>
class unit_cost_functor : public fiction::cost_functor<Lyt, uint8_t>

A pre-defined cost functor that uses unit costs.

Template Parameters:

  • Lyt – Coordinate layout type.

  • Cost – Integral cost type.

template<typename Lyt, typename Cost = double>
class random_cost_functor : public fiction::cost_functor<Lyt, double>

A pre-defined cost functor that uses random costs.

Template Parameters:

  • Lyt – Coordinate layout type.

  • Cost – Floating-point cost type.

A* Shortest Path

Header: fiction/algorithms/path_finding/a_star.hpp

struct a_star_params

Parameters for the A* algorithm.

Public Members

bool crossings = false

Allow paths to cross over obstructed tiles if they are occupied by wire segments.

template<typename Path, typename Lyt, typename Dist = uint64_t, typename Cost = uint8_t>
Path fiction::a_star(const Lyt &layout, const routing_objective<Lyt> &objective, const distance_functor<Lyt, Dist> &dist_fn = manhattan_distance_functor<Lyt, uint64_t>(), const cost_functor<Lyt, Cost> &cost_fn = unit_cost_functor<Lyt, uint8_t>(), const a_star_params &params = {}) noexcept

The A* path finding algorithm for shortest loop-less paths between a given source and target coordinate in a layout. This function automatically detects whether the given layout implements a clocking interface (see clocked_layout) and respects the underlying information flow imposed by layout’s clocking scheme.

A* is an extension of Dijkstra’s algorithm for shortest paths but offers better average complexity. It uses a heuristic distance function that estimates the remaining costs towards the target in every step. Thus, this heuristic function should neither be complex to calculate nor overestimating the remaining costs. Common heuristics to be used are the Manhattan and the Euclidean distance functions. See distance_functor for implementations.

If the given layout implements the obstruction interface (see obstruction_layout), paths will not be routed via obstructed coordinates and connections.

If the given layout is a gate-level layout and implements the obstruction interface (see obstruction_layout), paths may contain wire crossings if specified in the parameters. Wire crossings are only allowed over other wires and only if the crossing layer is not obstructed. Furthermore, it is ensured that crossings do not run along another wire but cross only in a single point (orthogonal crossings + knock-knees/double wires).

In certain cases it might be desirable to determine regular coordinate paths even if the layout implements a clocking interface. This can be achieved by static-casting the layout to a coordinate layout when calling this function: 

using clk_lyt = clocked_layout<cartesian_layout<>>;
using path = layout_coordinate_path<cartesian_layout<>>;
clk_lyt layout = ...;
auto shortest_path = a_star<path>(static_cast<cartesian_layout<>>(layout), {source, target});

A* was introduced in “A Formal Basis for the Heuristic Determination of Minimum Cost Paths” by Peter E. Hart, Nils J. Nilsson, and Bertram Raphael in IEEE Transactions on Systems Science and Cybernetics 1968, Volume 4, Issue 2.

This implementation is based on the pseudocode from https://en.wikipedia.org/wiki/A_star_search_algorithm.

Template Parameters:

  • Path – Type of the returned path.

  • Lyt – Type of the layout to perform path finding on.

  • Dist – Distance value type to be used in the heuristic estimation function.

  • Cost – Cost value type to be used when determining moving cost between coordinates.

Parameters:

  • layout – The layout in which the shortest path between a source and target coordinate is to be found.

  • objective – Source-target coordinate pair.

  • dist_fn – A distance functor that implements the desired heuristic estimation function.

  • cost_fn – A cost functor that implements the desired cost function.

  • params – Parameters.

Returns:

The shortest loop-less path in layout from objective.source to objective.target.

template<typename Lyt, typename Dist = uint64_t>
Dist fiction::a_star_distance(const Lyt &layout, const coordinate<Lyt> &source, const coordinate<Lyt> &target) noexcept

A distance function that does not approximate but compute the actual minimum path length on the given layout via A* traversal. Naturally, this function cannot be evaluated in \(\mathcal{O}(1)\), but has the polynomial complexity of A*.

If no path between source and target exists in layout, the returned distance is std::numeric_limits<Dist>::infinity() if that value is supported by Dist, or std::numeric_limits<Dist>::max(), otherwise.

Template Parameters:

  • Lyt – Coordinate layout type.

  • Dist – Distance type.

Parameters:

  • layout – The layout in which the distance between source and target is to be determined.

  • source – Source coordinate.

  • target – Target coordinate.

Returns:

Minimum path length between source and target in layout.

template<typename Lyt, typename Dist = uint64_t>
class a_star_distance_functor : public fiction::distance_functor<Lyt, uint64_t>

A pre-defined distance functor that uses the A* distance.

Template Parameters:

  • Lyt – Coordinate layout type.

  • Dist – Distance type.

Jump Point Search Shortest Path in a Cartesian Grid

Header: fiction/algorithms/path_finding/jump_point_search.hpp

template<typename Path, typename Lyt, typename Dist = uint64_t>
Path fiction::jump_point_search(const Lyt &layout, const routing_objective<Lyt> &objective, const distance_functor<Lyt, Dist> &dist_fn = manhattan_distance_functor<Lyt, Dist>()) noexcept

The Jump Point Search (JPS) path finding algorithm for shortest loop-less paths between a given source and target coordinate in a Cartesian layout. This function automatically detects whether the given layout implements a clocking interface (see clocked_layout) and respects the underlying information flow imposed by layout’s clocking scheme.

JPS was proposed as an optimization of A* for shortest paths and offers better average complexity on uniform-cost grids that allow diagonal connections. It uses a heuristic distance function that estimates the remaining costs towards the target in every step. Thus, this heuristic function should neither be complex to calculate nor overestimating the remaining costs. Common heuristics to be used are the Manhattan and the Euclidean distance functions. See distance_functor for implementations. Since JPS assumes a unit-cost grid, the use of cost functions together with JPS is not possible.

If the given layout implements the obstruction interface (see obstruction_layout), paths will not be routed via obstructed coordinates and connections.

In certain cases it might be desirable to determine regular coordinate paths even if the layout implements a clocking interface. This can be achieved by static-casting the layout to a coordinate layout when calling this function: 

using clk_lyt = clocked_layout<cartesian_layout<>>;
using path = layout_coordinate_path<cartesian_layout<>>;
clk_lyt layout = ...;
auto shortest_path = jump_point_search<path>(static_cast<cartesian_layout<>>(layout), {source, target});

JPS was introduced in “Online Graph Pruning for Pathfinding on Grid Maps” by Daniel Harabor and Alban Grastien in AAAI 2011.

Parts of this implementation are based on https://github.com/qiao/PathFinding.js.

Note

The original JPS highly relies on diagonal paths in the grid which are not possible in most Cartesian grid-based FCN technologies. Therefore, this implementation disallows diagonal paths. Consequently, and due to non-uniform clocking schemes, JPS might perform worse than A* in terms of runtime. It is recommended to use A* (see a_star).

Note

JPS does not support wire crossings.

Template Parameters:

  • Path – Type of the returned path.

  • Lyt – Type of the layout to perform path finding on.

  • Dist – Distance value type to be used in the heuristic estimation function.

Parameters:

  • layout – The layout in which the shortest path between a source and target is to be found.

  • objective – Source-target coordinate pair.

  • dist_fn – A distance functor that implements the desired heuristic estimation function.

Returns:

The shortest loop-less path in layout from objective.source to objective.target.

k Shortest Paths

Header: fiction/algorithms/path_finding/k_shortest_paths.hpp

struct yen_k_shortest_paths_params

Parameters for Yen’s \(k\)-shortest paths algorithm.

Public Members

a_star_params astar_params = {}

Parameters for the internal A* algorithm.

template<typename Path, typename Lyt>
path_collection<Path> fiction::yen_k_shortest_paths(const Lyt &layout, const routing_objective<Lyt> &objective, const uint32_t k, const yen_k_shortest_paths_params &params = {}) noexcept

Yen’s algorithm for finding up to \(k\) shortest paths without loops from a source to a target coordinate. If \(k\) is larger than the number of possible paths from source to target, the size of the returned path collection will be smaller than \(k\).

This implementation uses the A* algorithm with the Manhattan distance function internally.

This function automatically detects whether the given layout implements a clocking interface (see clocked_layout) and respects the underlying information flow imposed by layout’s clocking scheme. This algorithm does neither generate duplicate nor looping paths, even in a cyclic clocking scheme. That is, along each path, each coordinate can occur at maximum once.

If the given layout implements the obstruction interface (see obstruction_layout), paths will not be routed via obstructed coordinates or connections.

If the given layout is a gate-level layout and implements the obstruction interface (see obstruction_layout), paths may contain wire crossings if specified in the parameters. Wire crossings are only allowed over other wires and only if the crossing layer is not obstructed. Furthermore, it is ensured that crossings do not run along another wire but cross only in a single point (orthogonal crossings + knock-knees/double wires).

In certain cases it might be desirable to enumerate regular coordinate paths even if the layout implements a clocking interface. This can be achieved by static-casting the layout to a coordinate layout when calling this function: 

using clk_lyt = clocked_layout<cartesian_layout<>>;
using path = layout_coordinate_path<cartesian_layout<>>;
clk_lyt layout = ...;
auto k_paths = yen_k_shortest_paths<path>(static_cast<cartesian_layout<>>(layout), {source, target}, k);

The algorithm was originally described in “An algorithm for finding shortest routes from all source nodes to a given destination in general networks” by Jin Y. Yen in Quarterly of Applied Mathematics, 1970.

Template Parameters:

  • Path – Type of the returned individual paths.

  • Lyt – Type of the layout to perform path finding on.

Parameters:

  • layout – The layout in which the \(k\) shortest paths are to be found.

  • objective – Source-target coordinate pair.

  • k – Maximum number of shortest paths to find.

  • params – Parameters.

Returns:

A collection of up to \(k\) shortest loop-less paths in layout from objective.source to objective.target.

Enumerate All Paths

Header: fiction/algorithms/path_finding/enumerate_all_paths.hpp

struct enumerate_all_paths_params

Parameters for the algorithm that enumerates all paths in a layout.

Public Members

bool crossings = false

Allow paths to cross over obstructed tiles if they are occupied by wire segments.

template<typename Path, typename Lyt>
path_collection<Path> fiction::enumerate_all_paths(const Lyt &layout, const routing_objective<Lyt> &objective, const enumerate_all_paths_params &params = {}) noexcept

Enumerates all possible paths in a layout that start at a given source coordinate and lead to given target coordinate. This function automatically detects whether the given layout implements a clocking interface (see clocked_layout) and respects the underlying information flow imposed by layout’s clocking scheme. This algorithm does neither generate duplicate nor looping paths, even in a cyclic clocking scheme. That is, along each path, each coordinate can occur at maximum once.

If the given layout implements the obstruction interface (see obstruction_layout), paths will not be routed via obstructed coordinates or connections.

If the given layout is a gate-level layout and implements the obstruction interface (see obstruction_layout), paths may contain wire crossings if specified in the parameters. Wire crossings are only allowed over other wires and only if the crossing layer is not obstructed. Furthermore, it is ensured that crossings do not run along another wire but cross only in a single point (orthogonal crossings + knock-knees/double wires).

In certain cases it might be desirable to enumerate regular coordinate paths even if the layout implements a clocking interface. This can be achieved by static-casting the layout to a coordinate layout when calling this function: 

using clk_lyt = clocked_layout<cartesian_layout<>>;
using path = layout_coordinate_path<cartesian_layout<>>;
clk_lyt layout = ...;
auto all_paths = enumerate_all_paths<path>(static_cast<cartesian_layout<>>(layout), {source, target});

Template Parameters:

  • Path – Type of the returned individual paths.

  • Lyt – Type of the layout to perform path finding on.

Parameters:

  • layout – The layout whose paths are to be enumerated.

  • objective – Source-target coordinate pair.

  • params – Parameters.

Returns:

A collection of all unique paths in layout from objective.source to objective.target.