CXXGraph
v4.1.0
CXXGraph est une bibliothèque C++ complète qui gère les algorithmes graphiques. Cette bibliothèque d'en-tête uniquement sert d'alternative à la bibliothèque Boost Graph (BGL).
Nous recherchons :
Si vous êtes intéressé, veuillez nous contacter à [email protected] ou contribuer à ce projet. Nous vous attendons !
| Complété | Description | Date d'achèvement |
|---|---|---|
| ✔️ | Version 0.4.0 | 7 octobre 2022 |
| ✔️ | Version 0.5.0 | 23 mars 2023 |
| ✔️ | Première version stable 1.0.0 | 28 mars 2023 |
| ✔️ | Version 1.0.1 | 7 mai 2023 |
| ✔️ | Version 1.1.0 | 8 mai 2023 |
| ✔️ | Version stable 2.0.0 | 1 juin 2023 |
| ✔️ | Version stable 3.0.0 | 3 novembre 2023 |
| ✔️ | Version 3.1.0 | 9 janvier 2023 |
| Présenter l'hypergraphe #122 | À déterminer | |
| Version stable 4.0.0 | À déterminer |
Pour installer sur des systèmes Unix/Linux, exécutez ce qui suit à partir de la ligne de commande :
$ sudo tar xjf CXXGraph-{version}.tar.bz2
Pour désinstaller :
$ sudo rm -f /usr/include/Graph.hpp /usr/include/CXXGraph*
Pour installer sur les systèmes Fedora/CentOS/RedHat, exécutez ce qui suit à partir de la ligne de commande :
$ sudo rpm -ivh CXXGraph-{version}.noarch.rpm
Pour désinstaller :
$ sudo rpm -e CXXGraph-{version}
Pour installer sur les systèmes Debian/Ubuntu, exécutez ce qui suit à partir de la ligne de commande :
$ sudo dpkg -i CXXGraph_{version}.deb
Pour désinstaller :
$ sudo apt-get remove CXXGraph
Pour les installations autocompilées à l'aide de CMake, exécutez ce qui suit à partir de la ligne de commande une fois la compilation terminée :
$ sudo make install
L'explication des classes peut être trouvée dans la section Classes de la documentation Doxygen.
Pour utiliser la bibliothèque, placez simplement le fichier d'en-tête là où vous en avez besoin. C'est aussi simple que ça !
Travaux en cours
Le test unitaire nécessite CMake 3.9 et versions ultérieures, ainsi que la bibliothèque GoogleTest .
GoogleTest
git clone https://github.com/google/googletest.git
cd googletest # Main directory of the cloned repository
mkdir -p build # Create a directory to hold the build output
cd build
cmake .. # Generate native build scripts for GoogleTest
make # Compile
sudo make install # Install in /usr/local/ by defaultDepuis le répertoire de base :
mkdir -p build # Create a directory to hold the build output
cd build # Enter the build folder
cmake -DTEST=ON .. # Generate native build scripts for GoogleTest,
make # CompileUne fois le build compilé, exécutez l'exécutable "test_exe" dans le répertoire "build" avec la commande suivante :
./test_exe
Le Benchmark nécessite CMake 3.9 et versions ultérieures, la bibliothèque GoogleTest et la bibliothèque Google Benchmark .
Référence Google
# Check out the library
$ git clone https://github.com/google/benchmark.git
# Google Benchmark requires GoogleTest as a dependency. Add the source tree as a subdirectory
$ git clone https://github.com/google/googletest.git benchmark/googletest
# Go to the library's root directory
$ cd benchmark
# Make a build directory to place the build output
$ cmake -E make_directory " build "
# Generate the build system files with CMake
$ cmake -E chdir " build " cmake -DCMAKE_BUILD_TYPE=Release ../
# If starting with CMake 3.13, you can use the following:
# cmake -DCMAKE_BUILD_TYPE=Release -S . -B "build"
# Build the library
$ cmake --build " build " --config Release
# Install the library
$ sudo cmake --build " build " --config Release --target installDepuis le répertoire de base :
mkdir -p build # Create a directory to hold the build output
cd build # Enter the build folder
cmake -DBENCHMARK=ON .. # Generate native build scripts for Google Benchmark
make # CompileUne fois le build compilé, exécutez l'exécutable "benchmark" dans le répertoire "build" avec la commande suivante :
./benchmark
Vous pouvez vérifier le résultat du benchmark en utilisant ce lien.
Pour créer un package tarball, exécutez ce qui suit à partir de la ligne de commande :
# Enter Packaging Directory
$ cd packaging
# Execute the script to generate tarballs
$ ./tarballs.shPour créer un package RPM, exécutez ce qui suit à partir de la ligne de commande :
# Enter Packaging Directory
$ cd packaging/rpm
# Execute the script to generate tarballs
$ ./make_rpm.shPour créer un package deb, exécutez ce qui suit à partir de la ligne de commande :
# Enter Packaging Directory
$ cd packaging/deb
# Execute the script to generate tarballs
$ ./make_deb.shGraphique Algorithme de chemin le plus court de Dijkstras (Le chemin le plus court de Dijkstra) [Algorithme de Dijkstra] (https://www.interviewbit.com/blog/find-shortest-path-dijkstras-algorithm/) est utilisé pour trouver le chemin le plus court d'un nœud source à tous les autres nœuds accessibles dans le graphique. L'algorithme suppose initialement que tous les nœuds sont inaccessibles à partir du nœud source donné, nous marquons donc les distances de tous les nœuds comme étant infinies. (infini) à partir du nœud source (INF / infini signifie impossible à atteindre).
Spécialisation en cadran de l'algorithme de Dijkstra.
Lorsque les poids des bords sont de petits entiers (limités par un paramètre C ), des files d'attente spécialisées qui profitent de ce fait peuvent être utilisées pour accélérer l'algorithme de Dijkstra. Le premier algorithme de ce type était l'algorithme de Dial (Dial 1969) pour les graphiques avec des poids de bord entiers positifs, qui utilise une file d'attente de compartiments pour obtenir un temps d'exécution O(|E|+|V|C) .(source wikipedia)
Vous trouverez ci-dessous l'algorithme complet :
Sur ce lien, vous pouvez trouver des illustrations étape par étape.
L'algorithme de Prim L'algorithme de Prim est un algorithme glouton qui trouve un arbre couvrant minimum pour un graphe non orienté pondéré. Cela signifie qu'il trouve un sous-ensemble d'arêtes qui forme un arbre incluant chaque sommet, où le poids total de toutes les arêtes de l'arbre est minimisé. L'algorithme fonctionne en construisant cet arbre un sommet à la fois, à partir d'un sommet de départ arbitraire, en ajoutant à chaque étape la connexion la moins chère possible de l'arbre à un autre sommet.
Mesures:
(Breadth First Search) Algorithme de recherche en largeur d'abord (Breadth First Search) Breadth First Search , également cité sous le nom de BFS , est un algorithme de traversée graphique. Complexité temporelle O(|V| + |E|) où V est le nombre de sommets et E est le nombre d'arêtes du graphe. Les applications de Breadth First Search sont :
Et il y en a bien d'autres...
(Recherche en profondeur d'abord) Algorithme de recherche en profondeur en premier (Recherche en profondeur en premier) La recherche en profondeur en premier , également citée sous le nom de DFS , est un algorithme de traversée graphique. Complexité temporelle O(|V| + |E|) où V est le nombre de sommets et E est le nombre d'arêtes du graphique. Les applications de la recherche en profondeur d'abord sont :
Et il y en a bien d'autres...
Best First Search Best First Search est une classe d'algorithmes de recherche qui parcourt le graphe en explorant le nœud le plus prometteur choisi selon une fonction d'évaluation. La complexité temporelle dans le pire des cas est O(n * log n) où n est le nombre de nœuds dans le graphique.
Cycle (théorie des graphes)
L'existence d'un cycle dans les graphes orientés et non orientés peut être déterminée par le fait que la recherche en profondeur d'abord (DFS) trouve une arête qui pointe vers un ancêtre du sommet actuel (elle contient une arête arrière). Tous les bords arrière que DFS ignore font partie des cycles. Dans un graphe non orienté, l'arête menant au parent d'un nœud ne doit pas être comptée comme une arête arrière, mais la recherche de tout autre sommet déjà visité indiquera une arête arrière. Dans le cas de graphes non orientés, seul un temps O(n) est nécessaire pour trouver un cycle dans un graphe à n sommets, puisqu'au plus n − 1 arêtes peuvent être des arêtes d'arbre.
De nombreux algorithmes de tri topologique détecteront également les cycles, car ceux-ci constituent des obstacles à l'existence de l'ordre topologique. De plus, si un graphe orienté a été divisé en composantes fortement connectées, les cycles n'existent qu'à l'intérieur des composantes et non entre elles, puisque les cycles sont fortement connectés.
Pour les graphiques orientés, des algorithmes basés sur des messages distribués peuvent être utilisés. Ces algorithmes reposent sur l’idée qu’un message envoyé par un sommet dans un cycle reviendra à lui-même. Les algorithmes de détection de cycle distribué sont utiles pour traiter des graphiques à grande échelle à l'aide d'un système de traitement de graphiques distribué sur un cluster d'ordinateurs (ou superordinateur).
Les applications de la détection de cycle incluent l'utilisation de graphiques d'attente pour détecter les blocages dans les systèmes concurrents.
L'algorithme Bellman-Ford peut être utilisé pour trouver la distance la plus courte entre une source et un nœud cible. Complexité temporelle O(|V| . |E|) où V est le nombre de sommets et E est le nombre d'arêtes du graphe qui est supérieur à l'algorithme du chemin le plus court de Dijkstra. La complexité temporelle de l'algorithme de Dijkstra est O(|E| + |V| log |v| ). L'avantage de Bellman-ford par rapport à Dijkstra est qu'il peut gérer des graphiques avec des poids de bord négatifs. De plus, si le graphique contient un cycle de poids négatif, l'algorithme peut détecter et signaler la présence d'un cycle négatif.
Cette vidéo donne un bon aperçu de la mise en œuvre de l'algorithme. Cette conférence du MIT donne une preuve de l'exactitude de Bellman-Ford et de sa capacité à détecter les cycles négatifs. Applications :
Algorithme Floyd Warshall
Nous initialisons la matrice de solution de la même manière que la matrice du graphique d'entrée dans un premier temps. Ensuite, nous mettons à jour la matrice de solution en considérant tous les sommets comme sommets intermédiaires. L'idée est de sélectionner un par un tous les sommets et de mettre à jour tous les chemins les plus courts qui incluent le sommet sélectionné comme sommet intermédiaire dans le chemin le plus court. Lorsque nous choisissons le sommet numéro k comme sommet intermédiaire, nous avons déjà considéré les sommets {0, 1, 2, .. k-1} comme sommets intermédiaires. Pour chaque paire (i, j) de sommets source et destination respectivement, il existe deux cas possibles.
Réduction transitive
Cet algorithme est utilisé pour construire un graphe orienté avec la même accessibilité et satisfait à la fermeture transitive, avec le moins d'arêtes possible. Plus concrètement, il crée un graphe équivalent minimum avec le moins d'arêtes possible, supprimant les chemins de « court-circuit » à travers le graphe.
Cela se fait en parcourant chaque paire de nœuds, en vérifiant s'il existe deux bords qui sortent du premier nœud OU du dernier nœud, en supprimant le bord de la paire de nœuds s'il existe.
En pseudocode : foreach x dans graph.vertices foreach y dans graph.vertices foreach z dans graph.vertices supprimer l'arête xz si les arêtes xy et yz existent
Notre implémentation a des portes if qui vérifient précocement les bords à plusieurs endroits, ce qui lui donne un temps d'exécution légèrement plus rapide que le pseudocode cubique ici.
L'algorithme Kruskal peut être utilisé pour trouver la forêt couvrante minimale d'un graphe non orienté pondéré par les bords. Complexité temporelle O(E log E) = O(E log V) où V est le nombre de sommets et E est le nombre d'arêtes du graphique. La principale limitation de vitesse de cet algorithme est le tri des bords.
Pour une compréhension rapide de la procédure de l'algorithme, regardez cette vidéo. Certaines des applications réelles sont :
D'autres algorithmes pour trouver la forêt couvrante minimale sont l'algorithme de Prim ou l'algorithme de Borůvka.
L'algorithme de Borůvka est un algorithme glouton qui peut être utilisé pour trouver un arbre couvrant minimum dans un graphe, ou une forêt couvrant minimale dans le cas d'un graphe qui n'est pas connecté.
L'algorithme commence par trouver l'arête de poids minimum incident à chaque sommet du graphique et par ajouter toutes ces arêtes à la forêt. Ensuite, il répète un processus similaire consistant à trouver la lisière de poids minimum de chaque arbre construit jusqu'à présent vers un arbre différent, et à ajouter toutes ces lisières à la forêt. Chaque répétition de ce processus réduit le nombre d'arbres, dans chaque composant connecté du graphique, à au plus la moitié de cette ancienne valeur, donc après de nombreuses répétitions logarithmiques, le processus se termine. Lorsque c’est le cas, l’ensemble des arêtes qu’il a ajoutées forme la forêt couvrante minimale.
On peut montrer que l'algorithme de Borůvka prend O (log V) itérations de la boucle externe jusqu'à ce qu'elle se termine, et donc s'exécute dans le temps O (E log V), où E est le nombre d'arêtes et V est le nombre de sommets dans G (en supposant E ≥ V).
Définition mathématique du problème : Soit G l'ensemble des nœuds d'un graphe et n un nœud donné de cet ensemble. Soit C le sous-ensemble non strict de G contenant à la fois n et tous les nœuds accessibles depuis n, et soit C' son complément. Il existe un troisième ensemble M, qui est le sous-ensemble non strict de C contenant tous les nœuds accessibles depuis n'importe quel nœud de C'. Le problème consiste à trouver tous les nœuds qui appartiennent à C mais pas à M.
Algorithme actuellement implémenté :
Application:
Cet algorithme est utilisé dans les systèmes de récupération de place pour décider quels autres objets doivent être libérés, étant donné qu'un objet est sur le point d'être libéré.
L'algorithme Ford-Fulkerson est un algorithme glouton permettant de trouver un débit maximum dans un réseau de flux. L'idée derrière l'algorithme est la suivante : tant qu'il existe un chemin depuis la source (nœud de départ) jusqu'au récepteur (nœud de fin), avec une capacité disponible sur tous les bords du chemin, nous envoyons le flux le long de l'un des chemins. Ensuite, nous trouvons un autre chemin, et ainsi de suite. Un chemin avec une capacité disponible est appelé chemin d'augmentation.
L'algorithme de Kosaraju est un algorithme temporel linéaire permettant de trouver les composantes fortement connectées d'un graphe orienté. Il est basé sur l'idée que si l'on est capable d'atteindre un sommet v à partir du sommet u, alors on devrait pouvoir atteindre le sommet u à partir du sommet v et si tel est le cas, on peut dire que les sommets u et v sont fortement connectés - ils sont dans un sous-graphe fortement connecté. Voici un exemple :
1). Créez une pile vide 'S' et effectuez un parcours DFS d'un graphique. Dans le parcours DFS, après avoir appelé DFS récursif pour les sommets adjacents d'un sommet, poussez le sommet pour l'empiler. 2). Inversez les directions de tous les arcs pour obtenir le graphique de transposition. 3). Un par un, faites sortir un sommet de S alors que S n'est pas vide. Laissez le sommet éclaté être « v ». Prenez v comme source et effectuez DFS (appelez DFSUtil(v)). Le DFS à partir de v imprime le composant fortement connecté de v.
L'algorithme de Kahn trouve un ordre topologique en supprimant de manière itérative les nœuds du graphe qui n'ont pas d'arêtes entrantes. Lorsqu'un nœud est supprimé du graphique, il est ajouté à l'ordre topologique et toutes ses arêtes sont supprimées, ce qui permet de sélectionner l'ensemble de nœuds suivant sans arête entrante.
L'algorithme Welsh Powell Coloring est un algorithme gourmand de coloration des sommets. Cet algorithme est également utilisé pour trouver le numéro chromatique d'un graphique.
L'algorithme Welsh Powell comprend les étapes suivantes :
L'algorithme renvoie un résultat std::map<Node, int> qui attribue à chaque nœud une couleur classée par nombres entiers. Les utilisateurs peuvent également interroger l'ordre chromatique minimum du graphique en interrogeant la valeur la plus élevée de la carte résultante.
std::map<Node, int > result = graph.welshPowellColoring();
auto chromatic_color = std::max_element(result.begin(), result.end(),
[]( const auto & lhs, const auto & rhs) {
return lhs. second < rhs. second ;
}La coloration minimale part de 1 au lieu de 0.
L'algorithme suppose que le graphique n'est pas orienté. Toutes les sources et inspirations sont liées dans la déclaration de l’algorithme et des cas de tests.
Un partitionnement par sommets divise les arêtes d'un graphe en partitions de taille égale. Les sommets qui contiennent les extrémités d’une arête sont également placés dans la même partition que l’arête elle-même. Cependant, les sommets ne sont pas uniques entre les partitions et peuvent devoir être répliqués (coupés), en raison de la répartition de leurs arêtes sur les différentes partitions.
Le facteur de réplication quantifie le nombre de sommets répliqués sur les ordinateurs par rapport au nombre de sommets du graphe d'entrée d'origine.
Cet algorithme est une simple coupe de sommets à la manière d'un round-robin. Il prend les bords du graphique d'origine et les attribue aux partitions, en les divisant en tailles égales (ou similaires). Cet algorithme ne s'occupe pas de l'optimisation de la réplication des sommets (Replication Factor) mais équilibre uniquement les bords dans les partitions.
Les algorithmes de partitionnement gourmands utilisent l’intégralité de l’historique des affectations de bords pour prendre la décision suivante. L'algorithme stocke l'ensemble des partitions A(v) auxquelles chaque sommet v déjà observé a été attribué ainsi que les tailles de partition actuelles. Lors du traitement de l'arête e ∈ E reliant les sommets vi, vj ∈ V , l'algorithme glouton suit cet ensemble simple de règles :
L'algorithme HDRF (High Degree (sont) répliqués en premier) est un algorithme glouton de coupe de sommets tel que décrit dans cet article. Cet algorithme tente d'optimiser le facteur de réplication en utilisant l'historique des affectations d'arêtes et le degré de sommet incrémentiel. Avec une fonction qui prend en compte ces deux facteurs, calculez la meilleure partition pour attribuer le bord analysé. Les répliques créées sont basées sur le degré des sommets, et les sommets répliqués sont probablement ce qu'on appelle un "Hub-Node", qui sont les sommets de degré le plus élevé.
La coupe de sommet efficace et équilibrée (EBV) est un algorithme de coupe de sommet hors ligne tel que décrit dans cet article. Cet algorithme tente d'équilibrer les partitions en fonction du nombre d'arêtes et de sommets de chaque partition et du facteur de réplication. Il applique une formule pour évaluer la partition dans laquelle attribue l'arête qui prend également en compte le nombre total d'arêtes et de sommets du graphe. La formule d'évaluation est la suivante :
La valeur la plus basse est prise comme identifiant de partition.
La matrice de degrés est une matrice carrée qui fournit des informations sur la connectivité des nœuds dans un graphique. Pour les graphes orientés, il reflète le nombre d'arêtes entrantes et sortantes pour chaque nœud, tandis que pour les graphes non orientés, il représente le nombre d'arêtes incidents à chaque nœud.
La matrice laplacienne est une matrice carrée dérivée de la matrice de contiguïté et de la matrice de degrés d'un graphe. Il joue un rôle déterminant dans l'analyse de diverses propriétés du graphique, telles que la connectivité, le nombre d'arbres couvrant et d'autres caractéristiques spectrales.
La matrice de transition est couramment utilisée dans l'étude des chaînes de Markov et des processus stochastiques. Dans le contexte d'un graphique, il désigne les probabilités de transition d'un nœud à un autre, souvent basées sur des poids de bord ou des critères prédéterminés. Cette matrice trouve des applications dans divers domaines tels que l'analyse de réseau, l'apprentissage automatique et l'optimisation.
Si vous souhaitez apporter votre soutien, vous pouvez créer une pull request ou signaler un problème . Si vous souhaitez modifier le code, résoudre un problème ou implémenter une nouvelle fonctionnalité, veuillez lire notre guide de CONTRIBUTION.
Si vous souhaitez discuter de nouvelles fonctionnalités ou si vous avez des questions ou des suggestions sur la bibliothèque, veuillez ouvrir une discussion ou simplement discuter sur
Site CXXGraph
E-mail : [email protected]
Profil GitHub
Pour me soutenir, ajoutez une étoile au projet ou suivez-moi
Pour rester à jour, regardez le projet
Nous sommes référencés par :
Merci à la communauté de TheAlgorithms pour quelques inspirations algorithmiques.
Merci à GeeksForGeeks pour une inspiration d'algorithme.
Merci à toutes les personnes qui ont déjà contribué à CXXGraph !
Si vous utilisez ce logiciel, veuillez suivre les instructions de CITATION. Merci!
Nous avons participé au Hacktoberfest 2021. Merci à tous les contributeurs !
Nous avons participé au Hacktoberfest 2022. Merci à tous les contributeurs !
Nous avons participé au Hacktoberfest 2023. Merci à tous les contributeurs !
Afficher la valeur estimée du projet
@ZigRazor |
|---|
