Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package br.uefs.ecomp.Game.util;
- import java.util.ArrayList;
- import java.util.LinkedList;
- /**
- * Classe que implementa um grafo
- *
- * @author Daniel Andrade
- * @author Cássio Santos
- * @see br.uefs.ecomp.Game.util.Vertex
- * @see br.uefs.ecomp.Game.util.GraphPathSearch
- */
- public class Graph {
- private final int totalVertex;
- private final double aMatrix[][];
- private int actualVertex;
- private final Vertex[] vertex;
- public Graph(int numberOfVertex) {
- this.totalVertex = numberOfVertex;
- this.aMatrix = new double[this.totalVertex][this.totalVertex];
- this.vertex = new Vertex[this.totalVertex];
- this.actualVertex = 0;
- }
- /**
- *
- * @param label Label do vértice
- * @param x Coordenada x
- * @param y Coordenada y
- * @return O vértice criado
- * @throws DuplicateVertexException
- */
- public Vertex addVertex(String label, int x, int y) throws DuplicateVertexException {
- if (!this.containsVertex(label)) {
- Vertex v = new Vertex(label, this.actualVertex, x, y);
- this.vertex[this.actualVertex++] = v;
- return v;
- }
- throw new DuplicateVertexException();
- }
- /**
- * Busca um vértice através da Label.
- *
- * @param label Label do vértice a ser buscado
- * @return O vértice que corresponde a label ou null caso ele não existir.
- */
- public Vertex getVertexByLabel(String label) {
- for (Vertex v : this.vertex) {
- if (v != null && v.getLabel().equals(label)) {
- return v;
- }
- }
- return null;
- }
- /**
- * Busca um vértice através da id
- *
- * @param id Id do vértice a ser buscado
- * @return O vértice que corresponde a ID ou null caso ele não existir
- */
- public Vertex getVertexById(int id) {
- for (Vertex v : this.vertex) {
- if (v != null && v.getId() == id) {
- return v;
- }
- }
- return null;
- }
- /**
- * Cria uma nova aresta
- *
- * @param a Vértice que deve ser ligada a vértice b
- * @param b Vértice que deve ser ligada a vértice a
- */
- public void addEdge(String a, String b) {
- if (this.containsVertex(a) && this.containsVertex(b)) {
- Vertex va = this.getVertexByLabel(a);
- Vertex vb = this.getVertexByLabel(b);
- this.aMatrix[va.getId()][vb.getId()] = this.getWeigth(va, vb);
- this.aMatrix[vb.getId()][va.getId()] = this.getWeigth(va, vb);
- }
- }
- /**
- * Verifica se dois vétices estão ligados por uma aresta
- *
- * @param a Vértice 1
- * @param b Vértice 2
- * @return
- */
- public boolean isConnected(String a, String b) {
- if (this.containsVertex(a) && this.containsVertex(b)) {
- Vertex va = this.getVertexByLabel(a);
- Vertex vb = this.getVertexByLabel(b);
- return this.aMatrix[va.getId()][vb.getId()] != 0;
- }
- return false;
- }
- /**
- * Verifica se o vértice com a label correspondente já existe.
- *
- * @param s Label do vértice
- * @return True caso exista, false caso contrário.
- */
- private boolean containsVertex(String s) {
- for (Vertex v : this.vertex) {
- if (v != null && v.getLabel().equals(s)) {
- return true;
- }
- }
- return false;
- }
- /**
- * Verifica todos os vértices adjacentes a um dado vértice.
- *
- * @param s Vértice a ser analisado
- * @return Uma coleção de todos os vétices adjacentes.
- */
- public LinkedList<String> adjacentNodes(String s) {
- LinkedList<String> adj = new LinkedList<>();
- if (this.containsVertex(s)) {
- Vertex v = this.getVertexByLabel(s);
- for (int i = 0; i < this.totalVertex; i++) {
- if (this.aMatrix[v.getId()][i] != 0) {
- adj.add(this.getVertexById(i).getLabel());
- }
- }
- }
- return adj;
- }
- /**
- * Verifica quais os caminhos possíveis partindo do vértice A e chegando no
- * vértice B
- *
- * @param a Vértice de origem
- * @param b Vértice de destino
- * @return Uma coleção de caminhos possíveis
- * @throws VertexNotFoundException
- */
- public ArrayList<ArrayList<String>> getAllPossiblePaths(String a, String b) throws VertexNotFoundException {
- if (this.containsVertex(a) && this.containsVertex(b)) {
- return new GraphPathSearch(a, b, this).getAllPossiblePaths();
- }
- throw new VertexNotFoundException();
- }
- /**
- * Calcula o menor caminho do vértice A até o vértice B
- *
- * @param a Vértice de origem
- * @param b Vértice de destino
- * @return O menor caminho entre os dois vértices
- * @throws PathlessException
- */
- public ArrayList<String> smallerPath(String a, String b) throws PathlessException {
- if (this.containsVertex(a) && this.containsVertex(b)) {
- ArrayList<ArrayList<String>> paths = new GraphPathSearch(a, b, this).getAllPossiblePaths();
- ArrayList<String> lowerCostPath = null;
- double costOfLowerPath = Double.MAX_VALUE;
- for (ArrayList<String> p : paths) {
- double actualCost = 0;
- for (int i = 0; i < p.size(); i++) {
- Vertex va = this.getVertexByLabel(p.get(i));
- Vertex vb;
- if (i == p.size() - 1) {
- vb = this.getVertexByLabel(p.get(0));
- } else {
- vb = this.getVertexByLabel(p.get(i + 1));
- }
- actualCost += this.aMatrix[va.getId()][vb.getId()];
- }
- if (costOfLowerPath > actualCost) {
- costOfLowerPath = actualCost;
- lowerCostPath = p;
- }
- }
- if (lowerCostPath != null) {
- return lowerCostPath;
- }
- }
- throw new PathlessException();
- }
- /**
- * Calcula o peso de uma aresta com base na distância euclidiana entre os
- * vértices.
- *
- * @param a Label do vértice de origem
- * @param b Label do vértice de destino
- * @return O peso da aresta
- */
- private double getWeigth(Vertex a, Vertex b) {
- double x = Math.pow((b.getX() - a.getX()), 2);
- double y = Math.pow((b.getY() - a.getY()), 2);
- return Math.sqrt(x + y);
- }
- /**
- * Calcula a distância euclidiana entre dois vértices
- *
- * @param a Label do vértice de origem
- * @param b Label do vértice de destino
- * @return A distância entre os dois vértices
- * @throws VertexNotFoundException
- */
- public double LinearDistance(String a, String b) throws VertexNotFoundException {
- if (this.containsVertex(a) && this.containsVertex(b)) {
- return this.getWeigth(this.getVertexByLabel(a), this.getVertexByLabel(b));
- }
- throw new VertexNotFoundException();
- }
- public double[][] getAMatrix() {
- return this.aMatrix;
- }
- /**
- * Calcula o peso total de um caminho.
- *
- * @param p Caminho percorrido
- * @return O peso.
- */
- public double getPathWeigth(ArrayList<String> p) {
- double actualCost = 0;
- for (int i = 0; i < p.size(); i++) {
- Vertex va = this.getVertexByLabel(p.get(i));
- Vertex vb;
- if (p.size() > 2) {
- if (i == p.size() - 1) {
- vb = this.getVertexByLabel(p.get(0));
- } else {
- vb = this.getVertexByLabel(p.get(i + 1));
- }
- actualCost += this.aMatrix[va.getId()][vb.getId()];
- }
- else{
- try {
- actualCost = this.LinearDistance(p.get(0), p.get(1));
- } catch (VertexNotFoundException ex) {}
- }
- }
- return actualCost;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement