Estudo sobre Grafos com Elixir
Published: 2023-11-15 19:35:05

### 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.

```elixir
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.

```elixir
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.

```elixir
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).

```elixir
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 conexã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.