Estudo sobre Grafos

estudo_sobre_grafos.livemd

Estudo sobre Grafos

Introdução

Este estudo tem como objetivo explicar o conceito de grafos e demonstrar uma aplicação simples de grafos em Elixir. O código em Elixir define um módulo Person com uma estrutura básica de entidade e um módulo ProfessionalFinder, que contém uma função para encontrar um profissional na lista de amigos de uma pessoa.

Grafos

Em ciência da computação, um grafo é uma estrutura de dados que consiste em um conjunto finito de nós (ou vértices) e um conjunto de arestas que conectam esses nós. Um grafo pode ser usado para representar relações entre diferentes entidades.

Existem dois tipos principais de grafos:

Grafo Direcionado (DiGraph): Em um grafo direcionado, as arestas têm uma direção, ou seja, vão de um nó para outro. Essa direção é frequentemente representada por setas.

Grafo Não Direcionado: Em um grafo não direcionado, as arestas não têm direção. A relação entre os nós é mútua.

Nós e Arestas

Nó (ou Vértice): Representa uma entidade no grafo. No código Elixir, uma estrutura Person (Pessoa) é usada para representar os nós. Cada pessoa tem um nome, uma profissão e uma lista de amigos (nós conectados).

Aresta: Representa uma relação entre nós. No contexto desse exemplo, as arestas são amizades entre pessoas.

Explicação do Código Elixir

Módulo Person

O módulo Person define uma struct que representa uma pessoa com atributos como name (nome), profession (profissão) e uma lista de friends (amigos). Essa estrutura captura as informações básicas necessárias para uma pessoa no contexto de uma rede social.

defmodule Person do
  @moduledoc """
  Person Entity
  """
  defstruct name: nil, profession: nil, friends: []
end

Módulo ProfessionalFinder

O módulo ProfessionalFinder contém uma função chamada search/2, que procura por uma pessoa com uma profissão específica na lista de amigos de uma pessoa fornecida.

A função recebe uma pessoa e uma profissão como entrada. Ela inicializa uma fila de busca com os amigos da pessoa de entrada e um conjunto para acompanhar os nós verificados. A função privada do_search/3 realiza uma pesquisa em largura (BFS) no grafo para encontrar uma pessoa com a profissão especificada.

defmodule ProfessionalFinder do
  @moduledoc """
  Find a professional on your friends list
  """

  @spec search(Person.t(), String.t()) :: {:ok, Person.t()} | {:error, :not_found}
  def search(person, profession) do
    search_queue = :queue.from_list(person.friends)
    checked = MapSet.new()

    do_search(search_queue, checked, profession)
  end

  defp do_search({[], []}, _, _), do: {:error, :not_found}

  defp do_search(search_queue, checked, profession) do
    friend = :queue.head(search_queue)

    with false <- MapSet.member?(checked, friend),
         ^profession <- friend.profession do
      {:ok, friend}
    else
      # has already checked
      true ->
        do_search(:queue.tail(search_queue), checked, profession)

      _profession ->
        search_queue
        |> :queue.tail()
        |> append_friends(friend.friends)
        |> do_search(MapSet.put(checked, friend), profession)
    end
  end

  defp append_friends(queue, []), do: queue

  defp append_friends(queue, friends) do
    Enum.reduce(friends, queue, fn friend, queue ->
      :queue.in(friend, queue)
    end)
  end
end

Exemplo de Uso

O exemplo a seguir cria uma pequena rede social de pessoas e usa o ProfessionalFinder para procurar uma pessoa com uma profissão específica na rede.

Criação de Pessoas:

Anuj, Peggy, Tom, Jonny, Claire, Alice, Bob e João representam indivíduos na rede social.

Definição de Amizades:

Amizades são definidas usando o campo friends na struct Person.

anuj = %Person{name: "Anuj", profession: "Engineer"}
peggy = %Person{name: "Peggy", profession: "Doctor"}
tom = %Person{name: "Tom", profession: "Seller"}
jonny = %Person{name: "Jonny", profession: "Carpenter"}
claire = %Person{name: "Claire", profession: "Lawyer", friends: [tom, jonny]}
alice = %Person{name: "Alice", profession: "Engineer", friends: [peggy]}
bob = %Person{name: "Bob", profession: "Manger", friends: [anuj, peggy]}
joao = %Person{name: "Joao", profession: "Farmer", friends: [alice, bob, claire]}

Execução da Busca:

O exemplo procura por uma pessoa com a profissão "Vendedor" na lista de amigos de João usando ProfessionalFinder.search(person, profession).

person = joao
profession = "Seller"
ProfessionalFinder.search(person, profession)

Saída:

A saída {:ok, %Person{name: "Tom", profession: "Vendedor", friends: []}} indica que uma pessoa chamada Tom com a profissão "Vendedor" foi encontrada. Observe que Tom não é uma conexão direta de João. Tom é amigo de Claire que é amiga de João, ou seja Tom é uma coneção de segundo grau de João.

A pesquisa utilizando grafos busca primeiro os amigos mais próximos de João, se não encontrar nenhum vendedor nessa lista então a busca se expandirá para os amigos dos amigos de João. Dependendo do seu objetivo, talvez queira estabelecer um limite para não acabar encontrando um completo desconhecido.

Conclusão

Grafos são uma estrutura de dados versátil que pode ser aplicada em diversos cenários. por exemplo:

• Redes Sociais: Modelagem de amizades e conexões entre usuários baseados em grau de conexão ou proximidade geográfica.

• Sistemas de Recomendação: Análise de padrões de comportamento de usuários para recomendar produtos ou conteúdo.

• Logística e Roteamento: Otimização de rotas em redes de transporte, como GPS e logística de entrega.