Implementando Grafos (Graphs) com NodeJS e Javascript

Grafos: Explorando Conexões e Relacionamentos Complexos

Grafos são uma estrutura de dados essencial que permite representar relações complexas entre elementos, como redes sociais, sistemas de navegação e otimização de rotas. Aqui vamos abordar a implementação e conceitos básicos dos grafos em NodeJS/JavaScript, vamos tentar trazer insights valiosos.

Implementação

A Teoria

Aqui você vai lembrar muito de árvores (Trees) porque o grafo é uma coleção de nós (ou vértices) e arestas que conectam pares desses nós. Grafos podem ser dirigidos ou não dirigidos e podem incluir arestas com pesos, que oferecem uma representação de custo ou distância entre os nós... sim começa a ficar um pouco mais complexo mas vamos tentar simplificar essa parada ai.

A Prática

Bora pro código então, uma versão básica de grafos precisa ter o número de nós que o grafo tem, e seus nós (sua lista de nós):

class Graph {
  constructor() {
    this.numberOfNodes = 0
    this.adjacentList = {}
  }
}

Parece mais complicado do que é, mas é isso ai. Acabou...brinks! Bora adicionar outras funções pra deixar mais claro:

class Graph {
  constructor() {
    this.numberOfNodes = 0
    this.adjacentList = {}
  }
  add(node) {
    this.adjacentList[node] = []
    this.numberOfNodes++
  }
  addEdge(node1, node2) {
    this.adjacentList[node1].push(node2)
    this.adjacentList[node2].push(node1)
  }
  showConnections() {
    const all = Object.keys(this.adjacentList)
    for (let node of all) {
      let nodeConnections = this.adjacentList[node]
      let connections = ''
      let vertex
      for (vertex of nodeConnections) {
        connections += vertex + ' '
      }
      console.log(`${node} --> ${connections}`)
    }
  }
}

Explicando alguns pontos:

add(node) {
    this.adjacentList[node] = [];
    this.numberOfNodes++;
}

No código acima a gente adiciona um item no grafo, mas preta atenção, mesmo que o nome seja adjacentList na realidade a gente esta com um objeto. Quando adicionamos no adjacentList[node] a gente cria um elemento novo e esse elemento recebe um array vazio de valor, porque não tem conexões com outros elementos.

 addEdge(node1, node2) {
    this.adjacentList[node1].push(node2);
    this.adjacentList[node2].push(node1);
}

Pra adicionar um edge, a gente precisa dizer que esse egde vai conectar os elementos X e Y. Por isso temos o node1 e node2, são os elementos que a edge vai conectar. Quando a gente adiciona uma edge a gente tem que fazer ida e volta, ou seja, adiconar um edge de X para Y e de Y para X, por isso temos 2 pushs que são inversos.

Nesse caso fazemos isso porque não é um grafo direcionado (onde a edge vai só de X para Y e não volta) e também não temos peso nas edges, mas se precisase seria aqui que colocariamos. Se tiver trabalhando com peso (um grafo de ruas, ou relações de amizades em rede social por exemplo) poderiamos por um peso dessa forma (mais ou menos):

addEdge(node1, node2, weight = 0) {
    this.addVertex(node1);
    this.addVertex(node2);
    this.vertices[node1].push({ node: node2, weight });
    this.vertices[node2].push({ node: node1, weight });
}

Testando:

const myGraph = new Graph()
myGraph.add(0)
myGraph.add(1)
myGraph.add(2)
myGraph.add(3)
myGraph.addEdge(0, 2)
myGraph.addEdge(1, 2)
myGraph.addEdge(1, 3)
myGraph.addEdge(2, 3)
myGraph.showConnections()

Rodando isso no seu console, vc deve receber algo nessas linhas:

0 --> 2
1 --> 2 3
2 --> 0 1 3
3 --> 1 2

Isso representa:

• 0 tem conexão com o 2.
• 1 tem conexão com o 2 e com o 3.
• 2 tem conexão com o 0, 1 e com o 3.
• 3 tem conexão com 1 e com o 2.

Essas informações te lembram algo? 👀

Aonde Você Pode Usar/Ver

Aqui não temos muito pra onde fugir, os melhores exemplos são:

Redes Sociais

Grafos são ideais para modelar redes sociais, permitindo representar usuários como vértices e suas conexões ou relações como arestas, facilitando análises complexas de rede.

Sistemas de Navegação e Mapas

Em sistemas de navegação, grafos ajudam a calcular rotas ótimas, utilizando algoritmos como Dijkstra ou A* para encontrar o caminho mais curto entre pontos em um mapa.

Mas é lógico que grafos são uma estrutura de dados que pode ser usada pra várias coisas, por exemplo, se você tem um e-commerce você pode ter um grafo que relaciona produtos e o peso ("weight") seria um percentual de que aquele produto é comprado junto a outro produto, então na hora que alguém colocasse algo no carrinho de compras você mostraria um produto recomendado para ser comprado junto onde o percentual fosse alto (maior peso no grafo)... e assim vai...

Dicas

• Escolha a representação do grafo (lista ou matriz de adjacência, etc.) com base no tipo de operações que você precisa realizar com mais frequência, como busca ou inserção de nós.
• Para grafos grandes, considere o uso de estruturas de dados especializadas que otimizem o uso de memória e o tempo de processamento, hoje temos bancos especificos para grafos, libs especificas, etc.
• Implemente e teste algoritmos de grafos fundamentais, como busca em profundidade (DFS) e busca em largura (BFS), para garantir que sua estrutura de grafo funcione efetivamente sob várias condições. (Vamos fazer isso num post mais pra frente, lá em cima onde cito meu post inicial sobre as 15 estruturas e algoritmos mais utilizados a gente vai abordar isso).

Considerações do Jon

A ideia aqui é termos uma base de como grafos funcionam, dificilmente você vai ter que criar uma estrutura de grafos no seu dia a dia, ou dar manutenção nisso. Mesmo se você tiver trabalhando em empresas como Meta, Instagram, Twitter (X), você vai precisar entender a estrutura, e talvez criar features ou resolver bugs que estão próximos as estruturas, mas dificilmente você vai ficar mexendo no core do grafo o tempo todo, uma vez criado com as funções necessárias, você só vai mudar se a necessidade do teu produto mudar por algum motivo tipo aumento repentido de usuários, inclusão de novas features como peso ou filas de prioridade, etc.

E Você?!

Já criou/utilizou algo parecido nos seus projetos ou no seu trampo? Compartilhe aqui nos comentários suas dúvidas, se já fez, experiências, desafios, dicas, etc!! Vamos explorar esses conceitos juntos, ah e se viu algum bug, erro, melhoria, também comenta aí!