Package demelo.graph

Class Graph

java.lang.Object
demelo.graph.Graph
public class Graph extends Object
Classe Graph representa a estrutura de dados para um Grafo na Teoria dos Grafos. Esta implementação é genérica o suficiente para representar diversos tipos de grafos: - Grafos Direcionados (Digrafos) - Grafos Não-Direcionados - Grafos Ponderados (Arestas com pesos) - Grafos Não-Ponderados

Teoria dos Grafos: - Vértices: Os nós do grafo, representados pela classe Node. - Arestas: As conexões entre os nós, representadas pela classe Edge. - Lista de Adjacência: Uma estrutura de dados eficiente para representar grafos esparsos, armazenada como Map<Node, List<Edge>>.

Complexidade: - Adicionar um Vértice: O(1) - Adicionar uma Aresta: O(1) em média, se ignorarmos o tempo necessário para verificar a duplicação. - Busca: O(1) para vértices e O(V) para arestas, onde V é o número de vértices.

Insights Práticos: - Redes Sociais: Utilizado para modelar relações entre indivíduos, podendo ajudar a identificar padrões e recomendar conexões. - Sistemas de Recomendação: Eficiente para filtragem colaborativa, onde os nós podem ser usuários ou itens, e as arestas podem representar preferências ou comportamentos. - Roteamento em Redes: Utilizado em algoritmos como OSPF (Open Shortest Path First) e BGP (Border Gateway Protocol) para encontrar o caminho mais eficiente entre dispositivos em uma rede. - Modelagem de Transporte: Pode ser utilizado para otimizar rotas de veículos, calcular tempos de tráfego e avaliar a eficiência do sistema. - Processamento de Texto: Utilizado em análise de sentimento, classificação de tópicos, e outras aplicações de NLP (Processamento de Linguagem Natural). - Flexibilidade Algorítmica: A classe é projetada para permitir a fácil inclusão de métodos que implementam algoritmos gráficos específicos. Isso inclui, mas não está limitado a, busca em profundidade (DFS), busca em largura (BFS), algoritmos de caminho mais curto como Dijkstra e Floyd-Warshall, e algoritmos de fluxo máximo como Ford-Fulkerson.

- NodeNotFoundException é lançada se um nó não for encontrado durante a adição de uma aresta. - DuplicatedEdgeException é lançada se uma aresta duplicada for tentada ser adicionada.

