Etiqueta: graphs

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:

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

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.

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.

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.

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.

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