Implementa búsquedas sobre Grafos utilizando BFS (Breadth First Search) con Java


BFS (Breadth first search) es un algoritmo para la búsqueda sobre grafos por amplitud, en este post se explicará como implementarlo con Java, se tomará como base el post Implementa un grafo de ciudades en Java y también te puede interesar el post Implementa búsquedas sobre Grafos utilizando DFS (Depth First Search) con Java.

Creando las clases base para la construcción del grafo

El grafo que se creará contendrá información de ciudades y la distancia entre ellas, para hacerlo necesitaremos 3 clases Node, Edge y Graph. A continuación se mostrará cada una de ellas con su explicación:

Node.java


import java.util.ArrayList;

import java.util.List;

/**

 * @author raidentrance

 *

 */

public class Node {

	private String city;

	private List adjacents = new ArrayList();

	public Node(String city) {

		this.city = city;

	}

	public void addEdge(Edge edge) {

		adjacents.add(edge);

	}

	public List getAdjacents() {

		return adjacents;

	}

	public String getCity() {

		return city;

	}

	@Override

	public String toString() {

		return "Node [city=" + city + ", adjacents=" + adjacents + "]";

	}

}

La clase Node representará una ciudad en nuestro grafo, como se puede ver la ciudad contiene una lista de Edges los cuáles representarán las uniones entre los nodos, más adelante se darán más detalles sobre la clase Edge.

Edge.java


/**

 * @author raidentrance

 *

 */

public class Edge {

	private Node origin;

	private Node destination;

	private double distance;

	public Edge(Node origin, Node destination, double distance) {

		this.origin = origin;

		this.destination = destination;

		this.distance = distance;

	}

	public Node getOrigin() {

		return origin;

	}

	public void setOrigin(Node origin) {

		this.origin = origin;

	}

	public Node getDestination() {

		return destination;

	}

	public void setDestination(Node destination) {

		this.destination = destination;

	}

	public double getDistance() {

		return distance;

	}

	public void setDistance(double distance) {

		this.distance = distance;

	}

	@Override

	public String toString() {

		return "Edge [origin=" + origin.getCity() + ", destination=" + destination.getCity() + ", distance=" + distance

				+ "]";

	}

}

La clase Edge representa la unión entre dos nodos, como se puede ver contiene un nodo origen, uno destino y la distancia entre ambos.

Graph.java


import java.util.ArrayList;

import java.util.List;

/**

 * @author raidentrance

 *

 */

public class Graph {

	private List nodes = new ArrayList();

	public void addNode(Node node) {

		nodes.add(node);

	}

	public List getNodes() {

		return nodes;

	}

	@Override

	public String toString() {

		return "Graph [nodes=" + nodes + "]";

	}

}

La clase Graph representará el conjunto de las ciudades junto con sus uniones y direcciones.

Creando el grafo

Una vez que contamos con las clases necesarias para crear nuestro grafo el siguiente paso será llenarlo con la información de las ciudades que utilizaremos, se utilizará el mismo grafo que en el ejemplo de DFS:

cities-graph

Analicemos el grafo:

  • Es posible ir del df a Toluca y a cuernavaca
  • Es posible ir de Toluca a Tlaxcala, Puebla, DF y Cuernavaca
  • Es posible ir de Cuernavaca al DF y a Puebla
  • Es posible ir de Puebla a Toluca y Tlaxcala
  • En este ejemplo solo podemos llegar a Tlaxcala pero no podemos ir a ningún otro lugar
  • En este ejemplo existe la ciudad de Cancún pero no hay una ruta hacia ella.

Veamos el código para construirlo:

MapBuilder.java


import com.raidentrance.graphs.Edge;

import com.raidentrance.graphs.Graph;

import com.raidentrance.graphs.Node;

/**

 * @author raidentrance

 *

 */

public class MapBuilder {

	private static final Graph instance = new Graph();

	private MapBuilder() {

	}

	public static Graph getGraph() {

		Node df = new Node("DF");

		Node toluca = new Node("Toluca");

		Node cuernavaca = new Node("Cuernavaca");

		Node puebla = new Node("Puebla");

		Node tlaxcala = new Node("Tlaxcala");

		Node cancun = new Node("Cancún");

		df.addEdge(new Edge(df, toluca, 100));

		df.addEdge(new Edge(df, cuernavaca, 90));

		toluca.addEdge(new Edge(toluca, puebla, 350));

		toluca.addEdge(new Edge(toluca, cuernavaca, 150));

		toluca.addEdge(new Edge(toluca, tlaxcala, 340));

		toluca.addEdge(new Edge(toluca, df, 100));

		cuernavaca.addEdge(new Edge(cuernavaca, df, 90));

		cuernavaca.addEdge(new Edge(cuernavaca, puebla, 100));

		puebla.addEdge(new Edge(puebla, tlaxcala, 20));

		puebla.addEdge(new Edge(puebla, toluca, 350));

		instance.addNode(df);

		instance.addNode(toluca);

		instance.addNode(cuernavaca);

		instance.addNode(puebla);

		instance.addNode(cancun);

		instance.addNode(tlaxcala);

		return instance;

	}

}

La clase MapBuilder tiene un método que devuelve un objeto de tipo Graph que representa el grafo definido en la imagen anterior.

Implementando BFS sobre el grafo

El siguiente paso será implementar el algoritmo BFS para búsqueda de ciudades en el grafo que definimos, para esto crearemos la clase GraphBfsSearch.

GraphBfsSearch.java


import java.util.HashSet;

import java.util.LinkedList;

import java.util.List;

import java.util.Optional;

import com.raidentrance.graphs.Edge;

import com.raidentrance.graphs.Graph;

import com.raidentrance.graphs.Node;

import com.raidentrance.map.MapBuilder;

/**

 * @author raidentrance

 *

 */

public class GraphBfsSearch {

	private Graph graph;

	public GraphBfsSearch() {

		graph = MapBuilder.getGraph();

	}

	private Optional<Node> getNode(String city) {

		List<Node> nodes = graph.getNodes();

		for (Node node : nodes) {

			if (node.getCity().equals(city)) {

				return Optional.of(node);

			}

		}

		return Optional.empty();

	}

	public boolean hasPathBfs(String source, String destination) {

		Optional<Node> start = getNode(source);

		Optional<Node> end = getNode(destination);

		if (start.isPresent() && end.isPresent()) {

			return hasPathBfs(start.get(), end.get());

		} else {

			return false;

		}

	}

	public boolean hasPathBfs(Node source, Node destination) {

		LinkedList<Node> nextToVisit = new LinkedList<>();

		HashSet<String> visited = new HashSet<>();

		nextToVisit.add(source);

		while (!nextToVisit.isEmpty()) {

			Node node = nextToVisit.remove();

			if (node.getCity().equals(destination.getCity())) {

				return true;

			}

			if (visited.contains(node.getCity())) {

				continue;

			}

			visited.add(node.getCity());

			for (Edge edge : node.getAdjacents()) {

				nextToVisit.add(edge.getDestination());

			}

		}

		return false;

	}

}

Analicemos cada uno de los componentes:

  • El atributo graph contiene el grafo a utilizar.
  • El constructor inicializa la variable graph con el grafo definido en la imágen anterior.
  • El método OptionalgetNode(String city): Recibe como parámetro una ciudad y devuelve el Nodo en el grafo en caso de existir que contenga el nombre de la ciudad.
  • El método boolean hasPathBfs(String source, String destination): Recibe dos ciudades, el origen y el destino, con esto ejecuta el método de búsqueda BFS para determinar si existe la ruta en el grafo.
  • El método booleanhasPathBfs(Node source, Node destination): Recibe un nodo origen y uno nodo destino siguiendo la siguiente lógica:
    • Se agrega el nodo origen a los nodos por visitar
    • Se ejecuta la siguiente lógica mientras existan ciudades por visitar
      • Remueve y devuelve el primer nodo por visitar
      • Si ese nodo es igual al destino devolvemos que si existe una ruta por visitar y termina el proceso
      • Valida si la ciudad que se está buscando ya fue visitada, en ese caso continua con la siguiente iteración
      • Agrega la ciudad que se validó a la lista de nodos visitados
      • itera todos los nodos adjacentes para agregarlos a las ciudades por visitar
    • En caso de no encontrar una ruta devuelve false.

