rusito-23/wahlaan

Greedy algorithm implementation for graph coloring using plain C

Wahlaan 🤓

Discrete Math II 2019 - Famaf, Argentina. Uses the Greedy algorithm for Graph Coloring with C.

Test Suites

• SANITY

    Runs several UnitTests over the required functions.
  

• PERFORMANCE

    Runs several actions, saving the partial time for each of one:
  

  • Graph reading
  • Greedy with natural order
  • WelshPowell Re-Ordering and Greedy
  • 100 SwitchVertices
  • 1000 RMBCs + Greedy

• COLOR

    Shows the results of Greedy with the following orders:
  

  • Natural
  • Welsh Powell
  • 100 SwitchVértices
  • 100 RMBCs

• BIPARTITO

    Shows the results of running Greedy and Bipartite over the graph.
  

Makefile 🔛

The makefile provides the following targets:

• make <suite> GRAPH=Path/to/Graph Suite over a Graph

  Example: make sanity GRAPH=Graphs/K4.txt

• make <suite>-all FOLDER=Path/To/Folder Suite over a folder of Graphs

  Ejemplo: make performance-all FOLDER=Graphs/Performance

• make <suite>-valgrind GRAPH=Path/To/Graph Suite over a Graph with Valgrind results:

  make bipartito-valgrind GRAPH=Graphs/Bipartito.txt VALGRIND='valgrind --leak-check=full --show-leak-kinds=all'

Structure

.
├── Graphs
│   ├── Bipartite
│   ├── Color
│   │   └── Small graphs to check COLOR suite
│   ├── Complete
│   │   └── Complete Graphs
│   └── Performance
│       └── Large graphs to test the PERFORMACE suite
├── Makefile
├── README.md
├── Test
│   ├── PrintTests.c
│   ├── TestSuites.c
│   ├── Tests.h
│   ├── TestsMultiples.c
│   └── UnitTests.c
├── Wahlaan
│   ├── Project .c files
│   └── Rii.h
└── main.c

wahlaan's Issues

Agregar por parámetro el nombre del archivo en main.c

Se me ocurre que se debería poder tomar por parámetro el nombre del archivo de la forma:

main.c --suite PERFORMANCE --graph Path/al/archivo

Esto serviría para correr el proyecto desde algunos IDEs como Clion, que no dan la posibilidad de redirigir el stdin.

Eliminar todo el uso de la estructura del Grafo del Proyecto

NADA DE USO DE LA ESTRUCTURA

En varios lados en el proyecto se usa mi estructura de Grafo, cuando se deberían usar las funciones dadas por el proyecto mismo. ERROR GRAVE WACHIN ARREGLALO

Completar los UnitTest

Los unit test están incompletos

Falta:

• Test de CopiarGrafo (OK)

• Test de cantidad de colores (OK)

• Corregir test de bipartito para chequear cantidad de colores (OK)

• Agregar Test de coloreo propio y chequearlo luego de cada orden (OK)

• test para validar que los reordenes no hace aumentar los colores en Greedy!

• test suite custom para poder correr test propios y no depender de las suites existentes