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) ![]()
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!
Trending in Questions
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
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
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
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
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
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
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
I am happy to introduce the very α version of the new programming language compiled to BEAM.
Welcome Cure.
It has literally three kille...
New
Hobbes is a low-level distributed database for the Elixir programming language.
Hobbes provides a simple, safe, and scalable storage lay...
New
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
Beam Bots (or just BB for short) is a framework for building fault-tolerant robotics applications in Elixir using familiar OTP patterns. ...
New
ExRatatui lets you cook up rich terminal UIs in Elixir, powered by Rust’s ratatui via Rustler NIFs. Build interactive terminal applicatio...
New
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
Categories:
Sub Categories:
Forums
Popular Tags
- #ecto
- #liveview
- #troubleshooting
- #learning-elixir
- #deployment
- #library
- #erlang
- #testing
- #genserver
- #mix
- #absinthe
- #remote-other
- #otp
- #plug
- #how-to-question
- #macros
- #postgres
- #elixirconf
- #channels
- #exunit
- #discussion
- #code-sync
- #podcasts
- #javascript
- #onsite
- #dialyzer
- #docker
- #authentication
- #umbrella
- #full-time-contract
- #podcasts-by-brainlid
- #ecto-query
- #blog-post
- #elixirconf-us
- #elixir-ls
- #ai
- #phoenix_html
- #iex
- #graphql
- #genstage
- #websockets
- #supervisor
- #advent-of-code
- #distillery
- #processes
- #api
- #forms
- #hex
- #security
- #metaprogramming










Showing Posts 1 to 4- Show Best Posts
- Show All (oldest first)
- Show All (newest first)
dimitarvp
Upload it somewhere public and put a link here?
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
:errorA 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
here it is
quda
Thanks for your suggestions, @hernytan.
I inversed by putting queue in front on neighbors
The result is even worse:
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.