Caso de ejemplo

Analicemos el método boolean hasPathBfs(Node source, Node destination) en el caso yendo de Puebla a Cuernavaca.

Inicio :Source =Puebla, Destination=Cuernavaca,

  • Se Agrega a nextToVisit la ciudad de puebla
  • la variable nextToVisit contiene a la ciudad de puebla, mientras no esté vacía se ejecutarán las siguientes iteraciones:

Iteración 1:  Visited={},NextToVisit={Puebla}

  • Se remueve de nextToVisit la ciudad de puebla y se asigna en la variable node
  • Se valida si la ciudad de la variable node (Puebla) es igual a la ciudad de destino (Cuernavaca), devuelve falso así que continua.
  • Se valida si la lista visited contiene la ciudad de Puebla, devuelve falso así que continua.
  • Agrega a visited la ciudad de Puebla
  • Obtiene todos los nodos adyacentes de puebla (Tlaxcala y Toluca) y los agrega a la lista nextToVisit

cities-graph

Iteración 1: Visited={Puebla},NextToVisit={Tlaxcala, Toluca}

  • Se remueve el primer elemento de nextToVisit (Tlaxcala) y se asigna en la variable node
  • Se valida si la ciudad de la variable node (Tlaxcala) es igual a la ciudad de destino (Cuernavaca), devuelve falso así que continua.
  • Se valida si la lista visited contiene la ciudad de Tlaxcala, devuelve falso así que continua.
  • Agrega a visited la ciudad de Tlaxcala
  • Agrega todos los nodos adyacentes de Tlaxcala a la lista nextToVisit, en este caso no hay ninguno así que continua.

graph - Page 1

Iteración 1: Visited={Tlaxcala,Puebla},NextToVisit={Toluca}

  • Se remueve el primer elemento de nextToVisit (Toluca) y se asigna en la variable node
  • Se valida si la ciudad de la variable node (Toluca) es igual a la ciudad de destino (Cuernavaca), devuelve falso así que continua.
  • Se valida si la lista visited contiene la ciudad de Toluca, devuelve falso así que continua.
  • Agrega a visited la ciudad de Toluca
  • Agrega todos los nodos adyacentes de Toluca (Puebla, Cuernavaca,Tlaxcala, DF) a la lista nextToVisit.

graph - Page 1

Iteración 1: Visited={Tlaxcala,Puebla,Toluca},NextToVisit={Puebla, Cuernavaca,Tlaxcala, DF}

  • Se remueve el primer elemento de nextToVisit (Puebla) y se asigna en la variable node
  • Se valida si la ciudad de la variable node (Puebla) es igual a la ciudad de destino (Cuernavaca), devuelve falso así que continua.
  • Se valida si la lista visited contiene la ciudad dePuebla, devuelve verdadero así que se salta las siguientes líneas del loop y se va a la siguiente iteración.

graph - Page 1

Iteración 1: Visited={Tlaxcala,Puebla,Toluca},NextToVisit={ Cuernavaca,Tlaxcala, DF}

  • Se remueve el primer elemento de nextToVisit (Cuernavaca) y se asigna en la variable node
  • Se valida si la ciudad de la variable node (Cuernavaca) es igual a la ciudad de destino (Cuernavaca), devuelve verdadero así que termina el programa indicando que si existe una ruta entre puebla y Cuernavaca.

graph - Page 1

Probando los distintos escenarios

Para terminar agregaremos un main a nuestra aplicación, para probar todos los posibles escenarios.


	public static void main(String[] args) {

		GraphBfsSearch graph = new GraphBfsSearch();

		System.out.println("\n\t Paths from DF \n");

		System.out.println(String.format("From DF to DF %s", graph.hasPathBfs("DF", "DF")));

		System.out.println(String.format("From DF to Toluca %s", graph.hasPathBfs("DF", "Toluca")));

		System.out.println(String.format("From DF to Cuernavaca %s", graph.hasPathBfs("DF", "Cuernavaca")));

		System.out.println(String.format("From DF to Puebla %s", graph.hasPathBfs("DF", "Puebla")));

		System.out.println(String.format("From DF to Tlaxcala %s", graph.hasPathBfs("DF", "Tlaxcala")));

		System.out.println(String.format("From DF to Cancún %s", graph.hasPathBfs("DF", "Cancún")));

		// Paths from Toluca

		System.out.println("\n\t Paths from Toluca \n");

		System.out.println(String.format("From Toluca to Toluca %s", graph.hasPathBfs("Toluca", "Toluca")));

		System.out.println(String.format("From Toluca to DF %s", graph.hasPathBfs("Toluca", "DF")));

		System.out.println(String.format("From Toluca to Cuernavaca %s", graph.hasPathBfs("Toluca", "Cuernavaca")));

		System.out.println(String.format("From Toluca to Puebla %s", graph.hasPathBfs("Toluca", "Puebla")));

		System.out.println(String.format("From Toluca to Tlaxcala %s", graph.hasPathBfs("Toluca", "Tlaxcala")));

		System.out.println(String.format("From Toluca to Cancún %s", graph.hasPathBfs("Toluca", "Cancún")));

		System.out.println("\n\t Paths from Cuernavaca \n");

		System.out.println(

				String.format("From Cuernavaca to Cuernavaca %s", graph.hasPathBfs("Cuernavaca", "Cuernavaca")));

		System.out.println(String.format("From Cuernavaca to DF %s", graph.hasPathBfs("Cuernavaca", "DF")));

		System.out.println(String.format("From Cuernavaca to Toluca %s", graph.hasPathBfs("Cuernavaca", "Toluca")));

		System.out.println(String.format("From Cuernavaca to Puebla %s", graph.hasPathBfs("Cuernavaca", "Puebla")));

		System.out.println(String.format("From Cuernavaca to Tlaxcala %s", graph.hasPathBfs("Cuernavaca", "Tlaxcala")));

		System.out.println(String.format("From Cuernavaca to Cancún %s", graph.hasPathBfs("Cuernavaca", "Cancún")));

		System.out.println("\n\t Paths from Puebla \n");

		System.out.println(String.format("From Puebla to Puebla %s", graph.hasPathBfs("Puebla", "Puebla")));

		System.out.println(String.format("From Puebla to Cuernavaca %s", graph.hasPathBfs("Puebla", "Cuernavaca")));

		System.out.println(String.format("From Puebla to DF %s", graph.hasPathBfs("Puebla", "DF")));

		System.out.println(String.format("From Puebla to Toluca %s", graph.hasPathBfs("Puebla", "Toluca")));

		System.out.println(String.format("From Puebla to Tlaxcala %s", graph.hasPathBfs("Puebla", "Tlaxcala")));

		System.out.println(String.format("From Puebla to Cancún %s", graph.hasPathBfs("Puebla", "Cancún")));

		System.out.println("\n\t Paths from Tlaxcala \n");

		System.out.println(String.format("From Tlaxcala to Tlaxcala %s", graph.hasPathBfs("Tlaxcala", "Tlaxcala")));

		System.out.println(String.format("From Tlaxcala to Puebla %s", graph.hasPathBfs("Tlaxcala", "Puebla")));

		System.out.println(String.format("From Tlaxcala to Cuernavaca %s", graph.hasPathBfs("Tlaxcala", "Cuernavaca")));

		System.out.println(String.format("From Tlaxcala to DF %s", graph.hasPathBfs("Tlaxcala", "DF")));

		System.out.println(String.format("From Tlaxcala to Toluca %s", graph.hasPathBfs("Tlaxcala", "Toluca")));

		System.out.println(String.format("From Tlaxcala to Cancún %s", graph.hasPathBfs("Tlaxcala", "Cancún")));

		System.out.println("\n\t Paths from Cancún \n");

		System.out.println(String.format("From Cancún to Cancún %s", graph.hasPathBfs("Cancún", "Cancún")));

		System.out.println(String.format("From Cancún to Tlaxcala %s", graph.hasPathBfs("Cancún", "Tlaxcala")));

		System.out.println(String.format("From Cancún to Puebla %s", graph.hasPathBfs("Cancún", "Puebla")));

		System.out.println(String.format("From Cancún to Cuernavaca %s", graph.hasPathBfs("Cancún", "Cuernavaca")));

		System.out.println(String.format("From Cancún to DF %s", graph.hasPathBfs("Cancún", "DF")));

		System.out.println(String.format("From Cancún to Toluca %s", graph.hasPathBfs("Cancún", "Toluca")));

	}

Al ejecutar el programa mostrará la siguiente salida:


	 Paths from DF 

From DF to DF true

From DF to Toluca true

From DF to Cuernavaca true

From DF to Puebla true

From DF to Tlaxcala true

From DF to Cancún false

	 Paths from Toluca 

From Toluca to Toluca true

From Toluca to DF true

From Toluca to Cuernavaca true

From Toluca to Puebla true

From Toluca to Tlaxcala true

From Toluca to Cancún false

	 Paths from Cuernavaca 

From Cuernavaca to Cuernavaca true

From Cuernavaca to DF true

From Cuernavaca to Toluca true

From Cuernavaca to Puebla true

From Cuernavaca to Tlaxcala true

From Cuernavaca to Cancún false

	 Paths from Puebla 

From Puebla to Puebla true

From Puebla to Cuernavaca true

From Puebla to DF true

From Puebla to Toluca true

From Puebla to Tlaxcala true

From Puebla to Cancún false

	 Paths from Tlaxcala 

From Tlaxcala to Tlaxcala true

From Tlaxcala to Puebla false

From Tlaxcala to Cuernavaca false

From Tlaxcala to DF false

From Tlaxcala to Toluca false

From Tlaxcala to Cancún false

	 Paths from Cancún 

From Cancún to Cancún true

From Cancún to Tlaxcala false

From Cancún to Puebla false

From Cancún to Cuernavaca false

From Cancún to DF false

From Cancún to Toluca false

De este modo se pueden realizar búsquedas sobre un grafo utilizando el algoritmo BFS.

Si te gusta el contenido y quieres enterarte cuando realicemos un post nuevo síguenos en nuestras redes sociales https://twitter.com/geeks_mx y https://www.facebook.com/geeksJavaMexico/.

Autor: Alejandro Agapito Bautista

Twitter: @raidentrance

Contacto:raidentrance@gmail.com

Búsqueda binaria en Java paso a paso


El algoritmo de búsqueda binaria funciona sobre arreglos ordenados y es utilizado para buscar un elemento en los mismos.

Funcionamiento

El funcionamiento del algoritmo es simple y cuenta con las siguientes partes:

  • Datos de entrada :
    • Un arreglo ordenado
    • Un valor a buscar en el arreglo
  • Datos de salida:
    • La posición del elemento en el arreglo o -1 en caso de no encontrarlo

El algoritmo de búsqueda binaria sigue los siguientes pasos:

  • Verifica si el elemento a buscar es menor al máximo elemento en el arreglo y mayor al mínimo elemento del arreglo, en caso de no ser así  se devolverá -1 ya que sabemos que no se encuentra el elemento.
  • Obtiene el elemento que se encuentra en la mitad del arreglo y lo compara con el valor que se busca.
  • En caso de que el elemento sea mayor al valor que se busca se descartará la parte derecha y se volverá a ejecutar la misma validación pero solo sobre el lado izquierdo del arreglo.
  • El paso anterior se repetirá hasta encontrar el elemento
  • En caso de no encontrar el elemento se devolverá -1 para indicar que no se encontró.

Ejemplo práctico

A continuación presentaremos un ejemplo paso a paso de la búsqueda binaria, imaginemos el siguiente arreglo donde se desea buscar el número 400:

paso1

  • Evaluar que el número 400 es mayor al menor elemento del arreglo y menor al máximo elemento del arreglo, en este caso 10 es menor y 2222 es mayor a 400, entonces podemos pasar al siguiente paso.
  • Obtendremos el elemento de la mitad del arreglo utilizando la siguiente ecuación (límite inferior + límite superior)/2
  • En este caso la mitad del arreglo es 120, una vez hecho esto evaluaremos si 120 es mayor o menor al número que buscamos, que en este caso es 400, 400 es mayor a 120, esto significa que se encuentra del lado derecho del arreglo, así que el lado izquierdo será descartado como se muestra en la siguiente imagen:

paso2

  • Una vez hecho esto volveremos a dividir el arreglo, pero en este caso nuestro límite inferior no será 10 sino ahora será 200, y el nuevo valor de en medio será 500 como se muestra en la siguiente imagen:

paso3

  • Una vez más evaluaremos si el número 500 es mayor o menor al número que buscamos que es 400, en este caso 400 es menor a 500, entonces la parte de la derecha será descartada como se muestra en la siguiente imagen:

paso4

  • Con lo anterior el nuevo límite inferior es el 200 y el nuevo límite superior es 400 así que ejecutaremos nuestra ecuación para obtener el elemento de la mitad, en este caso es la posición 7 del arreglo que es 200 así que volveremos a reducir en uno el límite superior, con esto tanto el límite superior como el límite inferior se encuentran en la posición 8 como se muestra en la siguiente imagen:

paso 5

  • Listo ! encontramos el elemento que buscábamos en el arreglo, esto nos tomó 4 iteraciones en lugar de 9 si hubiéramos iterado el arreglo indice por indice, con esto se demuestra que es mucho más eficiente que iterar el arreglo posición por posición. La complejidad de una búsqueda lineal es de O(n) mientras que la complejidad de una búsqueda binaria es O(Log n) lo cuál indica que es mucho más eficiente, solo consideremos que para poder ejecutarla el arreglo debe estar ordenado.

Implementación de la búsqueda binaria en Java

A continuación se presenta el código para ejecutar la búsqueda binaria en Java:

public class ChallengeClass {
	public static int binarySearch(int[] array, int minLimit, int maxLimit, int value) {
		if (maxLimit >= 0 && array[minLimit] <= value && array[maxLimit] >= value) {
			int mid = getMidValue(minLimit, maxLimit);
			System.out.println(String.format("Límite inferior %d límite superior %d valor en el arreglo %d valor a buscar %d", minLimit,maxLimit,array[mid],value));
			if (array[mid] == value) {
				return mid;
			} else if (array[mid] <span 				data-mce-type="bookmark" 				id="mce_SELREST_start" 				data-mce-style="overflow:hidden;line-height:0" 				style="overflow:hidden;line-height:0" 			></span>< value) {
				return binarySearch(array, mid + 1, maxLimit, value);
			}
			return binarySearch(array, minLimit, mid - 1, value);
		}
		return -1;
	}

	public static int getMidValue(int minLimit, int maxLimit) {
		return (maxLimit + minLimit) / 2;
	}

	public static void main(String[] args) {
		int value = 400;
		int[] array = { 10, 15, 20, 40, 50, 100, 120, 200, 400, 500, 600, 800 ,2222};
		int result = binarySearch(array, 0, array.length - 1, value);
		System.out.println(String.format("Result %d", result));
	}
}

La implementación presentada fue hecha sin utilizar ningún api de Java para el manejo de búsquedas u ordenamientos.

Implementación de búsqueda binaria utilizando clases existentes en Java

Como sabemos Java provee de un framework para el manejo de colecciones y arreglos, a continuación se presenta el código para ejecutar la búsqueda binaria utilizando dichas clases:

import java.util.Arrays;

public class ChallengeClass {

	public static void main(String[] args) {
		int[] array = { 10, 15, 20, 40, 50, 100, 120, 200, 400, 500, 600, 800, 2222 };
		int result = Arrays.binarySearch(array, 400);
		System.out.println(String.format("Result %d", result));
	}
}

Es importante mencionar que el método binarySearch de la clase Arrays también requiere que el arreglo que se pase como parámetro se encuentre ordenado, en caso contrario los resultados pueden ser erróneos.

Si te gusta el contenido y quieres enterarte cuando realicemos un post nuevo síguenos en nuestras redes sociales https://twitter.com/geeks_mx y https://www.facebook.com/geeksJavaMexico/.

Autor: Alejandro Agapito Bautista

Twitter: @raidentrance

Contacto:raidentrance@gmail.com

Aprende a utilizar anotaciones creando tu propio ORM


Cuando desarrollamos aplicaciones en Java el uso de anotaciones es muy común, pero se han puesto a pensar ¿Cómo crear tus propias anotaciones y como utilizarlas en Java ?, en este post explicaremos como hacerlo con ejemplos prácticos.

Tipos de anotaciones

Existen 3 tipos de anotaciones:

  • Marker annotation
  • Single value annotation
  • Multi value annotation

Marker annotation

A continuación se presenta como hacer una anotación de tipo Marker annotation:

public @interface Example {
}

Single value annotation

A continuación se presenta como hacer una anotación de tipo Single value annotation:

public @interface Example {
	int value() default 100;
}

Como se puede ver se creó una anotación llamada example la cual tiene un atributo llamado value con un valor por defecto de 100, para utilizarla se hará del siguiente modo:

@Example(value=200)

Esto cambiará el valor de value de 100 a 200.

Multi value annotation

A continuación se presenta como hacer una anotación de tipo Multi value annotation:

public @interface Example {
	int value() default 100;
	int value2() default 200;
	int value3() ;
}

Una anotación puede tener multiples atributos, el ejemplo anterior muestra una anotación con 3 valores value, value2 y value3, para utilizarla haremos lo siguiente:

@Example(value=200, value2=300, value3=400)

@Taget

Es posible definir en que lugar es o no permitido utilizar una anotación, para esto utilizaremos la anotación @Target la cual recibe como parámetro un valor de la enumeración java.lang.annotation.ElementType, a continuación se presentan los posibles valores y su significado:

  • TYPE : A nivel de clase, interfaz o enumeración
  • FIELD: A nivel de campos
  • METHOD: A nivel de métodos
  • CONSTRUCTOR: A nivel de constructores
  • LOCAL_VARIABLE : A nivel de variables locales
  • ANNOTATION_TYPE: A nivel de anotaciones
  • PARAMETER: A nivel de parámetros

Ejemplo práctico

Un caso de ejemplo muy común para utilizar anotaciones es un ORM, en nuestro caso práctico crearemos algunas anotaciones para definirlo y veremos como leerlo.

Anotación @Table:

import java.lang.annotation.ElementType;
import java.lang.annotation.Target;

@Target(ElementType.TYPE)
public @interface Table {
	String name();
	String schema();
}

Ejemplo práctico

En este ejemplo mostraremos como crear algunas anotaciones y obtener el valor de las mismas para simular un pequeño ORM.

import java.lang.annotation.ElementType;
import java.lang.annotation.Retention;
import java.lang.annotation.RetentionPolicy;
import java.lang.annotation.Target;

/**
 * @author raidentrance
 *
 */
@Target(ElementType.TYPE)
@Retention(RetentionPolicy.RUNTIME)
public @interface Table {
	String name();

	String schema();
}

La anotación table se utilizará para determinar el nombre de la tabla y el esquema de la base de datos a utilizar.


import java.lang.annotation.ElementType;
import java.lang.annotation.Retention;
import java.lang.annotation.RetentionPolicy;
import java.lang.annotation.Target;

/**
 * @author raidentrance
 *
 */
@Target(ElementType.FIELD)
@Retention(RetentionPolicy.RUNTIME)
public @interface Column {
	String name();

	String description();
}

La anotación @Column se utilizará para definir el nombre de una columna en una tabla de una base de datos.


import java.beans.IntrospectionException;
import java.beans.PropertyDescriptor;
import java.lang.reflect.Field;
import java.lang.reflect.InvocationTargetException;
import java.util.logging.Logger;

import com.raidentrance.orm.annotations.Column;
import com.raidentrance.orm.annotations.Table;

/**
 * @author maagapi
 *
 */
public class CustomEntityManager {

	private static final CustomEntityManager manager = new CustomEntityManager();

	private static final Logger log = Logger.getLogger(CustomEntityManager.class.getName());

	private CustomEntityManager() {
	}

	public void persist(Object user) {
		Table table = user.getClass().getAnnotation(Table.class);
		log.info(String.format("Inserting in table %s", table.name()));
		Field[] fields = user.getClass().getDeclaredFields();
		for (Field field : fields) {
			Column annotation = field.getAnnotation(Column.class);
			if (annotation != null) {
				try {
					Object invoke = new PropertyDescriptor(field.getName(), user.getClass()).getReadMethod().invoke(user);
					log.info(String.format("Column %s = %s", annotation.name(), invoke));
				} catch (IllegalArgumentException | IllegalAccessException | InvocationTargetException | IntrospectionException e) {
					log.info(e.getMessage());
				}
			}
		}
	}

	public static CustomEntityManager getEntityManager() {
		return manager;
	}

}

La clase CustomEntityManager se utilizará para simular el EntityManagerFactory de JPA, como se puede ver tiene un constructor privado y una instancia static para hacerlo singleton.

A continuación se muestra como obtener el valor de las anotaciones aplicadas en la clase haciendo uso del objeto:

Table table = user.getClass().getAnnotation(Table.class);
log.info(String.format("Inserting in table %s", table.name()));

Probando todo junto

Para probar todo junto crearemos una clase que hará uso del CustomEntityManager:

import com.raidentrance.orm.persistence.CustomEntityManager;

/**
 * @author raidentrance
 *
 */
public class TestApplication {
	public static void main(String[] args) {
		CustomEntityManager entityManager = CustomEntityManager.getEntityManager();

		entityManager.persist(new User("raidentrance", "SuperSecret"));
	}
}

Como se puede entender el uso de las anotaciones simulando un pequeño ORM, si ejecutas el programa la salida será la siguiente:

ene 22, 2018 5:09:10 PM com.raidentrance.orm.persistence.CustomEntityManager persist
INFORMACIÓN: Inserting in table USER
ene 22, 2018 5:09:10 PM com.raidentrance.orm.persistence.CustomEntityManager persist
INFORMACIÓN: Column USERNAME = raidentrance
ene 22, 2018 5:09:10 PM com.raidentrance.orm.persistence.CustomEntityManager persist
INFORMACIÓN: Column PASSWORD = SuperSecret

Si te gustó este ejemplo coméntalo en la sección de comentarios o en nuestras redes sociales https://twitter.com/geeks_mx y https://www.facebook.com/geeksJavaMexico/, para agregar la integración de JDBC para hacer funcionar nuestro ORM.

 

Autor: Alejandro Agapito Bautista

Twitter: @raidentrance

Contacto:raidentrance@gmail.com

Aprende a consumir servicios REST vía HTTPS leyendo precios de criptomonedas


Una de las tareas más comunes de un desarrollador es consumir servicios REST vía HTTPS, en este post se explicará lo siguiente:

  • Generar un certificado HTTPS
  • Instalar el certificado en la máquina virtual
  • Crear un cliente REST
  • Hacer una petición para obtener el valor de criptomonedas

Paso 1 Analizar el api a consumir

En este ejemplo leeremos información sobre criptomonedas, para hacerlo utilizaremos el api REST de Bitso (Empresa dedicada a la compra y venta de bitcoins, ripple, litecoin, entre otras criptomonedas). Para más información sobre los endpoints disponibles ver el siguiente link Documentación Bitso. En este ejemplo se consumirá un servicio para obtener el precio del bitcoin y ripple para esto se utilizará el endpoint ticker con los siguientes parámetros:

Es importante mencionar que los precios mostrados en este sitio son en pesos mexicanos.

Paso 2 Configurar el projecto

Una vez que entendemos el api que se va a consumir que conocemos los endpoints que se ejecutarán, el siguiente paso será crear un proyecto, para esto se creará un proyecto Maven e incluiremos las siguientes dependencias:

