Observación obvia: Greedy con un orden dado es determinístico y el "orden natural" también.
Asi que Greedy con el orden natural les debe dar igual que lo que se dice acá.
(Aunque no les pedi una función "OrdenNatural" es algo que deberian poder programar en una linea con las funciones que si estan dadas en el proyecto)
Por otro lado, WelshPowell y los reordenes por bloques de colores no son determísticos según el proyecto (no especificamos cómo se ordenan vertices con el mismo grado o el mismo color) asi que les puede dar distinto.
queen10.Numero de vertices=100. Numero de lados=1470.
Greedy con el orden natural:16 colores
Greedy con WelshPowell:17 colores
Con una cantidad moderada de iteraciones baja a 14 y con mas iteraciones a 13 e incluso 12. Nunca pude colorearlo con 11 colores.
X(G) es 10 asi que no les puede dar menos de eso.
queen13.Numero de vertices=169. Numero de lados=3328
Greedy con el orden natural:21 colores
Greedy con WelshPowell:23 colores
Se lo puede bajar a 17 con varios reordenes por bloque de colores. X(G)=13.
School1 de la pagina de DIMACS. Numero de vertices=385. Numero de lados=19095
Greedy con el orden natural:42 colores
Greedy con WelshPowell:34 colores
Haciendo 100 ordenes aletorios baja a 32
Haciendo 426 reordenes por bloque de colores logro bajarlo a 14,pero incluso con 3000 reordenes no parece mejorar.
Numero de vertices=1010. Numero de lados=60980
Greedy con orden natural:42 colores
Greedy con WelshPowell:34 colores
Se lo puede bajar a 14 colores.
X(G) es mayor o igual que 11.
Numero de vertices=3779. Numero de lados=371357
Greedy con orden natural:77 colores
Greedy con WelshPowell:97 colores
Lo puedo bajar a 72 colores con los reordenes por bloques, pero X(G)=61 asi que hay espacio para bajarlo mas.
Este grafo tiene solo 3080 vertices pero 4 millones de lados. (4303060 para ser exacto)
Es un grafo que les puede demorar mucho a pesar de la poca cantidad de vertices si no programan bien algunas cosas.
Greedy con orden natural:339 colores
Greedy con WelshPowell:264 colores
642 reordenes por bloques lo disminuye a 112.
Tiempo total para 3102 Greedys:1m39.539s
Numero de vertices=2210104. Numero de lados=8807410
Greedy con orden natural:5 colores
Greedy con WelshPowell:2099 colores.
Con algunos reordenes el coloreo se puede bajar a 4 colores.
Tiempo total para 3102 Greedys: 6m15.192s
Este grafo es importante para el manejo de memoria: si no la usan bien, puede provocar stack overflow.
Grafo comprimido, grande. Welsh Powell va a dar mucho mas del X(G)
Este grafo es el "antecesor" del BxB1100... de arriba. Si les falla con el BxB1100... pero anda bien con este, entonces es muy plausible que tengan un stack overflow problem. Si los dos fallan entonces es mas plasusible que el error este en otro lado.Un grafo aleatorio con 1999999 vertices y 10123123 lados. ESTE GRAFO ES MUY IMPORTANTE: Varios grupos podian trabajar con otros grafos grandes sin problemas, pero tenian un error especifico en Greedy que hacia que con este (y otros grafos similares) demorasen HORAS para hacer menos de 10 Greedys. Sin embargo, si Greedy esta bien programado, deberia demorar muy pocos minutos.
Numero de vertices=221651. Numero de lados=12528006
Greedy con orden natural:600 colores
Greedy con WelshPowell:581 colores
3000 reordenes por bloque de colores lo baja a 523.
Tiempo total:6m4.944s
Numero de vertices=23658. Numero de lados=5586907
Greedy con orden natural:173 colores
Greedy con WelshPowell:239 colores
Luego de solo 33 reordenes lo habia bajado a 167
pero luego de un total de 3000 RMBCs eso fue lo mejor que pude obtener.
tiempo total 2m41.231s
GRAFO BIPARTITO con 2135792 vertices y 2162836 lados.
Greedy con orden natural:6 colores
Greedy con WelshPowell:5 colores
Reordenes lo bajan a 4.
Tiempo total para 3102 Greedys:3m41.215s
Numero de vertices=20002. Numero de lados=49601 Greedy con orden natural:6 colores
Numero de vertices=20482. Numero de lados=56705 Greedy con orden natural:6 colores
casi 1 millón de vértices y lados.
Un grafo aleatorio con 22 vertices y 99 lados
X(G)=1500 (comprimido)
Un grafo aleatorio con 1789 vertices y 875431 lados. Comprimido
Estos tres grafos todos dan WP en exceso del coloreo final que se puede obtener. (en los tres casos se puede colorear con 5 colores)
.