quda

quda

Hi,
I am quite new to Elixir… about one month experience.
I’m trying to implement a program for shortest path calculation between two points using Breadth-first search (BFS) algorithm on a directed graph, using recursion.
The code I wrote is this:

defmodule BFS do
  def neibors(node, edges) do
    Enum.filter(edges, fn x -> x.from == node end)
    |> Enum.map(& &1.to)
  end

  def bfs(start, target, graph) do
    que = neibors(start, graph)
    visited = [start]
    Enum.reverse(search(que, {target, graph}, visited, [start]))
  end

  defp search([node | rest], data, visited, prev) do
    {target, graph} = data
    if Enum.member?(visited, node) == false do
      if node == target do
         [target|prev]
      else
        search(neibors(node, graph) ++ rest, data, [node | visited], [node | prev])
      end
    end
  end
end

The test graph picture I cannot upload (new users cannot upload pictures) :face_with_raised_eyebrow:
But this is the test data model I use:

graph = [
  %{from: 'A', to: 'B'},
  %{from: 'A', to: 'C'},
  %{from: 'B', to: 'G'},
  %{from: 'C', to: 'F'},
  %{from: 'C', to: 'D'},
  %{from: 'D', to: 'E'},
  %{from: 'E', to: 'H'},
  %{from: 'F', to: 'D'},
  %{from: 'F', to: 'G'},
  %{from: 'H', to: 'G'}
]

I want to get the shortest path from node A to node H. This is obviously A->C->D->E->H

I cannot manage to collect the path’s nodes, instead it collects all traversed nodes:

 BFS.bfs('A', 'H', graph) 
['A', 'B', 'G', 'C', 'F', 'D', 'E', 'H']

Obviously, something is wrong in my algorithm implementation, I need a way to collect only the nodes of the shortest path not all of them. How ?

Thanks in advance for your help!

Showing Posts 1 to 4

dimitarvp

dimitarvp

Upload it somewhere public and put a link here?

hernytan

hernytan

The code you have written is not a BFS, but actually a DFS. This is because after you visit a node, you push its neighbors into the front of the queue, when you should push it onto the back of the queue. Remember: going to the front is cutting the queue!

More importantly, your code also doesn’t handle the case when you do revisit a node. Say you go from A → B → A. Then your search function just returns nothing.

Also, you should add a case to handle if the target node is missing. Maybe return an :error

A suggestion, you can also make the visited data structure a MapSet, that way you can use the in-built data functions to test if a node has been visited:

quda

quda OP

here it is

quda

quda OP

Thanks for your suggestions, @hernytan.

I inversed by putting queue in front on neighbors

  search(rest ++ neibors(node, graph), data, [node | visited], [node | prev])

The result is even worse:

iex(4)> BFS.bfs('A','H',edges)
nil

More importantly, your code also doesn’t handle the case when you do revisit a node. Say you go from A → B → A. Then your search function just returns nothing.

I don’t get this… What should return in this case?

About the third hint, that with MapSet, I’m afraid I don’t know how to do this.

Thanks anyway.

— All posts loaded —

Where Next? Top

Trending in Questions Top

Blokh
Hey guys, I’ve got a huge CSV ( around 10 GB ) that needs to be processed hourly Do you guys have any suggestions what is the best prac...
New
kszambelanczyk
Hello! Could someone please give me a help/sample code, how to delete a file from s3 using waffle/waffle_ecto from Phoenix app. I creat...
New
RemyXRenard
I’m seeing that a list inside a Kino.DataTable will be interpreted as a charlist, even if the Kino.configure() is set to charlists: :as_l...
New
velrest
So my question is quite simple and i have found no conclusive answer on forum, google or AI. Should we use :erlang.float for Integer to ...
New
samoloth
Hi, I’ve just set up an application with ash_authentication. There is only magic link strategy for now, so there is no confirmation add o...
New
FlyingNoodle
If a change or preparation module uses Ash.Changeset.get_argument/2 or Ash.Query.get_argument/2 (or any of the other get_argument functio...
New
psy-q
I’m trying to set up Emacs with elixir-ls via lsp-mode and credo via Flycheck. This should mostly be preconfigured as Flycheck picks up c...
New

Other Trending Topics Top

mudasobwa
I am happy to introduce the very α version of the new programming language compiled to BEAM. Welcome Cure. It has literally three kille...
New
garrison
Hobbes is a low-level distributed database for the Elixir programming language. Hobbes provides a simple, safe, and scalable storage lay...
New
marciok
Hi there! We created Gust: A task orchestrator inspired by Airflow. For those who have never heard about Aiflow, it’s a Python-based wor...
New
jimsynz
Beam Bots (or just BB for short) is a framework for building fault-tolerant robotics applications in Elixir using familiar OTP patterns. ...
New
mcass19
ExRatatui lets you cook up rich terminal UIs in Elixir, powered by Rust’s ratatui via Rustler NIFs. Build interactive terminal applicatio...
New
Damirados
Hello everyone. After busy few months I am happy to announce v0.1.0 of Emerge & Solve. They are GUI (Emerge) and State management (S...
New

We're in Beta

About us Mission Statement

Options

Thread Display Mode




Thread Preview

Skip Thread Previews