sauzeauyannis/aa-topological_sorting

graph topological sort and circuit detection

AA-Topological_Sorting

Table of Contents

• Français
  • Présentation
  • Utilisation
  • Compétences acquises
  • Résultat
• English
  • Presentation
  • Use
  • Skills acquired
  • Result

Français

Présentation

Ce projet a été effectué en quatrième année du CMI Informatique à l'UFR SFA Université de Poitiers dans le cadre de l'enseignement Algorithmique avancée.

Ce projet a été développé en monôme avec Visual Studio Code.

Utilisation

Pour compiler le projet, vous pouvez utiliser le Makefile.

La commande make help permet de voir les différentes commandes possibles.

Pour tester un des graphes du dossier graph, vous devez saisir la commande make test<n> avec n le numéro du graphe que vous voulez tester, par exemple pour tester le graphe graph/graph104.alists il suffit de faire make test4.

Pour tester un graphe aléatoire de 100 sommets avec une probabilité de 0.3 d’existence d’arc il faut utiliser la commande make testRandom.

Enfin pour tout tester, exécutez la commande make testAll.

Compétences acquises

• Choisir ou spécifier un type de données abstrait pour résoudre un problème particulier
• Implémenter des types de données abstraits à partir de structures de données classiques
• Utiliser les graphes pour modéliser des problèmes combinatoires ou d'optimisation
• Appliquer des algorithmes classiques en dehors de leur contexte habituel

Résultat

Nous avons obtenu la note de 12/20.

English

Presentation

This project was done in the fourth year of the CMI Informatique at the UFR SFA Université de Poitiers as part of the Advanced Algorithmics course.

This project was developed in monome with Visual Studio Code.

Use

To compile the project, you can use the Makefile.

The command make help allows you to see the different possible commands.

To test one of the graphs in the graph folder, you need to enter the command make test<n> with n the number of the graph you want to test, e.g. to test the graph/graph104.alists just do make test4.

To test a random graph of 100 vertices with a probability of 0.3 of arc existence you have to use the command make testRandom.

Finally, to test everything, run the command make testAll.

Skills acquired

• Choose or specify an abstract data type to solve a particular problem
• Implement abstract data types from classical data structures
• Use graphs to model combinatorial or optimization problems
• Apply classical algorithms outside their usual context

Result

We obtained a score of 12/20.