Caso de uso de Grafos

Grafos

El origen de la palabra grafo es griego y su significado etimológico es "trazar". aparece con gran frecuencia como respuesta a problemas de la vida cotidiana, algunos ejemplos podrían ser los siguientes:un gráfico de una serie de tareas a realizar indicando su secuenciación  (un organigrama), grafos matemáticos que representan las relaciones binarias, una red de carreteras, la red de enlaces ferroviarios o aéreos o la red eléctrica de una ciudad, (ver la figura 1). En cada caso es conveniente representar gráficamente el problema dibujando un grafo como un conjunto de puntos (nodos o vértices) con líneas conectándolos (arcos).

Ejemplo del uso de Grafo, Servicio de Entregas

Ahora veremos un ejemplo real del uso de grafos, en el que se selecciona un barrio de origen y otro de destino, la moto lo que hará es mirar la ruta que implique menos gasto, en este caso menos distancia.

Imágenes

Algunas Explicaciones del Proyecto

Primero que todo, se preguntaran de donde es el mapa, bueno pues es de la ciudad de Barranquilla, Colombia, Bueno ahora si sobre el proyecto, para manejar el grafo se usan tres matrices, una matriz de identidad que es la que nos dice de que barrio a que barrio hay conexion, las segunda es la matriz de costos, esta nos dice cuanto nos cuesta ir de un barrio a otro, siempre y cuando exista la conexión entre dichos barrios.

La ultima matriz es llamada la matriz de Floyd y se usa para determinar la ruta que tenga menos costo entre dos barrios.

Aqui la imagen de las tres matrices:

Matriz Costos

 Matriz de Floyd

Matriz Identidad

Donde aparecen ceros (0) o inf es por que no hay conexión. Cada columna y cada fila es un barrio.

Ademas el proyecto te permite insertar un barrio, cambiar las conexiones, aislar un barrio que no es mas que borrar todas las conexiones que este barrio tiene, salientes y entrantes. Ademas de recorrer lo barrios con una motocicleta, creas una moto y le indicas a que barrio debe ir, y puedes manejar varias motos.

Proyecto completo

http://dl.dropbox.com/u/61822104/Proyectos%20Java%20Zone/ServicioEntregas.rar

Caso de uso de arboles binarios

http://repositorio.upct.es/bitstream/handle/10317/2745/pfc4277.pdf?sequence=1

Introducción

Vamos a hablar primero un poco de que son los arboles binarios; “Un árbol binario es un grafo conexo, a cíclico y no dirigido tal que el grado de cada vértice no es mayor a 3”, eso significa que tenemos un grafo donde cada nodo puede tener máximo 2 hijos u hojas  y estas hojas no pueden tener como hijos a cualquier otra hoja anterior como podemos ver en la figura que se relaciona a continuación:

¿Para que sirve un árbol binario?

Como todos sabemos un árbol binario es una estructura de datos, y como todas, este sirve para organizar datos para facilitar su manipulación, ya sea el ingreso, borrado o búsqueda de datos, y precisamente una de las principales ventajas de los árboles binarios es la búsqueda, ya que como en muchos algoritmos de búsqueda necesitamos tener la información ordenada y en nuestros árboles binarios precisamente los datos van ingresando de forma ordenada. Recorridos con los conocidos métodos recursivos:

1. Inorden
2. Postorden
3. Preorden

 
                            Caso de estudio

  Creación de una interfaz gráfica para la gestión de un árbol genealógico.

Introducción

Un árbol genealógico es un árbol que presenta la herencia biológica de una persona, comenzando con sus padres y retrocediendo a través de las generaciones, pasando por sus abuelos, bisabuelos, etc. La diferencia entre un árbol genealógico teórico y un árbol genealógico real es que el árbol real puede no estar perfectamente equilibrado, debido a la falta de datos o a la existencia de datos incompletos. En lo que respecta a este caso de estudio, se va a crear una interfaz gráfica para la gestión de un árbol genealógico que permitirá al usuario seleccionar un padre y luego ir introduciendo los hijos de cualquiera de los padres existentes en el programa. A su vez también se podrá eliminar cualquier nodo. El programa también permite guardar los datos introducidos en un documento de texto, imprimir el árbol guardado y salir del sistema.

Diseño inicial

El programa está formado por cuatro componentes: la clase árbol, la clase hoja, la clase test y la interfaz gráfica de usuario (GUI).

En un principio el programa se ejecutaba a través de la clase test (donde se encuentra el método main). Por lo que por consola se mostraba un pequeño menú con cuatro opciones: añadir, eliminar, guardar, imprimir y salir.