<dependencies>
	<dependency>
		<groupId>org.apache.storm</groupId>
		<artifactId>storm-core</artifactId>
		<version>1.0.1</version>
	</dependency>
	<dependency>
		<groupId>org.glassfish.jersey.core</groupId>
		<artifactId>jersey-client</artifactId>
		<version>2.17</version>
	</dependency>
	<dependency>
		<groupId>org.glassfish.jersey.media</groupId>
		<artifactId>jersey-media-json-jackson</artifactId>
		<version>2.17</version>
	</dependency>
</dependencies>

Y el siguiente plugin de Maven:

<build>
	<plugins>
		<plugin>
			<artifactId>maven-compiler-plugin</artifactId>
			<version>3.2</version>
			<configuration>
				<source>1.8</source>
				<target>1.8</target>
			</configuration>
		</plugin>
	</plugins>
</build>

Con estas dependencias y este plugin tendremos la versión de Java 8 y las dependencias necesarias para trabajar con Jersey client (El api que se utilizará para consumir servicios).

Paso 3 Creando modelo de la aplicación

Un paso importante al crear un cliente REST es des serializar la respuesta a objetos java, para esto debemos crear una representación del JSON en clases Java.

Json:

{
	success: true,
	payload: {
		high: "15.13",
		last: "14.69",
		created_at: "2017-12-18T14:13:36+00:00",
		book: "xrp_mxn",
		volume: "1700513.79486861",
		vwap: "14.14839779",
		low: "14.07",
		ask: "14.69",
		bid: "14.50"
	}
}

Clases Java:

PayLoad.java


import com.fasterxml.jackson.annotation.JsonProperty;

/**
 * @author raidentrance
 *
 */
public class Payload {

	@JsonProperty("high")
	private double high;

	@JsonProperty("last")
	private double last;

	@JsonProperty("created_at")
	private String createdAt;

	@JsonProperty("book")
	private String book;

	@JsonProperty("volume")
	private Double volume;

	@JsonProperty("vwap")
	private Double vwap;

	@JsonProperty("low")
	private Double low;

	@JsonProperty("ask")
	private Double ask;

	@JsonProperty("bid")
	private Double bid;

	public double getHigh() {
		return high;
	}

	public void setHigh(double high) {
		this.high = high;
	}

	public double getLast() {
		return last;
	}

	public void setLast(double last) {
		this.last = last;
	}

	public String getCreatedAt() {
		return createdAt;
	}

	public void setCreatedAt(String createdAt) {
		this.createdAt = createdAt;
	}

	public String getBook() {
		return book;
	}

	public void setBook(String book) {
		this.book = book;
	}

	public Double getVolume() {
		return volume;
	}

	public void setVolume(Double volume) {
		this.volume = volume;
	}

	public Double getVwap() {
		return vwap;
	}

	public void setVwap(Double vwap) {
		this.vwap = vwap;
	}

	public Double getLow() {
		return low;
	}

	public void setLow(Double low) {
		this.low = low;
	}

	public Double getAsk() {
		return ask;
	}

	public void setAsk(Double ask) {
		this.ask = ask;
	}

	public Double getBid() {
		return bid;
	}

	public void setBid(Double bid) {
		this.bid = bid;
	}

	@Override
	public String toString() {
		return "Payload [high=" + high + ", last=" + last + ", createdAt=" + createdAt + ", book=" + book + ", volume="
				+ volume + ", vwap=" + vwap + ", low=" + low + ", ask=" + ask + ", bid=" + bid + "]";
	}

}

CoinPrice.java


/**
 * @author raidentrance
 *
 */
public class CoinPrice {
	private boolean success;
	private Payload payload;

	public boolean isSuccess() {
		return success;
	}

	public void setSuccess(boolean success) {
		this.success = success;
	}

	public Payload getPayload() {
		return payload;
	}

	public void setPayload(Payload payload) {
		this.payload = payload;
	}

	@Override
	public String toString() {
		return "RipplePrice [success=" + success + ", payload=" + payload + "]";
	}

}

Paso 4 Creando el cliente REST

El siguiente paso es empezar a escribir código, lo primero que escribiremos será un AbstractClient, que servirá para dar soporte para escribir multiples clientes REST:

AbstractClient.java


import java.util.logging.Logger;

import javax.ws.rs.client.Client;
import javax.ws.rs.client.ClientBuilder;
import javax.ws.rs.client.WebTarget;

/**
 * @author raidentrance
 *
 */
public class AbstractClient {
	private String url;
	private String contextPath;

	private static final Logger log = Logger.getLogger(AbstractClient.class.getName());

	public AbstractClient(String url, String contextPath) {
		this.url = url;
		this.contextPath = contextPath;
	}

	protected WebTarget createClient(String path) {
		String assembledPath = assembleEndpoint(path);
		Client client = ClientBuilder.newClient();
		WebTarget target = client.target(assembledPath);
		return target;
	}

	private String assembleEndpoint(String path) {
		String endpoint = url.concat(contextPath).concat(path);
		log.info(String.format("Calling endpoint %s", endpoint));
		return endpoint;
	}
}

La clase AbstractClient será la clase base que se utilizará para todos los clientes que creemos, cuenta con dos métodos principales:

  • assembleEndpoint(String path) : Construye la url a ejecutar
  • WebTarget createClient(String path) : Crea el cliente HTTP para invocar la petición REST, en caso de requerir autenticar la petición este es el lugar para hacerlo.

ApplicationEndpoint.java


/**
 * @author raidentrance
 *
 */
public class ApplicationEndpoint {
	private static String TICKER = "/ticker";

	public static String getCoinPrice(String coin) {
		return TICKER.concat(String.format("?book=%s", coin));
	}
}

La clase ApplicationEndpoint se utiliza para definir los endpoints a ejecutar en la aplicación.

ServiceException.java


/**
 * @author raidentrance
 *
 */
public class ServiceException extends Exception {
	private Integer httpStatusCode;

	private static final long serialVersionUID = -1873750263916403862L;

	public ServiceException(String message, Integer httpStatusCode) {
		super(message);
		this.httpStatusCode = httpStatusCode;
	}

	public Integer getHttpStatusCode() {
		return httpStatusCode;
	}

	public void setHttpStatusCode(Integer httpStatusCode) {
		this.httpStatusCode = httpStatusCode;
	}
}

La clase ServiceException se utilizará para propagar los errores en caso de que existan.
BitsoClient


import java.util.logging.Logger;

import javax.ws.rs.client.WebTarget;
import javax.ws.rs.core.MediaType;
import javax.ws.rs.core.Response;
import javax.ws.rs.core.Response.Status;

import com.raidentrance.client.endpoints.ApplicationEndpoint;
import com.raidentrance.client.error.ServiceException;
import com.raidentrance.client.model.CoinPrice;

/**
 * @author raidentrance
 *
 */
public class BitsoClient extends AbstractClient {
	private static final Logger log = Logger.getLogger(BitsoClient.class.getName());

	public BitsoClient(String url, String contextPath) {
		super(url, contextPath);
	}

	public CoinPrice getRipplePrice() throws ServiceException {
		log.info("Getting ripple price");
		WebTarget client = createClient(ApplicationEndpoint.getCoinPrice("xrp_mxn"));
		Response response = client.request(MediaType.APPLICATION_JSON).get();
		log.info("Status " + response.getStatus());
		CoinPrice result = null;
		Integer status = response.getStatus();
		if (Status.OK.getStatusCode() == status) {
			result = response.readEntity(CoinPrice.class);
		} else {
			throw new ServiceException(response.readEntity(String.class), status);
		}
		return result;
	}

	public CoinPrice getBitcoinPrice() throws ServiceException {
		log.info("Getting ripple price");
		WebTarget client = createClient(ApplicationEndpoint.getCoinPrice("btc_mxn"));
		Response response = client.request(MediaType.APPLICATION_JSON).get();
		log.info("Status " + response.getStatus());
		CoinPrice result = null;
		Integer status = response.getStatus();
		if (Status.OK.getStatusCode() == status) {
			result = response.readEntity(CoinPrice.class);
		} else {
			throw new ServiceException(response.readEntity(String.class), status);
		}
		return result;
	}

}

Ahora es tiempo de crear el cliente REST en este caso será la clase BitsoClient como se puede ver recibe los siguientes parámetros en el constructor:

  • url : Representa la url a consumir
  • contextPath : Representa la url base de los servicios

También cuenta con 2 métodos:

  • getRipplePrice() : Como su nombre lo indica devuelve un objeto con el precio actual de la criptomoneda ripple.
  • getBitcoinPrice() : Como su nombre lo indica devuelve un objeto con el precio actual de la criptomoneda bitcoin.

TestClient.java


import com.raidentrance.client.error.ServiceException;
import com.raidentrance.client.model.CoinPrice;

/**
 * @author raidentrance
 *
 */
public class TestClient {
	public static void main(String[] args) throws ServiceException {
		BitsoClient client = new BitsoClient("https://api.bitso.com/", "v3");
		CoinPrice ripplePrice = client.getRipplePrice();
		CoinPrice bitcoin = client.getBitcoinPrice();
		System.out.println(String.format("Ripple price %s",ripplePrice.toString()));
		System.out.println(String.format("Bitcoin price %s",bitcoin.toString()));
	}
}

La clase TestClient se utilizará para mostrar en consola los valores obtenidos por las API’s REST.

Ejecutando la aplicación

Si ejecutamos la aplicación y no contamos con el certificado para ejecutar la petición recibiremos el siguiente error:

SunCertPathBuilderException: unable to find valid certification path to requested target

Así que utilizaremos una clase llamada InstallCert.java creada por el equipo de sun que puedes encontrar aquí, ejecutarla pasando como parámetro la url de la cual deseas extraer el certificado con el siguiente comando :

java InstallCert api.bitso.com

El cuál mostrará la siguiente salida:

Opening connection to api.bitso.com:443...
Starting SSL handshake...

No errors, certificate is already trusted

Server sent 3 certificate(s):

 1 Subject CN=ssl511101.cloudflaressl.com, OU=PositiveSSL Multi-Domain, OU=Domain Control Validated
   Issuer  CN=COMODO ECC Domain Validation Secure Server CA 2, O=COMODO CA Limited, L=Salford, ST=Greater Manchester, C=GB
   sha1    11 bd 1f 03 0a b4 07 8c d3 f1 49 16 f2 97 0a 9f 97 07 55 cd
   md5     33 1e 1d 7f 95 09 de 0b 0b b8 31 9d f2 48 85 b8

 2 Subject CN=COMODO ECC Domain Validation Secure Server CA 2, O=COMODO CA Limited, L=Salford, ST=Greater Manchester, C=GB
   Issuer  CN=COMODO ECC Certification Authority, O=COMODO CA Limited, L=Salford, ST=Greater Manchester, C=GB
   sha1    75 cf d9 bc 5c ef a1 04 ec c1 08 2d 77 e6 33 92 cc ba 52 91
   md5     5e 0e 41 9b 20 ea 57 54 77 f1 1b 52 e2 c8 18 e0

 3 Subject CN=COMODO ECC Certification Authority, O=COMODO CA Limited, L=Salford, ST=Greater Manchester, C=GB
   Issuer  CN=AddTrust External CA Root, OU=AddTrust External TTP Network, O=AddTrust AB, C=SE
   sha1    ae 22 3c bf 20 19 1b 40 d7 ff b4 ea 57 01 b6 5f dc 68 a1 ca
   md5     c7 90 a5 6c 69 cb af 0b f3 f3 0a 40 d0 a2 ae cc

<strong>Enter certificate to add to trusted keystore or 'q' to quit: [1]</strong>

Oprimiremos la tecla de 1 y enter.

Ejecutaremos de nuevo el comando, seleccionaremos 1 de nuevo y notaremos que la salida es ahora la siguiente:

Added certificate to keystore 'jssecacerts' using alias 'api.bitso.com-1'

Este comando generará un archivo llamado jssecacerts, el último paso será copiar ese archivo al directorio $JAVA_HOME\jre\lib\security y listo, tu aplicación podrá hacer peticiones https a el dominio de bitso.

El último paso será ejecutar nuestra aplicación para validar que todo funciona bien y generará la siguiente salida:

dic 18, 2017 10:37:04 AM com.raidentrance.client.BitsoClient getRipplePrice
INFORMACIÓN: Getting ripple price
dic 18, 2017 10:37:04 AM com.raidentrance.client.AbstractClient assembleEndpoint
INFORMACIÓN: Calling endpoint https://api.bitso.com/v3/ticker?book=xrp_mxn
dic 18, 2017 10:37:05 AM com.raidentrance.client.BitsoClient getRipplePrice
INFORMACIÓN: Status 200
dic 18, 2017 10:37:05 AM com.raidentrance.client.BitsoClient getBitcoinPrice
INFORMACIÓN: Getting ripple price
dic 18, 2017 10:37:05 AM com.raidentrance.client.AbstractClient assembleEndpoint
INFORMACIÓN: Calling endpoint https://api.bitso.com/v3/ticker?book=btc_mxn
dic 18, 2017 10:37:06 AM com.raidentrance.client.BitsoClient getBitcoinPrice
INFORMACIÓN: Status 200
<strong>Ripple price RipplePrice [success=true, payload=Payload [high=15.13, last=14.67, createdAt=2017-12-18T16:37:02+00:00, book=xrp_mxn, volume=1908408.5657127, vwap=14.20595744, low=14.07, ask=14.64, bid=14.52]]
Bitcoin price RipplePrice [success=true, payload=Payload [high=382000.0, last=374994.16, createdAt=2017-12-18T16:37:03+00:00, book=btc_mxn, volume=301.0574943, vwap=373301.92134721, low=362505.0, ask=375800.0, bid=374994.16]]</strong>

Como se puede ver se imprimieron los precios de las criptomonedas de forma exitosa, ya dependerá de ti la aplicación que crees con esto.

Conclusión

En este post se tocaron temas importantes como:

  • Configurar un proyecto para hacer peticiones REST con Jersey
  • Crear un patrón de diseño para la construcción de clientes REST
  • Ejecutar peticiones REST vía HTTPS
  • Obtener el valor en pesos de las criptomonedas Bitcoin y Ripple

Si te gusta el contenido y quieres enterarte cuando realicemos un post nuevo síguenos en nuestras redes sociales https://twitter.com/geeks_mx y https://www.facebook.com/geeksJavaMexico/.

Autor: Alejandro Agapito Bautista

Twitter: @raidentrance

Contacto:raidentrance@gmail.com

Borrar elementos de un Arbol binario


En el post Árboles binarios en Java se habló sobre como crear un árbol binario en Java y se analizaron las siguientes operaciones:

  • Agregar un nuevo nodo
  • Buscar un nodo
  • Imprimir in order
  • Imprimir in pos order
  • Imprimir in pre order

En este post se explicará como implementar el borrado de un nodo en el árbol.

Posibles escenarios

Cuando queremos borrar un elemento de un árbol binario, nos daremos cuenta que hay 3 posibles escenarios:

  • El nodo no tiene nodos hijos
  • El nodo tiene 1 hijo
  • El nodo tiene 2 hijos

A continuación se presentará como borrar el nodo con Java para cada uno de ellos.

El nodo no tiene nodos hijos

Si el nodo que se desea borrar no tiene ningún nodo hijo, el borrado será muy simple ya que lo único que se debe hacer es asignar el valor de null a la referencia padre que apunta a el.

El borrado para este escenario tendrá una complejidad de  O(Log N) por la búsqueda + O(Log 1) del borrado lo cual da una complejidad total de O(Log N).

El nodo tiene un hijo

Si el nodo que se desea borrar tiene un nodo hijo el procedimiento será el siguiente:

  • Buscar el elemento que deseamos borrar
  • Apuntar el puntero padre que apunta a el a su nodo hijo

El borrado para este escenario tendrá una complejidad de O(Log N) por la búsqueda + O(1) de la actualización de referencias = O(Log N).

