Cette application est faite pour rendre votre vie plus facile lorsque vous traitez des graph et des algorithmes sur des graphs, il couvre une variété d’algorithmes tels que BFS DFS Dijkstra Prime Kosaraju bellman-ford, et il vous donne le résultat d’un algorithme sur un graph sous forme d’un grpah
Cette application est une application web réalisée avec l’architecture REST ( client ,serveur) avec Flask (Python) + Networkx (pour la gestion des graphs)+ Matplotlib(Dessin des graphs) en back end et NextJs + React +TypeScript + Regex (valider l’entrée utilisateur) + React Query (gestion de l’état de l’application) pour le front end et le docker pour le déploiement
git clone https://github.com/sohaibMan/GraphTheory.git
cd GraphTheory
####################################
## for docker users
####################################
docker compose up
## to stop it
docker compose down
## to build it
docker compose up --build
####################################
## to runt locally without docker(if you don't have docker installed)
####################################
## install the dependencies (front end)
cd nextjs && npm i
## install the dependencies (backend end)
cd ../flask && pip3 install -r requirements.txt
## note if u run on linux you need to give the app permission to write and read and delete to tmp_output folder if needed
chmod 770 tmp_output
## run the back end
python3 server.py
## run the front end
cd ../next && npm run dev
## now open http:https://localhost:3000 in your browser
Cette application est conviviale et très simple à utiliser , il suffit de suivre ces étapes pour l’utiliser
1- Dessiner pour voir votre graphique
vous avez cette zone de texte pour taper vos bords et nœuds de graphique dans ce format
noeud arête le poids (poids est facultatif)
Example :
- A B 2 sera interprété comme on a 2 noeuds A et B et un arrete A→ B de poids 2 (avec ordre)
-
1
2
3
sera interprété comma on a 3 noeuds 1 2 3
2- choisir un algorithme pour l’appliquer et saisir les valeurs requises
Astuces:
- Pour Changer l’orientation du graph clicker sur l’un des buttons:
- si le graph n’est pas bien dessiné, vous pouvez le redessiner à l’aide de ce bouton
Definition: L’algorithme de Dijkstra est un algorithme pour trouver les chemins les plus courts entre les nœuds dans un graphique pondéré
Les Etapes :
- Représentation graphique sous forme d'une liste
Notes : Nous supposons que le nœud A est 1 B est 2 et vice versa
A B 7
A C 1
B D 4
B F 1
C B 5
C E 2
C F 7
E D 5
E B 2
F E 3
L’interface
- le choix d’un nœud de départ et noe d'extrémité
Exemple: A,D
Explication:
- le chemin le plus court entre A et D est A→C→E→D avec le cout total 8
Exemple: E,F
Explication:
- le chemin le plus court entre E et F est E→B→F avec le cout total 3
Exemple : D,A
Explication:
- il ya pas de chmen entre D et A
pronouns par exemple le graph suivante: (graph simple orienté pondéré)
A B
B C
B D
A D
D E
B E
C A
Exemple BFS a partier de A
Exemple BFS a partier de E
Exemple DFS a partier de D
Exemple DFS a partier de C
pronouns par exemple le graph suivante: (graph simple not orienté pondéré)
6 1 10
1 2 28
2 3 16
3 4 12
4 5 22
5 6 24
4 7 18
5 7 24
7 2 14
Explication: en arrière-plan, l’algorithme fait les prochaines étapes
Explication:
Example :
0 1 1
0 2 4
1 4 7
1 3 2
1 2 -2
2 3 3
3 4 4
4 5 7
5 3 -3
source=0
Explication: