NetworkX é uma biblioteca de analise e manipulação de grafos.
O site do mantenedor é:
Para instalar o networkx use o comando a seguir:
$ pip install networkx[default]
Testando instalação:
Ao realizar este comando testamos para verificar se a instalação foi corretamente instalada.
import networkx as nx
G = nx.Graph()
Parte do material deste tutorial veio do CHATGPT4.
grafo = {
"A": ["B", "C"],
"B": ["A", "D", "E"],
"C": ["A", "F"],
"D": ["B"],
"E": ["B", "F"],
"F": ["C", "E"]
}
Essa síntese destaca os marcos e conceitos mais relevantes na evolução da teoria dos grafos.
Os grafos são relações entre partes, e podemos entender seus elementos como se segue:
A implementação de um grafo pode ser feita de várias formas, pois é um conceito.
Porem as formas mais comuns são descritos a seguir:
É uma lista onde, para cada vértice do grafo, armazenamos uma lista de seus vértices adjacentes. É uma forma eficiente de armazenar grafos esparso.
Exemplo em python:
A matriz de adjacência é uma das formas mais comuns de representar um grafo em termos de estrutura de dados. Ela utiliza uma matriz bidimensional (um array de arrays) para expressar as relações entre os vértices de um grafo.
Vantagens:
Desvantagens:
Para o grafo com vértices A,B,C e arestas (A,B),(B,C):
A matriz de adjacência (não ponderada) seria:
A B C
A [0, 1, 0]
B [1, 0, 1]
C [0, 1, 0]Se este fosse um grafo ponderado, onde a aresta (A,B) tem peso 3 e (B,C) tem peso 2, a matriz seria:
A B C
A [0, 3, 0]
B [3, 0, 2]
C [0, 2, 0]
Apresentaremos um problema de Rota, onde teremos apenas 5 pontes para ir do ponto A ao ponto C.
Nele apresentaremos uma proposta descritiva e depois uma proposta em Python.
Vamos ao grafo dado:
Vértices:A,B,C,D,E Ligações: A−B,B−E,E−C,D−A,B−C
A matriz de adjacência é uma matriz n×n onde n é o número de vértices. A entrada M(i,j) será 1 se o vértice i estiver ligado ao vértice j e 0 caso contrário.
Uma maneira simples de fazer isso é usando uma busca em largura (BFS). Vamos criar um exemplo em Python para isso:
import heapq
def heuristic(node, goal):
# Como um grafo não possui coordenadas espaciais, podemos usar uma heurística trivial.
return 0
def a_star(graph, start, goal):
open_list = [(0, start)]
g_costs = {node: float('inf') for node in range(len(graph))}
g_costs[start] = 0
came_from = {}
while open_list:
current_cost, current_node = heapq.heappop(open_list)
if current_node == goal:
path = []
while current_node in came_from:
path.insert(0, current_node)
current_node = came_from[current_node]
path.insert(0, start)
return path
for neighbor, cost in enumerate(graph[current_node]):
if cost == 1: # Existe uma aresta
tentative_g_cost = g_costs[current_node] + 1
if tentative_g_cost < g_costs[neighbor]:
came_from[neighbor] = current_node
g_costs[neighbor] = tentative_g_cost
f_cost = tentative_g_cost + heuristic(neighbor, goal)
heapq.heappush(open_list, (f_cost, neighbor))
return None
graph = [
[0, 1, 0, 1, 0], # A
[1, 0, 1, 0, 1], # B
[0, 1, 0, 0, 1], # C
[1, 0, 0, 0, 0], # D
[0, 1, 1, 0, 0] # E
]
path = a_star(graph, 0, 2)
if path:
print(" -> ".join(chr(65 + node) for node in path))
else:
print("Não foi encontrado um caminho de A para C.")Resultado:
A -> B -> C
Outros usos de Grafo:
Agora teremos como objetivo desenvolver um NLP que irá analisar de comandos dados de forma textual, utilizando grafos como base de tomada de decisão.
Para isso temos duas tabelas:
Palavras: Contem uma lista de palavras usadas nos textos.
Comandos: Contem uma lista de comandos possíveis.
Usaremos como exemplo de vértice apenas quando duas palavras em sequencia estiverem atendidas em determinado grafo, ai ligaremos estes aos comandos.
Esta tabela contém uma lista de palavras chave que podem ser usadas para determinar ações.
| Palavras |
|---|
| Grave |
| Diário |
| Reproduza |
| Música |
| Ligue |
| Luz |
Esta tabela associa sequências de palavras a ações específicas.
| Sequência de Palavras | Ação |
|---|---|
| Grave Diário | Gravação de entradas no diário |
| Reproduza Música | Tocar música |
| Ligue Luz | Acender a luz |
Neste caso, o grafo seria algo assim:
A ideia aqui é que, se alguém dissesse “Grave meu Diário”, o sistema reconheceria a sequência “Grave Diário” e acionaria a função correspondente de “Gravação de entradas no diário”. As stop words, como “meu”, seriam ignoradas pelo sistema.
Para implementar isso, você poderia criar um dicionário em Python que mapeia sequências de palavras (arestas) a ações, e então usar esse dicionário para determinar a ação apropriada com base na entrada do usuário.
Certifique-se de que você tem o MySQL instalado e em execução. Depois, você pode instalar o conector MySQL para Python:
pip install mysql-connector-python
pip install nltk
Crie um novo banco de dados chamado graph_db e um usuário para esse banco de dados. Você pode fazer isso usando a interface de linha de comando do MySQL ou um cliente GUI como o MySQL Workbench.
Aqui está uma sugestão de estrutura:
words: Guarda os vértices do tipo palavra.commands: Guarda os vértices do tipo comando.edges: Guarda as arestas, referenciando palavras e comandos.CREATE DATABASE graph_db;
USE graph_db;
-- Tabela de palavras
CREATE TABLE words (
word_id INT AUTO_INCREMENT PRIMARY KEY,
word_name VARCHAR(50) UNIQUE NOT NULL
);
-- Tabela de comandos
CREATE TABLE commands (
command_id INT AUTO_INCREMENT PRIMARY KEY,
command_name VARCHAR(50) UNIQUE NOT NULL
);
-- Tabela de arestas
CREATE TABLE edges (
edge_id INT AUTO_INCREMENT PRIMARY KEY,
word_id1 INT,
word_id2 INT,
command_id INT,
FOREIGN KEY (word_id1) REFERENCES words(word_id),
FOREIGN KEY (word_id2) REFERENCES words(word_id),
FOREIGN KEY (command_id) REFERENCES commands(command_id)
);
Nesta estrutura:
words tem um ID único para cada palavra e um nome que é exclusivo.commands tem um ID único para cada comando e um nome que é exclusivo.edges tem um ID único para cada aresta. As colunas word_id e command_id são chaves estrangeiras que apontam para os IDs nas tabelas words e commands, respectivamente.Com essa estrutura, a tabela edges representa as relações entre palavras e comandos. Isso significa que cada entrada (linha) na tabela edges é uma relação entre uma palavra específica na tabela words e um comando específico na tabela commands.
Configurando aplicação e Banco de dados
Iremos primeiramente criar as ferramentas basicas para cadastrar as informações e o ambiente.
Então temos a conexão com o banco de dados.
import mysql.connector
import nltk
nltk.download("stopwords")
from nltk.corpus import stopwords
stop_words = set(stopwords.words('portuguese'))
# Configuração da conexão com o banco
DB_CONFIG = {
"host": "localhost",
"user": "your_username",
"password": "your_password",
"database": "graph_db"
}
"""Cria arestas com base em frases de exemplo."""
frases = [
"Comece a gravação de áudio",
"Salve esse texto importante",
"Defina um alerta para amanhã",
"Quero a gravação dessa reunião",
"Salve a anotação rapidamente"
]
comandos = [
"Iniciar gravação",
"Salvar texto",
"Configurar alerta",
"Iniciar gravação",
"Salvar anotação"
]
Criaremos a função de criar a conexão:
def connect_to_database():
"""Retorna uma conexão com o banco de dados."""
return mysql.connector.connect(**DB_CONFIG)Criamos agora a função de pegar o ID:
def get_id(name, table):
"""Busca o ID de um item pelo nome, na tabela especificada."""
connection = connect_to_database()
cursor = connection.cursor()
column = "word_name" if table == "words" else "command_name"
query = f"SELECT * FROM {table} WHERE {column}=%s"
cursor.execute(query, (name,))
result = cursor.fetchone()
cursor.close()
connection.close()
return result[0] if result else NoneAgora criamos a função que popula as arestas:
def populaArestas(word1, word2, command):
"""Popula a tabela edges com as relações entre palavras e comando."""
connection = connect_to_database()
cursor = connection.cursor()
word1_id = get_id(word1, 'words')
word2_id = get_id(word2, 'words')
command_id = get_id(command, 'commands')
if not word1_id or not word2_id or not command_id:
print(f"Erro: Palavras ou comando não encontrados: '{word1}', '{word2}', '{command}'")
return
insert_query = "INSERT INTO edges (word_id, command_id) VALUES (%s, %s)"
# Inserindo relação da primeira palavra com o comando
cursor.execute(insert_query, (word1_id, command_id))
# Inserindo relação da segunda palavra com o comando
cursor.execute(insert_query, (word2_id, command_id))
connection.commit()
cursor.close()
connection.close()Agora iremos criar os nossos comandos, para isso temos duas funções:
def cadastreCMD(command_name):
"""Cadastra um novo comando na tabela commands."""
connection = connect_to_database()
cursor = connection.cursor()
insert_query = "INSERT INTO commands (command_name) VALUES (%s)"
try:
cursor.execute(insert_query, (command_name,))
connection.commit()
except mysql.connector.Error as err:
print(f"Erro ao inserir comando '{command_name}': {err}")
cursor.close()
connection.close()
def ExemploCMD():
for cmd in comandos:
cadastreCMD(cmd)Agora iremos cadastrar nossas palavras, para isso iremos usar o exemplo a seguir:
Serão implementadas da seguinte forma:
def CadastraWords(word_name):
"""Cadastra uma nova palavra na tabela words."""
connection = connect_to_database()
cursor = connection.cursor()
insert_query = "INSERT INTO words (word_name) VALUES (%s)"
try:
cursor.execute(insert_query, (word_name,))
connection.commit()
except mysql.connector.Error as err:
print(f"Erro ao inserir palavra '{word_name}': {err}")
cursor.close()
connection.close()
def ExemploWords():
for frase in frases:
palavras = frase.split() # Separa a frase em palavras individuais
for palavra in palavras:
# Ignoramos palavras muito comuns (stop words) e números
if palavra.lower() not in stop_words and not palavra.isnumeric():
CadastraWords(palavra)Agora iremos criar a função:
get_id_from_Table – Retorna o ID de uma dado valor de uma dada tabela para uma dada coluna.
CriaArestas – Cria a tabela de relacionamento (grafo) de Palavras.
def get_id_words(value, column_name):
"""Retorna o ID associado a um valor em uma coluna e tabela específicos."""
connection = connect_to_database()
cursor = connection.cursor()
select_query = f"SELECT word_id FROM words WHERE {column_name} = %s"
cursor.execute(select_query, (value,))
result = cursor.fetchone()
cursor.close()
connection.close()
return result[0] if result else None
def get_id_commands(value, column_name):
"""Retorna o ID associado a um valor em uma coluna e tabela específicos."""
connection = connect_to_database()
cursor = connection.cursor()
select_query = f"SELECT command_id FROM commands WHERE {column_name} = %s"
cursor.execute(select_query, (value,))
result = cursor.fetchone()
cursor.close()
connection.close()
return result[0] if result else None
def CriaArestas(Word1, Word2, Cmd):
print(Word1)
print(Word2)
"""Cria uma aresta associando Word1 e Word2 ao comando Cmd."""
word1_id = get_id_words(Word1, "word_name")
word2_id = get_id_words(Word2, "word_name")
cmd_id = get_id_commands(Cmd, "command_name")
print(word1_id);
print(word2_id);
print(cmd_id);
if not word1_id or not word2_id or not cmd_id:
print("Erro: Um ou mais valores não foram encontrados no banco de dados.")
return
connection = connect_to_database()
cursor = connection.cursor()
insert_query = """
INSERT INTO edges (word_id1, word_id2, command_id)
VALUES (%s, %s, %s)
"""
try:
cursor.execute(insert_query, (word1_id, word2_id, cmd_id))
connection.commit()
except mysql.connector.Error as err:
print(f"Erro ao inserir aresta: {err}")
cursor.close()
connection.close()Agora iremos povoar as arestas. Para isso usaremos a função:
ExemploAresta – Faz o cadastro das arestas baseado nas stop-words e palavras não numéricas.
def ExemploAresta():
for index, frase in enumerate(frases):
palavras = [palavra for palavra in frase.split() if palavra.lower() not in stop_words and not palavra.isnumeric()]
for i in range(len(palavras) - 1):
# Criamos arestas entre palavras sequenciais e associamos a um comando
CriaArestas(palavras[i], palavras[i+1], comandos[index])
Neste código podemos ver onde tudo se encaixa.
Onde criamos os exemplos, e finalizamos o cadastro.
connect_to_database()
ExemploWords();
ExemploCMD();
ExemploAresta();Aqui disponibilizo o arquivo do grafo, já montado.
GITHUB:
https://github.com/marcelomaurin/grafo01
No próximo post iremos apresentar a conclusão com o projeto montado o sistema de busca, onde faremos conclusões e testes no projeto.
