@spec bellman_ford(keyword()) :: result()

Find shortest path using Bellman-Ford with keyword options.

Options

• :in - The graph to search
• :from - Starting node
• :to - Target node
• :zero - Identity value for the weight type
• :add - Function to add two weights
• :compare - Function to compare weights (:lt, :eq, :gt)

Examples

Pathfinding.BellmanFord.bellman_ford(
  in: graph,
  from: :a,
  to: :c,
  zero: 0,
  add: &(&1 + &2),
  compare: &Yog.Utils.compare/2
)

@spec bellman_ford(
  Yog.t(),
  Yog.node_id(),
  Yog.node_id(),
  weight,
  (weight, weight -> weight),
  (weight, weight ->
     :lt
     | :eq
     | :gt)
) ::
  result()
when weight: var

Find the shortest path between two nodes using Bellman-Ford.

Parameters

• graph - The graph to search
• from - Starting node
• to - Target node
• zero - Identity value for the weight type
• add - Function to add two weights
• compare - Function to compare weights (:lt, :eq, :gt)

Returns

• {:ok, path} - A Path struct containing the nodes and weight
• {:error, :negative_cycle} - A negative cycle was detected
• {:error, :no_path} - No path exists between the nodes

Examples

iex> graph = Yog.directed()
...> |> Yog.add_node(:a, nil)
...> |> Yog.add_node(:b, nil)
...> |> Yog.add_node(:c, nil)
...> |> Yog.add_edge!(:a, :b, 4)
...> |> Yog.add_edge!(:b, :c, -3)
iex> compare = &Yog.Utils.compare/2
iex> {:ok, path} = BellmanFord.bellman_ford(graph, :a, :c, 0, &(&1 + &2), compare)
iex> path.nodes
[:a, :b, :c]
iex> path.weight
1

iex> # Graph with negative cycle
iex> bad_graph = Yog.directed()
...> |> Yog.add_node(:a, nil)
...> |> Yog.add_node(:b, nil)
...> |> Yog.add_edge!(:a, :b, 1)
...> |> Yog.add_edge!(:b, :a, -3)
iex> compare = &Yog.Utils.compare/2
iex> BellmanFord.bellman_ford(bad_graph, :a, :b, 0, &(&1 + &2), compare)
{:error, :negative_cycle}

@spec has_negative_cycle?(
  Yog.graph(),
  Yog.node_id(),
  any(),
  (any(), any() -> any()),
  (any(), any() ->
     :lt | :eq | :gt)
) ::
  boolean()

Checks if the graph contains a negative cycle reachable from the source.

@spec implicit_bellman_ford(keyword()) :: implicit_result(any())

Implicit Bellman-Ford using keyword options.

Options

• :from - Starting state
• :successors_with_cost - Function returning neighbors with costs
• :is_goal - Function to check if a state is the goal
• :zero - Identity value for the weight type
• :add - Function to add two weights
• :compare - Function to compare weights

Examples

Pathfinding.implicit_bellman_ford(
  from: 1,
  successors_with_cost: fn n -> [{n+1, -1}] end,
  is_goal: fn n -> n == 10 end,
  zero: 0,
  add: &(&1 + &2),
  compare: &Yog.Utils.compare/2
)

@spec implicit_bellman_ford(
  state,
  (state -> [{state, cost}]),
  (state -> boolean()),
  cost,
  (cost, cost -> cost),
  (cost, cost -> :lt | :eq | :gt)
) :: implicit_result(cost)
when state: var, cost: var

Run Bellman-Ford on an implicit (generated) graph.

Similar to implicit Dijkstra, but supports negative edge weights and can detect negative cycles.

Parameters

• from - Starting state
• successors - Function state -> [{neighbor, cost}]
• is_goal - Function state -> boolean to check if goal reached
• zero - Identity value for the weight type
• add - Function to add two weights
• compare - Function to compare weights

Returns

• {:ok, cost} - Minimum cost to reach goal
• {:error, :negative_cycle} - A negative cycle was found
• {:error, :no_goal} - Goal is unreachable

Examples

# Search with negative weights
iex> successors = fn
...>   1 -> [{2, -1}]
...>   2 -> [{3, -2}]
...>   3 -> [{4, -3}]
...>   4 -> []
...> end
iex> {:ok, cost} = BellmanFord.implicit_bellman_ford(
...>   1, successors, fn x -> x == 4 end,
...>   0, &(&1 + &2), &Yog.Utils.compare/2
...> )
iex> cost
-6

@spec implicit_bellman_ford_by(keyword()) :: implicit_result(any())

Implicit Bellman-Ford with key function using keyword options.

Options

• :from - Starting state
• :successors_with_cost - Function returning neighbors with costs
• :visited_by - Function to extract a key for visited tracking
• :is_goal - Function to check if a state is the goal
• :zero - Identity value for the weight type
• :add - Function to add two weights
• :compare - Function to compare weights

@spec implicit_bellman_ford_by(
  state,
  (state -> [{state, cost}]),
  (state -> term()),
  (state -> boolean()),
  cost,
  (cost, cost -> cost),
  (cost, cost -> :lt | :eq | :gt)
) :: implicit_result(cost)
when state: var, cost: var

Implicit Bellman-Ford with a key function for visited state tracking.

Similar to implicit_bellman_ford/6, but uses a key function for visited tracking.

Parameters

• from - Starting state
• successors - Function state -> [{neighbor, cost}]
• key_fn - Function state -> key for visited tracking
• is_goal - Function state -> boolean to check if goal reached
• zero - Identity value for the weight type
• add - Function to add two weights
• compare - Function to compare weights

@spec reconstruct_path(
  %{required(Yog.node_id()) => Yog.node_id()},
  Yog.node_id(),
  Yog.node_id(),
  any()
) ::
  Yog.Pathfinding.Path.t()

Reconstructs a path from the predecessor map returned by Bellman-Ford.

@spec relaxation_passes(
  Yog.graph(),
  Yog.node_id(),
  any(),
  (any(), any() -> any()),
  (any(), any() ->
     :lt | :eq | :gt)
) ::
  %{required(Yog.node_id()) => any()}

Computes relaxation passes for all-pairs shortest paths.

Returns a map of all node distances after V-1 relaxation passes.