El nodo tiene 2 hijos

Este es el escenario más complejo y debemos seguir lo siguiente:

  1. Buscar el elemento
  2. Para el siguiente paso tenemos dos opciones
    • Buscar el elemento más grande en el sub árbol de la izquierda (Que será conocido como predecesor).
    • Buscar el elemento más pequeño en el sub árbol de la derecha (Que será conocido como sucesor)
  3. Intercambiar el predecesor o sucesor con el nodo que se desea borrar, antes de hacerlo se deben validar los siguientes dos escenarios
    1. Si el predecesor o sucesor no tienen nodos hijos: El elemento se intercambiará con el predecesor o sucesor y será borrado
    2. Si el predecesor o sucesor tiene un nodo hijo: El elemento se intercambiará con el predecesor o sucesor, será borrado y su hijo ahora será hijo del predecesor o sucesor.

El borrado para este escenario tendrá una complejidad de O(Log N).

Analizando el código

Una vez que entendemos lo que se debe realizar, el siguiente paso será programarlo y analizar paso a paso el código:

  • Programando la búsqueda del predecessor:
public Node findPredecessor() {
	if (this.getRight() == null) {
		return this;
	} else {
		return this.getRight().findPredecessor();
	}
}
  • Programando la búsqueda del sucessor:
public Node findSuccessor() {
	if (this.getLeft() == null) {
		return this;
	} else {
		return this.getLeft().findSuccessor();
	}
}
  • Programando el borrado:
public Node delete(Integer value) {
	Node response = this;
	if (value < this.value) { 		this.left = this.left.delete(value); 	} else if (value > this.value) {
		this.right = this.right.delete(value);
	} else {
		if (this.left != null && this.right != null) {
			Node temp = this;
			Node maxOfTheLeft = this.left.findPredecessor();
			this.value = maxOfTheLeft.getValue();
			temp.left=temp.left.delete(maxOfTheLeft.getValue());
		} else if (this.left != null) {
			response = this.left;
		} else if (this.right != null) {
			response = this.right;
		} else {
			response = null;
		}
	}
	return response;
}

Analizando método por método:

  • findPredecessor : Busca el nodo más grande de la rama

  • findSuccessor : Busca el nodo más pequeño de la rama
  • delete: Busca en el árbol y cuando encuentra el elemento intercambia el predecesor de la izquierda por el elemento a borrar

Todo el código

A continuación se muestra como se ve la clase Node completa:


import java.util.Optional;

public class Node {
	private Integer value;
	private Node left;
	private Node right;

	public Node(Integer value) {
		this.value = value;
	}

	public Integer getValue() {
		return value;
	}

	public void setValue(Integer value) {
		this.value = value;
	}

	public Node getLeft() {
		return left;
	}

	public void setLeft(Node left) {
		this.left = left;
	}

	public Node getRight() {
		return right;
	}

	public void setRight(Node right) {
		this.right = right;
	}

	public void add(Integer value) {
		if (value < this.value) {
			if (left != null) {
				left.add(value);
			} else {
				left = new Node(value);
			}
		} else {
			if (right != null) {
				right.add(value);
			} else {
				right = new Node(value);
			}
		}
	}

	public Optional<Node> find(Integer value) {
		if (value == this.value) {
			return Optional.of(this);
		} else if (value < this.value) {
			if (this.left != null) {
				return this.left.find(value);
			} else {
				return Optional.empty();
			}
		} else {
			if (this.right != null) {
				return this.right.find(value);
			} else {
				return Optional.empty();
			}
		}
	}

	public void printInOrder() {
		if (left != null) {
			left.printInOrder();
		}
		System.out.println(value);
		if (right != null) {
			right.printInOrder();
		}
	}

	public void printPreOrder() {
		System.out.println(value);
		if (left != null) {
			left.printPreOrder();
		}
		if (right != null) {
			right.printPreOrder();
		}
	}

	public void printPosOrder() {
		if (left != null) {
			left.printPreOrder();
		}
		if (right != null) {
			right.printPreOrder();
		}
		System.out.println(value);
	}

	public Node findPredecessor() {
		if (this.getRight() == null) {
			return this;
		} else {
			return this.getRight().findPredecessor();
		}
	}

	public Node findSuccessor() {
		if (this.getLeft() == null) {
			return this;
		} else {
			return this.getLeft().findSuccessor();
		}
	}

	public Node delete(Integer value) {
		Node response = this;
		if (value < this.value) { 			this.left = this.left.delete(value); 		} else if (value > this.value) {
			this.right = this.right.delete(value);
		} else {
			if (this.left != null && this.right != null) {
				Node temp = this;
				Node maxOfTheLeft = this.left.findPredecessor();
				this.value = maxOfTheLeft.getValue();
				temp.left = temp.left.delete(maxOfTheLeft.getValue());
			} else if (this.left != null) {
				response = this.left;
			} else if (this.right != null) {
				response = this.right;
			} else {
				response = null;
			}
		}
		return response;
	}

	@Override
	public String toString() {
		return "Node [value=" + value + ", left=" + left + ", right=" + right + "]";
	}

}

 Probando el código

El último paso es probar todo el código y ver que el borrado funciona, para esto ejecutaremos el siguiente código:

public class TreeTest {
	public static void main(String[] args) {
		Node root = new Node(32);
		root.add(10);
		root.add(55);
		root.add(1);
		root.add(19);
		root.add(16);
		root.add(23);
		root.add(79);
		System.out.println("Tree before deletion");
		root.printPreOrder();
		root.delete(55);
		root.delete(16);
		root.delete(32);
		System.out.println("Tree after deletion");
		root.printPreOrder();

	}
}<span 				data-mce-type="bookmark" 				id="mce_SELREST_start" 				data-mce-style="overflow:hidden;line-height:0" 				style="overflow:hidden;line-height:0" 			></span>

Como se puede ver es posible borrar nodos en los 3 escenarios mencionados anteriormente.

Si te gusta el contenido y quieres enterarte cuando realicemos un post nuevo síguenos en nuestras redes sociales https://twitter.com/geeks_mx y https://www.facebook.com/geeksJavaMexico/.

Autor: Alejandro Agapito Bautista

Twitter: @raidentrance

Contacto:raidentrance@gmail.com

Implementa un grafo de ciudades en Java


Una de las estructuras de datos más complejas y más útiles son los grafos (Graphs), en este post se explicará paso a paso como implementar uno en Java. Para este ejemplo se creará uno sobre algunas de las ciudades que se encuentran en México.

Conceptos básicos

Antes de crear el grafo debemos entender algunos conceptos básicos:

  • Vértice (Vertex) : Es un punto donde varias líneas se unen
  • Arista (Edge) : Es un término matemático que representa una línea que conecta 2 vértices
  • Grafo (Graph) : Es el término que representa un conjunto de vértices y aristas.

Ejemplo práctico

En el ejemplo que se presentará se creará un Grafo de ciudades, cada nodo será una ciudad (DF, Toluca, Cuernavaca, Puebla y Tlaxcala) que se unirán con un conjunto de aristas con su distancia, la siguiente imagen es una representación gráfica:

graphs

Creando el modelo

Como siempre el primer paso será crear el modelo con las clases a utilizar, para esto crearemos 3 clases Node, Edge y Grap que serán mostradas a continuación:

Node.java


import java.util.ArrayList;
import java.util.List;

/**
 * @author raidentrance
 *
 */
public class Node {
	private String city;
	private List<Edge> edges;

	public Node(String city) {
		this.city = city;
	}

	public String getCity() {
		return city;
	}

	public void setCity(String city) {
		this.city = city;
	}

	public List<Edge> getEdges() {
		return edges;
	}

	public void addEdge(Edge edge) {
		if (edges == null) {
			edges = new ArrayList<>();
		}
		edges.add(edge);
	}

	@Override
	public String toString() {
		return "\n \tNode [city=" + city + ", edges=" + edges + "]";
	}
}

Edge.java

/**
 * @author raidentrance
 *
 */
public class Edge {
	private Node origin;
	private Node destination;
	private double distance;