See Also:

  • Constructor Summary

    Constructors
    Constructor
    Description
    Graph()
    Inicializa um novo objeto Graph com uma lista de adjacência vazia.

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    addEdge(String sourceId, String destinationId, boolean create)
    Adiciona uma aresta direcionada ao grafo entre dois nós específicos.
    void
    addEdge(String sourceId, String destinationId, int edgeValue, boolean create)
    Adiciona uma aresta direcionada com um valor específico ao grafo.
    void
    addNode(String id)
    Adiciona um novo Nó ao grafo com um id específico e valor padrão de 0.
    void
    addNode(String id, int value)
    Adiciona um novo Nó ao grafo com um id e valor específicos.
    void
    addUndirectedEdge(String sourceId, String destinationId, int edgeValue, boolean create)
    Adiciona uma aresta não direcionada ao grafo.
    int[][]
    getAdjacencyMatrix()
    Retorna a matriz de adjacência do grafo.
    int
    getEdgeValue(Node source, Node target)
    Retorna o valor de uma aresta entre um nó de origem e um nó de destino.
    int
    getMaximumDegree()
    Obtém o grau máximo entre todos os nós do grafo.
    int
    getMinimumDegree()
    Obtém o grau mínimo entre todos os nós do grafo.
    List<Node>
    getNeighbors(String nodeId)
    Obtém a lista de nós vizinhos de um dado nó.
    int
    getNodeDegree(String nodeId)
    Obtém o grau de um dado nó.
    List<Node>
    getNodesList()
    Obtém uma lista de nós do grafo.
    boolean
    isDirected()
    Verifica se o grafo é direcionado ou não.
    boolean
    isRegular()
    Verifica se o grafo é regular.
    void
    printAdjacencyMatrix()
    Imprime a matriz de adjacência do grafo no console.
    void
    printGraph()
    Imprime uma representação textual do grafo no console, mostrando os nodos e suas arestas adjacentes.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • Graph

      public Graph()
      Inicializa um novo objeto Graph com uma lista de adjacência vazia.

      Este construtor cria um novo objeto Graph e inicializa sua lista de adjacência como um HashMap vazio. É útil quando você deseja construir um grafo do zero.

  • Method Details

    • addNode

      public void addNode(String id)
      Adiciona um novo Nó ao grafo com um id específico e valor padrão de 0.

      Este método cria um novo objeto Node com o id fornecido e um valor padrão de 0. Ele então adiciona este nó à lista de adjacência do grafo, caso ainda não exista.

      Parameters:
      id - O identificador único para o novo nó.

    • addNode

      public void addNode(String id, int value)
      Adiciona um novo Nó ao grafo com um id e valor específicos.

      Este método cria um novo objeto Node com o id e valor fornecidos. Ele então adiciona este nó à lista de adjacência do grafo, caso ainda não exista.

      Parameters:
      id - O identificador único para o novo nó.
      value - O valor a ser associado ao novo nó.

    • addEdge

      public void addEdge(String sourceId, String destinationId, boolean create) throws NodeNotFoundException, DuplicatedEdgeException
      Adiciona uma aresta direcionada ao grafo entre dois nós específicos. Conceitos Formais: - Aresta Direcionada: Uma ligação entre dois nós que vai de um nó de origem a um nó de destino. Neste caso, a aresta é orientada do nó com ID 'sourceId' para o nó com ID 'destinationId'. Insights Práticos: - Útil em cenários onde a direção importa, como em sistemas de rotas, fluxos de trabalho ou grafos de dependência.
      Parameters:
      sourceId - O ID do nó de origem.
      destinationId - O ID do nó de destino.
      create - Um booleano que indica se o nó deve ser criado caso ainda não exista.
      Throws:
      NodeNotFoundException - Se o nó não existir e 'create' for falso.
      DuplicatedEdgeException - Se a aresta já existir.

    • addUndirectedEdge

      public void addUndirectedEdge(String sourceId, String destinationId, int edgeValue, boolean create) throws NodeNotFoundException, DuplicatedEdgeException
      Adiciona uma aresta não direcionada ao grafo. Conceitos Formais: - Aresta Não Direcionada: Uma ligação entre dois nós que não tem uma direção específica. Neste caso, são criadas duas arestas direcionadas para emular uma aresta não direcionada. Insights Práticos: - Útil em cenários como redes sociais, onde uma amizade é mutual.
      Parameters:
      sourceId - O ID do primeiro nó.
      destinationId - O ID do segundo nó.
      edgeValue - O valor (peso) da aresta.
      create - Um booleano que indica se o nó deve ser criado caso ainda não exista.
      Throws:
      NodeNotFoundException - Se o nó não existir e 'create' for falso.
      DuplicatedEdgeException - Se a aresta já existir.

    • addEdge

      public void addEdge(String sourceId, String destinationId, int edgeValue, boolean create) throws NodeNotFoundException, DuplicatedEdgeException
      Adiciona uma aresta direcionada com um valor específico ao grafo. Conceitos Formais: - Grafo Ponderado: Um grafo onde cada aresta tem um peso ou valor associado. Insights Práticos: - Útil em cenários como mapas de rotas, onde o peso pode representar distância, tempo ou custo.
      Parameters:
      sourceId - O ID do nó de origem.
      destinationId - O ID do nó de destino.
      edgeValue - O valor (peso) da aresta.
      create - Um booleano que indica se os nós devem ser criados caso ainda não existam.
      Throws:
      NodeNotFoundException - Se o nó não existir e 'create' for falso.
      DuplicatedEdgeException - Se a aresta já existir.

    • getAdjacencyMatrix

      public int[][] getAdjacencyMatrix()
      Retorna a matriz de adjacência do grafo. Conceitos Formais: - Matriz de Adjacência: É uma matriz quadrada usada para representar um grafo finito. O elemento matrix[i][j] é 1 se existe uma aresta do vértice i ao vértice j, e 0 caso contrário. Insights Práticos: - Útil quando é necessário realizar operações matriciais no grafo, como encontrar o caminho mais curto.
      Returns:
      Uma matriz 2D de inteiros representando a matriz de adjacência do grafo.

    • getNodesList

      public List<Node> getNodesList()
      Obtém uma lista de nós do grafo. Conceitos Formais: - Vértice (Nó): Elemento básico do qual os grafos são formados. Insights Práticos: - Útil para iterações onde você precisa acessar todos os nós. Por exemplo, quando você está preenchendo a matriz de adjacência ou buscando um nó específico.
      Returns:
      Uma lista contendo todos os nós no grafo.

    • getEdgeValue

      public int getEdgeValue(Node source, Node target)
      Retorna o valor de uma aresta entre um nó de origem e um nó de destino. Conceitos Formais: - Peso de Aresta: Um número associado a uma aresta em um grafo ponderado. - Grafo Ponderado: Um grafo em que cada aresta tem um peso ou valor associado. - Aresta: Um par ordenado ou não ordenado de nós conectados em um grafo. Insights Práticos: - Essa função é particularmente útil em algoritmos que precisam considerar o peso das arestas, como algoritmos de caminho mínimo ou máxima vazão. - Também é usado internamente para preencher a matriz de adjacência com os pesos das arestas.
      Parameters:
      source - Nó de origem da aresta.
      target - Nó de destino da aresta.
      Returns:
      Retorna o valor (peso) da aresta entre os nós de origem e destino. Retorna 0 se não existe uma aresta entre os dois nós.

    • getNeighbors

      public List<Node> getNeighbors(String nodeId) throws NodeNotFoundException
      Obtém a lista de nós vizinhos de um dado nó.

      Teoria dos Grafos: Em teoria dos grafos, a vizinhança N(v) de um vértice v é o conjunto de todos os vértices que são extremidades de pelo menos uma aresta com v. No caso de grafos direcionados, isso pode ser diferenciado em vizinhança de entrada e de saída.

      Aplicações Práticas: Esse método é fundamental para operações como buscas em grafos (DFS, BFS), detecção de comunidades, cálculo de centralidade, por exemplo. É uma operação frequentemente utilizada em algoritmos de grafos.

      Parameters:
      nodeId - O ID do nó cujos vizinhos são desejados.
      Returns:
      Uma lista de nós que são vizinhos do nó em questão.
      Throws:
      NodeNotFoundException - se o nó com o ID fornecido não for encontrado no grafo.

    • getNodeDegree

      public int getNodeDegree(String nodeId) throws NodeNotFoundException
      Obtém o grau de um dado nó.

      Teoria dos Grafos: Em teoria dos grafos, o grau de um vértice v, denotado como deg(v), é o número de arestas que têm v como uma extremidade. Em grafos direcionados, pode-se diferenciar entre grau de entrada e grau de saída.

      Aplicações Práticas: O grau de um nó é uma medida de centralidade que pode ser usada para entender a importância ou influência de um vértice em uma rede. É um indicador básico, mas poderoso, usado em análise de redes, detecção de anomalias, por exemplo.

      Parameters:
      nodeId - O ID do nó cujo grau é desejado.
      Returns:
      O grau do nó.
      Throws:
      NodeNotFoundException - se o nó com o ID fornecido não for encontrado no grafo.

    • getMinimumDegree

      public int getMinimumDegree()
      Obtém o grau mínimo entre todos os nós do grafo.

      Teoria dos Grafos: O grau mínimo é o menor grau entre todos os vértices do grafo. Ele é uma métrica importante para entender a esparsidade da rede e pode ser crucial em algoritmos que buscam otimizar caminhos, como Dijkstra e Prim.

      Aplicações Práticas: O grau mínimo é frequentemente utilizado para entender pontos de falha em redes ou para identificar nós que são menos conectados e, portanto, menos influentes em uma rede social, por exemplo.

      Returns:
      O grau mínimo entre todos os nós do grafo.

    • getMaximumDegree

      public int getMaximumDegree()
      Obtém o grau máximo entre todos os nós do grafo.

      Teoria dos Grafos: O grau máximo é o maior grau entre todos os vértices de um grafo. Ele pode ser um indicador de vértices que são centrais ou importantes para a conectividade do grafo.

      Aplicações Práticas: Em redes sociais, o nó com o grau máximo pode ser uma pessoa muito conectada ou influente. Em redes de computadores, pode ser um roteador principal ou um servidor.

      Returns:
      O grau máximo entre todos os nós do grafo.

    • isRegular

      public boolean isRegular()
      Verifica se o grafo é regular.

      Teoria dos Grafos: Um grafo é dito regular se todos os seus vértices possuem o mesmo grau. Essa é uma propriedade estrutural interessante que simplifica muitos problemas em teoria dos grafos.

      Aplicações Práticas: Grafos regulares são importantes em design de redes, onde a uniformidade pode simplificar o roteamento e balanceamento de carga. Também são utilizados em modelagem e simulação de sistemas igualmente distribuídos.

      Returns:
      Verdadeiro se o grafo é regular, falso caso contrário.

    • isDirected

      public boolean isDirected()
      Verifica se o grafo é direcionado ou não.

      Teoria dos Grafos: Um grafo é considerado direcionado (ou digrafo) quando as arestas possuem uma orientação, ou seja, a aresta que vai do vértice A para o vértice B não é a mesma que vai de B para A.

      Aplicações Práticas: 1. Redes Sociais: Representar quem segue quem. 2. Rotas: Representar a direção única de um caminho. 3. Dependências em sistemas: Representar a ordem em que tarefas devem ser realizadas.

      Complexidade: O algoritmo tem uma complexidade de tempo O(V * E), onde V é o número de vértices e E é o número de arestas. Isso ocorre porque para cada nó, verificamos todas as suas arestas adjacentes.

      Returns:
      Verdadeiro se o grafo é direcionado, Falso caso contrário.

    • printAdjacencyMatrix

      public void printAdjacencyMatrix()
      Imprime a matriz de adjacência do grafo no console.

      Teoria dos Grafos: A matriz de adjacência é uma representação quadrada do grafo onde o elemento (i, j) é 1 se há uma aresta entre os vértices i e j, e 0 caso contrário. Em grafos ponderados, o peso substitui o valor 1.

      Complexidade do Algoritmo: O tempo de execução é O(n^2), onde n é o número de vértices. Isso se deve à iteração por cada célula da matriz.

    • printGraph

      public void printGraph()
      Imprime uma representação textual do grafo no console, mostrando os nodos e suas arestas adjacentes.

      Teoria dos Grafos: Essa função fornece uma representação baseada em lista de adjacências do grafo. Cada nó é impresso junto com uma lista de arestas que saem dele.

      Complexidade do Algoritmo: O tempo de execução é O(n + e), onde n é o número de vértices e e é o número de arestas. Isso ocorre porque cada vértice e cada aresta são visitados uma vez.