Si se escribe la opción añadir se pedirá el nombre del hijo que se quiere añadir y el nombre del padre al que se quiere añadir ese nuevo hijo. Si el nombre del padre es igual a “null”, es que este hijo va a ser un nuevo nodo raíz y si no se irá comparando el nombre del padre introducido por teclado con todos los nombres de los nodos que haya en el documento de texto guardado “read.txt” y cuando lo encuentre se insertara el nuevo hijo a ese padre. Abajo se muestra el método para que se pueda entender mejor:

public Leaf addNewChild(String childName, String parentName, Leaf
rootNode){

//se da el número de hijos de ese nodo

         for(int i=0; i<rootNode.getChildren().size(); i++){

// se recorren todos los hijos de esa hoja y en el nodo en el que este en ese momento será el padre.
     
   Leaf parentNode = rootNode.getChildren().get(i);

// se comparan los nombres
      
       if(parentNode.getName().equals(parentName)){

// si es el nombre que el programa está buscando, inserta el nodo

parentNode.insertChild(new Leaf(childName,parentNode));

//se encuentra un nodo con el mismo nombre que el usuario ha introducido

control = true;

//en el caso de que el usuario ponga más de un nodo con el mismo nombre, el programa solo añade el hijo en el primer nodo. Otra posibilidad es quitar el "break" y el programa añade el nuevo hijo a todos los padres con el mismo nombre.//

break;}

//cierro if si el nodo tiene hijos, el programa llama al método recursivo

 if (parentNode.getChildren().size() != 0){
      addNewChild(childName, parentName, parentNode);}
}

//cierro for

         return rootNode;}


//cierro método addNewChild

Si la opción es eliminar el programa pedirá el nombre del nodo a eliminar y se irá comparando con cada uno de los hijos del árbol .Si corresponde con uno de los nodos guardados en el documento de texto se eliminara dicho nodo introducido. Abajo se muestra el método para su mejor compresión:

//metodo que elimina el nombre de nodo que se le pasa

public void removeChild(String Node, Leaf rootNode){

//se da el número de hijos de este subárbol


for(int i=0; i<rootNode.getChildren().size(); i++){


//se recorre uno a uno los nodos del árbol

Leaf parentNode = rootNode.getChildren().get(i);

// se comparan los nombres

if(parentNode.getName().equals(Node)){

// si es el nombre que el programa está buscando,elimina el nodo

rootNode.getChildren().remove(i);

// se encuentra un nodo con el mismo nombre que el usuario ha introducido

control = true; break; }

//llamada al método recursivo

removeChild(Node,parentNode); }

//cierra for
}

//cierra removeChild()

Si la opción es guardar se almacenara en un documento de texto ese nuevo padre e hijo introducido anteriormente en la opción añadir o si se ha eliminado algún nodo también se modificara el documento de texto “read.txt”.

se muestra un ejemplo de lo que almacena el archivo “read.txt”:

Si la opción es imprimir se mostrara por consola el documento de texto donde se guardan los datos que se introducen por teclado pero en forma de árbol. El archivo que lo muestra así es el “out.txt”.

+

A continuación se muestra un ejemplo de lo que almacena el archivo “out.txt”:

Implementación de la interfaz grafica 

Para diseñar la interfaz grafica que visualice de la forma más clara y sencilla el árbol genealógico se crea una ventana principal donde hay un área de texto donde se mostrara el árbol y unos botones que serán añadir, eliminar y salir. En la Figura se muestra como quedaría dicha interfaz.

Si se pulsa el botón añadir se abrirá una nueva ventana donde se podrá introducir el nombre del hijo y se mostrara un desplegable con todos los nodos almacenados en el archivo “read.txt” para poder seleccionar el padre al que se quiere añadir ese hijo.

Cuando se pulse el botón “Add” estos datos serán guardados en un documento de texto y a su vez el árbol se imprimirá en el área de texto de la ventana principal en forma de árbol.

Si el botón seleccionado es eliminar se abrirá una nueva ventana donde se volverá a mostrar un desplegable con todos los nodos almacenados en el archivo “read.txt”. Entonces se elegirá el nodo a eliminar.

Cuando se pulse el botón “Clear” el nodo seleccionado se eliminara, se guardara dicho cambio y el árbol será mostrado en la ventana principal de nuevo.

Al pulsar el botón de salir se abrirá una nueva ventana con un pequeño menú donde se le preguntara al usuario si está seguro de querer salir del programa. Si se pulsa que “Si” el programa se cerrara y si es que “No” el programa permanecerá abierto.