	public Edge(Node origin, Node destination, double distance) {
		this.origin = origin;
		this.destination = destination;
		this.distance = distance;
	}

	public Node getOrigin() {
		return origin;
	}

	public void setOrigin(Node origin) {
		this.origin = origin;
	}

	public Node getDestination() {
		return destination;
	}

	public void setDestination(Node destination) {
		this.destination = destination;
	}

	public double getDistance() {
		return distance;
	}

	public void setDistance(double distance) {
		this.distance = distance;
	}

	@Override
	public String toString() {
		return "\n Edge [origin=" + origin.getCity() + ", destination=" + destination.getCity() + ", distance="
				+ distance + "]";
	}

}

Graph


import java.util.ArrayList;
import java.util.List;

/**
 * @author raidentrance
 *
 */
public class Graph {

	private List<Node> nodes;

	public void addNode(Node node) {
		if (nodes == null) {
			nodes = new ArrayList<>();
		}
		nodes.add(node);
	}

	public List<Node> getNodes() {
		return nodes;
	}

	@Override
	public String toString() {
		return "Graph [nodes=" + nodes + "]";
	}

}

A continuación se presenta la explicación:

  • Un Graph contiene una lista de nodos
  • Cada nodo contiene el nombre de una ciudad y una lista de aristas
  • Cada arista contiene la unión de las ciudades así como la distancia entre ellas

Creando el grafo de ciudades

Una vez que se creó el modelo el siguiente paso será llenarlo con la información de las ciudades.


/**
 * @author raidentrance
 *
 */
public class MapRepresentation {

	public static Graph getCities() {
		Node df = new Node("DF");
		Node toluca = new Node("Toluca");
		Node cuernavaca = new Node("Cuernavaca");
		Node puebla = new Node("Puebla");
		Node tlaxcala = new Node("Tlaxcala");

		df.addEdge(new Edge(df, toluca, 100));
		df.addEdge(new Edge(df, cuernavaca, 90));

		toluca.addEdge(new Edge(toluca, cuernavaca, 150));
		toluca.addEdge(new Edge(toluca, puebla, 350));
		toluca.addEdge(new Edge(toluca, tlaxcala, 340));

		cuernavaca.addEdge(new Edge(cuernavaca, puebla, 100));

		puebla.addEdge(new Edge(puebla, tlaxcala, 20));

		Graph graph = new Graph();
		graph.addNode(df);
		graph.addNode(toluca);
		graph.addNode(cuernavaca);
		graph.addNode(puebla);
		return graph;
	}

	public static void main(String[] args) {
		Graph graph = getCities();
		System.out.println(graph);
	}
}

Salida:

Graph [nodes=[
 	Node [city=DF, edges=[
 Edge [origin=DF, destination=Toluca, distance=100.0],
 Edge [origin=DF, destination=Cuernavaca, distance=90.0]]],
 	Node [city=Toluca, edges=[
 Edge [origin=Toluca, destination=Cuernavaca, distance=150.0],
 Edge [origin=Toluca, destination=Puebla, distance=350.0],
 Edge [origin=Toluca, destination=Tlaxcala, distance=340.0]]],
 	Node [city=Cuernavaca, edges=[
 Edge [origin=Cuernavaca, destination=Puebla, distance=100.0]]],
 	Node [city=Puebla, edges=[
 Edge [origin=Puebla, destination=Tlaxcala, distance=20.0]]]]]

Si observamos la salida del programa podemos ver que cada ciudad cuenta con sus aristas que representan la unión de ambos puntos y cuenta con la distancia entre ellas como se mostró en la imagen.

Siguientes pasos

En próximos posts se explicará ejecutar algoritmos sobre este grafo, agregar dirección a las aristas y muchas más operaciones, si te gusta el contenido y quieres enterarte cuando realicemos un post nuevo síguenos en nuestras redes sociales https://twitter.com/geeks_mx y https://www.facebook.com/geeksJavaMexico/.

Autor: Alejandro Agapito Bautista

Twitter: @raidentrance

Contacto:raidentrance@gmail.com

Listas doblemente ligadas en Java


En el post anterior Listas ligadas en Java paso a paso y en Español aprendimos como utilizar listas simplemente ligadas, en este explicaremos como crear listas doblemente ligadas en Java.

A diferencia de las listas simplemente ligadas las listas doblemente ligadas contienen una referencia al nodo siguiente y una al anterior, esto debe ser considerado al momento de agregar los valores al principio y al final de ella.

Creando la clase Nodo


public class Node {
	private Integer value;
	private Node nextElement;
	private Node previousElement;

	public Node(Integer value) {
		this.value = value;
	}

	public Integer getValue() {
		return value;
	}

	public void setValue(Integer value) {
		this.value = value;
	}

	public Node getNextElement() {
		return nextElement;
	}

	public void setNextElement(Node nextElement) {
		this.nextElement = nextElement;
	}

	public Node getPreviousElement() {
		return previousElement;
	}

	public void setPreviousElement(Node previousElement) {
		this.previousElement = previousElement;
	}

	@Override
	public String toString() {
		return "Node [value=" + value + ", nextElement=" + ((nextElement != null) ? nextElement.getValue()
				: null) + ", previousElement=" +( (previousElement != null) ? previousElement.getValue() : null) + "]";
	}

}

Como se puede observar la clase nodo contiene 3 atributos:

  • Integer value : Contiene el valor a almacenar en la lista

  • Node nextElement: Contiene una referencia al nodo siguiente
  • Node previousElement: Contiene una referencia al nodo anterior

Con estos atributos la lista doblemente ligada se verá como la siguiente imagen:

doublylinkedlist

Creando la lista doblemente ligada

Una vez que se ha creado el nodo, el siguiente paso es crear la lista doblemente ligada.


public class DoublyLinkedList {
	private Node tail;
	private Node head;

	public void addLast(Integer value) {
		Node node = new Node(value);
		if (tail == null && head == null) {
			tail = node;
			head = node;
		} else {
			tail.setNextElement(node);
			node.setPreviousElement(tail);
			tail = node;
		}
	}

	public void addFirst(Integer value) {
		Node node = new Node(value);
		if (tail == null && head == null) {
			tail = node;
			head = node;
		} else {
			node.setNextElement(head);
			head.setPreviousElement(node);
			head = node;
		}
	}

	public void print() {
		for (Node i = head; i != null; i = i.getNextElement()) {
			System.out.printf("\t %s ", i.toString());
		}
		System.out.println();
	}
}

El código anterior muestra como realizar las siguientes operaciones en una lista doblemente ligada:

  • void addLast(Integer value) : Agrega un nodo al final de la lista

  • void addFirst(Integer value) : Agrega un nodo al principio de la lista

  • void print() : Imprime los elementos en la lista

Es importante mencionar que cada elemento de la lista debe mantener una referencia tanto al nodo siguiente como al nodo anterior.

Probando la lista

El último paso será probar la lista doblemente ligada, veamos el código:

public class TestDoublyLinkedList {
	public static void main(String[] args) {
		DoublyLinkedList list = new DoublyLinkedList();
		list.addLast(10);
		list.addLast(11);
		list.addLast(12);
		list.addLast(13);
		list.addLast(14);
		list.addFirst(9);
		list.addFirst(8);
		list.print();
	}
}

Salida:

Node [value=8, nextElement=9, previousElement=null] 	 Node [value=9, nextElement=10, previousElement=8] 	 Node [value=10, nextElement=11, previousElement=9] 	 Node [value=11, nextElement=12, previousElement=10] 	 Node [value=12, nextElement=13, previousElement=11] 	 Node [value=13, nextElement=14, previousElement=12] 	 Node [value=14, nextElement=null, previousElement=13]

La salida muestra por cada nodo su valor, su nodo anterior y su nodo siguiente.

Si te gusta el contenido compártelo y no olvides seguirnos en nuestras redes sociales https://twitter.com/geeks_mx y https://www.facebook.com/geeksJavaMexico/.

Autor: Alejandro Agapito Bautista

Twitter: @raidentrance

Contacto:raidentrance@gmail.com