univeridad politÉcnica de madrid - upm · 2015-11-25 · agradecimientos en primer lugar agradecer...
TRANSCRIPT
UNIVERSIDAD POLITÉCNICA DE MADRID
FACULTAD DE INFORMÁTICA
TRABAJO FIN DE CARRERA
DOMINACIÓN EN GRAFOS
AUTOR: JORGE DURÁN HERAS
TUTOR: GREGORIO HERNANDEZ PEÑALVER
FECHA DE PRESENTACIÓN: 24 NOVIEMBRE 2014
AGRADECIMIENTOS
En primer lugar agradecer a Don Gregorio Hernández Peñalver, del
Departamento de Matemática Aplicada de la Facultad de Informática de Madrid, por ser
mi tutor, ayudarme en todas las fases del proyecto y por toda la paciencia que ha
mostrado durante este largo trayecto.
Especialmente dar las gracias a mis padres, Antonio y María Rosa, por darme
todo su apoyo y esfuerzo para que pueda realizar y culminar mi trayectoria universitaria.
Soy lo que soy gracias a vosotros.
Agradecer eternamente el apoyo mostrado a mi esposa Mónica, por estar ahí en
todo momento, animarme a culminar el proyecto y por su experiencia y ayuda para
guiarme en la presentación del mismo. Con tu confianza y apoyo lo he conseguido.
Muchas gracias a toda mi familia y la de mi esposa, por su apoyo, pero quiero
hacer mención especial a Maximiliano y Angélica por insistir en que terminara el
proyecto. Max, desde donde quieras que estés, gracias por mostrarme el camino.
i
I NDICE
Contenido PARTE I .....................................................................................................................................................1
INTRODUCCIÓN ......................................................................................................................................1
CAPÍTULO 1.- INTRODUCCIÓN ..........................................................................................................3
CAPÍTULO 2.- COMPLEJIDAD COMPUTACIONAL .........................................................................5
2.1 CLASE P (Polynomial-time) ............................................................................................ 5
2.2 CLASE NP (Non-deterministic polynomial-time) ........................................................... 5
2.3 CLASE NPH (Non-deterministic polynomial-time hard) ................................................ 6
2.4 CLASE NPC (Non-deterministic polynomial-time complete) ........................................ 6
PARTE II ....................................................................................................................................................9
TEORÍA ......................................................................................................................................................9
CAPITULO 3.- TEORÍA ...................................................................................................................... 11
3.1 Conceptos generales. .................................................................................................. 11
3.2 Algoritmo de generación aleatoria de grafos. ............................................................ 13
3.3 Tipos de grafos ............................................................................................................ 14
3.3.1 Grafo vacío .......................................................................................................... 14
3.3.2 Grafo completo. .................................................................................................. 15
3.3.3 Grafo bipartido completo. .................................................................................. 16
3.3.4 Grafo enlazado L(n, r).......................................................................................... 16
3.3.5 Grafo enlazado L(n, r, s) ...................................................................................... 17
3.3.7 Grafo ciclo. .......................................................................................................... 19
3.3.8 Grafo Rueda. ....................................................................................................... 20
3.3.9 Grafo estrella. ..................................................................................................... 21
3.3.10 Grafo de Herschel ............................................................................................... 22
3.3.11 Grafo de Petersen ............................................................................................... 23
3.3.12 Grafo de Heawood. ............................................................................................. 23
3.3.13 Grafo de Grötzsch. .............................................................................................. 24
CAPÍTULO 4.- DOMINACION EN GRAFOS .................................................................................... 26
ii
4.1 Descripción del problema ............................................................................................ 26
4.2 Heurísticas – Algoritmos (ejemplos) ............................................................................ 27
4.2.1 Greedy Algorithm ................................................................................................ 28
4.2.2 Algoritmo Weighted Dominance. ........................................................................ 30
4.2.3 Algoritmo Tree Growing ...................................................................................... 35
4.3.3 Algoritmo Marking ............................................................................................... 39
PARTE III ............................................................................................................................................... 45
DISEÑO ................................................................................................................................................... 45
CAPÍTULO 5.- DISEÑO ....................................................................................................................... 47
5.1 Introducción ................................................................................................................ 47
5.2 Diseño de alto nivel ..................................................................................................... 47
5.2.1 Definición de los Límites del Sistema .................................................................. 47
5.2.2 Diagrama de Casos de Usos ................................................................................. 49
5.2.3 Descripción de los Actores .................................................................................. 52
5.2.4 Casos de uso en formato de alto nivel ................................................................ 52
5.2.5 Casos de uso en formato expandido ................................................................... 64
5.3 Diseño de bajo nivel .................................................................................................. 108
5.3.1 Diagrama de clases. ........................................................................................... 108
5.3.2 Visión general. ................................................................................................... 108
PARTE IV ............................................................................................................................................. 113
MANUAL DE USUARIO .................................................................................................................... 113
CAPÍTULO 6.- MANUAL DE USUARIO ......................................................................................... 115
6.1 Partes de la aplicación. .............................................................................................. 115
6.1.1 Barra de menús.................................................................................................. 115
6.1.2 Menú File. .......................................................................................................... 116
6.1.3 Menú Edit. ......................................................................................................... 117
6.1.4 Menú Algorithms. .............................................................................................. 118
6.1.5 Menú Graphs. .................................................................................................... 118
6.1.6 Menú Help. ........................................................................................................ 120
6.1.7 Panel de acciones. ............................................................................................. 120
iii
6.1.8 Panel de algoritmos. ......................................................................................... 121
6.1.9 Área de texto. .................................................................................................... 121
6.1.10 Área de trabajo/dibujo. .................................................................................... 122
6.2 Operaciones básicas. ................................................................................................. 122
6.2.1 Crear un grafo nuevo. ....................................................................................... 122
6.2.2 Crear un grafo aleatorio. ................................................................................... 123
6.2.3 Crear un grafo aleatorio con pesos. .................................................................. 124
6.2.4 Exportar grafo. .................................................................................................. 124
6.2.5 Importar grafo. .................................................................................................. 125
6.2.6 Salir. ................................................................................................................... 126
6.2.7 Añadir nodo....................................................................................................... 126
6.2.8 Añadir arista. ..................................................................................................... 126
6.2.9 Añadir peso a un nodo. ..................................................................................... 126
6.2.10 Eliminar nodo. ................................................................................................... 127
6.2.11 Eliminar arista. .................................................................................................. 127
6.2.12 Eliminar grafo. ................................................................................................... 127
6.2.13 Grafos predefinidos. ......................................................................................... 127
6.3 Ejecución de algoritmos. ........................................................................................... 129
6.3.1 Ejecución inmediata. ......................................................................................... 129
6.3.2 Ejecución paso a paso. ...................................................................................... 129
6.3.3 Algoritmos. ........................................................................................................ 130
Bibliografía ......................................................................................................................................... 149
iv
I NDICE DE FIGURAS
- Figura 1.1: Redes móviles ............................................................................................................ 3
- Figura 2.1: Clases de complejidad ............................................................................................... 6
- Figura 3.1: Ejemplo de grafo ..................................................................................................... 12
- Figura 3.2: a.- Conjunto dominante de G. b.- Conjunto dominante minimal. c.- Conjunto
dominante de cardinalidad mínimo ............................................................................................ 13
- Figura 3.3: Pseudocódigo generación aleatoria de grafos ........................................................ 14
- Figura 3.4: Grafo vacío de 10 vértices ....................................................................................... 15
- Figura 3.5: Grafo completo de 8 vértices K8 ............................................................................ 15
- Figura 3.6: Grafo bipartido completo de 7 vértices K4,3 .......................................................... 16
- Figura 3.7: Grafo enlazado L(8,2) .............................................................................................. 17
- Figura 3.8: Grafo enlazado L(8,2,1) ........................................................................................... 18
- Figura 3.9: Grafo rejilla rectangular (3 filas, 8 columnas) ......................................................... 19
- Figura 3.10: Grafo ciclo de 12 vértices C12 ............................................................................... 20
- Figura 3.11: Grafo Rueda W12 .................................................................................................. 21
- Figura 3.12: Grafo estrella de 12 vértices. ................................................................................ 21
- Figura 3.13: Grafo de Herschel .................................................................................................. 22
- Figura 3.14: Grafo de Petersen.................................................................................................. 23
- Figura 3.15: Grafo de Heawood ................................................................................................ 24
- Figura 3.16: Grafo de Grötzsch .................................................................................................. 25
- Figura 4.1: Conjunto dominante ............................................................................................... 26
- Figura 4.2: Primer paso algoritmo greedy ................................................................................. 28
- Figura 4.3: Segundo paso (paso intermedio) algoritmo greedy ................................................ 29
- Figura 4.4: Paso final algoritmo greedy ..................................................................................... 30
- Figura 4.5: Grafo inicial algoritmo weighted dominance .......................................................... 32
- Figura 4.6: Cálculo nuevos pesos algoritmo weighted dominance ........................................... 32
- Figura 4.7: Vértice con mayor peso algoritmo weighted dominance ....................................... 33
- Figura 4.8: Grafo resultado eliminar vértice y vecinos algoritmo weighted dominance .......... 33
- Figura 4.9: Siguiente vértice añadido al conjunto dominante algoritmo weigthed dominance
..................................................................................................................................................... 34
- Figura 4.10: Final ejecución algoritmo weigthed dominance ................................................... 34
v
- Figura 4.11: Ejemplo de solución “mala” algoritmo tree growing ........................................... 36
- Figura 4.12: Grafo inicial algoritmo tree growing ..................................................................... 37
- Figura 4.13: Selección del vértice inicial (mayor grado) ........................................................... 37
- Figura 4.14 – 4.15: Paso general algoritmo tree growing ......................................................... 38
- Figura 4.16: Paso general en el que ya no hay vértices no dominados (blancos) ................... 38
- Figura 4.17: Conjunto dominante conexo, solución del algoritmo tree growing ..................... 39
- Figura 4.18: Grafo ejemplo algoritmo marking ........................................................................ 41
- Figura 4.19: Grafo inicial algoritmo marking ............................................................................ 41
- Figura 4.20: Nodo seleccionado del grafo inicial algoritmo marking ....................................... 42
- Figura 4.21: Paso completado algoritmo marking .................................................................... 42
- Figura 4.22: Nodo inicial no seleccionado algoritmo marking.................................................. 43
- Figura 4.23: Grafo inicial completado algoritmo marking ........................................................ 44
- Figura 4.24: Conjunto dominante resultado algoritmo marking .............................................. 44
- Figura 5.1: Diagrama de casos de uso ...................................................................................... 51
- Figura 5.2: Diagrama de clases (parte1) ................................................................................. 110
- Figura 5.3: Diagrama de clases (parte2) ................................................................................. 111
- Figura 6.1: Menú File .............................................................................................................. 116
- Figura 6.2: Menú Edit. ............................................................................................................. 117
- Figura 6.3: Menú Algorithms .................................................................................................. 118
- Figura 6.4: Menú Graphs ........................................................................................................ 118
- Figura 6.5: Opciones grafo completo ...................................................................................... 119
- Figura 6.6: Opciones Bound Graph ......................................................................................... 119
- Figura 6.7: Grid ....................................................................................................................... 119
- Figura 6.8: Opciones Shapes. .................................................................................................. 120
- Figura 6.9: Menú Help............................................................................................................ 120
- Figura 6.10: Panel de acciones. ............................................................................................... 121
- Figura 6.11: Panel de algoritmos. ........................................................................................... 121
- Figura 6.12: Área de texto – Explicación Add Edge ................................................................ 122
- Figura 6.13: Área de dibujo – ejemplo grafo .......................................................................... 122
- Figura 6.14: Crear grafo nuevo ............................................................................................... 123
- Figura 6.15: Creación grafo aleatorio- Probabilidad aristas ................................................... 123
vi
- Figura 6.16: Grafo aleatorio con pesos asignados. ................................................................. 124
- Figura 6.17: Exportar grafo. ..................................................................................................... 125
- Figura 6.18: Insertar peso a un nodo ...................................................................................... 127
- Figura 6.19: Ejecución paso a paso.......................................................................................... 130
- Figura 6.20: Grafo ejemplo (Petersen). ................................................................................... 131
- Figura 6.21: Ejemplo ejecución inmediata – Algoritmo Greedy.............................................. 131
- Figura 6.22: Ejemplo ejecución paso a paso – Algoritmo Greedy – Paso1. ............................ 132
- Figura 6.23: Ejemplo ejecución paso a paso – Algoritmo Greedy – Paso2 ............................. 133
- Figura 6.24: Ejemplo ejecución paso a paso – Algoritmo Greedy – Paso3. ............................ 134
- Figura 6.25: Grafo ejemplo – Weighted Dominance ............................................................... 135
- Figura 6.26: Introducir número de sensores – Weighted Dominance .................................... 135
- Figura 6.27: Ejecución inmediata – Weighted Dominance ..................................................... 135
- Figura 6.28: Ejecución paso a paso – Weighted Dominance – Paso1 ..................................... 136
- Figura 6.29: Ejecución paso a paso – Weighted Dominance – Paso2 ..................................... 136
- Figura 6.30: Ejecución paso a paso – Weighted Dominance – Paso3 ..................................... 137
- Figura 6.31: Grafo ejemplo – Tree Growing ............................................................................ 138
- Figura 6.32: Ejecución inmediata – Tree Growing................................................................... 138
- Figura 6.33: Ejecución paso a paso – Tree Growing – Paso1 .................................................. 139
- Figura 6.34: Ejecución paso a paso – Tree Growing – Paso2 .................................................. 139
- Figura 6.35: Ejecución paso a paso – Tree Growing – Pasos intermedios .............................. 139
- Figura 6.36: Ejecución paso a paso – Tree Growing – Paso final ............................................ 140
- Figura 6.37: Ejecución paso a paso – Tree Growing – Solución .............................................. 140
- Figura 6.38: Grafo ejemplo – Algoritmo Marking ................................................................... 141
- Figura 6.39: Selección grafo inicial – Algoritmo Marking ........................................................ 142
- Figura 6.40: Grafo inicial seleccionado – Algoritmo Marking ................................................. 143
- Figura 6.41: Ejecución inmediata – Algoritmo Marking .......................................................... 144
- Figura 6.42: Ejecución paso a paso – Algoritmo Marking – Nodo inicial ................................ 145
- Figura 6.43: Ejecución paso a paso – Algoritmo Marking – Paso2 .......................................... 146
- Figura 6.44: Ejecución paso a paso – Algoritmo Marking – Pasos intermedios. ..................... 147
- Figura 6.45: Ejecución paso a paso – Algoritmo Marking – Paso final. ................................... 147
vii
viii
I NDICE DE CUADROS
- Cuadro 5.1: Caso de uso: Exportar grafo ................................................................................... 52
- Cuadro 5.2: Caso de uso: Importar grafo .................................................................................. 53
- Cuadro 5.3: Caso de uso: Crear grafo nuevo ............................................................................. 53
- Cuadro 5.4: Caso de uso: Añadir vértice ................................................................................... 53
- Cuadro 5.5: Caso de uso: Eliminar vértice ................................................................................. 54
- Cuadro 5.6: Caso de uso: Añadir arista ..................................................................................... 54
- Cuadro 5.7: Caso de uso: Eliminar arista ................................................................................... 54
- Cuadro 5.8: Caso de uso: Añadir peso ....................................................................................... 55
- Cuadro 5.9: Caso de uso: Mover vértice ................................................................................... 55
- Cuadro 5.10: Caso de uso: Eliminar grafo ................................................................................. 55
- Cuadro 5.11: Caso de uso: Generar grafo aleatorio .................................................................. 56
- Cuadro 5.12: Caso de uso: Generar grafo aleatorio con pesos ................................................. 56
- Cuadro 5.13: Caso de uso: Ejecutar algoritmo paso a paso ...................................................... 57
- Cuadro 5.14: Caso de uso: Detener algoritmo ......................................................................... 57
- Cuadro 5.15: Caso de uso: Siguiente paso algoritmo ................................................................ 57
- Cuadro 5.16: Caso de uso: Crear grafo vacío. ........................................................................... 58
- Cuadro 5.17: Caso de uso: Crear grafo completo Km ............................................................... 58
- Cuadro 5.18: Caso de uso: Crear grafo completo bipartido Km,n ............................................ 58
- Cuadro 5.19: Caso de uso: Crear grafo enlazado Ln,r ............................................................... 59
- Cuadro 5.20: Caso de uso: Crear grafo enlazado Ln,r,s ............................................................. 59
- Cuadro 5.21: Caso de uso: Crear grafo rejilla rectangular ........................................................ 60
- Cuadro 5.22: Caso de uso: Crear grafo ciclo Cn ........................................................................ 60
- Cuadro 5.23: Caso de uso: Crear grafo rueda Wn ..................................................................... 60
- Cuadro 5.24: Caso de uso: Crear grafo estrella ......................................................................... 61
- Cuadro 5.25: Caso de uso: Crear grafo Herschel ....................................................................... 61
- Cuadro 5.26: Caso de uso: Crear grafo Petersen ...................................................................... 61
- Cuadro 5.27: Caso de uso: Crear grafo Heawood ..................................................................... 62
- Cuadro 5.28: Caso de uso: Crear grafo Grotzsch ....................................................................... 62
- Cuadro 5.29: Caso de uso: Ejecución algoritmo Dominating Set. ............................................. 62
- Cuadro 5.30: Caso de uso: Ejecución algoritmo Weighted Dominance. ................................... 63
ix
- Cuadro 5.31: Caso de uso: Ejecución algoritmo Tree Growing ................................................ 63
- Cuadro 5.32: Caso de uso: Ejecución algoritmo Marking ......................................................... 64
- Cuadro 5.33: Caso de uso: Mostrar información ...................................................................... 64
- Cuadro 5.34: Caso de uso extendido: Escenario principal: Exportar grafo .............................. 66
- Cuadro 5.35: Caso de uso extendido: Escenarios alternativos: Exportar grafo ........................ 66
- Cuadro 5.36: Caso de uso extendido: Escenario principal: Importar grafo .............................. 68
- Cuadro 5.37: Caso de uso extendido: Escenarios alternativos: Importar grafo ....................... 68
- Cuadro 5.38: Caso de uso extendido: Escenario principal: Crear grafo nuevo......................... 69
- Cuadro 5.39: Caso de uso extendido: Escenarios alternativos: Crear grafo nuevo .................. 69
- Cuadro 5.40: Caso de uso extendido: Escenario principal: Añadir vértice ............................... 70
- Cuadro 5.41: Caso de uso extendido: Escenarios alternativos: Añadir vértice ........................ 71
- Cuadro 5.42: Caso de uso extendido: Escenario principal: Eliminar vértice ............................ 72
- Cuadro 5.43: Caso de uso extendido: Escenarios alternativos: Eliminar vértice ...................... 72
- Cuadro 5.44: Caso de uso extendido: Escenario principal: Añadir arista ................................. 73
- Cuadro 5.45: Caso de uso extendido: Escenarios alternativos: Añadir arista .......................... 73
- Cuadro 5.46: Caso de uso extendido: Escenario principal: Eliminar arista .............................. 74
- Cuadro 5.47: Caso de uso extendido: Escenarios alternativos: Eliminar edge ......................... 74
- Cuadro 5.48: Caso de uso extendido: Escenario principal: Añadir peso .................................. 75
- Cuadro 5.49: Caso de uso extendido: Escenarios alternativos: Añadir peso............................ 76
- Cuadro 5.50: Caso de uso extendido: Escenario principal: Mover vértices ............................. 77
- Cuadro 5.51: Caso de uso extendido: Escenario principal: Eliminar grafo ............................... 78
- Cuadro 5.52: Caso de uso extendido: Escenario alternativo: Eliminar grafo ........................... 78
- Cuadro 5.53: Caso de uso extendido: Escenario principal: Generar grafo aleatorio ................ 79
- Cuadro 5.54: Caso de uso extendido: Escenarios alternativos: Generar grafo aleatorio ......... 79
- Cuadro 5.55: Caso de uso extendido: Escenario principal: Generar grafo aleatorio con pesos80
- Cuadro 5.56: Caso de uso extendido: Escenarios alternativos: Generar grafo aleatorio con
pesos ......................................................................................................................................... 81
- Cuadro 5.57: Caso de uso extendido: Escenario principal: Ejecutar algoritmo paso a paso .... 82
- Cuadro 5.58: Caso de uso extendido: Escenario principal: Detener algoritmo ........................ 83
- Cuadro 5.59: Caso de uso extendido: Escenario principal: Siguiente paso algoritmo ............. 84
- Cuadro 5.60: Caso de uso extendido: Escenario principal: Crear grafo vacío .......................... 85
- Cuadro 5.61: Caso de uso extendido: Escenarios alternativos: Crear grafo vacío ................... 85
x
- Cuadro 5.62: Caso de uso extendido: Escenario principal: Crear grafo completo Km .............. 86
- Cuadro 5.63: Caso de uso extendido: Escenarios alternativos: Crear grafo completo Km ....... 86
- Cuadro 5.64: Caso de uso extendido: Escenario principal: Crear grafo completo bipartido
Km,n .......................................................................................................................................... 87
- Cuadro 5.65: Caso de uso extendido: Escenarios alternativos: Crear grafo completo bipartido
Km,n .......................................................................................................................................... 88
- Cuadro 5.66: Caso de uso extendido: Escenario principal: Crear grafo enlazado Ln,r.............. 89
- Cuadro 5.67: Caso de uso extendido: Escenarios alternativos: Crear grafo enlazado Ln,r ....... 89
- Cuadro 5.68: Caso de uso extendido: Escenario principal: Crear grafo enlazado Ln,r,s ........... 90
- Cuadro 5.69: Caso de uso extendido: Escenarios alternativos: Crear grafo enlazado Ln,r,s .... 91
- Cuadro 5.70: Caso de uso extendido: Escenario principal: Crear grafo rejilla rectangular ....... 92
- Cuadro 5.71: Caso de uso extendido: Escenarios alternativos: Crear grafo rejilla rectangular 92
- Cuadro 5.72: Caso de uso extendido: Escenario principal: Crear grafo ciclo Cn ....................... 93
- Cuadro 5.73: Caso de uso extendido: Escenarios alternativos: Crear grafo ciclo Cn ................ 93
- Cuadro 5.74: Caso de uso extendido: Escenario principal: Crear grafo rueda Wn ................... 94
- Cuadro 5.75: Caso de uso extendido: Escenarios alternativos: Crear grafo rueda Wn ............ 94
- Cuadro 5.76: Caso de uso extendido: Escenario principal: Crear grafo estrella ....................... 95
- Cuadro 5.77: Caso de uso extendido: Escenarios alternativos: Crear grafo estrella ................ 96
- Cuadro 5.78: Caso de uso extendido: Escenario principal: Crear grafo de Herschel ................ 96
- Cuadro 5.79: Caso de uso extendido: Escenario principal: Crear grafo de Petersen ................ 97
- Cuadro 5.80: Caso de uso extendido: Escenario principal: Crear grafo de Heawood ............... 98
- Cuadro 5.81: Caso de uso extendido: Escenario principal: Crear grafo de Grotzsch ................ 99
- Cuadro 5.82: Caso de uso extendido: Escenario principal: Ejecución algoritmo Dominating Set
................................................................................................................................................ 100
- Cuadro 5.83: Caso de uso extendido: Escenarios alternativos: Ejecución algoritmo Dominating
Set ........................................................................................................................................... 101
- Cuadro 5.84: Caso de uso extendido: Escenario principal: Ejecución algoritmo Weighted
Dominance ................................................................................................................................. 102
- Cuadro 5.85: Caso de uso extendido: Escenarios alternativos: Ejecución algoritmo Weighted
Dominance .............................................................................................................................. 103
- Cuadro 5.86: Caso de uso extendido: Escenario principal: Ejecución algoritmo Tree Growing
................................................................................................................................................... 104
xi
- Cuadro 5.87: Caso de uso extendido: Escenarios alternativos: Ejecución algoritmo Tree
Growing .................................................................................................................................. 105
- Cuadro 5.88: Caso de uso extendido: Escenario principal: Ejecución algoritmo Marking ..... 106
- Cuadro 5.89: Caso de uso extendido: Escenarios alternativos: Ejecución algoritmo Marking107
1
PARTE I
INTRODUCCIO N
2
3
CAPI TULO 1.- INTRODUCCIO N
En el mundo actual existen numerosos problemas sin resolver debido a su
enorme complejidad. Esta complejidad viene detallada y clasificada en la Teoría de
Complejidad que a continuación explicaremos.
En el presente proyecto se ha querido realizar una aplicación informática que
modela distintos algoritmos que permiten obtener una solución a los distintos problemas
presentes dentro de la dominación en grafos. Estos problemas están presentes en
muchos ámbitos de la tecnología. Uno de ellos es el ámbito de la vigilancia para obtener
el conjunto mínimo de cámaras necesarias para tener vigiladas el mayor número de
objetos posibles, como calles, salas de museo, etc. Pero es en el ámbito de las
comunicaciones y las redes ad-hoc donde la dominación en grafos cobra mayor
relevancia, donde los vértices de esa red no se conocen o están en continuo movimiento.
Los conjunto dominantes conexos, por ejemplo, se utilizan para obtener buenos
enlaces o caminos en redes móviles.
Ilustración 1 - Figura 1.1: Redes móviles
Los algoritmos estudiados no reportan una solución única ni tampoco óptima,
simplemente será una solución próxima a la mejor posible. De esta forma se puede
obtener solución a problemas cuya complejidad no permite obtener una solución única.
4
En teoría de complejidad destacamos dos tipos de problemas:
NP-Difícil (NP-Hard)
NP-Completo (NP-Complete)
El objetivo de este proyecto es realizar distintos algoritmos que den solución al
problema del Conjunto Dominante (Dominating Set) de un grafo, ya que el problema
de calcular un conjunto dominante mínimo es NP-Difícil, nos centraremos en presentar
distintos algoritmos que obtienen soluciones aproximadas al problema Minimum
Dominating Set (conjunto dominante de cardinal mínimo), y a alguna de sus variantes.
Dado que la solución no es única, se ha desarrollado una aplicación java que
ejecuta varios algoritmos que son distintos en su forma de llegar a la solución y que
calculan soluciones rápidas y próximas a la solución óptima.
Concretamente la aplicación permite ejecutar dichos algoritmos partiendo desde
distintos grafos:
Grafos conocidos.
Grafos aleatorios.
Grafos creados manualmente.
5
CAPI TULO 2.- COMPLEJIDAD COMPUTACIONAL
En complejidad computacional hay dos términos que son utilizados para evaluar
la complejidad de un algoritmo, el espacio y el tiempo.
Espacio: Se estima la cantidad de memoria que será necesaria en la ejecución
del algoritmo.
Tiempo: Se estima la cantidad de pasos (tiempo) necesarios en la ejecución del
algoritmo.
Los diversos problemas se clasifican según su complejidad en distintas clases.
Estas clases son: L, NL, P, PCompleto, NP, NPH, NPCompleto etc., pero en esta
sección nos centraremos en los problemas polinomiales no determinados (NP, NPH,
NPC).
2.1 CLASE P (Polynomial-time)
Un problema pertenece a la clase P si puede ser resuelto mediante un algoritmo
en un tiempo polinomial.
Complejidad 𝑂(𝑛𝑘) siendo 𝑘 una constante y 𝑛 → ∞.
2.2 CLASE NP (Non-deterministic polynomial-time)
Es el conjunto de todos los problemas que pueden ser verificados por un
algoritmo en tiempo polinomial.
La clase P está contenida en NP, P ⊆ NP: Si un problema se puede solucionar en
un tiempo polinómico, su solución se puede verificar en tiempo polinómico.
6
2.3 CLASE NPH (Non-deterministic polynomial-time hard)
NPH (NP-Hard o NP-Difícil) es el conjunto de los problemas de decisión que
contiene los problemas H tales que todo problema L en NP puede ser transformado
polinomialmente en H.
Contiene los problemas de decisión que son a los menos tan difíciles como un
problema NP.
Si podemos encontrar un algoritmo A que resuelve uno de los problemas H de
NP-hard en tiempo polinómico, entonces es posible construir un algoritmo que trabaje
en tiempo polinómico para cualquier problema de NP ejecutando primero la reducción
de este problema en H y luego ejecutando el algoritmo A.
2.4 CLASE NPC (Non-deterministic polynomial-time complete)
La clase NP-completo puede definirse alternativamente como la intersección
entre NP y NPH.
Se puede decir que los problemas de NP-completo son los problemas más
difíciles de NP y muy probablemente no formen parte de la clase de complejidad P.
Ilustración 2 - Figura 2.1: Clases de complejidad
7
Todos los algoritmos que se conocen para utilizar en problemas NP-completos
utilizan tiempo exponencial con respecto al tamaño de la entrada. Se desconoce si
existen algoritmos más rápidos, por lo tanto, para resolver un problema NP-completo de
tamaño arbitrario, se utiliza uno de los siguientes enfoques.
Aproximación: Un algoritmo que rápidamente encuentra una solución no
necesariamente óptima, pero dentro de un cierto rango de error. No todos los
problemas NP-completos tienen algoritmos de aproximación.
Probabilístico: Utiliza aleatoriedad para obtener en promedio una buena
solución con una pequeña probabilidad de fallo, para una distribución de los
datos de entrada.
Restricciones: Restringiendo la estructura de las entradas se pueden obtener
algoritmos más rápidos.
Casos particulares: Puede ocurrir que se reconozcan casos particulares del
problema para los cuales existen soluciones rápidas.
Algoritmo genético: Mejoran las posibles soluciones hasta encontrar una que
esté cerca del óptimo. No existe forma de garantizar la calidad de la respuesta.
Heurísticas: Un algoritmo que trabaja razonablemente bien en muchos casos. En
general son rápidos, pero no existe medida de la calidad de la respuesta.
8
9
PARTE II
TEORI A
10
11
CAPITULO 3.- TEORI A
A continuación vamos a introducir los conceptos básicos en la teoría de grafos,
ya que serán necesarios para comprender el desarrollo de este proyecto.
3.1 Conceptos generales.
3.1.1 Definición. Un grafo G = (V, A) consiste en un conjunto no vacío y
finito V, cuyos miembros se llaman vértices y una familia finita A de pares no
ordenados de vértices a cuyos elementos llamaremos aristas o arcos y que denotaremos
por (u, v), donde u y v є V.
3.1.2 Definición. Se denomina orden del grafo al número de vértices del
grafo G. Es la cardinalidad del conjunto V y se denota por |V|. Por lo general se utiliza n
para denotar el orden de G.
3.1.3 Definición. Se denomina grado de un vértice al número de aristas
incidentes al vértice. Se denota g(x) o del inglés d(x). El grado máximo de un grafo G es
denotado por ∆(𝐺) y el grado mínimo por 𝛿(𝐺).
3.1.4 Definición. El número de aristas, es decir, la cardinalidad del conjunto A
se denomina tamaño del grafo y se denota por |A|. Se suele utilizar m para denotar el
tamaño de G.
Dado un grafo G = (V, A) podemos afirmar que:
Dos vértices son adyacentes si tienen una arista común.
Una arista y un vértice son incidentes si el vértice es extremo de la arista.
12
Se denomina grado de un vértice al número de aristas incidentes con él,
contando los bucles como dos aristas. Se denota por d(v) al grado del vértice
v.
Ilustración 3 - Figura 3.1: Ejemplo de grafo
Según el grafo de la figura 3.1:
El orden del grafo es 6. |V| = 6.
El tamaño del grafo es 7. |A| = 7.
El vértice 6 es adyacente a los vértices 1,2,3 y 4.
o Su grado es 4. d(6) =4.
o Es incidente de las siguientes aristas (1,6), (2,6), (3,6) y (4,6).
3.1.5 Definición. Un grafo simple G = (V, A) diremos que es un grafo
ponderado si tiene asociado una función W: A → R llamada función de ponderación.
Denominaremos peso de un vértice v a la suma de los pesos 𝑊𝑖𝑗, de sus aristas
incidentes.
3.1.6 Definición. Un grafo es conexo si cada par de vértices está conectado por
un camino; es decir, si para cualquier par de vértices (u, v), existe al menos un camino
posible desde u hacia v.
13
3.1.7 Definición. Un grafo completo es un grafo simple en el que todo par de
vértices está unido por una arista. Se designa con 𝐾𝑛 al grafo completo de n vértices.
Este grafo tiene 𝑛(𝑛−1)
2 aristas.
3.1.8 Definición. Sea G(V, A) un grafo de orden n. Un subconjunto S de V se
llama dominante si todo vértice v de V – S es vecino de un elemento de S.
Al número mínimo de elementos de un conjunto dominante se le llama
número de dominación del grafo y se designa por 𝛾(𝐺).
Un conjunto dominante D es minimal si para cualquier elemento x de D, el
conjunto D – {x} no es dominante.
Ilustración 4 - Figura 3.2: a.- Conjunto dominante de G. b.- Conjunto dominante minimal. c.- Conjunto dominante de cardinalidad mínimo
3.2 Algoritmo de generación aleatoria de grafos.
Las funcionalidades de generación de grafos aleatorios son muy útiles para
obtener conjuntos de muestreo de grafos de forma rápida.
Dentro de los posibles algoritmos que se suelen utilizar para generar grafos de
forma aleatoria, vamos a mencionar el que nos ha servido de base para la aplicación.
14
El modelo de grafo G(n, p), llamado Generación aleatoria de grafos Erdos
Rényi, consiste en:
Crear aleatoriamente n vértices del grafo
Donde la probabilidad de existencia de arista entre cada par de vértices
viene determinada por el valor de p: 0 ≤ 𝑝 ≤ 1. Modificado en la
aplicación para poner valores a modo de porcentaje 0 ≤ 𝑝 ≤ 100.
Para garantizar una alta conectividad de los grafos generados se suele trabajar
con valores de 𝑝 ≥log (𝑛)
𝑛.
1: Inicializar grafo G(V, E)
2: for i ← 1 to n
3: for j ← i+1 to n
4: añadir arco (i, j) a E con probabilidad p
5: return (G)
Ilustración 5 - Figura 3.3: Pseudocódigo generación aleatoria de grafos
3.3 Tipos de grafos
En este apartado vamos a explicar los tipos de grafos que se pueden crear
directamente en la aplicación, incluyendo un ejemplo visual.
3.3.1 Grafo vacío
Aquel que no tiene aristas. En la aplicación, el grafo vacío ha sido representado
en forma de círculo.
15
Ilustración 6 - Figura 3.4: Grafo vacío de 10 vértices
3.3.2 Grafo completo.
Grafo simple G en el que cada par de vértices u y v están unidos por una arista;
es decir, contiene todas las posibles aristas.
El grafo completo de n vértices tiene n vértices y n(n − 1) / 2 aristas, y se nota
Kn. Es un grafo regular con todos sus vértices de grado n − 1.
Ilustración 7 - Figura 3.5: Grafo completo de 8 vértices 𝑲𝟖
16
3.3.3 Grafo bipartido completo.
Sea (W, X) una partición del conjunto de vértices V del grafo G, un grafo
bipartido completo es aquél donde cada vértice en W es adyacente solo a cada vértice en
X.
Se denota como 𝐾𝑚,𝑛 donde m y n son el número de nodos en cada conjunto de
vértices W y X.
En la figura 3.6 podemos ver que la partición de vértices es la siguiente:
W = { 1, 2, 3, 4 }
V = { 5, 6, 7 }
Ilustración 8 - Figura 3.6: Grafo bipartido completo de 7 vértices 𝑲𝟒,𝟑
3.3.4 Grafo enlazado L(n, r).
El grafo enlazado es una figura compuesta por n vértices y r elementos
conexos.
17
Ilustración 9 - Figura 3.7: Grafo enlazado L(8,2)
La figura 3.7 muestra un grafo con valor 8 para n y 2 para r. Se puede observar
claramente las dos componentes conexas del grafo en forma de cuadrados:
Componente conexa 1: Vértices { 1, 3, 5, 7 }
Componente conexa 2: Vértices { 2, 4, 6, 8 }
3.3.5 Grafo enlazado L(n, r, s)
El grafo enlazado L(n, r, s) es una figura compuesta por n vértices, r elementos
conexos y s elementos conexos a su vez.
Si el valor de r y de s es 1, se obtiene el grafo ciclo.
18
Ilustración 10 - Figura 3.8: Grafo enlazado L(8,2,1)
Como se puede observar al ser el valor de la segunda componente conexa s
igual a 1, se crea el grafo ciclo.
3.3.6 Grafo rejilla rectangular.
El grafo en rejilla rectangular es una unión de un grafo simple de 4 vértices con
grado para y 4 aristas que forman un ciclo.
La sucesión de este grafo en horizontal y vertical origina una rejilla compuesta
por multitud de cuadrados. En la aplicación se creará el grafo en función del número de
filas y columnas que deseemos.
19
Ilustración 11 - Figura 3.9: Grafo rejilla rectangular (3 filas, 8 columnas)
3.3.7 Grafo ciclo.
En Teoría de grafos, un Grafo ciclo o simplemente ciclo es un grafo con la
forma de un polígono de n lados.
Consiste en un camino cerrado en el que no se repite ningún vértice a excepción
del primero que aparece dos veces como principio y fin del camino. Un Grafo ciclo de n
vértices se denota 𝐶𝑛.
El número de vértices en un grafo 𝐶𝑛 es igual al número de aristas, y cada
vértice tiene grado par, por lo tanto cada vértice tiene dos aristas incidentes. Si el grafo
G (V, A) es un ciclo 𝐶𝑛:
Tiene n vértices V = {𝑉1, , 𝑉2,..., 𝑉𝑛}
Tiene n aristas formadas A = {{𝑉𝑖, 𝑉𝑖+1 }i =1,..., n}U{𝑉𝑛, 𝑉1}
20
Ilustración 12 - Figura 3.10: Grafo ciclo de 12 vértices 𝑪𝟏𝟐
3.3.8 Grafo Rueda.
Dado un vértice central C en el plano y n vértices 𝑃𝑖, i = 0, 1,..., n, entre los
cuales no hay tres alineados, llamamos grafo rueda de centro C y n vértices al conjunto
de aristas (C, 𝑃𝑖) y de (𝑃𝑖, 𝑃𝑖+1). Si los puntos Pi están en los vértices de un polígono
regular y C en su centro, se obtienen grafos de rueda regulares.
El número de aristas en un grafo de rueda es igual al doble de número de
vértices – 2, y cada vértice tiene grado 3, excepto el vértice central que tiene (n – 1). Si
el grafo G (V, A) es un grafo Rueda 𝑊𝑛.
Tiene n vértices 𝑉 = {𝑉1, 𝑉2, . . . , 𝑉𝑛 }
Tiene 2n-2 aristas formadas por un ciclo y una estrella: A = A′ U A′′
donde:
A’ = {{𝑉𝑖 , 𝑉𝑖+1}i = 2,..., n}U {𝑉𝑛 , 𝑉2}
A’’ = {{𝑉𝑖 , 𝑉𝑖}i = 2,..., n}
21
Ilustración 13 - Figura 3.11: Grafo Rueda 𝑾𝟏𝟐
3.3.9 Grafo estrella.
Llamamos grafo estrella o estrellado de centro C y n vértices al conjunto de
segmentos C𝑃𝑖, siendo 𝑃𝑖 una sucesión de vértices 𝑃𝑖, i = 0, 1,..., n, entre los cuales no
hay tres alineados. Si los puntos 𝑃𝑖están en los vértices de un polígono regular y C en su
centro, se obtienen grafos estrellados regulares.
Ilustración 14 - Figura 3.12: Grafo estrella de 12 vértices.
22
3.3.10 Grafo de Herschel
El grafo de Herschel es un grafo bipartido no dirigido construido por 11
vértices y 18 aristas, siendo el grafo poliedro no Hamiltoniano más pequeño.
Surge a raíz de la creación de un juego desarrollado por el astrónomo británico
Alexander Stweart Herschel, llamado “Icosian”. Encontró el poliedro convexo para el
que el juego no tenía solución.
Las propiedades más representativas de este grafo son:
Es un grafo planar: “Puede ser dibujado sin que las aristas que se dibujan
se crucen”.
Es un grafo 3-conexo: El borrado de dos vértices cualesquiera deja un
subgrafo conectado. Por lo tanto, siguiendo el teorema Steinitz’s, el grafo
Herschel es un grafo poliedro.
Es un grafo bipartido: Sus vértices pueden separarse en dos conjuntos de
5 y 6 vértices respectivamente tal que cada arista tiene un vértice en cada
conjunto.
Ilustración 15 - Figura 3.13: Grafo de Herschel
23
3.3.11 Grafo de Petersen
El grafo de Petersen es uno de los grafos más representativos de la teoría de
grafos y está compuesto por 10 vértices de grado 3 y 15 aristas.
Las propiedades más representativas son:
Es un grafo regular de grado 3.
Dos vértices adyacentes no tienen vecinos en común, no obstante, no es
bipartido, pues existen varios ciclos de longitud impar.
Dos vértices no adyacentes tienen exactamente un vecino en común.
Es un grafo no planar.
Ilustración 16 - Figura 3.14: Grafo de Petersen
3.3.12 Grafo de Heawood.
Creado por Percy John Heawood. Es un grafo no dirigido compuesto por 14
vértices y 21 aristas. El grafo es cúbico y todos los ciclos del grafo se componen por 6 o
más aristas. Cada grafo cúbico más pequeño tiene menos ciclos. Este grafo es el grafo
cúbico más pequeño de cintura 6.
24
Tiene 24 conjuntos de aristas sin vértices en común. Para cada uno el conjunto
de aristas forma un ciclo hamiltoniano.
Ilustración 17 - Figura 3.15: Grafo de Heawood
3.3.13 Grafo de Grötzsch.
El grafo de Grötzsch es el grafo más pequeño del tipo sin 3-ciclos compuesto
por 11 vértices y 20 aristas. Es idéntico al grafo de Mycielski de orden 4.
Su nombre surge después de que el alemán Herbert Grötzsch lo utilizara para
demostrar la necesidad de planaridad en el teorema de Grötzsch, dicho teorema dice que
todo grafo planar sin 3-ciclos se puede colorear con 3 colores
Este grafo es miembro de una secuencia infinita de grafos sin 3-ciclos que
comienza con el grafo nulo. Esta secuencia de grafos la usó Mycielski para demostrar la
existencia de grafos sin 3-ciclos. Por lo que a veces este grafo es llamado también el
grafo de Mycielski.
25
Ilustración 18 - Figura 3.16: Grafo de Grötzsch
26
CAPI TULO 4.- DOMINACION EN GRAFOS
4.1 Descripción del problema
El conjunto dominante de un grafo G = (V, E) es un subconjunto V' de V tal
que cada vértice que no pertenezca a V' está unido a (al menos) un miembro de V'.
El número dominante γ(G) es el cardinal del menor conjunto dominante de G.
Dado un grafo G = (V, E) el problema de optimización del conjunto dominante
consiste en hallar D ⊆ V un conjunto dominante de tamaño mínimo. El problema de
decisión asociado consiste en, dado k determinar si γ(G) ≤ k es un clásico problema
NP-completo en la teoría de complejidad computacional (Garey y Johnson, 1979). Por
lo tanto, se cree que no hay ningún algoritmo eficiente que encuentre un pequeño
conjunto dominante para un grafo dado.
Las figuras (a) - (c) muestran tres ejemplos de juegos para dominar un
grafo. En cada ejemplo, cada vértice blanco es adyacente a al menos un vértice rojo, y
se dice que el vértice blanco está dominado por el vértice rojo. El número dominación
de esta gráfica es 2: los ejemplos (b) y (c) muestran que existe un conjunto dominante
con 2 vértices, y se puede comprobar que no existe un conjunto dominante con sólo 1
vértice para este grafo.
Ilustración 19 - Figura 4.1: Conjunto dominante
27
Los problemas presentes en el mundo de la comunicación, donde se pretende
calcular el número mínimo de centros de transmisiones (broadcast center, hubs,… )
para comunicar con todos los posibles destinos, es un ejemplo muy común de un
problema de dominación.
En el presente proyecto estudiaremos distintos algoritmos heurísticos que den
una solución al problema de Dominación en Grafos.
4.2 Heurísticas – Algoritmos (ejemplos)
Este tipo de problemas tienen por objetivo encontrar el conjunto dominante C
con la menor cardinalidad posible, que domine todos los vértices del grafo desde los
vértices que formen C.
Un conjunto dominante puede ser independiente o conexo.
Se denomina conjunto dominante independiente si cualquier par de
vértices u, v de dicho conjunto C no son adyacentes.
Se denomina conjunto dominante conexo, cuando los vértices que
forman C crean un subgrafo D que es conexo.
Los algoritmos heurísticos que vamos a estudiar son:
Greedy Algorithm
Tree Growing Algorithm
Marking Algorithm
Weighted Dominance
De los cuales dos algoritmos obtienen soluciones o conjuntos dominantes no
conexos (Algoritmos Greedy y Weighted Dominance) y los otros dos
(Algoritmos Tree Growing y Marking) consiguen conjuntos dominantes conexos
(CDS).
28
4.2.1 Greedy Algorithm
Es el algoritmo más sencillo, donde el conjunto S dominante se va formando
con los vértices v que tienen mayor grado.
1: S := ∅;
2: while ∃ white nodes do
3: choose v ∈ {x | w(x) = {𝑚𝑎𝑥𝑢∈𝑉{w(u)}};
4: S := S ∪ {v};
5: end while
4.2.1.1 Ejemplo de ejecución – Algoritmo greedy.
Se ha utilizado el grafo de Gortzsch para ilustrar el algoritmo greedy para
obtener un conjunto dominante.
Ilustración 20 - Figura 4.2: Primer paso algoritmo greedy
29
Como se puede observar en la figura 4.2, el primer paso ha escogido el vértice
11 por ser el vértice con mayor grado (d(11) = 5). Los vértices en color gris han sido los
eliminados por ser vecinos del vértice 11, de esta forma se intenta obtener un conjunto
dominante de cardinalidad mínima.
Ilustración 21 - Figura 4.3: Segundo paso (paso intermedio) algoritmo greedy
En este segundo paso, hay varios vértices con el mismo grado, d(1, 2, 3,
4,5)=4, simplemente por orden se ha seleccionado y añadido al conjunto dominante al
vértice 1, eliminando del siguiente paso los vecinos de este vértice.
30
Ilustración 22 - Figura 4.4: Paso final algoritmo greedy
Por último se ha incluido el vértice 3 en el conjunto dominante, y como
resultado todos los nodos del grafo de Grotzsch quedan dominados por el conjunto de
vértices {1, 3, 11}. Como se puede observar la solución no es única y no es conexa.
4.2.2 Algoritmo Weighted Dominance.
Es el único algoritmo que incluye peso en los vértices del grafo. Previamente se
ha de escoger un número determinado de nodos que queremos que formen parte del
conjunto dominante. De esta forma el algoritmo en base a los pesos de los vértices
calculará el conjunto dominante mínimo con lo k nodos seleccionados.
Input: graph G, where all v ∈ 𝑉𝐺 has a valid W (weight) = w(v) >= 0
k number;
1: While k > 0 then
2: for all v ∈ 𝑉𝐺 ; w(v) = {w(v) + ∑ 𝑤(𝑢)𝑢𝜖𝑁(𝑣) }
31
3: choose e ∈ {x | w(x) = {𝑚𝑎𝑥𝑢∈𝑉{w(v)}};
4: add e to domination set
5: G = {𝑉𝐺 − {𝑣} − {𝑁(𝑣)}}
6: k--;
6: Return domination set.
El grafo inicial G contiene una serie de vértices VG, donde todo v ∈ VG tiene un
determinado peso, w(v).
Por cada nodo que vaya a formar parte del conjunto dominante final, número
determinado por k, se calcula un nuevo peso a cada vértice como el peso de propio
vértice y la suma de los pesos de sus vértices vecinos N(v).
Una vez calculado este nuevo peso, se escoge el nodo que tenga mayor peso y
ese pasará a formar parte del conjunto dominante final y el grafo resultante será el
formado por todos los vértices VG menos v y todos los vecinos de v (N(v)).
El algoritmo para su ejecución cuando VG = {} o k = 0. Obteniendo un conjunto
dominante de cardinalidad k.
Este algoritmo es muy útil para calcular donde deberíamos situar, por ejemplo, k
cámaras de vigilancia y de esta forma tener controlados la mayoría de las obras de un
museo dando importancia a cada obra incrementando su peso.
4.2.2.1 Ejemplo de ejecución
Tomando el siguiente grafo como ejemplo:
32
Ilustración 23 - Figura 4.5: Grafo inicial algoritmo weighted dominance
Como se puede observar todos los vértices del grafo tienen un determinado peso.
Ilustración 24 - Figura 4.6: Cálculo nuevos pesos algoritmo weighted dominance
En la ilustración 23 podemos ver el nuevo peso de cada vértice, resultante de
sumar su propio peso y el peso de sus vértices vecinos.
El siguiente paso es escoger el nodo que tenga mayor peso para incluirlo en el
conjunto dominante final.
33
Ilustración 25 - Figura 4.7: Vértice con mayor peso algoritmo weighted dominance
A continuación mostramos el grafo resultante de eliminar el vértice añadido al
conjunto dominante y todos los vecinos de este.
Ilustración 26 - Figura 4.8: Grafo resultado eliminar vértice y vecinos algoritmo weighted dominance
Como se puede observar los vértices en este momento vuelven a tener el peso
que tenían al comienzo del algoritmo y volvemos a calcular su nuevo peso.
34
Ilustración 27 - Figura 4.9: Siguiente vértice añadido al conjunto dominante algoritmo weigthed dominance
Después de volver a calcular los nuevos pesos, se añade el nodo con mayor peso
al conjunto dominante final, repitiendo el proceso de la primera iteración.
Este proceso se repite hasta que el grafo resultante de eliminar el último
vértice añadido al conjunto dominante y todos sus vecinos, sea vacío o el conjunto
dominante final ya tenga k vértices seleccionados.
A continuación mostramos el resultado final de ejecutar el algoritmo para k=3.
Ilustración 28 - Figura 4.10: Final ejecución algoritmo weigthed dominance
El conjunto dominante final es el formado por los nodos que aparecen en amarillo.
35
4.2.3 Algoritmo Tree Growing
El algoritmo Tree Growing parte de un grafo conexo y obtiene un conjunto
dominante también conexo, tratando el grafo inicial como un árbol, partiendo de un
vértice inicial v por el que va recorriendo sus ramas.
Entrada: Un grafo conectado G, un vértice inicial v ∈ 𝑉𝐺 y una función de
selección de nodos grises.
Salida: Un árbol de expansión ordenado T de G con nodo inicial v.
1: Inicializar árbol T con vértice inicial v.
2: Inicializar vértices blancos.
3: While S ≠ ∅
4: seleccionamos e ∈ {x | w(x) = {𝑚𝑎𝑥𝑢∈𝑉{w(u)}};
5: añadimos e al conjunto dominante
6: actualizamos vértices grises
7: actualizamos vértices blancos
8: Return conjunto dominante.
El funcionamiento del algoritmo es el siguiente. Distinguimos tres tipos de
vértices:
Negros: vértices del conjunto dominante conexo y parte de la solución.
Grises: vértices vecinos de los vértices negros.
Blancos: vértices no dominados.
Consta de tres pasos:
Comienzo: Elegimos el nodo de mayor grado, lo metemos en el
conjunto dominante solución S, será un nodo negro y sus vecinos
grises.
36
Paso general: Elegir de entre los nodos grises el que tiene mayor
número de vecinos blancos. Dicho vértice pasa a ser negro y sus
vecinos grises.
Iteración: El algoritmo continúa hasta que no haya vértices blancos (no
dominados).
Este algoritmo puede obtener una solución “mala”, como se puede observar en
la figura 4.11, puesto que no consigue acercarse a un conjunto dominante mínimo.
Ilustración 29 - Figura 4.11: Ejemplo de solución “mala” algoritmo tree growing
Como se puede observar el propio algoritmo nos hace recorrer el árbol en
anchura en lugar de en profundidad por lo que nos proporciona un conjunto dominante
lejos de ser mínimo, la solución “perfecta” sería la que se muestra en la imagen de la
derecha en la figura 4.11.
Como mejora al algoritmo, que no se ha implementado en la aplicación del
presente proyecto, se plantea la opción de mejorar el paso general para optimizar la
solución:
Paso general: Elegir un nodo gris y un vecino blanco que tengan el
máximo número de vecinos blancos y marcar ambos vértices como
negros y sus vecinos en gris.
Esta mejora no ha sido implementada ya que la solución que obtiene es similar
a la del siguiente algoritmo “Marking”.
37
4.2.3.1 Ejemplo de ejecución
Para mostrar el siguiente algoritmo en ejecución se ha escogido un grafo igual
al de la figura 4.12.
Ilustración 30 - Figura 4.12: Grafo inicial algoritmo tree growing
En la figura 4.13 se muestra el grafo inicial del algoritmo Tree Growing, donde
todos los nodos inicialmente son marcados como no dominados (nodos blancos).
Ilustración 31 - Figura 4.13: Selección del vértice inicial (mayor grado)
Se selecciona como vértice negro (perteneciente al conjunto dominante
solución) al de mayor grado de entre los nodos blancos y se marcan todos sus vecinos
como nodos grises.
38
Ilustración 32 - Figura 4.14 – 4.15: Paso general algoritmo tree growing
Las figuras 4.14 y 4.15 muestran el paso general del algoritmo, donde los
vértices 2, 3, 4, 5 y 6 van pasando a formar parte del conjunto dominante solución y sus
vecinos se van marcando como vértices grises.
De esta forma el árbol se recorre en anchura, proporcionando una solución que
no es mínima. Como hemos comentado anteriormente hay una mejora de este algoritmo
que recorre el árbol en profundidad y que ofrece una mejor solución.
Ilustración 33 - Figura 4.16: Paso general en el que ya no hay vértices no dominados (blancos)
En la figura 4.16 se muestra el paso general en el que todos los vértices están
en el conjunto dominante solución o son vértices grises, por lo que el algoritmo para en
este paso.
39
Ilustración 34 - Figura 4.17: Conjunto dominante conexo, solución del algoritmo tree growing
La figura 4.17 nos muestra el resultado final donde el conjunto dominante es
conexo, tiene forma de árbol y está formado por los vértices { 1, 2, 3, 4, 5, 6, 7 }.
4.3.3 Algoritmo Marking
El algoritmo de marking es un algoritmo local, que es aquel en el que un
determinado nodo solo posee información de los nodos conectados a el (vecinos) a una
distancia determinada k. De esta forma se nombra a estos algoritmos como k-local.
Estos algoritmos tienen mucha relevancia hoy en día gracias a las redes
móviles, ya sean Wireless, teléfonos móviles o redes ad-hoc. En todas ellas un
determinado nodo solo conoce los puntos de enlace que posee. Dicho de otra forma en
una red móvil, el grafo se va construyendo a medida que el grafo es recorrido.
Mencionar que el algoritmo desarrollado parte de una premisa en la que los nodos
parten de una posición conocida y esta no varía, esta premisa es cierta en redes de
servidores, donde la localización del servidor central de una empresa es fija en una
localización, pero como todos conocemos, esto no ocurre en redes de teléfonos móviles
donde los nodos pueden aparecer y desaparecer constantemente, así como los GPS, en
la que la posición cambia constantemente.
40
En este sentido se necesita un algoritmo que, sin conocer el grafo completo, sea
capaz de obtener un conjunto dominante, no necesariamente conexo. Siguiendo el
ejemplo de las redes móviles, un conjunto dominante pudiera ser los backbones de la
red.
Los nodos solo envían y reciben información de sus vecinos, de esta forma no
sería necesario conocer el grafo completo para poder recorrerlo, tal y como ocurre en las
redes móviles.
El algoritmo implementado sigue los siguientes pasos:
1. Cada vértice u conoce su conjunto de vecinos N(u).
2. Cada vértice u transmite N(u), y recibe N(v) de todos sus vecinos.
3. Si el vértice u tiene dos vecinos v, w y w no pertenece al conjunto de
vecinos de v N(v) (y puesto que el grafo es no dirigido v no pertenece al
conjunto de vecinos de w N(w)), entonces u pertenecerá al conjunto
dominante conexo CDS.
Parte de un grafo inicial conocido (establecido manualmente en la aplicación),
que será recorrido por completo y en el que en cada iteración el nodo seleccionado u
recorrerá su lista de vecinos N(u) y los vecinos de cada uno de estos N(v). De esta forma
si u tiene un par de vecinos v, w donde w no pertenece a N(v) entonces u pasará a
formar parte del conjunto dominante.
4.3.3.1 Ejemplo de ejecución
A continuación mostramos el grafo a modo de ejemplo para la ejecución del
algoritmo.
41
Ilustración 35 - Figura 4.18: Grafo ejemplo algoritmo marking
El grafo inicial conocido será el formado por los nodos 7, 8, 17 y 18
(Gi={7,8,17,18}).
Ilustración 36 - Figura 4.19: Grafo inicial algoritmo marking
El grafo inicial ha de ser recorrido por completo por eso no se sigue ningún
criterio a la hora de escoger el primer nodo. Por lo que u en la primera iteración será el
nodo 7.
42
Ilustración 37 - Figura 4.20: Nodo seleccionado del grafo inicial algoritmo marking
De la imagen anterior podemos ver que N(u) = {4, 5, 6, 8) y que para v = 4 y
w = 8, siendo N(v) = {3, 5, 6, 7}, se puede comprobar que w no pertenece a N(v).
En este caso el nodo u se incluye en el conjunto dominante y N(u) se añaden al
grafo inicial, tal y como se puede ver en la siguiente imagen.
Ilustración 38 - Figura 4.21: Paso completado algoritmo marking
43
Ahora vamos a incluir un ejemplo sobre el mismo grafo en el que el nodo
analizado no se incluye en el conjunto dominante final. El nodo u es el 5.
Ilustración 39 - Figura 4.22: Nodo inicial no seleccionado algoritmo marking
Siendo N(u) = {4, 6, 7} y siendo v = 4, w = 6, N(v) = {3, 5, 6, 7}, se puede
observar que w pertenece a N(v).
Si escogiéramos otro par de vértices distintos, por ejemplo v = 7, w = 4,
tendríamos que N(v) = {4, 5, 6, 8}, donde w vuelve a pertenecer a N(v) y así para cada
par de vértices que escojamos, por lo que podemos concluir que u no pertenecerá al
conjunto dominante final.
El algoritmo sigue avanzando hasta que el grafo sea recorrido por completo.
44
Ilustración 40 - Figura 4.23: Grafo inicial completado algoritmo marking
Y se obtiene el resultado final, CDS = {3, 4, 7, 8, 13, 15, 17, 18, 21} que
cumple ser un conjunto dominante conexo.
Ilustración 41 - Figura 4.24: Conjunto dominante resultado algoritmo marking
45
PARTE III
DISEN O
46
47
CAPI TULO 5.- DISEN O
5.1 Introducción
Para realizar el diseño, análisis y modelado del sistema se ha utilizado el tipo
de notación UML.
Lenguaje Unificado de Modelado (LUM o UML, por sus siglas en inglés,
Unified Modeling Language) es el lenguaje de modelado de sistemas software más
conocido y utilizado en la actualidad. Se ha convertido en el estándar de facto en la
industria, debido a que ha sido creado por los autores de los tres métodos más usados en
la programación orientada a objetos (Grady Booch, Jim Rumbaugh, y Ivar Jacobson).
Es un lenguaje gráfico para visualizar, especificar, construir y documentar un
sistema software. UML ofrece un estándar para describir un modelo del sistema. Con
UML se consigue fusionar la notación de las técnicas de modelado existentes hasta el
momento de su creación para formar una herramienta compartida entre todos los
ingenieros software que trabajan en el desarrollo orientado a objetos.
Es importante remarcar que UML es un “lenguaje de modelado” para
especificar o para describir métodos o procesos. Se utiliza para definir un sistema, para
detallar los artefactos en el sistema y para documentar y construir. En otras palabras, es
el lenguaje en el que está descrito el modelo.
5.2 Diseño de alto nivel
5.2.1 Definición de los Límites del Sistema
En la actualidad se presentan numerosos problemas que pueden ser resueltos a
nivel computacional usando la dominación de grafos. Este es el objetivo del proyecto
48
realizado y de la aplicación diseñada e implementada para ejecutar una serie de
algoritmos que den distintas soluciones a dichos problemas.
La aplicación necesita de una serie de herramientas para crear, modificar,
borrar, importar, exportar grafos a los cuales se les aplicará los distintos algoritmos
implementados.
En esta sección vamos a delimitar las funcionalidades que componen la
aplicación.
Dichas funcionalidades son:
§ Herramientas de pintado manual de grafos.
Pintado de vértices.
Pintado de aristas.
Movimiento de vértices.
Borrado de vértices.
Borrado de aristas.
Añadir peso al vértice.
Borrar grafo.
§ Herramientas de creación de distintos grafos predeterminados.
Vacío.
Completo Kn.
Completo bipartido Km,n.
Enlazado Ln,r.
Enlazado Ln,r,s.
Rejilla rectangular.
Ciclo Cn
Rueda Wn
Estrella
Herschel
Petersen
Heawood
Grotzsch
49
§ Herramientas de generación aleatoria de grafos.
Creación de grafos aleatorios de mayor o menor densidad.
Creación de grafos aleatorios con pesos asignados a los vértices.
§ Herramientas de gestión de ficheros.
Exportar (guardar) fichero del grafo.
Importar (abrir) fichero del grafo.
Los algoritmos de dominación, conexa o no, de grafos son los siguientes:
§ Dominación: Greedy.
§ Dominación: Weighted Dominance.
§ Dominación conexa: Tree Growing.
§ Dominación conexa: Marking
5.2.2 Diagrama de Casos de Usos
Para especificar el comportamiento y la comunicación de un sistema mediante
su interacción con los usuarios y/u otros sistemas, se utilizan los diagramas de casos de
uso.
Sirven para mostrar cómo reacciona el sistema ante eventos que se producen en
el mismo. Cada caso de uso especifica una unidad coherente de funcionalidad.
50
Casos de Usos:
Importar grafo.
Exportar grafo.
Crear grafo nuevo (vacío).
Añadir vértice.
Eliminar vértice.
Añadir arista.
Eliminar arista.
Añadir peso.
Mover vértices.
Eliminar grafo.
Generar grafo aleatorio.
Generar grafo aleatorio con pesos.
Ejecutar algoritmo paso a paso.
Detener algoritmo paso a paso.
Siguiente paso algoritmo.
Crear grafo vacío.
Crear grafo completo Kn
Crear grafo completo bipartido Km,n
Crear grafo enlazado Ln,r
Crear grafo enlazado Ln,r,s
Crear grafo rejilla rectangular
Crear grafo ciclo Cn
Crear grafo rueda Wn
Crear grafo estrella
Crear grafo Herschel
Crear grafo Petersen
Crear grafo Heawood
Crear grafo Grotzsch
Ejecución algoritmo Greedy
Ejecución algoritmo Weighted Dominance
Ejecución algoritmo Tree Growing
Ejecución algoritmo Marking
Mostar información (about)
51
Usuario
Exportar grafo
Crear grafo
nuevo
Añadir vértice
Añadir arista
Eliminar arista
Mover vértice
Eliminar grafo
Generar grafo
aleatorio
Ejecutar algoritmo
paso a paso
Detener algoritmo
paso a paso
Eliminar vértice
Añadir peso
Generar grafo
aleatorio con
pesos
Crear grafo
vacio
Crear grafo
completo Km
Crear grafo
completo bipartido
Km,n
Crear grafo
enlazado Ln,r
Crear grafo
enlazado Ln,r,s
Crear grafo rejilla
rectangular
Crear grafo
ciclo Cn
Crear grafo
rueda Wn
Crear grafo
estrella
Crear grafo
Herschel
Crear grafo
Petersen
Crear grafo
Heawood
Crear grafo
Grotzsch
Ejecución algoritmo
Dominating Set
Ejecución
algoritmo Pirate
Ejecución
algoritmo Tree
Growing
Ejecución
algoritmo Marking
Mostrar
información
Usuario
System
Importar grafo
Siguiente paso
algortimo
Ilustración 42 - Figura 5.1: Diagrama de casos de uso
52
5.2.3 Descripción de los Actores
El único actor para todas las funcionalidades del Sistema es el Usuario.
5.2.4 Casos de uso en formato de alto nivel
A continuación detallaremos uno a uno los casos de uso de la aplicación en
formato de alto nivel.
5.2.4.1 Exportar grafo
Caso de Uso Exportar grafo
Actores Usuario
Tipo Primario
Descripción El usuario selecciona Export para exportar el grafo actual
en pantalla.
El sistema muestra una ventana para que el usuario
seleccione la ubicación del fichero a exportar y su nombre.
El usuario selecciona la ubicación e inserta el nombre del
fichero.
El sistema guarda el grafo en formato de texto para usarlo
posteriormente. Tabla 1 - Cuadro 5.1: Caso de uso: Exportar grafo
53
5.2.4.2 Importar grafo
Caso de Uso Importar grafo
Actores Usuario
Tipo Primario
Descripción El usuario selecciona Import para importar el grafo actual
en pantalla.
El sistema muestra una ventana para que el usuario
seleccione el fichero que contiene el grafo a importar.
El usuario selecciona el fichero.
El sistema muestra por pantalla el grafo que estaba en
formato de texto. Tabla 2 - Cuadro 5.2: Caso de uso: Importar grafo
5.2.4.3 Crear grafo nuevo
Caso de Uso Crear grafo nuevo
Actores Usuario
Tipo Primario
Descripción El usuario selecciona New para crear grafo nuevo.
El sistema muestra una ventana solicitando el número de
vértices.
El usuario inserta el número de vértices deseados.
El sistema crea en pantalla un grafo vacío con el número
de vértices introducido por el usuario. Tabla 3 - Cuadro 5.3: Caso de uso: Crear grafo nuevo
5.2.4.4 Añadir vértice
Caso de Uso Añadir vértice
Actores Usuario
Tipo Primario
Descripción El usuario selecciona Add node para la creación de un
nuevo vértice e indica su lugar haciendo click en cualquier
parte del área de dibujo sin que coincida con un vértice ya
dibujado.
El sistema crea un nuevo vértice en el lugar seleccionado y
lo numera siguiendo el orden de creación. Tabla 4 - Cuadro 5.4: Caso de uso: Añadir vértice
54
5.2.4.5 Eliminar vértice
Caso de Uso Eliminar vértice
Actores Usuario
Tipo Primario
Descripción El usuario selecciona Remove node para la eliminación de
un vértice y selecciona el vértice a eliminar haciendo click
sobre él.
El sistema elimina el vértice seleccionado. Tabla 5 - Cuadro 5.5: Caso de uso: Eliminar vértice
5.2.4.6 Añadir arista
Caso de Uso Añadir arista
Actores Usuario
Tipo Primario
Descripción El usuario selecciona Add edge para añadir una arista,
selecciona haciendo click sobre el vértice de origen y sin
soltar arrastra el puntero hasta el vértice destino.
El sistema crea una arista entre los dos vértices indicados. Tabla 6 - Cuadro 5.6: Caso de uso: Añadir arista
5.2.4.7 Eliminar arista
Caso de Uso Eliminar arista
Actores Usuario
Tipo Primario
Descripción El usuario selecciona Remove edge para la eliminación de
una arista y selecciona la arista a eliminar haciendo click
sobre los dos vértices que une.
El sistema elimina la arista indicada. Tabla 7 - Cuadro 5.7: Caso de uso: Eliminar arista
55
5.2.4.8 Añadir peso
Caso de Uso Añadir peso
Actores Usuario
Tipo Primario
Descripción El usuario selecciona Add weight y selecciona el vértice
sobre el que quiere añadir el peso haciendo click sobre él.
El sistema muestra una nueva ventana solicitando el peso
al usuario.
El usuario inserta el peso deseado.
El sistema muestra el peso indicado sobre el vértice
seleccionado. Tabla 8 - Cuadro 5.8: Caso de uso: Añadir peso
5.2.4.9 Mover vértice
Caso de Uso Mover vértice
Actores Usuario
Tipo Primario
Descripción El usuario selecciona el vértice a mover haciendo click
sobre el y sin soltar el botón arrastra el vértice hasta la
posición deseada.
El sistema muestra según arrastra el vértice el usuario, su
nueva posición. Tabla 9 - Cuadro 5.9: Caso de uso: Mover vértice
5.2.4.10 Eliminar grafo
Caso de Uso Eliminar grafo
Actores Usuario
Tipo Primario
Descripción El usuario selecciona Remove graph para la eliminación
del grafo que hay actualmente en pantalla.
El sistema elimina el grafo. Tabla 10 - Cuadro 5.10: Caso de uso: Eliminar grafo
56
5.2.4.11 Generar grafo aleatorio
Caso de Uso Generar grafo aleatorio
Actores Usuario
Tipo Primario
Descripción El usuario selecciona Random para crear un grafo
aleatorio.
El sistema muestra una nueva pantalla solicitando la
probabilidad de arcos entre los vértices.
El usuario inserta la probabilidad.
El sistema muestra una nueva pantalla solicitando el
número de vértices.
El usuario inserta el número de vértices.
El sistema crea un nuevo grafo aleatorio con los
parámetros introducidos. Tabla 11 - Cuadro 5.11: Caso de uso: Generar grafo aleatorio
5.2.4.12 Generar grafo aleatorio con pesos
Caso de Uso Generar grafo aleatorio con pesos
Actores Usuario
Tipo Primario
Descripción El usuario selecciona Random with weight para crear un
grafo aleatorio y asignar pesos a los vértices de forma
aleatoria.
El sistema muestra una nueva pantalla solicitando la
probabilidad de arcos entre los vértices.
El usuario inserta la probabilidad.
El sistema muestra una nueva pantalla solicitando el
número de vértices.
El usuario inserta el número de vértices.
El sistema crea un nuevo grafo aleatorio con los
parámetros introducidos. Tabla 12 - Cuadro 5.12: Caso de uso: Generar grafo aleatorio con pesos
57
5.2.4.13 Ejecutar algoritmo paso a paso
Caso de Uso Ejecutar algoritmo paso a paso
Actores Usuario
Tipo Primario
Descripción El usuario selecciona la opción Step by Step.
El sistema queda a la espera de que el usuario seleccione el
algoritmo a ejecutar. Tabla 13 - Cuadro 5.13: Caso de uso: Ejecutar algoritmo paso a paso
5.2.4.14 Detener algoritmo
Caso de Uso Detener algoritmo
Actores Usuario
Tipo Primario
Descripción El usuario selecciona Stop para parar el algoritmo en
ejecución.
El sistema para el algoritmo paso a paso y muestra por
pantalla la solución. Tabla 14 - Cuadro 5.14: Caso de uso: Detener algoritmo
5.2.4.15 Siguiente paso algoritmo
Caso de Uso Siguiente paso algoritmo
Actores Usuario
Tipo Primario
Descripción El usuario selecciona Next para ejecutar el siguiente paso
en el algoritmo.
El sistema ejecuta el siguiente paso en el algoritmo y
muestra la solución a dicho paso. Tabla 15 - Cuadro 5.15: Caso de uso: Siguiente paso algoritmo
58
5.2.4.16 Crear grafo vacío
Caso de Uso Crear grafo vacío
Actores Usuario
Tipo Primario
Descripción El usuario selecciona la opción Empty graph.
El sistema muestra una nueva pantalla solicitando al
usuario el número de nodos.
El usuario introduce el número de nodos.
El sistema crea el grafo con el parámetro introducido. Tabla 16 - Cuadro 5.16: Caso de uso: Crear grafo vacío.
5.2.4.17 Crear grafo completo Km
Caso de Uso Crear grafo completo Km
Actores Usuario
Tipo Primario
Descripción El usuario selecciona la opción Completed graph Km.
El sistema muestra una nueva pantalla solicitando al
usuario el número de nodos.
El usuario introduce el número de nodos.
El sistema crea el grafo con el parámetro introducido. Tabla 17 - Cuadro 5.17: Caso de uso: Crear grafo completo Km
5.2.4.18 Crear grafo completo bipartido Km,n
Caso de Uso Crear grafo completo bipartido Km,n
Actores Usuario
Tipo Primario
Descripción El usuario selecciona la opción Completed bipartite graph
Km,n.
El sistema muestra una nueva pantalla solicitando al
usuario el número de vértices que aparecerán a la
izquierda.
El usuario introduce el número de vértices.
El sistema muestra una nueva pantalla solicitando al
usuario el número de nodos que aparecerán a la derecha.
El sistema crea el grafo con los parámetros introducidos. Tabla 18 - Cuadro 5.18: Caso de uso: Crear grafo completo bipartido Km,n
59
5.2.4.19 Crear grafo enlazado Ln,r
Caso de Uso Crear grafo enlazado Ln,r
Actores Usuario
Tipo Primario
Descripción El usuario selecciona la opción L(n,r).
El sistema muestra una nueva pantalla solicitando al
usuario el número de vértices.
El usuario introduce el número de vértices.
El sistema muestra una nueva pantalla solicitando el valor
del entrelazado r.
El usuario introduce el valor de r deseado.
El sistema crea el grafo con los parámetros introducidos. Tabla 19 - Cuadro 5.19: Caso de uso: Crear grafo enlazado Ln,r
5.2.4.20 Crear grafo enlazado Ln,r,s
Caso de Uso Crear grafo enlazado Ln,r,s
Actores Usuario
Tipo Primario
Descripción El usuario selecciona la opción L(n,r,s).
El sistema muestra una nueva pantalla solicitando al
usuario el número de vértices.
El usuario introduce el número de vértices.
El sistema muestra una nueva pantalla solicitando el valor
del entrelazado r.
El usuario introduce el valor de r deseado.
El sistema muestra una nueva pantalla solicitando el valor
del doble entrelazado s.
El sistema crea el grafo con los parámetros introducidos. Tabla 20 - Cuadro 5.20: Caso de uso: Crear grafo enlazado Ln,r,s
60
5.2.4.21 Crear grafo rejilla rectangular
Caso de Uso Crear grafo rejilla rectangular
Actores Usuario
Tipo Primario
Descripción El usuario selecciona la opción Rectangle.
El sistema muestra una nueva pantalla solicitando al
usuario el número de filas de la rejilla.
El usuario introduce el número de las filas.
El sistema muestra una nueva pantalla solicitando el valor
del número de columnas.
El usuario introduce el valor deseado.
El sistema crea el grafo con los parámetros introducidos. Tabla 21 - Cuadro 5.21: Caso de uso: Crear grafo rejilla rectangular
5.2.4.22 Crear grafo ciclo Cn
Caso de Uso Crear grafo ciclo Cn
Actores Usuario
Tipo Primario
Descripción El usuario selecciona la opción Cicle (Cn).
El sistema muestra una nueva pantalla solicitando al
usuario el número de nodos.
El usuario introduce el número de nodos.
El sistema crea el grafo con el parámetro introducido. Tabla 22 - Cuadro 5.22: Caso de uso: Crear grafo ciclo Cn
5.2.4.23 Crear grafo rueda Wn
Caso de Uso Crear grafo rueda Wn
Actores Usuario
Tipo Primario
Descripción El usuario selecciona la opción Wheel (Wn).
El sistema muestra una nueva pantalla solicitando al
usuario el número de nodos.
El usuario introduce el número de nodos.
El sistema crea el grafo con el parámetro introducido. Tabla 23 - Cuadro 5.23: Caso de uso: Crear grafo rueda Wn
61
5.2.4.24 Crear grafo estrella
Caso de Uso Crear grafo estrella
Actores Usuario
Tipo Primario
Descripción El usuario selecciona la opción Star
El sistema muestra una nueva pantalla solicitando al
usuario el número de nodos.
El usuario introduce el número de nodos.
El sistema crea el grafo con el parámetro introducido. Tabla 24 - Cuadro 5.24: Caso de uso: Crear grafo estrella
5.2.4.25 Crear grafo Herschel
Caso de Uso Crear grafo Herschel
Actores Usuario
Tipo Primario
Descripción El usuario selecciona la opción Herschel.
El sistema crea el grafo con el grafo de Herschel. Tabla 25 - Cuadro 5.25: Caso de uso: Crear grafo Herschel
5.2.4.26 Crear grafo Petersen
Caso de Uso Crear grafo Petersen
Actores Usuario
Tipo Primario
Descripción El usuario selecciona la opción Petersen.
El sistema crea el grafo con el grafo de Petersen. Tabla 26 - Cuadro 5.26: Caso de uso: Crear grafo Petersen
62
5.2.4.27 Crear grafo Heawood
Caso de Uso Crear grafo Heawood
Actores Usuario
Tipo Primario
Descripción El usuario selecciona la opción Heawood.
El sistema crea el grafo con el grafo de Heawood. Tabla 27 - Cuadro 5.27: Caso de uso: Crear grafo Heawood
5.2.4.28 Crear grafo Grotzsch
Caso de Uso Crear grafo Grotzsch
Actores Usuario
Tipo Primario
Descripción El usuario selecciona la opción Grotzsch.
El sistema crea el grafo con el grafo de Grotzsch. Tabla 28 - Cuadro 5.28: Caso de uso: Crear grafo Grotzsch
5.2.4.29 Ejecución algoritmo Dominating Set
Caso de Uso Ejecución algoritmo Dominating Set
Actores Usuario
Tipo Primario
Descripción El usuario selecciona la opción Dominating Set.
El sistema en cada paso:
Selecciona el vértice de mayor grado entre los
vértices no dominados.
Marca el vértice como perteneciente al conjunto
dominante.
Marca sus vecinos como nodos dominados.
El proceso sigue hasta su finalización cuando ya no hay
vértices no dominados y pinta el conjunto dominante en el
grafo inicial. Tabla 29 - Cuadro 5.29: Caso de uso: Ejecución algoritmo Dominating Set.
63
5.2.4.30 Ejecución algoritmo Weighted Dominance
Caso de Uso Ejecución algoritmo Weighted Dominance
Actores Usuario
Tipo Primario
Descripción El usuario selecciona la opción Weighted Dominance.
El sistema muestra una nueva pantalla solicitando al
usuario el número de sensores deseado.
El usuario introduce el número de sensores.
El sistema en cada paso:
Recalcula los pesos en el grafo (sumando a cada
vértice su propio peso y el de sus vecinos).
Selecciona el vértice con mayor peso.
Marca como nodos eliminados a todos sus vecinos.
El sistema realiza esos pasos tantas veces como sensores se
han introducido. Tabla 30 - Cuadro 5.30: Caso de uso: Ejecución algoritmo Weighted Dominance.
5.2.4.31 Ejecución algoritmo Tree Growing
Caso de Uso Ejecución algoritmo Tree Growing
Actores Usuario
Tipo Primario
Descripción El usuario selecciona la opción Tree Growing
El sistema marca todos los vértices como blancos (no
dominados).
El sistema selecciona al vértice con mayor grado y lo
incluye en el conjunto dominante conexo.
El sistema marca todos los vértices vecinos como nodos
grises.
El sistema en cada paso:
Selecciona el vértice con mayor grado entre los
vértices grises.
Incluye el vértice en el conjunto dominante conexo.
Marca los vértices vecinos, dentro de los no
dominados (blancos) como nodos grises.
El sistema prosigue su ejecución hasta que no haya más
nodos blancos (no dominados). Tabla 31 - Cuadro 5.31: Caso de uso: Ejecución algoritmo Tree Growing
64
5.2.4.32 Ejecución algoritmo Marking
Caso de Uso Ejecución algoritmo Marking
Actores Usuario
Tipo Primario
Descripción El usuario selecciona la opción Marking.
El sistema marca todos los vértices como grises
(desconocidos) y espera a que el usuario seleccione el
vértice o vértices iniciales (conocidos).
El usuario selecciona el grafo inicial.
El sistema marca el grafo inicial con sus vértices en color
negro.
El sistema en cada paso:
Selecciona un nodo conocido y marca sus vecinos
como conocidos.
Si el nodo tiene dos vecinos que no son vecinos
entre sí, incluye el nodo en el conjunto dominante
conexo.
El sistema prosigue la ejecución hasta que haya recorrido
todos los nodos conocidos. Tabla 32 - Cuadro 5.32: Caso de uso: Ejecución algoritmo Marking
5.2.4.33 Mostrar información
Caso de Uso Mostrar información
Actores Usuario
Tipo Primario
Descripción El usuario selecciona la opción About.
El sistema muestra una nueva ventana con la información
del autor de la aplicación. Tabla 33 - Cuadro 5.33: Caso de uso: Mostrar información
5.2.5 Casos de uso en formato expandido
Esta sección incluye la descripción de los casos de uso de la aplicación con un
mayor grado de detalle.
65
Este será el patrón seguido para documentar los casos de uso:
§ Caso de Uso: Nombre del caso de uso.
§ Objetivo: Explicación del objetivo.
§ Nivel: Primario o secundario.
§ Actor Principal: Primario o secundario.
§ Precondiciones: Condiciones que deben cumplirse antes de comenzar el
escenario del caso de uso.
§ Escenario Principal de éxito: Descripción de cada paso que compone el
caso de uso.
§ Escenarios Alternativos: Descripción de flujos alternativos de
comportamiento.
§ Garantías de éxito: Indica que debe cumplirse cuando el caso de uso se ha
completado con éxito.
§ Garantías de fracaso: Indica que debe cumplirse cuando el caso de uso
falla.
§ Puntos de extensión: Relaciones si las hay con otros casos de uso.
§ Prioridad: Importancia dentro del sistema.
§ Frecuencia: Ocurrencia del caso de uso.
66
5.2.5.1 Exportar grafo
§ Caso de Uso: Exportar grafo.
§ Objetivo: Guardar en un fichero todos los datos necesarios del grafo que se
muestra actualmente en pantalla.
§ Nivel: Primario.
§ Actor Principal: Usuario.
§ Precondiciones: Ninguna.
§ Escenario Principal de éxito:
Actor Sistema
1.- El usuario selecciona en el
sistema el menú File.
2.- El usuario selecciona el submenú
Export.
4.- El usuario navega hasta la ruta
destino del fichero a crear e
introduce el nombre del fichero.
5.- El usuario confirma la operación.
3.- El sistema muestra una pantalla
para seleccionar la ubicación del
fichero.
6.- El sistema crear un fichero de
salida con el nombre especificado
como parámetro.
7.- El sistema almacena en el fichero
los datos del grafo (vértices y
aristas). Tabla 34 - Cuadro 5.34: Caso de uso extendido: Escenario principal: Exportar grafo
§ Escenarios Alternativos:
Actor Sistema
5b.- El usuario cancela la operación. 6b.- El sistema cierra la ventana de
selección de la ubicación del fichero.
7b.- El sistema vuelve al estado
inicial, antes de iniciarse el caso de
uso.
1c.- El usuario selecciona el botón
de acceso directo a Export.
Tabla 35 - Cuadro 5.35: Caso de uso extendido: Escenarios alternativos: Exportar grafo
67
§ Garantías de éxito: Se han obtenido de forma correcta los datos del grafo y
creado correctamente el fichero de salida.
§ Garantías de fracaso:
La aplicación muestra un mensaje de error en el proceso, indicando
la causa del mismo.
No se crea el fichero de salida.
La aplicación vuelve al estado inicial, antes de iniciarse el caso de
uso.
§ Puntos de extensión: Ninguno.
§ Prioridad: Media.
§ Frecuencia: Alta.
5.2.5.2 Importar grafo
§ Caso de Uso: Importar grafo.
§ Objetivo: Cargar en la aplicación datos de un grafo guardado previamente.
§ Nivel: Primario.
§ Actor Principal: Usuario.
§ Precondiciones: Es necesario que el fichero a importar exista, sea legible y
que tenga el formato correcto.
68
§ Escenario Principal de éxito:
Actor Sistema
1.- El usuario selecciona en el
sistema el menú File.
2.- El usuario selecciona el submenú
Import.
4.- El usuario navega hasta la ruta
del fichero y lo selecciona.
5.- El usuario confirma la operación
3.- El sistema muestra una nueva
pantalla de selección del fichero.
6.- El sistema lee dicho fichero e
interpreta su contenido.
7.- Se dibuja el grafo en pantalla. Tabla 36 - Cuadro 5.36: Caso de uso extendido: Escenario principal: Importar grafo
§ Escenarios Alternativos:
Actor Sistema
5b.- El usuario cancela la operación. 6b.- El sistema cierra la pantalla de
selección de fichero.
7b.- El sistema vuelve al estado
inicial, antes de iniciarse el caso de
uso.
1c.- El usuario selecciona el botón
de acceso directo a Import.
Tabla 37 - Cuadro 5.37: Caso de uso extendido: Escenarios alternativos: Importar grafo
§ Garantías de éxito: Los vértices y aristas contenidos en el fichero se han
creado y componen el grafo del documento.
§ Garantías de fracaso:
La aplicación muestra un mensaje de error en el proceso, indicando
la causa del mismo.
No se crea el grafo en pantalla.
La aplicación vuelve al estado inicial, antes de iniciarse el caso de
uso.
§ Puntos de extensión: Ninguno.
§ Prioridad: Media.
§ Frecuencia: Alta.
69
5.2.5.3 Crear grafo nuevo
§ Caso de Uso: Crear grafo nuevo.
§ Objetivo: Crear un grafo vació con el número de vértices deseado.
§ Nivel: Primario.
§ Actor Principal: Usuario.
§ Precondiciones: Ninguna.
§ Escenario Principal de éxito:
Actor Sistema
1.- El usuario selecciona en el
sistema el menú File.
2.- El usuario selecciona el submenú
New.
4.- El usuario introduce el número
de vértices.
5.- El usuario confirma la operación.
3.- El sistema muestra una nueva
pantalla solicitando el número de
vértices deseados.
6.- El sistema crea el grafo vacío con
el número de vértices introducido. Tabla 38 - Cuadro 5.38: Caso de uso extendido: Escenario principal: Crear grafo nuevo
§ Escenarios Alternativos:
Actor Sistema
5b.- El usuario cancela la operación. 6b.- El sistema cierra la pantalla de
selección de fichero.
7b.- El sistema vuelve al estado
inicial, antes de iniciarse el caso de
uso.
1c.- El usuario selecciona el botón
de acceso directo a New.
Tabla 39 - Cuadro 5.39: Caso de uso extendido: Escenarios alternativos: Crear grafo nuevo
70
§ Garantías de éxito: El grafo es creado sin aristas con el número de vértices
introducido.
§ Garantías de fracaso: La aplicación permanecerá en el mismo estado antes
de iniciar el caso de uso.
§ Puntos de extensión: Ninguno.
§ Prioridad: Baja.
§ Frecuencia: Baja.
5.2.5.4 Añadir vértice
§ Caso de Uso: Añadir vértice.
§ Objetivo: Añade un nuevo vértice al grafo actual.
§ Nivel: Primario.
§ Actor Principal: Usuario.
§ Precondiciones: Ninguna.
§ Escenario Principal de éxito:
Actor Sistema
1.- El usuario selecciona en el
sistema el menú Edit.
2.- El usuario selecciona el submenú
Add Node.
3.- El usuario selecciona con el ratón
el lugar donde quiere añadir el
vértice.
4.- El sistema añade el nuevo vértice
al grafo.
5.- El sistema dibuja el nuevo
vértice. Tabla 40 - Cuadro 5.40: Caso de uso extendido: Escenario principal: Añadir vértice
71
§ Escenarios Alternativos
Actor Sistema
1b.- El usuario selecciona el botón
de acceso directo a Add Node.
Tabla 41 - Cuadro 5.41: Caso de uso extendido: Escenarios alternativos: Añadir vértice
§ Garantías de éxito: La cardinalidad |V| del grafo actual se ha incrementado
en uno.
§ Garantías de fracaso: La aplicación permanecerá en el mismo estado antes
de iniciar el caso de uso.
§ Puntos de extensión: Ninguno.
§ Prioridad: Alta.
§ Frecuencia: Alta.
5.2.5.5 Eliminar vértice
§ Caso de Uso: Eliminar vértice.
§ Objetivo: Eliminar un vértice y todas sus aristas del grafo actual.
§ Nivel: Primario.
§ Actor Principal: Usuario.
§ Precondiciones: Debe existir el elemento a eliminar.
72
§ Escenario Principal de éxito:
Actor Sistema
1.- El usuario selecciona en el
sistema el menú Edit.
2.- El usuario selecciona el submenú
Remove Node.
3.- El usuario selecciona con el ratón
el vértice que desea eliminar.
4.- El sistema elimina el vértice y
todas sus aristas. Tabla 42 - Cuadro 5.42: Caso de uso extendido: Escenario principal: Eliminar vértice
§ Escenarios Alternativos:
Actor Sistema
1b.- El usuario selecciona el botón
de acceso directo a Remove Node.
Tabla 43 - Cuadro 5.43: Caso de uso extendido: Escenarios alternativos: Eliminar vértice
§ Garantías de éxito: La cardinalidad |V| del grafo actual se ha decrementado
en uno. Las aristas del vértice son eliminadas.
§ Garantías de fracaso: La aplicación permanecerá en el mismo estado antes
de iniciar el caso de uso.
§ Puntos de extensión: Ninguno.
§ Prioridad: Alta.
§ Frecuencia: Alta.
5.2.5.6 Añadir arista.
§ Caso de Uso: Añadir arista.
§ Objetivo: Añade una arista entre dos nodos del grafo actual.
§ Nivel: Primario.
73
§ Actor Principal: Usuario.
§ Precondiciones: Deben existir al menos dos nodos.
§ Escenario Principal de éxito:
Actor Sistema
1.- El usuario selecciona en el
sistema el menú Edit.
2.- El usuario selecciona el submenú
Add Edge.
3.- El usuario selecciona con el ratón
el vértice origen de la arista y
arrastra el ratón hasta el vértice
destino y suelta.
4.- El sistema añade la nueva arista
al grafo.
5.- El sistema dibuja la nueva arista.
Tabla 44 - Cuadro 5.44: Caso de uso extendido: Escenario principal: Añadir arista
§ Escenarios Alternativos:
Actor Sistema
3b.- El usuario selecciona el vértice
origen pero no arrastra el ratón hasta
un vértice destino, cancelando la
operación.
4b.- El sistema no añade la arista y
permanece en el mismo estado que
antes de iniciarse el caso de uso.
1c.- El usuario selecciona el botón
de acceso directo a Add Edge.
Tabla 45 - Cuadro 5.45: Caso de uso extendido: Escenarios alternativos: Añadir arista
§ Garantías de éxito: La cardinalidad |A| del grafo se ha incrementado en
uno.
§ Garantías de fracaso: La aplicación permanecerá en el mismo estado que
antes de iniciarse el caso de uso.
§ Puntos de extensión: Ninguno.
§ Prioridad: Alta.
§ Frecuencia: Alta.
74
5.2.5.7 Eliminar arista
§ Caso de Uso: Eliminar arista.
§ Objetivo: Elimina la arista del grafo actual.
§ Nivel: Primario.
§ Actor Principal: Usuario.
§ Precondiciones: Debe existir el elemento a eliminar.
§ Escenario Principal de éxito:
Actor Sistema
1.- El usuario selecciona en el
sistema el menú Edit.
2.- El usuario selecciona el submenú
Remove Edge.
3.- El usuario selecciona con el ratón
el vértice origen y el vértice destino
de la arista que desea eliminar.
4.- El sistema elimina la arista.
Tabla 46 - Cuadro 5.46: Caso de uso extendido: Escenario principal: Eliminar arista
§ Escenarios Alternativos:
Actor Sistema
3b.- El usuario selecciona el vértice
origen pero no selecciona el vértice
destino, cancelando la operación.
4b.- El sistema no añade la arista y
permanece en el mismo estado que
antes de iniciarse el caso de uso.
1c.- El usuario selecciona el botón
de acceso directo a Remove Edge.
Tabla 47 - Cuadro 5.47: Caso de uso extendido: Escenarios alternativos: Eliminar edge
§ Garantías de éxito: La cardinalidad |A| del grafo se ha decrementado en
uno.
§ Garantías de fracaso: La aplicación permanecerá en el mismo estado que
antes de iniciarse el caso de uso.
75
§ Puntos de extensión: Ninguno.
§ Prioridad: Alta.
§ Frecuencia: Alta.
5.2.5.8 Añadir peso
§ Caso de Uso: Añadir peso.
§ Objetivo: Asignar peso al vértice seleccionado.
§ Nivel: Primario.
§ Actor Principal: Usuario.
§ Precondiciones: El grafo no debe ser nulo.
§ Escenario Principal de éxito:
Actor Sistema
1.- El usuario selecciona en el
sistema el menú Edit.
2.- El usuario selecciona el submenú
Add Weight.
3.- El usuario selecciona con el ratón
el vértice al que necesita añadirle
peso.
5.- El usuario introduce el peso
deseado.
6.- El usuario confirma la operación.
4.- El sistema muestra una nueva
pantalla solicitando al usuario el
valor del peso.
7.- El sistema añade el peso al
vértice del grafo.
8.- El sistema dibuja el peso sobre el
vértice. Tabla 48 - Cuadro 5.48: Caso de uso extendido: Escenario principal: Añadir peso
76
§ Escenarios Alternativos:
Actor Sistema
3b.- El usuario no selecciona el
vértice, cancelando la operación.
4b.- El sistema no añade el peso y
permanece en el mismo estado que
antes de iniciarse el caso de uso.
6c.- El usuario cancela la operación. 7c.- El sistema no añade el peso y
permanece en el mismo estado que
antes de iniciarse el caso de uso.
1d.- El usuario selecciona el botón
de acceso directo a Add Weight.
Tabla 49 - Cuadro 5.49: Caso de uso extendido: Escenarios alternativos: Añadir peso
§ Garantías de éxito: El vértice seleccionado tiene su peso asignado dentro
de un rango de valores.
§ Garantías de fracaso: La aplicación permanecerá en el mismo estado antes
de iniciarse el caso de uso.
§ Puntos de extensión: Ninguno.
§ Prioridad: Alta.
§ Frecuencia: Media.
5.2.5.9 Mover vértices
§ Caso de Uso: Mover vértices.
§ Objetivo: Cambiar de posición del vértice seleccionado.
§ Nivel: Primario.
§ Actor Principal: Usuario.
§ Precondiciones: Ninguna.
77
§ Escenario Principal de éxito:
Actor Sistema
1.- El usuario selecciona el vértice
con el ratón y sin soltar mueve el
vértice a la nueva posición deseada.
2.- El sistema cambia la ubicación
del vértice.
Tabla 50 - Cuadro 5.50: Caso de uso extendido: Escenario principal: Mover vértices
§ Escenarios Alternativos: Ninguno.
§ Garantías de éxito: El sistema dibuja correctamente el vértice en su nueva
posición.
§ Garantías de fracaso: La aplicación permanecerá en el mismo estado antes
de iniciar el caso de uso.
§ Puntos de extensión: Ninguno.
§ Prioridad: Alta.
§ Frecuencia: Alta.
5.2.5.10 Eliminar grafo
§ Caso de Uso: Eliminar grafo.
§ Objetivo: Elimina por completo el grafo actual.
§ Nivel: Primario.
§ Actor Principal: Usuario.
§ Precondiciones: Debe existir un grafo previo.
78
§ Escenario Principal de éxito:
Actor Sistema
1.- El usuario selecciona en el
sistema el menú Edit.
2.- El usuario selecciona el submenú
Remove Graph.
3.- El sistema elimina los vértices y
aristas del grafo actual.
Tabla 51 - Cuadro 5.51: Caso de uso extendido: Escenario principal: Eliminar grafo
§ Escenarios Alternativos:
Actor Sistema
1b.- El usuario selecciona el botón
de acceso directo a Remove Graph.
Tabla 52 - Cuadro 5.52: Caso de uso extendido: Escenario alternativo: Eliminar grafo
§ Garantías de éxito: El grafo actual queda eliminado por completo.
§ Garantías de fracaso: La aplicación permanecerá en el mismo estado antes
de iniciar el caso de uso.
§ Puntos de extensión: Ninguno.
§ Prioridad: Alta.
§ Frecuencia: Alta.
5.2.5.11 Generar grafo aleatorio
§ Caso de Uso: Generar grafo aleatorio.
§ Objetivo: Crear un grafo donde la posición de los vértices y las aristas se
generan aleatoriamente.
§ Nivel: Primario.
§ Actor Principal: Usuario.
79
§ Precondiciones: Ninguna.
§ Escenario Principal de éxito:
Actor Sistema
1.- El usuario selecciona en el
sistema el menú File.
2.- El usuario selecciona el submenú
Random.
4.- El usuario introduce la
probabilidad.
5.- El usuario confirma la operación.
7.- El usuario introduce el número.
8.- El usuario confirma la operación.
3.- El sistema muestra una nueva
pantalla preguntando al usuario la
probabilidad de que exista una arista
entre dos vértices.
6.- El sistema muestra una nueva
pantalla preguntando al usuario el
número de vértices deseado.
9.- El sistema crea el grafo aleatorio
con los parámetros introducidos. Tabla 53 - Cuadro 5.53: Caso de uso extendido: Escenario principal: Generar grafo aleatorio
§ Escenarios Alternativos:
Actor Sistema
5b.- El usuario cancela la operación
o introduce un valor erróneo.
6b.- El sistema muestra un mensaje
de error.
7b.- El sistema permanece en el
mismo estado que antes de iniciarse
el caso de uso.
8c.- El usuario cancela la operación
o introduce un valor erróneo.
9c.- El sistema muestra un mensaje
de error.
10c.- El sistema permanece en el
mismo estado que antes de iniciarse
el caso de uso. Tabla 54 - Cuadro 5.54: Caso de uso extendido: Escenarios alternativos: Generar grafo aleatorio
§ Garantías de éxito: Se ha creado un grafo de forma aleatorio con los
parámetros introducidos.
§ Garantías de fracaso: La aplicación permanecerá en el mismo estado antes
de iniciar el caso de uso.
80
§ Puntos de extensión: Ninguno.
§ Prioridad: Baja.
§ Frecuencia: Baja.
5.2.5.12 Generar grafo aleatorio con pesos
§ Caso de Uso: Generar grafo aleatorio con pesos.
§ Objetivo: Crear un grafo donde la posición de los vértices, las aristas y los
pesos se generan aleatoriamente.
§ Nivel: Primario.
§ Actor Principal: Usuario.
§ Precondiciones: Ninguna.
§ Escenario Principal de éxito:
Actor Sistema
1.- El usuario selecciona en el
sistema el menú File.
2.- El usuario selecciona el submenú
Random with Weight.
4.- El usuario introduce la
probabilidad.
5.- El usuario confirma la operación.
7.- El usuario introduce el número.
8.- El usuario confirma la operación.
3.- El sistema muestra una nueva
pantalla preguntando al usuario la
probabilidad de que exista una arista
entre dos vértices.
6.- El sistema muestra una nueva
pantalla preguntando al usuario el
número de vértices deseado.
9.- El sistema crea el grafo aleatorio
con los parámetros introducidos. Tabla 55 - Cuadro 5.55: Caso de uso extendido: Escenario principal: Generar grafo aleatorio con pesos
81
§ Escenarios Alternativos:
Actor Sistema
5b.- El usuario cancela la operación
o introduce un valor erróneo.
6b.- El sistema muestra un mensaje
de error.
7b.- El sistema permanece en el
mismo estado que antes de iniciarse
el caso de uso.
8c.- El usuario cancela la operación
o introduce un valor erróneo.
9c.- El sistema muestra un mensaje
de error.
10c.- El sistema permanece en el
mismo estado que antes de iniciarse
el caso de uso. Tabla 56 - Cuadro 5.56: Caso de uso extendido: Escenarios alternativos: Generar grafo aleatorio con pesos
§ Garantías de éxito: Se ha creado un grafo con pesos de forma aleatorio con
los parámetros introducidos.
§ Garantías de fracaso: La aplicación permanecerá en el mismo estado antes
de iniciar el caso de uso.
§ Puntos de extensión: Ninguno.
§ Prioridad: Baja.
§ Frecuencia: Baja.
5.2.5.13 Ejecutar algoritmo paso a paso
§ Caso de Uso: Ejecutar algoritmo paso a paso.
§ Objetivo: Cambiar el modo de ejecución al modo por pasos.
§ Nivel: Primario.
§ Actor Principal: Usuario.
§ Precondiciones: Ninguna.
82
§ Escenario Principal de éxito:
Actor Sistema
1.- El usuario selecciona la opción
Step by Step.
2.- El sistema se queda a la espera
hasta que el usuario elige el
algoritmo a ejecutar. Tabla 57 - Cuadro 5.57: Caso de uso extendido: Escenario principal: Ejecutar algoritmo paso a paso
§ Escenarios Alternativos: Ninguno.
§ Garantías de éxito: Se cambia el método de ejecución de inmediato a por
pasos.
§ Garantías de fracaso: La aplicación permanecerá en el mismo estado antes
de iniciar el caso de uso.
§ Puntos de extensión: Ninguno.
§ Prioridad: Alta.
§ Frecuencia: Alta.
5.2.5.14 Detener algoritmo paso a paso
§ Caso de Uso: Detener algoritmo paso a paso.
§ Objetivo: Detener el algoritmo que hay en ejecución en ese instante.
§ Nivel: Primario.
§ Actor Principal: Usuario.
§ Precondiciones: Debe haber un algoritmo en ejecución.
83
§ Escenario Principal de éxito:
Actor Sistema
1.- El usuario selecciona la opción
Stop.
2.- El sistema para el algoritmo en
ejecución.
3.- El sistema muestra la solución del
algoritmo ejecutado inmediatamente. Tabla 58 - Cuadro 5.58: Caso de uso extendido: Escenario principal: Detener algoritmo
§ Escenarios Alternativos: Ninguno.
§ Garantías de éxito: El algoritmo es parado adecuadamente y se muestra la
solución del algoritmo inmediatamente.
§ Garantías de fracaso: La aplicación permanecerá en el mismo estado antes
de iniciar el caso de uso.
§ Puntos de extensión: Ninguno.
§ Prioridad: Alta.
§ Frecuencia: Alta.
5.2.5.15 Siguiente paso algoritmo
§ Caso de Uso: Siguiente paso algoritmo.
§ Objetivo: Ejecutar el siguiente paso del algoritmo en ejecución.
§ Nivel: Primario.
§ Actor Principal: Usuario.
§ Precondiciones: Debe existir un algoritmo en ejecución.
84
§ Escenario Principal de éxito:
Actor Sistema
1.- El usuario selecciona la opción
Next.
2.- El sistema ejecuta el siguiente
paso del algoritmo.
3.- El sistema muestra la solución
parcial del algoritmo en dicho paso. Tabla 59 - Cuadro 5.59: Caso de uso extendido: Escenario principal: Siguiente paso algoritmo
§ Escenarios Alternativos: Ninguno.
§ Garantías de éxito: El siguiente paso en el algoritmo es ejecutado
correctamente.
§ Garantías de fracaso: La aplicación permanecerá en el mismo estado antes
de iniciar el caso de uso.
§ Puntos de extensión: Ninguna.
§ Prioridad: Alta.
§ Frecuencia: Alta.
5.2.5.16 Crear grafo vacío
§ Caso de Uso: Crear grafo vacío.
§ Objetivo: Crear un grafo sin aristas.
§ Nivel: Primario.
§ Actor Principal: Usuario.
§ Precondiciones: Ninguna.
85
§ Escenario Principal de éxito:
Actor Sistema
1.- El usuario selecciona en el
sistema el menú Graphs.
2.- El usuario selecciona el submenú
Empty Graph.
4.- El usuario introduce el número
de vértices.
5.- El usuario confirma la operación.
3.- El sistema muestra una nueva
pantalla solicitando al usuario el
número de vértices deseado.
6.- El sistema crea el grafo vacío con
los vértices deseados. Tabla 60 - Cuadro 5.60: Caso de uso extendido: Escenario principal: Crear grafo vacío
§ Escenarios Alternativos:
Actor Sistema
5b.- El usuario cancela la operación. 6.- El sistema no crea el grafo y
permanece en el mismo estado antes
de iniciarse el caso de uso. Tabla 61 - Cuadro 5.61: Caso de uso extendido: Escenarios alternativos: Crear grafo vacío
§ Garantías de éxito: El grafo vacío es creado con el número de vértices
deseado.
§ Garantías de fracaso: La aplicación permanecerá en el mismo estado antes
de iniciar el caso de uso.
§ Puntos de extensión: Ninguno.
§ Prioridad: Media.
§ Frecuencia: Media.
5.2.5.17 Crear grafo completo Km
§ Caso de Uso: Crear grafo completo Km.
§ Objetivo: Crear un grafo completo Km.
86
§ Nivel: Primario.
§ Actor Principal: Usuario.
§ Precondiciones: Ninguna.
§ Escenario Principal de éxito:
Actor Sistema
1.- El usuario selecciona en el
sistema el menú Graphs.
2.- El usuario selecciona el submenú
Completed Graph y la opción
Completed Graph (Km).
4.- El usuario introduce el número
de vértices.
5.- El usuario confirma la operación.
3.- El sistema muestra una nueva
pantalla solicitando al usuario el
número de vértices deseado.
6.- El sistema crea el grafo completo
con los vértices deseados. Tabla 62 - Cuadro 5.62: Caso de uso extendido: Escenario principal: Crear grafo completo Km
§ Escenarios Alternativos:
Actor Sistema
5b.- El usuario cancela la operación. 6.- El sistema no crea el grafo y
permanece en el mismo estado antes
de iniciarse el caso de uso. Tabla 63 - Cuadro 5.63: Caso de uso extendido: Escenarios alternativos: Crear grafo completo Km
§ Garantías de éxito: El grafo completo es creado con el número de vértices
deseado.
§ Garantías de fracaso: La aplicación permanecerá en el mismo estado antes
de iniciar el caso de uso.
§ Puntos de extensión: Ninguna.
§ Prioridad: Media.
§ Frecuencia: Media.
87
5.2.5.18 Crear grafo completo bipartido Km,n
§ Caso de Uso: Crear grafo completo bipartido Km,n.
§ Objetivo: Crear un grafo completo bipartido Km,n.
§ Nivel: Primario.
§ Actor Principal: Usuario.
§ Precondiciones: Ninguna.
§ Escenario Principal de éxito:
Actor Sistema
1.- El usuario selecciona en el
sistema el menú Graphs.
2.- El usuario selecciona el submenú
Completed Graph y la opción
Completed Bipartite Graph (Km,n).
4.- El usuario introduce el número
de vértices.
5.- El usuario confirma la operación.
7.- El usuario introduce el número
de vértices.
8.- El usuario confirma la operación.
3.- El sistema muestra una nueva
pantalla solicitando al usuario el
número de vértices que desea en la
parte izquierda del grafo.
6.- El sistema muestra una nueva
pantalla solicitando al usuario el
número de vértices que desea en la
parte derecha del grafo.
9.- El sistema crea el grafo completo
bipartido con los vértices deseados. Tabla 64 - Cuadro 5.64: Caso de uso extendido: Escenario principal: Crear grafo completo bipartido Km,n
88
§ Escenarios Alternativos:
Actor Sistema
5b.- El usuario cancela la operación. 6b.- El sistema no crea el grafo y
permanece en el mismo estado antes
de iniciarse el caso de uso.
8c.- El usuario cancela la operación 9c.- El sistema no crea el grafo y
permanece en el mismo estado antes
de iniciarse el caso de uso. Tabla 65 - Cuadro 5.65: Caso de uso extendido: Escenarios alternativos: Crear grafo completo bipartido Km,n
§ Garantías de éxito: El grafo completo es creado con el número de vértices
deseado.
§ Garantías de fracaso: La aplicación permanecerá en el mismo estado antes
de iniciar el caso de uso.
§ Puntos de extensión: Ninguna.
§ Prioridad: Media.
§ Frecuencia: Media.
5.2.5.19 Crear grafo enlazado Ln,r
§ Caso de Uso: Crear grafo enlazado Ln,r.
§ Objetivo: Crear un grafo enlazado Ln,r.
§ Nivel: Primario.
§ Actor Principal: Usuario.
§ Precondiciones: Ninguna.
89
§ Escenario Principal de éxito:
Actor Sistema
1.- El usuario selecciona en el
sistema el menú Graphs.
2.- El usuario selecciona el submenú
Bound Graph y la opción L(n,r).
4.- El usuario introduce el número
de vértices.
5.- El usuario confirma la operación.
7.- El usuario introduce el valor de r.
8.- El usuario confirma la operación.
3.- El sistema muestra una nueva
pantalla solicitando al usuario el
número de vértices que desea.
6.- El sistema muestra una nueva
pantalla solicitando al usuario el
valor de r.
9.- El sistema crea el grafo
entrelazado con los parámetros
introducidos. Tabla 66 - Cuadro 5.66: Caso de uso extendido: Escenario principal: Crear grafo enlazado Ln,r
§ Escenarios Alternativos:
5b.- El usuario cancela la operación. 6b.- El sistema no crea el grafo y
permanece en el mismo estado antes
de iniciarse el caso de uso.
8c.- El usuario cancela la operación 9c.- El sistema no crea el grafo y
permanece en el mismo estado antes
de iniciarse el caso de uso. Tabla 67 - Cuadro 5.67: Caso de uso extendido: Escenarios alternativos: Crear grafo enlazado Ln,r
§ Garantías de éxito: El grafo entrelazado es creado con los parámetros
introducidos.
§ Garantías de fracaso: La aplicación permanecerá en el mismo estado antes
de iniciar el caso de uso.
§ Puntos de extensión: Ninguna.
§ Prioridad: Media.
§ Frecuencia: Media.
90
5.2.5.20 Crear grafo enlazado Ln,r,s
§ Caso de Uso: Crear grafo enlazado Ln,r,s.
§ Objetivo: Crear un grafo enlazado Ln,r,s.
§ Nivel: Primario.
§ Actor Principal: Usuario.
§ Precondiciones: Ninguna.
§ Escenario Principal de éxito:
1.- El usuario selecciona en el
sistema el menú Graphs.
2.- El usuario selecciona el submenú
Bound Graph y la opción L(n,r,s).
4.- El usuario introduce el número
de vértices.
5.- El usuario confirma la operación.
7.- El usuario introduce el valor de r.
8.- El usuario confirma la operación.
10.- El usuario introduce el valor de
s.
11.- El usuario confirma la
operación.
3.- El sistema muestra una nueva
pantalla solicitando al usuario el
número de vértices que desea.
6.- El sistema muestra una nueva
pantalla solicitando al usuario el
valor de r.
9.- El sistema muestra una nueva
pantalla solicitando al usuario el
valor de s.
12.- El sistema crea el grafo
entrelazado con los parámetros
introducidos. Tabla 68 - Cuadro 5.68: Caso de uso extendido: Escenario principal: Crear grafo enlazado Ln,r,s
91
§ Escenarios Alternativos:
5b.- El usuario cancela la operación. 6b.- El sistema no crea el grafo y
permanece en el mismo estado antes
de iniciarse el caso de uso.
8c.- El usuario cancela la operación. 9c.- El sistema no crea el grafo y
permanece en el mismo estado antes
de iniciarse el caso de uso.
11d.- El usuario cancela la
operación.
12d.- El sistema no crea el grafo y
permanece en el mismo estado antes
de iniciarse el caso de uso. Tabla 69 - Cuadro 5.69: Caso de uso extendido: Escenarios alternativos: Crear grafo enlazado Ln,r,s
§ Garantías de éxito: El grafo entrelazado es creado con los parámetros
introducidos.
§ Garantías de fracaso: La aplicación permanecerá en el mismo estado antes
de iniciar el caso de uso.
§ Puntos de extensión: Ninguna.
§ Prioridad: Media.
§ Frecuencia: Media.
5.2.5.21 Crear grafo rejilla rectangular
§ Caso de Uso: Crear grafo rejilla rectangular.
§ Objetivo: Crear un grafo rejilla de forma rectangular.
§ Nivel: Primario.
§ Actor Principal: Usuario.
§ Precondiciones: Ninguna.
92
§ Escenario Principal de éxito:
1.- El usuario selecciona en el
sistema el menú Graphs.
2.- El usuario selecciona el submenú
Grids y la opción Rectangle.
4.- El usuario introduce el número
de filas.
5.- El usuario confirma la operación.
7.- El usuario introduce el número
de columnas.
8.- El usuario confirma la operación.
3.- El sistema muestra una nueva
pantalla solicitando al usuario el
número de filas que desea.
6.- El sistema muestra una nueva
pantalla solicitando al usuario el
número de columnas que desea.
9.- El sistema crea el grafo rejilla
con los parámetros deseados. Tabla 70 - Cuadro 5.70: Caso de uso extendido: Escenario principal: Crear grafo rejilla rectangular
§ Escenarios Alternativos:
Actor Sistema
5b.- El usuario cancela la operación. 6b.- El sistema no crea el grafo y
permanece en el mismo estado antes
de iniciarse el caso de uso.
8c.- El usuario cancela la operación 9c.- El sistema no crea el grafo y
permanece en el mismo estado antes
de iniciarse el caso de uso. Tabla 71 - Cuadro 5.71: Caso de uso extendido: Escenarios alternativos: Crear grafo rejilla rectangular
§ Garantías de éxito: Se crea el grafo rejilla con los parámetros introducidos.
§ Garantías de fracaso: La aplicación permanecerá en el mismo estado antes
de iniciar el caso de uso.
§ Puntos de extensión: Ninguna.
§ Prioridad: Media.
§ Frecuencia: Media.
93
5.2.5.22 Crear grafo ciclo Cn
§ Caso de Uso: Crear grafo ciclo Cn.
§ Objetivo: Crear un grafo ciclo Cn.
§ Nivel: Primario.
§ Actor Principal: Usuario.
§ Precondiciones: Ninguna.
§ Escenario Principal de éxito:
Actor Sistema
1.- El usuario selecciona en el
sistema el menú Graphs.
2.- El usuario selecciona el submenú
Shapes y la opción Cicle (Cn).
4.- El usuario introduce el número
de vértices.
5.- El usuario confirma la operación.
3.- El sistema muestra una nueva
pantalla solicitando al usuario el
número de vértices deseado.
6.- El sistema crea el grafo completo
con los vértices deseados. Tabla 72 - Cuadro 5.72: Caso de uso extendido: Escenario principal: Crear grafo ciclo Cn
§ Escenarios Alternativos:
Actor Sistema
5b.- El usuario cancela la operación. 6.- El sistema no crea el grafo y
permanece en el mismo estado antes
de iniciarse el caso de uso. Tabla 73 - Cuadro 5.73: Caso de uso extendido: Escenarios alternativos: Crear grafo ciclo Cn
§ Garantías de éxito: El grafo ciclo es creado con el número de vértices
deseado.
§ Garantías de fracaso: La aplicación permanecerá en el mismo estado antes
de iniciar el caso de uso.
§ Puntos de extensión: Ninguna.
94
§ Prioridad: Media.
§ Frecuencia: Media.
5.2.5.23 Crear grafo rueda Wn
§ Caso de Uso: Crear grafo rueda Wn.
§ Objetivo: Crear un grafo rueda Wn.
§ Nivel: Primario.
§ Actor Principal: Usuario.
§ Precondiciones: Ninguna.
§ Escenario Principal de éxito:
Actor Sistema
1.- El usuario selecciona en el
sistema el menú Graphs.
2.- El usuario selecciona el submenú
Shapes y la opción Wheel (Wn).
4.- El usuario introduce el número
de vértices.
5.- El usuario confirma la operación.
3.- El sistema muestra una nueva
pantalla solicitando al usuario el
número de vértices deseado.
6.- El sistema crea el grafo completo
con los vértices deseados. Tabla 74 - Cuadro 5.74: Caso de uso extendido: Escenario principal: Crear grafo rueda Wn
§ Escenarios Alternativos:
Actor Sistema
5b.- El usuario cancela la operación. 6.- El sistema no crea el grafo y
permanece en el mismo estado antes
de iniciarse el caso de uso. Tabla 75 - Cuadro 5.75: Caso de uso extendido: Escenarios alternativos: Crear grafo rueda Wn
95
§ Garantías de éxito: El grafo rueda es creado con el número de vértices
deseado.
§ Garantías de fracaso: La aplicación permanecerá en el mismo estado antes
de iniciar el caso de uso.
§ Puntos de extensión: Ninguna.
§ Prioridad: Media.
§ Frecuencia: Media.
5.2.5.24 Crear grafo estrella
§ Caso de Uso: Crear grafo estrella.
§ Objetivo: Crear un grafo estrella.
§ Nivel: Primario.
§ Actor Principal: Usuario.
§ Precondiciones: Ninguna.
§ Escenario Principal de éxito:
Actor Sistema
1.- El usuario selecciona en el
sistema el menú Graphs.
2.- El usuario selecciona el submenú
Shapes y la opción Star.
4.- El usuario introduce el número
de vértices.
5.- El usuario confirma la operación.
3.- El sistema muestra una nueva
pantalla solicitando al usuario el
número de vértices deseado.
6.- El sistema crea el grafo completo
con los vértices deseados. Tabla 76 - Cuadro 5.76: Caso de uso extendido: Escenario principal: Crear grafo estrella
96
§ Escenarios Alternativos:
Actor Sistema
5b.- El usuario cancela la operación. 6.- El sistema no crea el grafo y
permanece en el mismo estado antes
de iniciarse el caso de uso. Tabla 77 - Cuadro 5.77: Caso de uso extendido: Escenarios alternativos: Crear grafo estrella
§ Garantías de éxito: El grafo estrella es creado con el número de vértices
deseado.
§ Garantías de fracaso: La aplicación permanecerá en el mismo estado antes
de iniciar el caso de uso.
§ Puntos de extensión: Ninguna.
§ Prioridad: Media.
§ Frecuencia: Media.
5.2.5.25 Crear grafo Herschel
§ Caso de Uso: Crear grafo Herschel.
§ Objetivo: Crear el grafo de Herschel.
§ Nivel: Primario.
§ Actor Principal: Usuario.
§ Precondiciones: Ninguna.
§ Escenario Principal de éxito:
Actor Sistema
1.- El usuario selecciona en el
sistema el menú Graphs.
2.- El usuario selecciona el submenú
Herschel.
3.- El sistema crea el grafo de
Herschel. Tabla 78 - Cuadro 5.78: Caso de uso extendido: Escenario principal: Crear grafo de Herschel
97
§ Escenarios Alternativos: Ninguno.
§ Garantías de éxito: El grafo de Herschel es creado correctamente.
§ Garantías de fracaso: La aplicación permanecerá en el mismo estado antes
de iniciar el caso de uso.
§ Puntos de extensión: Ninguna.
§ Prioridad: Media.
§ Frecuencia: Media.
5.2.5.26 Crear grafo Petersen
§ Caso de Uso: Crear grafo Petersen.
§ Objetivo: Crear el grafo de Petersen.
§ Nivel: Primario.
§ Actor Principal: Usuario.
§ Precondiciones: Ninguna.
§ Escenario Principal de éxito:
Actor Sistema
1.- El usuario selecciona en el
sistema el menú Graphs.
2.- El usuario selecciona el submenú
Petersen.
3.- El sistema crea el grafo de
Petersen. Tabla 79 - Cuadro 5.79: Caso de uso extendido: Escenario principal: Crear grafo de Petersen
§ Escenarios Alternativos: Ninguno.
§ Garantías de éxito: El grafo de Petersen es creado correctamente.
98
§ Garantías de fracaso: La aplicación permanecerá en el mismo estado antes
de iniciar el caso de uso.
§ Puntos de extensión: Ninguna.
§ Prioridad: Media.
§ Frecuencia: Media.
5.2.5.27 Crear grafo Heawood
§ Caso de Uso: Crear grafo Heawood.
§ Objetivo: Crear el grafo de Heawood.
§ Nivel: Primario.
§ Actor Principal: Usuario.
§ Precondiciones: Ninguna.
§ Escenario Principal de éxito:
Actor Sistema
1.- El usuario selecciona en el
sistema el menú Graphs.
2.- El usuario selecciona el submenú
Heawood.
3.- El sistema crea el grafo de
Heawood. Tabla 80 - Cuadro 5.80: Caso de uso extendido: Escenario principal: Crear grafo de Heawood
§ Escenarios Alternativos: Ninguno.
§ Garantías de éxito: El grafo de Heawood es creado correctamente.
§ Garantías de fracaso: La aplicación permanecerá en el mismo estado antes
de iniciar el caso de uso.
§ Puntos de extensión: Ninguna.
99
§ Prioridad: Media.
§ Frecuencia: Media.
5.2.5.28 Crear grafo Grotzsch
§ Caso de Uso: Crear grafo Grotzsch.
§ Objetivo: Crear el grafo de Grotzsch.
§ Nivel: Primario.
§ Actor Principal: Usuario.
§ Precondiciones: Ninguna.
§ Escenario Principal de éxito:
Actor Sistema
1.- El usuario selecciona en el
sistema el menú Graphs.
2.- El usuario selecciona el submenú
Grotzsch.
3.- El sistema crea el grafo de
Grotzsch. Tabla 81 - Cuadro 5.81: Caso de uso extendido: Escenario principal: Crear grafo de Grotzsch
§ Escenarios Alternativos: Ninguno.
§ Garantías de éxito: El grafo de Grotzsch es creado correctamente.
§ Garantías de fracaso: La aplicación permanecerá en el mismo estado antes
de iniciar el caso de uso.
§ Puntos de extensión: Ninguna.
§ Prioridad: Media.
§ Frecuencia: Media.
100
5.2.5.29 Ejecución algoritmo Dominating Set
§ Caso de Uso: Ejecución algoritmo Dominating Set
§ Objetivo: Ejecutar el algoritmo Dominating Set.
§ Nivel: Primario.
§ Actor Principal: Usuario.
§ Precondiciones: Debe existir un grafo creado.
§ Escenario Principal de éxito:
Actor Sistema
1.- El usuario selecciona en el
sistema el menú Algorithms.
2.- El usuario selecciona el submenú
Dominanting Set.
El sistema en cada paso:
3.- Comprueba si el conjunto
de vértices candidatos a ser el
de mayor no es vacío.
4a.- Si el conjunto de
candidatos no es vacío.
5.- Selecciona el vértice de
mayor grado.
6.- Añade el vértice al
conjunto dominante S.
7.- Pinta el vértice
marcándolo como
perteneciente a S.
8.- Pinta sus vecinos como
vértices ya dominados.
9.- Elimina el vértice y sus
vecinos del grupo de vértices
candidatos.
10.- El sistema continúa el algoritmo
hasta su finalización, dependiendo
del método de ejecución. Tabla 82 - Cuadro 5.82: Caso de uso extendido: Escenario principal: Ejecución algoritmo Dominating Set
101
§ Escenarios Alternativos:
Actor Sistema
4b.- Si el conjunto de candidatos es
vacío.
5b.- El algoritmo ha finalizado
correctamente.
6b.- Los vértices marcados como
pertenecientes al conjunto S es la
solución al algoritmo.
1c.- El usuario selecciona el botón
de acceso directo a Dominating Set.
Tabla 83 - Cuadro 5.83: Caso de uso extendido: Escenarios alternativos: Ejecución algoritmo Dominating Set
§ Garantías de éxito:
El algoritmo Dominating Set ha terminado correctamente.
Los elementos del conjunto dominante S han sido marcados.
§ Garantías de fracaso: La aplicación permanecerá en el mismo estado antes
de iniciar el caso de uso.
§ Puntos de extensión: Caso de uso: Ejecutar algoritmo paso a paso.
§ Prioridad: Alta.
§ Frecuencia: Alta.
5.2.5.30 Ejecución algoritmo Weighted Dominance
§ Caso de Uso: Ejecución algoritmo Weighted Dominance
§ Objetivo: Ejecutar el algoritmo Weighted Dominance.
§ Nivel: Primario.
§ Actor Principal: Usuario.
102
§ Precondiciones:
Debe existir un grafo creado.
Todos los vértices deben tener asignado su peso.
§ Escenario Principal de éxito:
Actor Sistema
1.- El usuario selecciona en el
sistema el menú Algorithms.
2.- El usuario selecciona el submenú
Weighted Dominance.
4.- El usuario introduce el número
de sensores deseado.
5.- El usuario confirma la operación.
3.- El sistema muestra una nueva
pantalla solicitando el número de
sensores al usuario.
El sistema en cada paso:
6.- Se comprueba si quedan
sensores por ubicar.
7.- Se recalcula el peso de
cada vértice sumando su
propio peso y el de sus
vecinos.
8.- Se selecciona el vértice de
mayor peso y se coloca un
sensor en el.
9.- Se pinta el vértice donde
se ha colocado el sensor.
10.- Se elimina el vértice
seleccionado y todos sus
vecinos.
11.- El sistema prosigue el algoritmo
hasta su finalización, dependiendo
del método de ejecución. Tabla 84 - Cuadro 5.84: Caso de uso extendido: Escenario principal: Ejecución algoritmo Weighted Dominance
103
§ Escenarios Alternativos:
Actor Sistema
6b.- Si no hay más sensores.
7b.- El algoritmo ha finalizado
correctamente.
8b.- Los vértices marcados como
pertenecientes al conjunto S es la
solución al algoritmo.
5c.- El usuario cancela la operación. 6.- El sistema no ejecuta el algoritmo
y permanece en el mismo estado
antes de iniciarse el caso de uso.
1d.- El usuario selecciona el botón
de acceso directo a Weighted
Dominance.
Tabla 85 - Cuadro 5.85: Caso de uso extendido: Escenarios alternativos: Ejecución algoritmo Weighted Dominance
§ Garantías de éxito:
El algoritmo Weighted Dominance ha terminado correctamente.
Los elementos del conjunto dominante S han sido marcados.
§ Garantías de fracaso: La aplicación permanecerá en el mismo estado antes
de iniciar el caso de uso.
§ Puntos de extensión: Caso de uso: Ejecutar algoritmo paso a paso.
§ Prioridad: Alta.
§ Frecuencia: Alta.
5.2.5.31 Ejecución algoritmo Tree Growing
§ Caso de Uso: Ejecución algoritmo Tree Growing.
§ Objetivo: Ejecutar el algoritmo Tree Growing.
§ Nivel: Primario.
104
§ Actor Principal: Usuario.
§ Precondiciones: Debe existir un grafo creado.
§ Escenario Principal de éxito:
Actor Sistema
1.- El usuario selecciona en el
sistema el menú Algorithms.
2.- El usuario selecciona el submenú
Tree Growing.
3.- El sistema marca todos los
vértices como no dominados
(vértices blancos).
4.- Selecciona el vértice de mayor
peso (vértice raíz del árbol).
5.- Calcula el conjunto de vértices
dominados (nodos grises)
6.- Añade el vértice raíz al conjunto
dominante conexo S.
El sistema en cada paso:
7.- Comprueba si el conjunto
de vértices no dominados es
vacío.
8a.- Si el conjunto de
candidatos no es vacío.
9.- Selecciona el vértice gris
de mayor grado.
10.- Añade el vértice al
conjunto dominante S.
11.- Pinta el vértice
marcándolo como
perteneciente a S.
12.- Pinta sus vecinos como
vértices ya dominados
(vértices grises).
13.- Crea el nuevo conjunto
de vértices no dominados.
14.- El sistema prosigue el algoritmo
hasta su finalización, dependiendo
del método de ejecución. Tabla 86 - Cuadro 5.86: Caso de uso extendido: Escenario principal: Ejecución algoritmo Tree Growing
105
§ Escenarios Alternativos:
Actor Sistema
8b.- Si el conjunto de candidatos es
vacío.
9b.- El algoritmo ha finalizado
correctamente.
10b.- Los vértices marcados como
pertenecientes al conjunto S es la
solución al algoritmo.
1c.- El usuario selecciona el botón
de acceso directo a Tree Growing.
Tabla 87 - Cuadro 5.87: Caso de uso extendido: Escenarios alternativos: Ejecución algoritmo Tree Growing
§ Garantías de éxito:
El algoritmo Tree Growing ha terminado correctamente.
Los elementos del conjunto dominante S han sido marcados y son
conexos.
§ Garantías de fracaso: La aplicación permanecerá en el mismo estado antes
de iniciar el caso de uso.
§ Puntos de extensión: Caso de uso: Ejecutar algoritmo paso a paso.
§ Prioridad: Alta.
§ Frecuencia: Alta.
5.2.5.32 Ejecución algoritmo Marking
§ Caso de Uso: Ejecución algoritmo Marking.
§ Objetivo: Ejecutar el algoritmo Marking.
§ Nivel: Primario.
§ Actor Principal: Usuario.
§ Precondiciones: Debe existir un grafo creado.
106
§ Escenario Principal de éxito:
Actor Sistema
1.- El usuario selecciona en el
sistema el menú Algorithms.
2.- El usuario selecciona el submenú
Marking.
4.- El usuario selecciona el grafo
inicial.
5.- El usuario confirma la operación.
3.- El sistema muestra una nueva
pantalla solicitando al usuario el
grafo inicial.
6.- El sistema crea la lista de vértices
iniciales.
7.- El sistema crea la lista de vecinos
de los vértices iniciales.
El sistema en cada paso:
8.-Comprueba que el
conjunto de vértices iniciales
no sea vacío.
9.- Selecciona el primero en
la lista de vértices iniciales
(vértice u).
10.- Calcula la lista de
vecinos de los vecinos de u.
11a.- Si u no está en la lista
de vecinos.
12- Añade el vértice u al
conjunto dominante S.
13.- Añade los vecinos de u
como vértices iniciales
(conocidos).
14.- El sistema continúa el algoritmo
hasta su finalización, dependiendo
del método de ejecución. Tabla 88 - Cuadro 5.88: Caso de uso extendido: Escenario principal: Ejecución algoritmo Marking
107
§ Escenarios Alternativos:
Actor Sistema
8b.- Si el conjunto de candidatos es
vacío.
9b.- El algoritmo ha finalizado
correctamente.
10b.- Los vértices marcados como
pertenecientes al conjunto S es la
solución al algoritmo.
11b.- u está en la lista de vecinos.
12.- Añade los vecinos de u como
vértices iniciales (conocidos).
13.- El sistema prosigue el algoritmo
hasta su finalización, dependiendo
del método de ejecución.
5d.- El usuario cancela la operación. 6.- El sistema no ejecuta el algoritmo
y permanece en el mismo estado
antes de iniciarse el caso de uso.
1e.- El usuario selecciona el botón
de acceso directo a Marking.
Tabla 89 - Cuadro 5.89: Caso de uso extendido: Escenarios alternativos: Ejecución algoritmo Marking
§ Garantías de éxito:
El algoritmo Marking ha terminado correctamente.
Los elementos del conjunto dominante S han sido marcados.
§ Garantías de fracaso: La aplicación permanecerá en el mismo estado antes
de iniciar el caso de uso.
§ Puntos de extensión: Caso de uso: Ejecutar algoritmo paso a paso.
§ Prioridad: Alta.
§ Frecuencia: Alta.
108
5.3 Diseño de bajo nivel
Para la realización del diseño de bajo nivel se ha optado por mostrar el
diagrama de clases y así poder mostrar una visión global de los componentes del
sistema y la relación entre ellos.
5.3.1 Diagrama de clases.
Como ya hemos comentado anteriormente, se ha optado por usar una
metodología orientada a objetos para el desarrollo de la aplicación, de esta forma nos
beneficiamos de las ventajas que aporta dicha metodología como su posterior usabilidad
y de esta forma encontrar la finalidad de esta aplicación que no es otra que ser el punto
de partida para otras investigaciones futuras sobre la dominancia en grafos.
El siguiente diagrama de clases ha sido simplificado ya que una de las
decisiones que tomé al principio del proyecto fue no generar demasiadas clases,
pensando que en un futuro pudiera ser más fácil de entender, mantener y ampliar por un
posible usuario. Por otra parte dicha simplificación permite entender la relación
existente entre las clases creadas y la funcionalidad de cada una de ellas.
5.3.2 Visión general.
Antes de mostrar el diagrama de clases quiero introducir cada una de ellas y así
obtener una visión de su funcionalidad.
Frame Domination Graph
Para la creación de esta clase se ha utilizado una extensión de JFrame. Es la
clase encargada de la ventana principal de la aplicación y de la interacción de todas las
operaciones en esta.
109
Draw Object Steps
Esta es la clase encargada de todas las operaciones que necesiten
dibujar/mostrar en pantalla los grafos, resultados, acciones, o información de cualquier
tipo. Para ello se ha decido usar la clase JPanel.
Graph
Es la clase encargada de la ejecución de todos los algoritmos, cálculos y
comprobaciones sobre un grafo. También se incluye la creación de diversos grafos
conocidos.
Nodes
Clase que implementa los nodos de un grafo e incluye la funcionalidad para
guardar/obtener todas las propiedades de un nodo y las distintas funciones con este.
Edge
Clase que implementa los arcos entre nodos de un grafo e incluye la
funcionalidad para guardar/obtener todas las propiedades de un arco y las distintas
funciones con este.
AboutWindows
Clase JFrame que muestra la información sobre el proyecto.
110
FrameDominationGraph
<<Property>> - action : int<<Property>> - canvas : DrawObjectSteps<<Property>> - sensors : int
+ lock() : void+ main(java.lang.String[] args) : static void+ SetInfoPanel(java.lang.String info) : void+ unlock() : void
DrawObjectSteps
Node
<<Property>> - pointxy : Point<<Property>> - color_node : Color<<Property>> - status : Boolean<<Property>> - weight : Integer<<Property>> - selected : Boolean
+ Node() : Node+ Node(Point p, Color c, Boolean status, int weight, Boolean selected) : Node+ Add_Weight(Node n, int weight) : Node+ getColor_node() : Node+ getPointxy() : Point+ getSelected() : Boolean+ getStatus() : Boolean+ getWeight() : Integer+ Modify_color(Node n, Color c) : Node+ Modify_point(Node n, Point p) : Node+ Modify_Selected(Node n, boolean selected) : Node+ Modify_Weight(Node n, Integer weight) : Node+ setColor_node(Color color_node) : void+ setPointxy(Point pointxy) : void+ setSelected(Boolean selected) : void+ setStatus(Boolean status) : void+ setWeight(Integer weight) : void
Graph
<<Property>> - canvas : DrawObjectSteps<<Property>> - nodes_weight : Vector<<Property>> - nodes_removed : Vector
+ Graph() : Graph+ Calculate_Weight2(Vector list_nodes, Vector graph) : int+ Clone_List(Vector list_input) : Vector+ Clone_Nodes(Vector list_input) : Vector+ Completed_BipartiteGraphKmn(Integer num_nodes_left, Integer num_nodes_right, int x, int y, Vector nodes, Vector graph) : void+ Completed_GraphKn(Integer num_nodes, int x, int y, Vector nodes, Vector graph) : void+ Delete_Node_And_Edges(Vector nodes, Vector graph, Integer pos) : void+ Delete_Node_Weight(Vector nodes, Vector graph, Integer pos) : void+ Empty_Graph(Integer num_nodes, int x, int y, Vector nodes, Vector graph) : void+ Get_List_Neightboard(Vector pos_nodes, Vector graph) : Vector+ Grotzsch(int x, int y, Vector nodes, Vector graph) : void+ Heawood(int x, int y, Vector nodes, Vector graph) : void+ Herschel(int x, int y, Vector nodes, Vector graph) : void+ Interlace_GraphLnr(Integer num_nodes, Integer num_interlace, int x, int y, Vector nodes, Vector graph) : void+ Interlace_GraphLnrs(Integer num_nodes, Integer num_r, Integer num_s, int x, int y, Vector nodes, Vector graph) : void+ Is_Connected(Vector domination_nodes, Vector graph) : Boolean+ Mobile_Network_Algorithm(Vector pos_nodes_initial, Vector graph) : Vector+ Node_In_List(Integer u, Vector neightboards_w) : Boolean+ Petersen(int x, int y, Vector nodes, Vector graph) : void+ Pirate_Algorithm(Vector nodes, Vector graph, Integer k) : Vector+ Rectangle(Integer num_nodes_horizontal, Integer num_nodes_vertical, int x, int y, Vector nodes, Vector graph) : void+ Select_Node_Weight(Vector nodes_weight) : int+ Star(Integer num_nodes, int x, int y, Vector nodes, Vector graph) : void+ WheelWn(Integer num_nodes, int x, int y, Vector nodes, Vector graph) : void
Edge
<<Property>> - origin_point : Point<<Property>> - inter_point : Point<<Property>> - final_point : Point
+ getFinal_point() : Point + getInter_point() : Point+ getOrigin_point() : Point+ setFinal_point(Point final_point) : void+ setInter_point(Point inter_point) : void+ setOrigin_point(Point origin_point) :void
AboutWindows
+ AboutWindow()+ main(java.lang.String[] args) : static void
Ilustración 43 - Figura 5.2: Diagrama de clases (parte1)
111
Para simplificar el diagrama no se ha incluido la clase DrawObjectSteps
completa, ya que es la clase con mayor contenido y he optado por mostrar el diagrama
completo.
DrawObjectSteps
- Padre – parent : FrameDominationGraph <<Property>> - Points_number : int <<Property>> - nodes : Vector<<Property>> - exits_node : int <<Property>> - Random_nodes : int <<Property>> - image : Image<<Property>> - gBuffer : Graphics <<Property>> - node_change : int <<Property>> - pos_node_change : int<<Property>> - edge_aux : Edge <<Property>> - num_nodes_clicked : int <<Property>> - origin_edge: Point<<Property>> - final_edge: Point <<Property>> - list_nodes_ady : Vector <<Property>> - graph : Vector<<Property>> - list_nodes_selected : Vector <<Property>> - threadDominationSet : Thread <<Property>> - algorithm_number : int<<Property>> - Locked : Boolean <<Property>> - paso : int <<Property>> - res : String<<Property>> - res_aux : String <<Property>> - is_connected : Boolean <<Property>> - prueba : Vector<<Property>> - graph_all : Graph <<Property>> - node_select : int <<Property>> - num_nodes : int<<Property>> - list_ady_node : Vector <<Property>> - list_nodes_removed : Vector <<Property>> - domination_set : Vector<<Property>> - graph_domination : Vector <<Property>> - list_nodes : Vector <<Property>> - endDominationSet : Boolean<<Property>> - list_node_gray : Vector <<Property>> - pos : int <<Property>> - k : int<<Property>> - step : int <<Property>> - graph_pirate : Vector <<Property>> - nodes_selected : Vector<<Property>> - threadPirateAlgoritm : Thread <<Property>> - node_higher_weight : Boolean <<Property>> - nodes_removed : Vector<<Property>> - graph_mobile : Vector <<Property>> - pos_nodes_initial : Vector <<Property>> - nodes_initial_neightboard : Vector<<Property>> - num_nodes_initial : Integer <<Property>> - position_nodes_initial : int <<Property>> - position_neightboard : int<<Property>> - position_ady_neightboard : int <<Property>> - check_neightboard : Boolean <<Property>> - count_initial : int<<Property>> - nodes_gray : Vector <<Property>> - nodes_white : Vector <<Property>> - graph_connected : Vector<<Property>> - list_nodes_connected : Vector <<Property>> - node_select_connected: int <<Property>> - step_connected : int<<Property>> - threadMobile_NetworkAlgoritm : Thread <<Property>> - list_ady_node_aux : Vector<<Property>> - neightboard_nodes_initial_neightboard : Vector <<Property>> - node_n : Integer<<Property>> - threadDomination_ConnectedAlgoritm : Thread <<Property>> - nodes_black : Vector
+ add_weight(Point p, int action) : void+ Algorithm_Pirate(Integer k) : void+ Clone_List(Vector list_input) : Vector+ Delete_edge(Point p, int action) : void+ Delete_graph() : void+ Delete_Node_And_Edges(Vector nodes, Vector graph, Integer pos, Vector nodes_removed) : void+ Delete_Node_Edges(Vector nodes, Vector graph, Integer pos) : void+ delete_node(Point p, int action) : void+ Domination_Connected() : String+ Domination_Set() : String+ Draw_CompleteBipartiteGraphKmn(Integer num_nodes_left, Integer num_nodes_right) : void+ Draw_CompleteGraphKn(Integer num_nodes) : void+ draw_edge_change(Point p, int action) : void+ draw_edge_final(Point p, int action) : void+ draw_edge(Point p, int action) : void+ Draw_Empty_Graph(Integer num_nodes) : void+ Draw_Grotzsch() : void+ Draw_Heawood() : void+ Draw_Herschel() : void+ Draw_InterlaceGraphLnr(Integer num_nodes, Integer r) : void+ Draw_InterlaceGraphLnrs(Integer num_nodes, Integer r, Integer s) : void+ draw_node_change(Point p) : void+ draw_node_final(Point p, int action) : void+ draw_node(Point p, int action) : void+ Draw_Nodes_Mobile() : void+ Draw_Petersen() : void+ Draw_Rectangle(Integer num_col, .Integer num_row) : void+ Draw_Star(Integer num_nodes) : void+ Draw_WheelWn(Integer num_nodes) : void+ Find_Node_Greater_Degree(Vector nodes, Vector list_ady) : int+ Find_Position_Greater_Degree(Vector nodes, Vector graph) : int+ getNodes() : Vector+ Mobile_Network() : void+ Node_In_Graph(Integer position_node, Vector list) : Boolean+ Node_In_List(Integer position, Vector nodes) : Boolean+ Node_Select_Orange(int node_select, Vector list_nodes, Vector graph, Image image_draw, Graphics buffer, Graphics g, Color color) : Image+ Nodes_gray(Vector graph, Vector nodes_gray, Vector nodes_black, Integer node_select) : Vector+ Nodes_White(Vector nodes_white, Vector nodes_gray, Integer node_select) : Vector+ Not_Domination_Nodes(Vector nodes, Vector graph, Vector selected) : Vector+ paint_without_weight(Graphics g) : void+ paint(Graphics g) : void+ Random_Graph_With_Weight(int num_nodes, int probability) : void+ Random_Graph(int num_nodes, int probability) : void+ Remove_Edge_Redundant(Vector nodes, Vector graph) : Vector+ Select_initial_graph(Point p, int action) : Boolean+ update(Graphics g) : void
Ilustración 44 - Figura 5.3: Diagrama de clases (parte2)
112
113
PARTE IV
MANUAL DE USUARIO
114
115
CAPI TULO 6.- MANUAL DE USUARIO
DSA (Dominating Set Application) es una aplicación JAVA generada sobre un
archivo .jar para poder ser ejecutada en cualquier máquina que posea un sistema de
instalación JVM.
Se ha optado por una interfaz sencilla, intuitiva y que ha sido organizada como
la mayoría de las aplicaciones básicas del mercado.
6.1 Partes de la aplicación.
DSA se compone de los siguientes elementos:
Barra de menús.
Panel de acciones (acceso rápido).
Panel de algoritmos (acceso rápido).
Área de texto.
Área de trabajo/dibujo.
A continuación mostraremos con detalle cada uno de los componentes de la
ventana principal.
6.1.1 Barra de menús.
En este apartado describiremos todos los menús presentes en la aplicación,
así como las distintas opciones presentes en cada uno de ellos.
116
6.1.2 Menú File.
Este menú contiene las distintas opciones a la hora de crear/mostrar un grafo en
pantalla. A continuación describiremos brevemente cada una de las opciones.
Ilustración 45 - Figura 6.1: Menú File
New: Nos permite crear un nuevo grafo. Es necesario proporcionar el
número de nodos deseado. El grafo no contendrá ninguna arista.
Import: A partir de un fichero que contiene la información necesaria
para la creación del grafo, esta opción nos permite cargar dicho grafo en
pantalla.
Export: Al contrario que la opción anterior, esta nos permite guardar a
un fichero el grafo que aparece en ese momento en el área de dibujo.
Random: Como su nombre indica nos permite crear un grafo de forma
aleatoria, proporcionando el número de nodos y la probabilidad (0-100%)
de que exista una arista entre dos cualesquiera de los nodos.
Random with Weight: Crea un grafo aleatorio en las mismas
condiciones que la opción anterior pero nos crea el grafo asignando pesos
a los nodos de forma aleatoria (entre 0 y 20).
Exit: Permite cerrar la aplicación.
117
6.1.3 Menú Edit.
Contiene las distintas opciones para editar el grafo presente en el área de
dibujo.
Ilustración 46 - Figura 6.2: Menú Edit.
Las opciones son las siguientes:
Add Node: Nos permite añadir un nodo al grafo simplemente pinchando
sobre el área de dibujo en el lugar donde queremos que aparezca el nodo.
Esta es la opción que está seleccionada por defecto al inicio de la
aplicación.
Add Edge: Crea un arco entre dos de los nodos presentes en pantalla.
Seleccionando el nodo origen y sin soltar el botón derecho del ratón
arrastrar el puntero hasta el nodo destino y soltar.
Add Weight: Añade un determinado peso al nodo que es seleccionado.
Remove Node: Elimina el nodo que se selecciona.
Remove Edge: Elimina el arco existente entre el nodo que seleccionas
como origen y el nodo que seleccionas como destino.
Remove Graph: Borra el grafo existente en el área de dibujo.
118
6.1.4 Menú Algorithms.
El menú que describimos ahora simplemente contiene la opción de ejecutar los
distintos algoritmos que se pueden aplicar al grafo.
Dichos algoritmos son, Greedy, Weighted Dominance, Tree Growing y
Marking.
Ilustración 47 - Figura 6.3: Menú Algorithms
6.1.5 Menú Graphs.
Este menú contiene las opciones de creación de grafos conocidos o que
guardan ciertas características.
Ilustración 48 - Figura 6.4: Menú Graphs
Pasamos a explicar brevemente cada una de las opciones:
Empty Graph: Crea un grafo de un número de nodos proporcionado
vacío, es decir, sin arcos entre nodos. Acción idéntica que New en el
menú File.
Completed Graph: Crea un grafo completo con todos los arcos posibles
entre nodos. Hay dos opciones:
119
Ilustración 49 - Figura 6.5: Opciones grafo completo
Completed Graph (Kn): crea un grafo de un número de nodos dado (n),
que tiene un arco entre dos nodos cualesquiera. Este grafo se dibuja en
forma de anillo.
Completed Bipartite Graph (Km,n): como el anterior, crea un grafo de un
número determinado de nodos que tiene un arco entre dos nodos
cualesquiera, pero con la diferencia que el grafo se dibuja con (m) nodos
al lado izquierdo y (n) nodos al derecho.
Bound Graph: Crea un grafo entrelazado donde los nodos se unen de
forma entrelazada según el parámetro introducido. Hay dos opciones:
Ilustración 50 - Figura 6.6: Opciones Bound Graph
L(n,r): Crea un grafo entrelazado de n nodos, r es el valor para generar el
entrelazado, donde un nodo estará unido con el r nodo siguiente.
L(n,r,s): Es igual que el anterior pero se unen los nodos siguiendo dos
valores determinados, r y s.
Grid: Crea un grafo en forma de cuadrícula. En la que se determina el
número de nodos en las filas y el número de nodos en las columnas para
su creación.
Ilustración 51 - Figura 6.7: Grid
120
Shapes: Crea un grafo de una forma determinada. Hay tres opciones
implementadas.
Cicle(Cn): Crea un grafo de n nodos en forma de círculo.
Wheel(Wn): Crea un grafo de n nodos en forma de círculo pero que los
nodos están unidos a modo de radios de la rueda.
Star: Crea un grafo de n nodos a modo de estrella, generando un nodo
centra unido al resto de nodos alrededor de este.
Ilustración 52 - Figura 6.8: Opciones Shapes.
Herschel, Petersen, Heawood y Groztsch: Crea el grafo conocido por
el nombre de su creado. Al ser un grafo determinado no hay que
introducir ningún tipo de criterio.
6.1.6 Menú Help.
Este menú es sencillo y solo contiene la opción About donde se detalla la
finalidad de proyecto fin de carrera y el autor en una nueva ventana.
Ilustración 53 - Figura 6.9: Menú Help.
6.1.7 Panel de acciones.
Se decidió crear un panel con diversos botones a modo de acceso rápido a las
acciones más utilizadas y de esta forma poder trabajar sobre el grafo de forma más
cómoda y directa.
121
Las acciones elegidas son las de New, Import, Export, Add Node, Remove
Node, Add Edge, Remove Edge, Add Weight y Remove Graph.
Ilustración 54 - Figura 6.10: Panel de acciones.
6.1.8 Panel de algoritmos.
Utilizando el mismo criterio que para el panel de acciones, se ha creado un
panel vertical con los botones para la ejecución de los distintos algoritmos.
Se ha incluido la opción de seleccionar el modo de ejecución paso por paso y
de esta forma utilizando el botón Next se puede ir observando como el grafo cambia con
cada paso del algoritmo.
Ilustración 55 - Figura 6.11: Panel de algoritmos.
6.1.9 Área de texto.
Se ha utilizado una pequeña área de texto para incluir explicaciones sobre las
operaciones que se pueden realizar desde los paneles de acciones y algoritmos.
122
Por otra parte el panel también muestra los resultados de la ejecución de los
algoritmos en sus dos modos de ejecución, inmediata o paso a paso.
Ilustración 56 - Figura 6.12: Área de texto – Explicación Add Edge
6.1.10 Área de trabajo/dibujo.
Como he explicado anteriormente se ha optado por la clase de JAVA Canvas para
desarrollar el área de dibujo de los grafos, es una clase sencilla de manejar y que te
permite realizar todas las operaciones que necesitábamos para el desarrollo de esta
aplicación.
A continuación mostramos un ejemplo de un grafo dibujado en dicha área.
Ilustración 57 - Figura 6.13: Área de dibujo – ejemplo grafo
6.2 Operaciones básicas.
En este apartado vamos a entrar en detalle sobre todas las operaciones básicas
que se pueden realizar en la aplicación.
6.2.1 Crear un grafo nuevo.
Para la realización de un grafo nuevo hay dos posibilidades desde el acceso
rápido del panel de acciones (New) o desde el menú File (opción New).
123
La creación de un grafo nuevo solo contempla la posibilidad de crear el grafo
con el número de nodos que desees, pero no genera ninguna arista entre esos nodos.
Aparecerá la siguiente ventana donde se solicita el número de nodos deseado,
con un máximo de 40.
Ilustración 58 - Figura 6.14: Crear grafo nuevo
Una vez que el número de nodos es aceptado, el grafo aparecerá en pantalla
distribuyendo los nodos en forma de círculo.
6.2.2 Crear un grafo aleatorio.
Con esta opción podemos crear un grafo de forma aleatoria, solo indicando el
número deseado de nodos y la probabilidad de que exista una arista entre dos nodos
determinados.
En este caso esta opción solo está disponible desde el menú File (Random) y
una vez que es ejecutada aparece una ventana solicitando la probabilidad entre 0 y 100
de que exista una arista entre dos nodos cualesquiera.
Ilustración 59 - Figura 6.15: Creación grafo aleatorio- Probabilidad aristas
124
Una vez introducido la probabilidad, aparece una segunda ventana en la que se solicita
el número de nodos deseado (ver figura 6.14).
En esta ocasión y a diferencia del punto anterior, la distribución de los nodos
en el área de trabajo es totalmente aleatoria.
6.2.3 Crear un grafo aleatorio con pesos.
La acción es idéntica al paso anterior, solicitando exclusivamente la
probabilidad de la existencia de una arista entre dos nodos y el número de nodos. Pero
en esta ocasión el grafo se crea, de forma aleatoria, con un peso entre 0 y 20 asociado a
cada uno de los nodos.
Ilustración 60 - Figura 6.16: Grafo aleatorio con pesos asignados.
6.2.4 Exportar grafo.
Esta opción nos permite guardar el grafo que hay actualmente en el área de
trabajo. Una vez ejecutada simplemente aparecerá una ventana para seleccionar donde
guardar el grafo y el nombre que se le quiere dar al fichero.
125
Ilustración 61 - Figura 6.17: Exportar grafo.
El fichero se guarda con el siguiente formato sin ningún salto de línea.
NODE LIST: [(460,70;0) (340,150;0) (400,150;0) (460,150;0) (520,150;0) (580,150;0)
(340,230;0) (400,230;0) (460,230;0) (520,230;0) (580,230;0) (460,310;0) ]
ADYACENCE LIST: ([1, 2, 3, 4, 5][0, 6][0, 7][0, 8][0, 9][0, 10][1, 11][11, 2][3,
11][11, 4][5, 11][10, 9, 8, 7, 6])
Simplemente son dos listas la primera son los nodos del grafo en el que se
guardan las coordenadas XY del nodo y su peso. La siguiente es la lista de adyacencia
de los nodos, es decir, la lista de vértices que tiene cada uno de los nodos, por orden de
creación.
6.2.5 Importar grafo.
Al contrario que la opción anterior, importar grafo nos permite mostrar en el
área de trabajo un grafo guardado a fichero previamente. Se nos mostrará una ventana
similar a la Figura 6.17 en la que tendremos que elegir el fichero del grafo que
queremos importar.
126
6.2.6 Salir.
Para salir de la aplicación se deberá escoger la opción Exit del menú File.
6.2.7 Añadir nodo.
Es la acción por defecto de la aplicación. Para añadir un nodo simplemente hay
que hacer click con el botón izquierdo del ratón en cualquier lugar libre de la pantalla.
Si se pulsa sobre un nodo ya existente el nuevo nodo no será creado.
Si alguna otra opción ha sido escogida anteriormente al deseo de añadir un
nodo, hay que elegir la acción de añadir nodo desde el panel de acciones o desde el
menú Edit opción Add Node.
6.2.8 Añadir arista.
Para añadir una arista debemos seleccionar la operación desde el panel de
acciones y bien desde el menú Edit Add Edge.
Para añadir la arista entre dos nodos, hay que seleccionar con el botón
izquierdo del ratón el nodo origen de la arista y sin soltarlo arrastrar el ratón hasta el
nodo destino y soltar el botón izquierdo. La nueva arista aparecerá en pantalla.
6.2.9 Añadir peso a un nodo.
Esta operación también es seleccionable desde el panel de acciones o desde el
menú Edit. Para añadir el peso basta con seleccionar el nodo al que queremos añadir el
peso y aparecerá una ventana solicitando el valor del peso a añadir con un valor máximo
de 100.
127
Ilustración 62 - Figura 6.18: Insertar peso a un nodo
6.2.10 Eliminar nodo.
Para eliminar un nodo basta con seleccionar la acción y pinchar sobre el nodo a
eliminar. Se eliminara el propio nodo y todas las aristas que tenga.
6.2.11 Eliminar arista.
Una vez seleccionada esta operación, basta con seleccionar el nodo origen de la
arista a eliminar y posteriormente el nodo destino y de esta forma la arista será
eliminada del grafo.
6.2.12 Eliminar grafo.
Si se selecciona esta opción desde el menú File (Remove Graph) o desde el
panel de acciones, el grafo presente en el área de trabajo será eliminado completamente.
6.2.13 Grafos predefinidos.
En Teoría de Grafos se utilizan con relativa frecuencia una serie de grafos que
poseen ciertas propiedades o características y que por ellos son utilizados para explicar
teoremas o algoritmos.
Debido a su alta frecuencia se han creado un conjunto de ellos, para crearlos
basta con seleccionar el que deseamos desde el menú Graph e introducir los valores que
se solicitan en su caso.
128
Esta es la lista de grafos tipo que se han creado:
Grafo vació o nulo
Grafo completo (Kn)
Grafo completo bipartido (Km,n)
Grafo enlazado Ln,r
Grafo doblemente enlazado Ln,r,s
Grafo rejilla: Rectángulo
Grafo forma: Circulo (Cn), Rueda(Wn) y Estrella
Grafo de Herschel
Grafo de Petersen
Grafo de Heawood
Grafo de Grotzsch
129
6.3 Ejecución de algoritmos.
La finalidad de esta aplicación es la ejecución de varios algoritmos de
dominación en grafos. Para realizar esta tarea tenemos que seleccionar el algoritmo a
ejecutar en el panel de algoritmos o bien desde el menú Algorithms.
Hay dos tipos de ejecución posible, la ejecución inmediata (ejecución por
defecto) o la ejecución paso a paso, de la que hablaremos más adelante. El tipo de
ejecución debe seleccionarse desde el panel de algoritmos.
6.3.1 Ejecución inmediata.
Este tipo de ejecución muestra el resultado final de la ejecución del algoritmo
sin mostrar como se ha llegado a dicha solución final. El resultado del algoritmo será
mostrado sobre el propio algoritmo, seleccionando los nodos que forman parte del
conjunto dominante de dicho nodo y mostrando en el área de texto más información
sobre el resultado.
6.3.2 Ejecución paso a paso.
Se ha querido añadir este modo de ejecución para poder mostrar paso por paso
la ejecución de un algoritmo y de esta forma poder entender que paso va realizando en
cada iteración. Creo que es un punto importante ya que no podemos olvidar la finalidad
docente que también tiene esta aplicación.
Para pasar de una iteración a otra del algoritmo o para interrumpir su ejecución
se utilizan los botones Stop y Next que podemos encontrar en el panel de algoritmos.
130
Ilustración 63 - Figura 6.19: Ejecución paso a paso.
Cada vez que se pulsa el botón Next, el grafo será modificado y mostrado en el
área de trabajo para enseñar como ha avanzado el algoritmo en busca de la solución
final.
6.3.3 Algoritmos.
La aplicación puede ejecutar cuatro algoritmos diferentes, estos algoritmos son:
Algoritmo Greedy
Algoritmo Weighted Dominance
Algoritmo Tree Growing
Algoritmo Marking
A continuación pasamos a detallar en que consiste cada uno de los algoritmos y
como se realiza su ejecución.
6.3.3.1 Algoritmo Greedy.
Una vez que tenemos el grafo presente en el área de trabajo, solo necesitamos
ejecutar el algoritmo.
Vamos a representar un ejemplo de ejecución del algoritmo para un grafo
sencillo, tanto de forma inmediata como paso a paso.
131
Como ejemplo se ha optado por el grafo de Petersen, como mostramos a
continuación:
Ilustración 64 - Figura 6.20: Grafo ejemplo (Petersen).
Ejecución inmediata:
Ilustración 65 - Figura 6.21: Ejemplo ejecución inmediata – Algoritmo Greedy.
132
Como se puede observar en la figura 6.21, el conjunto dominante es el formado
por los nodos 1, 3 y 7, siendo el conjunto dominante no conexo.
Ahora vamos a mostrar como se ha llegado a esa solución ejecutando el
algoritmo paso a paso.
Paso 1:
Ilustración 66 - Figura 6.22: Ejemplo ejecución paso a paso – Algoritmo Greedy – Paso1.
Como se puede observar en el área de texto, en este paso 1 se ha escogido el
nodo con mayor grado (nodo 1) y se han eliminado de la lista de nodos posibles a sus
vecinos.
133
Paso 2:
Ilustración 67 - Figura 6.23: Ejemplo ejecución paso a paso – Algoritmo Greedy – Paso2
En este caso se ha escogido al nodo 3 como nodo de mayor grado y eliminado
a sus vecinos.
134
Paso 3:
Ilustración 68 - Figura 6.24: Ejemplo ejecución paso a paso – Algoritmo Greedy – Paso3.
Se ha seleccionado el nodo 7 con mayor grado y se han eliminado sus vértices,
al no haber más nodos disponibles, el algoritmo ha llegado a su final y pulsando una vez
más en el botón de Next lo que mostrará es el resultado del algoritmo, tal y como se
puede ver en la figura 6.21.
6.3.3.2 Algoritmo Weighted Dominance
Al igual que el resto de algoritmos, se pueden ejecutar desde el panel de
algoritmos o desde el menú Algorithms.
A continuación vamos a utilizar el siguiente ejemplo de grafo con pesos para
mostrar la ejecución del algoritmo.
135
Ilustración 69 - Figura 6.25: Grafo ejemplo – Weighted Dominance
Este algoritmo calcula, para un número determinado de “sensores”, en que
nodos deberían situarse para “vigilar” el mayor número de nodos posibles. Para ello
debemos proporcionar al algoritmo dicho número de sensores.
Ilustración 70 - Figura 6.26: Introducir número de sensores – Weighted Dominance
Para nuestro ejemplo hemos introducido 4 sensores.
Ejecución inmediata:
Ilustración 71 - Figura 6.27: Ejecución inmediata – Weighted Dominance
136
Como se puede observar el algoritmo ha utilizado los 4 sensores indicados, que
pasan a formar parte del conjunto dominante, pero el nodo 1 se ha quedado sin vigilar.
Como hemos explicado en la parte teórica de esta memoria, los algoritmos no son
perfectos y pueden ofrecer una solución que no es óptima.
Ejecución paso a paso:
Paso 1:
Ilustración 72 - Figura 6.28: Ejecución paso a paso – Weighted Dominance – Paso1
En ese paso a cada nodo se suma el peso de sus vecinos, de esta forma se puede
calcular el nodo con mayor peso y este será el seleccionado para formar parte del
conjunto dominante.
Paso 2:
Ilustración 73 - Figura 6.29: Ejecución paso a paso – Weighted Dominance – Paso2
137
Como hemos comentado anteriormente se elige el nodo que tiene mayor peso.
Paso 3:
Ilustración 74 - Figura 6.30: Ejecución paso a paso – Weighted Dominance – Paso3
En este paso se elimina el nodo seleccionado, eliminando a su vez a todos sus
vecinos y las adyacencias de estos, es decir, todos los arcos tanto del nodo seleccionado
como de sus vecinos.
En este paso el algoritmo comienza de nuevo, sumando los pesos y calculando
de nuevo el nodo con mayor peso.
El algoritmo avanza hasta que se cumpla una de las siguientes condiciones:
No queden nodos para seleccionar.
Se haya llegado al número establecido de sensores.
6.3.3.3 Algoritmo Tree Growing
Para explicar la ejecución de este algoritmo se ha optado por el siguiente grafo
a modo de ejemplo:
138
Ilustración 75 - Figura 6.31: Grafo ejemplo – Tree Growing
Ejecución inmediata:
Ilustración 76 - Figura 6.32: Ejecución inmediata – Tree Growing
La figura 6.32 nos muestra el resultado final donde el conjunto dominante es
conexo, tiene forma de árbol y está formado por los vértices {1, 2, 3, 4, 5, 6, 7}. No es
la solución óptima puesto que si en lugar de recorrer el árbol en anchura se hubiese
recorrido en profundidad, hubiésemos obtenido un CDS con solo 4 nodos, uno por nivel
del árbol.
Ejecución paso a paso:
Paso 1:
139
Ilustración 77 - Figura 6.33: Ejecución paso a paso – Tree Growing – Paso1
En este paso se muestra el grafo inicial del algoritmo Tree Growing, donde
todos los nodos inicialmente son marcados como no dominados (nodos blancos).
Paso 2:
Ilustración 78 - Figura 6.34: Ejecución paso a paso – Tree Growing – Paso2
Se selecciona como vértice negro (perteneciente al conjunto dominante
solución) al de mayor grado de entre los nodos blancos y se marcan todos sus vecinos
como nodos grises.
Pasos intermedios:
Ilustración 79 - Figura 6.35: Ejecución paso a paso – Tree Growing – Pasos intermedios
140
La figura 6.35 muestran el paso general del algoritmo, donde los vértices 2, 3,
4, 5 y 6 van pasando a formar parte del conjunto dominante solución y sus vecinos se
van marcando como vértices grises.
De esta forma el árbol se recorre en anchura, proporcionando una solución que
no es mínima. Como hemos comentado anteriormente hay una mejora de este algoritmo
que recorre el árbol en profundidad y que ofrece una mejor solución.
Ilustración 80 - Figura 6.36: Ejecución paso a paso – Tree Growing – Paso final
En la figura 6.36 se muestra el paso general en el que todos los vértices están
en el conjunto dominante solución o son vértices grises, por lo que el algoritmo para en
este paso.
Ilustración 81 - Figura 6.37: Ejecución paso a paso – Tree Growing – Solución
141
6.3.3.4 Algoritmo Marking
El siguiente grafo ha sido utilizado a modo de ejemplo para poder explicar el
funcionamiento de este algoritmo. Es un grafo en el que se puede representar
gráficamente una red móvil en la que inicialmente solo conoces una serie de nodos
determinados.
Ilustración 82 - Figura 6.38: Grafo ejemplo – Algoritmo Marking
Para la ejecución de este algoritmo se nos solicita que seleccionemos el grafo
inicial del que conocemos todos sus nodos.
142
Ilustración 83 - Figura 6.39: Selección grafo inicial – Algoritmo Marking
Se selecciona nodo por nodo haciendo click sobre él, el nodo será marcado en
negro. Una vez finalizado la selección del grafo inicial, hacemos click en cualquier
parte, sin seleccionar un nodo. De esta forma aparecerá un mensaje de confirmación con
el grafo inicial. Quedando, en este ejemplo, de la siguiente forma:
143
Ilustración 84 - Figura 6.40: Grafo inicial seleccionado – Algoritmo Marking
Ejecución inmediata:
Cuando el grafo inicial es confirmado aparece la solución final encontrada por
este algoritmo. Donde los nodos que pertenecen al conjunto dominante están marcados
en color amarillo. Este algoritmo solo ofrece soluciones que son grafos conexos.
144
Ilustración 85 - Figura 6.41: Ejecución inmediata – Algoritmo Marking
Ejecución paso a paso:
Paso 1:
Una vez seleccionado el grafo inicial, el algoritmo en cada paso selecciona uno
de los nodos iniciales para recorrer el grafo inicial completamente.
145
Ilustración 86 - Figura 6.42: Ejecución paso a paso – Algoritmo Marking – Nodo inicial
Paso 2:
Se comprueba por cada par de vecinos del nodo seleccionado si son vecinos entre ellos,
en caso de encontrar un par de vecinos que no son vecinos entre sí. Se añade el nodo
seleccionado al conjunto dominante final y todos sus vecinos pasan a ser miembros del
grafo inicial.
146
Ilustración 87 - Figura 6.43: Ejecución paso a paso – Algoritmo Marking – Paso2
Pasos intermedios:
De esta forma se va añadiendo al grafo conocido el resto de nodos desconocidos
y se recorre el grafo completamente. Seleccionado todos y cada uno de los nodos que
van perteneciendo al grafo inicial y se va construyendo el conjunto dominante final.
En este punto ya se han recorrido todos los nodos del grafo.
147
Ilustración 88 - Figura 6.44: Ejecución paso a paso – Algoritmo Marking – Pasos intermedios.
El siguiente paso es mostrar el resultado final.
Ilustración 89 - Figura 6.45: Ejecución paso a paso – Algoritmo Marking – Paso final.
148
149
Bibliografí a
[1] Boudreau, T., Glick, J., Greene, S., Spurlin, V., Woerh, J.J. - NetBeans: The
definitive Guide (2002)
[2] Ceballos, F.C. - JAVA 2. Interfaces gráficas y Aplicaciones (2006)
[3] J. Czyzowicz, S. Dobrev, T. Fevens, H. González-Aguilar, E. Kranakis, J.
Opatrny, J. Urrutia - Local Algorithms for Dominating and Connected Dominating Sets
of Unit Disk Graphs with Location Aware Nodes (2008)
[4] B. Das, V. Bharghavan - Routing in Ad-Hoc Networks Using Minimum Connected
Dominating Sets (1997)
[5] B. Das, E. Sivakumar, V. Bhargavan - Routing in ad Hoc Networks using a virtual
backbone (1997)
[6] S.Guha, S.Khuller - Approximation Algorithms for Connected Dominating Sets
(1998)
[7] Haynes T.W., Hedentiemi S.T., Slater P.J. - Fundamentals of domination in graphs
(1998)
[8] Hernandez Peñalver, G. - Grafos: teoría y algoritmos (2003)
[9] J. Urrutia - Local solutions for global problems in wireless networks (2006)
*También se han utilizado los distintos medios disponibles en internet para la
elaboración del presente proyecto, tales como Wikipedia, foros de programación etc.