Yog.Pathfinding.Bidirectional (YogEx v0.70.0)

Copy Markdown View Source

Bidirectional search algorithms that meet in the middle for dramatic speedups.

These algorithms start two simultaneous searches — one from the source and one from the target — that meet in the middle. This can dramatically reduce the search space compared to single-direction search.

For a graph with branching factor b and depth d:

  • Standard BFS: O(b^d) nodes explored
  • Bidirectional BFS: O(2 × b^(d/2)) nodes explored (up to 500x faster for long paths)

Requirements

  • Target node must be known in advance (unlike Dijkstra, which can route many at once).
  • Designed for point-to-point queries.

Summary

Types

path_result()

Result type for shortest path queries

Functions

shortest_path(opts)

Finds the shortest path in a weighted graph using bidirectional Dijkstra.

shortest_path(graph, from, to, zero \\ 0, add \\ &Kernel.+/2, compare \\ &Yog.Utils.compare/2)

Finds the shortest path in a weighted graph using bidirectional Dijkstra.

shortest_path_unweighted(opts)

Finds the shortest path in an unweighted graph using bidirectional BFS.

shortest_path_unweighted(graph, from, to)

Finds the shortest path in an unweighted graph using bidirectional BFS.

Types

path_result()

@type path_result() :: {:ok, Yog.Pathfinding.Path.t()} | :error

Result type for shortest path queries

Functions

shortest_path(opts)

@spec shortest_path(keyword()) :: path_result() | :none

Finds the shortest path in a weighted graph using bidirectional Dijkstra.

Options

  • :in - The graph
  • :from - The starting node ID
  • :to - The target node ID
  • :zero - The identity element for weights (e.g. 0)
  • :add - Weight addition function (e.g. fn a, b -> a + b end)
  • :compare - Comparison function (e.g. &Yog.Utils.compare/2)

Examples

iex> graph = Yog.undirected()
...> |> Yog.add_node(1, nil) |> Yog.add_node(2, nil) |> Yog.add_node(3, nil)
...> |> Yog.add_edge!(from: 1, to: 2, with: 5)
...> |> Yog.add_edge!(from: 2, to: 3, with: 10)
iex> {:ok, path} = Yog.Pathfinding.Bidirectional.shortest_path(
...>   in: graph, from: 1, to: 3,
...>   zero: 0, add: &+/2, compare: &Yog.Utils.compare/2
...> )
iex> path.nodes
[1, 2, 3]
iex> path.weight
15

shortest_path(graph, from, to, zero \\ 0, add \\ &Kernel.+/2, compare \\ &Yog.Utils.compare/2)

@spec shortest_path(
  Yog.t(),
  Yog.node_id(),
  Yog.node_id(),
  weight,
  (weight, weight -> weight),
  (weight, weight ->
     :lt
     | :eq
     | :gt)
) ::
  path_result() | :error
when weight: var

Finds the shortest path in a weighted graph using bidirectional Dijkstra.

Parameters

  • graph - The graph to search
  • from - The starting node ID
  • to - The target node ID
  • zero - The identity element for weights (e.g. 0)
  • add - Weight addition function (e.g. fn a, b -> a + b end)
  • compare - Comparison function returning :lt, :eq, or :gt

Returns

  • {:ok, path} - A Path struct containing the nodes and total weight
  • :error - No path exists between the nodes

Examples

iex> graph = Yog.undirected()
...> |> Yog.add_node(1, nil) |> Yog.add_node(2, nil) |> Yog.add_node(3, nil)
...> |> Yog.add_edge!(from: 1, to: 2, with: 5)
...> |> Yog.add_edge!(from: 2, to: 3, with: 10)
iex> {:ok, path} = Yog.Pathfinding.Bidirectional.shortest_path(graph, 1, 3, 0, &+/2, &Yog.Utils.compare/2)
iex> path.nodes
[1, 2, 3]
iex> path.weight
15

shortest_path_unweighted(opts)

@spec shortest_path_unweighted(keyword()) :: path_result() | :none

Finds the shortest path in an unweighted graph using bidirectional BFS.

This runs BFS from both source and target simultaneously, stopping when the frontiers meet.

Options

  • :in - The graph
  • :from - The starting node ID
  • :to - The target node ID

Examples

iex> graph = Yog.undirected()
...> |> Yog.add_node(1, nil) |> Yog.add_node(2, nil) |> Yog.add_node(3, nil)
...> |> Yog.add_edge!(from: 1, to: 2, with: 1)
...> |> Yog.add_edge!(from: 2, to: 3, with: 1)
iex> {:ok, path} = Yog.Pathfinding.Bidirectional.shortest_path_unweighted(in: graph, from: 1, to: 3)
iex> path.nodes
[1, 2, 3]
iex> path.weight
2
iex> Yog.Pathfinding.Bidirectional.shortest_path_unweighted(in: graph, from: 1, to: 99)
:error

shortest_path_unweighted(graph, from, to)

@spec shortest_path_unweighted(Yog.t(), Yog.node_id(), Yog.node_id()) ::
  path_result() | :error

Finds the shortest path in an unweighted graph using bidirectional BFS.

Parameters

  • graph - The graph to search
  • from - The starting node ID
  • to - The target node ID

Returns

  • {:ok, path} - A Path struct containing the nodes and edge count
  • :error - No path exists between the nodes

Examples

iex> graph = Yog.undirected()
...> |> Yog.add_node(1, nil) |> Yog.add_node(2, nil) |> Yog.add_node(3, nil)
...> |> Yog.add_edge!(from: 1, to: 2, with: 1)
...> |> Yog.add_edge!(from: 2, to: 3, with: 1)
iex> {:ok, path} = Yog.Pathfinding.Bidirectional.shortest_path_unweighted(graph, 1, 3)
iex> path.nodes
[1, 2, 3]
iex> path.weight
2
iex> Yog.Pathfinding.Bidirectional.shortest_path_unweighted(graph, 1, 99)
:error