Marat's Notes

First steps

What is the BFS?

https://en.wikipedia.org/wiki/Breadth-first_search

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’[1]), and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.

Task

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
    attr_accessor :member_id, :adjacents

    def initialize(member_id)
      @adjacents = Set.new
      @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
  
    def add_edge(node_one, node_two)
      node_one.adjacents << node_two
      node_two.adjacents << node_one
    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
        current_node.adjacents.each do |adjacent_node|
          next if @visited.include?(adjacent_node)
          queue << adjacent_node
          @visited << adjacent_node
          @edge_to[adjacent_node] = current_node
        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 :find_headings
    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

        @graph.add_edge(node, 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!

Implementing BFS search in the graph based data structures

First steps

Task

Implementation

Final