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!

First 4 of 4 Posts Switch mode

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

stjefim
Hello! Suppose you are building workflow (order / task / payment) processing system with the following requirements: Each workflow con...
New
jonnycharles
I’m in search of an Elixir library that offers PDF generation capabilities similar to Ruby’s Prawn. While there have been discussions abo...
New
spammy
I’m looking to build a personal workflow to quickly deploy web applications written in elixir/phoenix, for local consumption (ie not on t...
New
dli
Before I dive in myself, did anyone successfully sprinkle Hologram into their existing LiveView app? Looking for hints regarding: Addi...
New
roeland
Kia ora, We have been using elixir-google-api to connect to Google Drive. However, with the updates to Tesla due to CVEs this is now bro...
New
bottlenecked
Hi all, I wanted to ask how the community is dealing with post-release steps. Today we have Ecto migrations, which make sure that the db...
New
rahultumpala
Hello, I have an Elixir backend that implements a custom protocol over TCP. I want to load test the backend and assess the performance o...
New

Other Trending Topics Top

JesseHerrick
Hey, I’m Jesse and I’m the main contributor behind Dexter, a full-featured, lightning-fast Elixir LSP optimized for large codebases. It s...
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
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
netoum
Corex is an accessible, unstyled UI component library for Phoenix that integrates Zag.js state machines using Vanilla JavaScript and Live...
New
ausimian
Emily is an Elixir library that runs Nx computations on Apple’s MLX. Install it as the default Nx backend and Nx, defn, Axon, Nx.Serving,...
New
juhalehtonen
There has been a thread to discuss the Stack Overflow Developer Survey on this forum every year since 2018, so here’s yet another one for...
New

We're in Beta

About us Mission Statement