### First steps

What is the BFS?

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a ‘search key’), and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level. Get friends hierarchy based on friendships graph.

### Implementation

Let’s start from Member model, which can have different friendships levels.

``````class Member < ApplicationRecord
has_friendship

def friends_of_friends
Member.joins(:friendships).where(:id => friendships.pluck(:friend_id))
end
end
``````

This is the graph’s Node structure, it has link to the member_id and adjacents Set with uniq elements.

``````require "set"

module Structures
class Node

def initialize(member_id)
@member_id = member_id
end

def to_s
@member_id
end
end
end
``````

Let’s define Graph structure with nodes array, where we can get node by ID or add edge.

``````module Structures
class Graph
attr_accessor :nodes

def initialize
@nodes = []
end

def get_node(id)
@nodes.select { |x| x.member_id == id }&.first
end

end
end
end
``````

Funniest part - let’s go through our graph and perform search!

``````module Structures
class GraphQuery
def initialize(graph, source_node)
@graph = graph
@node = source_node
@visited = []
@edge_to = {}
search(source_node)
end

def build_path_to(node)
return unless has_path_to?(node)
path = []
while(node != @node) do
path.unshift(node)
node = @edge_to[node]
end

path.unshift(@node)
end

private
def search(node)
queue = []
queue << node
@visited << node

while queue.any?
current_node = queue.shift
end
end
end

def has_path_to?(node)
@visited.include?(node)
end
end
end
``````

This is the Search module, where we’re building Graph structure and iterating through all friendships. See code comments below.

``````module Search
class Query
include Dry::Transaction

step :graph_scope

def self.index_query(id:, q:, &block)
new.call(id: id, q: q, &block)
end

def build_graph
@graph = Structures::Graph.new
data = HasFriendship::Friendship.pluck(:friendable_id, :friend_id)
data.each do |friends|
node = @graph.get_node(friends.first)
friend_node = @graph.get_node(friends.last)

if !node
node = Structures::Node.new(friends.first)
end
if !friend_node
friend_node = Structures::Node.new(friends.last)
end

@graph.nodes << node
@graph.nodes << friend_node

end
@graph
end

def graph_scope(id:, result_pairs:)
graph = build_graph
# GET ROOT NODE
me = graph.get_node(id.to_i)
results = []
result_pairs.each_with_index do |result, index|
# GET FRIEND FROM GRAPH NODE
friend = graph.get_node(result['member_id'].to_i)
# BUILDING SHORTEST PATH TO THE FRIEND
path = Structures::GraphQuery.new(graph, me).build_path_to(friend)
graph_path = path.map(&:member_id)
mems = Member.where(id: graph_path).sort_by { |p| graph_path.index(p.id) }
# SOME CODE FOR RESULTS POPULATION
end
Success(result: results)
end
end
end
``````

### Final

Final result returns us shortest path between logged user and Ivan user through your closest friend.

``````{
"result": [
[
"Alan",
"Bart",
"Mark",
"Ivan"
]
]
}
``````

.

Stay tuned!