summaryrefslogtreecommitdiff
path: root/macros/latex/contrib/dijkstra
diff options
context:
space:
mode:
authorNorbert Preining <norbert@preining.info>2020-06-25 03:02:38 +0000
committerNorbert Preining <norbert@preining.info>2020-06-25 03:02:38 +0000
commitea55d28ebb1c0142549c51d9de0cd52745becc06 (patch)
tree5e6215ad517921cad501658823686903598f2f34 /macros/latex/contrib/dijkstra
parentf566a9b0d006a4d1aaa8501e771f6a5b7a55f9fe (diff)
CTAN sync 202006250302
Diffstat (limited to 'macros/latex/contrib/dijkstra')
-rw-r--r--macros/latex/contrib/dijkstra/README4
-rw-r--r--macros/latex/contrib/dijkstra/dijkstra-fr.pdfbin370577 -> 369070 bytes
-rw-r--r--macros/latex/contrib/dijkstra/dijkstra-fr.tex32
-rw-r--r--macros/latex/contrib/dijkstra/dijkstra.sty336
4 files changed, 203 insertions, 169 deletions
diff --git a/macros/latex/contrib/dijkstra/README b/macros/latex/contrib/dijkstra/README
index c619266cd5..f49d8f82cf 100644
--- a/macros/latex/contrib/dijkstra/README
+++ b/macros/latex/contrib/dijkstra/README
@@ -3,9 +3,9 @@ ___________________________________
L'extension
dijkstra
- v0.11
+ v0.12
- 9 sptembre 2017
+ 25 juin 2020
___________________________________
Authors : Christian Tellechea
diff --git a/macros/latex/contrib/dijkstra/dijkstra-fr.pdf b/macros/latex/contrib/dijkstra/dijkstra-fr.pdf
index c30674325d..84308d0026 100644
--- a/macros/latex/contrib/dijkstra/dijkstra-fr.pdf
+++ b/macros/latex/contrib/dijkstra/dijkstra-fr.pdf
Binary files differ
diff --git a/macros/latex/contrib/dijkstra/dijkstra-fr.tex b/macros/latex/contrib/dijkstra/dijkstra-fr.tex
index 1fc90dc173..ec76559db9 100644
--- a/macros/latex/contrib/dijkstra/dijkstra-fr.tex
+++ b/macros/latex/contrib/dijkstra/dijkstra-fr.tex
@@ -5,7 +5,7 @@
\documentclass[french,a4paper,10pt]{article}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
-\usepackage[margin=2cm]{geometry}
+\usepackage[margin=1cm]{geometry}
\usepackage[bottom]{footmisc}
\usepackage{libertine,boites,tikz,enumitem,MnSymbol,babel,xspace,listings,dijkstra}
\usetikzlibrary{arrows.meta}
@@ -62,7 +62,7 @@
\exemple@@
}
-\newcommand\exemple@@[2][37]{%
+\newcommand\exemple@@[2][30]{%
\xdef\@hparta{0.#1\linewidth}\xdef\@hpartb{0.\number\numexpr95-#1\relax\linewidth}%
\def\@tempa##1#2{\exemple@@@{##1}}%
\@tempa
@@ -84,7 +84,7 @@
\kern.5ex\relax
\leavevmode$\vcenter{\hsize=\@hparta\relax
\ttfamily\small\the@code\par}$%
- \hfill
+ \hfill\vrule\hfill
$\vcenter{\hsize=\@hpartb\relax
\newlinechar`\^^M\everyeof{\noexpand}\scantokens{#1}\par}$%
\endbreakbox
@@ -169,7 +169,7 @@ Dans le graphe \emph{non orienté} suivant, quel est le plus court chemin pour al
\end{center}
\paragraph{Lire le graphe}
-Pour trouver le plus court chemin pour aller de A à F, il faut d'abord lire le graphe. Comme il est fréquent que les graphes sont peu peuplés, j'ai pris le parti de définir un graphe par une liste d'adjacence. Ainsi, la macro \verb|\readgraph|, qui va lire le graphe, admet comme argument obligatoire une liste d'adjacence :
+Pour trouver le plus court chemin pour aller de A à F, il faut d'abord lire le graphe. Comme il est fréquent que les graphes soient peu peuplés, j'ai pris le parti de définir un graphe par une liste d'adjacence. Ainsi, la macro \verb|\readgraph|, qui va lire le graphe, admet comme argument obligatoire une liste d'adjacence :
\code/\readgraph{
A [B=7, D=15],
@@ -179,7 +179,7 @@ Pour trouver le plus court chemin pour aller de A à F, il faut d'abord lire le g
E [F=14]
}/
-Les espaces sont ignorés de part et d'autre des noms des sommets, des crochets (ouvrants et fermants), des signes «\verb/=/» et des virgules. Ainsi, ce n'est que dans les noms des sommets que les espaces ne sont pas ignorés : par exemple, le sommet «\verb*|A 1|» est distinct du sommet «\verb*|A1|».
+Les espaces sont ignorés de part et d'autre des noms des sommets, des crochets (ouvrants et fermants), des signes «\verb/=/» et des virgules. Ainsi, ce n'est que dans les noms des sommets que les espaces ne sont pas ignorés : par exemple, le sommet «\verb|A 1|» est distinct du sommet «\verb*|A1|».
\paragraph{Conditions sur les distances}
Les distances entre sommets \emph{doivent} être positives, c'est une limitation intrinsèque à l'algorithme de Dijkstra pour qu'il fonctionne sans erreur. La méthode de programmation utilisée dans cette extension exige de plus que ces distances soient des nombres \emph{entiers}.\medbreak
@@ -195,7 +195,7 @@ F [B=16, C=3, E=14]/
Par conséquent, la liste d'adjacence entrée par l'utilisateur ne doit pas contenir d'incohérence. Si l'on spécifie la distance entre un sommet A et un sommet B par \verb|A[B=<x>,...]| on peut s'économiser la peine de spécifier cette même distance entre B et A puisque c'est fait par l'extension \DIJK automatiquement. En revanche, une erreur sera émise si dans la liste d'adjacence, on trouve \verb|A[B=<x>,...]| puis \verb|B[A=<y>,...]| où \verb-<y>- et \verb-<x>- sont différents.
\paragraph{Lancer l'algorithme}
-Une fois que le graphe est lu par la macro \verb|\readgraph|, on peut lancer l'algorithme avec la macro \verb|\dijkstra{<A>}{<B>}| où \verb-<A>- et \verb-<B>- sont deux sommets du graphe. La distance minimale entre ces deux sommets est stockée dans la macro \verb|\dijkdist| et le chemin correspondant dans \verb|\dijkpath|.
+Une fois que le graphe est lu par la macro \verb|\readgraph|, on lance l'algorithme avec \verb|\dijkstra{<A>}{<B>}| où \verb-<A>- et \verb-<B>- sont deux sommets du graphe. La distance minimale entre ces deux sommets est stockée dans la macro \verb|\dijkdist| et le chemin correspondant dans \verb|\dijkpath|.
\exemple|\readgraph{
A [B=7, D=15],
@@ -207,9 +207,9 @@ Tableau : \dijkstra{A}{F}\par
Distance A-F = \dijkdist\par
Chemin = \dijkpath|
-Dans le tableau, les colonnes sont disposées dans le \emph{même ordre} que celui des sommets dans la liste d'adjacence lue par \verb|readgraph|.
+Dans le tableau, les colonnes sont disposées dans le \emph{même ordre} que celui des sommets dans la liste d'adjacence lue par \verb|\readgraph|.
-\section{Graphe non orienté}
+\section{Graphe orienté}
Pour spécifier à \verb|\readgraph| que la liste d'adjacence est celle d'un graphe \emph{orienté}, la macro doit être suivie d'une étoile.
\begin{center}
@@ -266,11 +266,13 @@ On peut également régler des \verb|<paramètres>| pour toutes les exécutions de l
\begin{center}
\verb|\setdijk{<paramètres>}|
\end{center}
-mais aussi modifier des \verb|<paramètres>| \emph{par défaut} avec
+mais aussi modifier des \verb|<paramètres>| \emph{par défaut} avec
\begin{center}
\verb|\setdijkdefault{<paramètres>}|
\end{center}
+Pour réinitialiser toutes les \verb|<clés>| à leur \verb|<valeur>| par défaut, il faut exécuter la macro \verb|\initdijk|.\medbreak
+
Voici toutes les \verb|<clés>|, leur \verb|<valeur>| par défaut et leur description.
\cleval{show-tab}{booléen}
@@ -362,7 +364,9 @@ ce qui a pour effet de mettre le sommet de provenance en indice de la distance.
Tableau : \dijkstra{A}{F}|
\paragraph{Mise en évidence du sommet fixé}
-Le premier sommet fixé est celui de départ et sa distance est toujours 0. La macro \verb|\highlightfistnode| prend comme argument la distance (qui est 0) et le traite pour effectuer sa mise en forme. Sa définition par défaut, qui compose cette distance en gras, est :
+Le premier sommet fixé est celui de départ et sa distance est toujours 0.
+
+La macro \verb|\highlightfistnode| prend comme argument la distance (qui est 0) et le traite pour effectuer sa mise en forme. Sa définition par défaut, qui compose cette distance en gras, est :
\code|\newcommand*\highlightfirstnode[1]{$\mathbf{#1}$}|
@@ -393,14 +397,6 @@ Pour obtenir d'autre effets, on peut redéfinir ces macros. L'exemple donné n'est
E [F=14]}
Tableau : \dijkstra{A}{F}|
-\section{Historique des versions}
-Merci d'envoyer \emph{via} email tout bug, dysfonctionnement, erreur ou demande de fonctionnalité à \verb|unbonpetit@netc.fr|
-
-\paragraph{v0.1\quad 06/09/2017} Première version.
-\paragraph{v0.2\quad 10/09/2017} Retrait d'un \verb|\show| dans le code, laissé par oubli après les phases de débogage.
-
-Nettoyage du code.
-
\section{Code}
Le code ci-dessous est l'exact verbatim du fichier \verb|dijkstra.sty| :
diff --git a/macros/latex/contrib/dijkstra/dijkstra.sty b/macros/latex/contrib/dijkstra/dijkstra.sty
index a1e8872804..b8c673449e 100644
--- a/macros/latex/contrib/dijkstra/dijkstra.sty
+++ b/macros/latex/contrib/dijkstra/dijkstra.sty
@@ -4,15 +4,15 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% %
\def\dijkname {dijkstra} %
-\def\dijkver {0.11} %
+\def\dijkver {0.12} %
% %
-\def\dijkdate {2017/09/09} %
+\def\dijkdate {2020/06/25} %
% %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% --------------------------------------------------------------------
% This work may be distributed and/or modified under the
-% conditions of the LaTeX Project Public License, either version 1.3
+% conditions of the LaTeX Project Public License, either version 1.3c
% of this license or (at your option) any later version.
% The latest version of this license is in
%
@@ -24,11 +24,10 @@
% This work has the LPPL maintenance status `maintained'.
%
% The Current Maintainer of this work is Christian Tellechea
-% Copyright : Christian Tellechea 2017
+% Copyright : Christian Tellechea 2017-2020
% email: unbonpetit@netc.fr
% Commentaires, suggestions et signalement de bugs bienvenus !
% Comments, bug reports and suggestions are welcome.
-% Copyright: Christian Tellechea 2017
% --------------------------------------------------------------------
% L'extension dijkstra est composée des 4 fichiers suivants :
% - code : dijkstra.sty
@@ -36,6 +35,8 @@
% - fichier lisezmoi : README
% --------------------------------------------------------------------
%
+\csname dijkloadonce\endcsname
+\let\dijkloadonce\endinput
\NeedsTeXFormat{LaTeX2e}
\ProvidesPackage{dijkstra}[\dijkdate\space v\dijkver\space Dijkstra Algorithm (CT)]
\RequirePackage{simplekv}
@@ -59,6 +60,15 @@
\def\dijk_swapargs#1#2#3{#1{#3}{#2}}
\def\dijk_ifstar#1#2{\def\dijk_ifstar_i{\skv_ifx{*\dijk_nxttok}{\skv_first{#1}}{#2}}\futurelet\dijk_nxttok\dijk_ifstar_i}
\def\dijk_ifopt#1#2{\def\dijk_ifopt_i{\skv_ifx{[\dijk_nxttok}{#1}{#2}}\futurelet\dijk_nxttok\dijk_ifopt_i}
+\def\dijk_stripsp#1%
+{%
+ \long\def\dijk_stripsp##1{\expanded{\dijk_stripsp_i\_marksp##1\__nil\_marksp#1\_marksp\_nil}}%
+ \long\def\dijk_stripsp_i##1\_marksp#1##2\_marksp##3\_nil{\dijk_stripsp_ii##3##1##2\__nil#1\__nil\_nil}%
+ \long\def\dijk_stripsp_ii##1#1\__nil##2\_nil{\dijk_stripsp_iii##1##2\_nil}%
+ \long\def\dijk_stripsp_iii##1##2\__nil##3\_nil{\unexpanded{##2}}%
+}
+\dijk_stripsp{ }
+
\def\dijk_foreach#1\in#2#3%
{%
@@ -73,11 +83,12 @@
{%
\def#1{#2}%
\skv_ifx{\dijk_quark#1}
- {}
- {%
- \skv_ifx{#1\empty}{}{\csname dijk_loopcode_\number\dijk_nest\endcsname}%
- \dijk_foreach_i#1%
- }%
+ {%
+ }
+ {%
+ \skv_ifx{#1\empty}{}{\csname dijk_loopcode_\number\dijk_nest\endcsname}%
+ \dijk_foreach_i#1%
+ }%
}%
\def\dijk_ifinst#1#2%
@@ -99,24 +110,29 @@
\expandafter\readgraph_b\dijk_graph,\dijk_quark[],%
}
-\def\dijk_sanitizegraph#1[#2],%
+\def\dijk_sanitizegraph#1,%
+{%
+ \expandafter\expandafter\expandafter\dijk_sanitizegraph_i\dijk_stripsp{#1},% bugfix 0.12
+}
+
+\def\dijk_sanitizegraph_i#1[#2],%
{%
\skv_ifx{\dijk_quark#1}
- {%
- \dijk_removelastcommainmacro\dijk_graph
- }
- {%
- \skv_eearg{\def\dijk_childnodes}{\skv_removeextremespaces{#1}[}%
- \dijk_foreach\dijk_temp\in{#2}{\expandafter\dijk_sanitizegraph_i\dijk_temp\_nil}%
- \dijk_removelastcommainmacro\dijk_childnodes
- \dijk_eaddtomacro\dijk_graph{\dijk_childnodes],}%
- \dijk_sanitizegraph
- }%
+ {%
+ \dijk_removelastcommainmacro\dijk_graph
+ }
+ {%
+ \skv_eearg{\def\dijk_childnodes}{\dijk_stripsp{#1}[}%
+ \dijk_foreach\dijk_temp\in{#2}{\expandafter\dijk_sanitizegraph_ii\dijk_temp\_nil}%
+ \dijk_removelastcommainmacro\dijk_childnodes
+ \dijk_eaddtomacro\dijk_graph{\dijk_childnodes],}%
+ \dijk_sanitizegraph
+ }%
}
-\def\dijk_sanitizegraph_i#1=#2\_nil
+\def\dijk_sanitizegraph_ii#1=#2\_nil
{%
- \dijk_eeaddtomacro\dijk_childnodes{\skv_removeextremespaces{#1}=}%
+ \dijk_eeaddtomacro\dijk_childnodes{\dijk_stripsp{#1}=}%
\dijk_eaddtomacro\dijk_childnodes{\the\numexpr#2\relax,}%
}
@@ -133,54 +149,55 @@
\def\readgraph_b#1#2[#3]#4,%
{%
\skv_ifx{\dijk_quark#1}
- {%
- \skv_exparg{\dijk_foreach\dijk_tempnodename\in}{\dijk_initlistofnodes}
- {% pour chaque sommet
- \skv_eearg{\dijk_foreach\dijk_tempnodechild\in}{\csname dijknode\dijk_tempnodename\endcsname}
- {% pour chaque enfant
- \expandafter\readgraph_c\dijk_tempnodechild\_nil\dijk_currentnodechildname\dijk_currentnodechilddist% capturer nom et distance de l'enfant
- \dijk_exptwoargs\dijk_ifinst\dijk_initlistofnodes{\dijk_currentnodechildname,}% si l'enfant n'est pas dans la liste des sommets
- {}%
- {%
- \dijk_eaddtomacro\dijk_initlistofnodes{\dijk_currentnodechildname,}% l'y mettre
- \dijk_cscmd\let{dijknode\dijk_currentnodechildname}\empty% et initialiser la liste de ses enfants
- }%
- \unless\ifdijk_oriented% si graphe non orienté, ajouter les distances inverses
- \skv_exparg{\skv_eearg\dijk_ifinst{\csname dijknode\dijk_currentnodechildname\endcsname}}{\dijk_tempnodename=}% si le parent est dans déjà un des enfants de l'enfant
- {%
- \expandafter\def\expandafter\readgraph_d\expandafter########\expandafter1\dijk_tempnodename=########2,########3\_nil{%
- \unless\ifnum########2=\dijk_currentnodechilddist\relax% si distance différente : erreur, c'est pas normal
- \errmessage{Distance "\dijk_tempnodename=########2" incorrecte dans \dijk_currentnodechildname{} comprise comme "\dijk_tempnodename=\dijk_currentnodechilddist"}%
- \dijk_cscmd\edef{dijknode\dijk_currentnodechildname}{########1\dijk_tempnodename=\dijk_currentnodechilddist,########3}%
- \fi
- }%
- \expandafter\expandafter\expandafter\readgraph_d\csname dijknode\dijk_currentnodechildname\endcsname\_nil
- }%
- {% sinon, l'y mettre
- \dijk_cscmd\edef{dijknode\dijk_currentnodechildname}{\dijk_tempnodename=\dijk_currentnodechilddist,\csname dijknode\dijk_currentnodechildname\endcsname}%
- }%
- \fi
- }%
+ {%
+ \skv_exparg{\dijk_foreach\dijk_tempnodename\in}{\dijk_initlistofnodes}
+ {% pour chaque sommet
+ \skv_eearg{\dijk_foreach\dijk_tempnodechild\in}{\csname dijknode\dijk_tempnodename\endcsname}
+ {% pour chaque enfant
+ \expandafter\readgraph_c\dijk_tempnodechild\_nil\dijk_currentnodechildname\dijk_currentnodechilddist% capturer nom et distance de l'enfant
+ \dijk_exptwoargs\dijk_ifinst\dijk_initlistofnodes{\dijk_currentnodechildname,}% si l'enfant n'est pas dans la liste des sommets
+ {%
}%
- \dijk_cnt0
- \skv_exparg{\dijk_foreach\dijk_tempnodename\in}{\dijk_initlistofnodes}
- {% pour chaque sommet, construire la liste de ses enfants
- \advance\dijk_cnt1
- \dijk_cscmd\let{listofchilds_\dijk_tempnodename}\empty
- \skv_eearg{\dijk_foreach\dijk_tempnodechild\in}{\csname dijknode\dijk_tempnodename\endcsname}
- {%
- \expandafter\readgraph_c\dijk_tempnodechild\_nil\dijk_currentnodechildname\dijk_currentnodechilddist
- \expandafter\dijk_eaddtomacro\csname listofchilds_\dijk_tempnodename\endcsname{\dijk_currentnodechildname,}%
- }%
+ {%
+ \dijk_eaddtomacro\dijk_initlistofnodes{\dijk_currentnodechildname,}% l'y mettre
+ \dijk_cscmd\let{dijknode\dijk_currentnodechildname}\empty% et initialiser la liste de ses enfants
}%
- \edef\dijk_numberofnodes{\the\dijk_cnt}%
+ \unless\ifdijk_oriented% si graphe non orienté, ajouter les distances inverses
+ \skv_exparg{\skv_eearg\dijk_ifinst{\csname dijknode\dijk_currentnodechildname\endcsname}}{\dijk_tempnodename=}% si le parent est dans déjà un des enfants de l'enfant
+ {%
+ \expandafter\def\expandafter\readgraph_d\expandafter########\expandafter1\dijk_tempnodename=########2,########3\_nil{%
+ \unless\ifnum########2=\dijk_currentnodechilddist\relax% si distance différente : erreur, c'est pas normal
+ \errmessage{Distance "\dijk_tempnodename=########2" incorrecte dans \dijk_currentnodechildname{} comprise comme "\dijk_tempnodename=\dijk_currentnodechilddist"}%
+ \dijk_cscmd\edef{dijknode\dijk_currentnodechildname}{########1\dijk_tempnodename=\dijk_currentnodechilddist,########3}%
+ \fi
+ }%
+ \expandafter\expandafter\expandafter\readgraph_d\csname dijknode\dijk_currentnodechildname\endcsname\_nil
+ }%
+ {% sinon, l'y mettre
+ \dijk_cscmd\edef{dijknode\dijk_currentnodechildname}{\dijk_tempnodename=\dijk_currentnodechilddist,\csname dijknode\dijk_currentnodechildname\endcsname}%
+ }%
+ \fi
+ }%
}%
- {%
- \def\dijk_currentnodename{#1}%
- \dijk_eaddtomacro\dijk_initlistofnodes{\dijk_currentnodename,}%
- \dijk_cscmd\def{dijknode\dijk_currentnodename}{#3,}%
- \readgraph_b
+ \dijk_cnt0
+ \skv_exparg{\dijk_foreach\dijk_tempnodename\in}{\dijk_initlistofnodes}
+ {% pour chaque sommet, construire la liste de ses enfants
+ \advance\dijk_cnt1
+ \dijk_cscmd\let{listofchilds_\dijk_tempnodename}\empty
+ \skv_eearg{\dijk_foreach\dijk_tempnodechild\in}{\csname dijknode\dijk_tempnodename\endcsname}
+ {%
+ \expandafter\readgraph_c\dijk_tempnodechild\_nil\dijk_currentnodechildname\dijk_currentnodechilddist
+ \expandafter\dijk_eaddtomacro\csname listofchilds_\dijk_tempnodename\endcsname{\dijk_currentnodechildname,}%
+ }%
}%
+ \edef\dijk_numberofnodes{\the\dijk_cnt}%
+ }%
+ {%
+ \def\dijk_currentnodename{#1}%
+ \dijk_eaddtomacro\dijk_initlistofnodes{\dijk_currentnodename,}%
+ \dijk_cscmd\def{dijknode\dijk_currentnodename}{#3,}%
+ \readgraph_b
+ }%
}%
\def\readgraph_c#1=#2\_nil#3#4%
@@ -197,9 +214,12 @@
\def\dijk_removenode#1%
{% enlève le sommet #1 de la liste des sommets non vus
\skv_exparg{\dijk_ifinst}{\expandafter,\dijk_nodestoexplore}{,#1,}
- {\def\dijk_removenode_i##1,#1,##2\_nil{\skv_exparg{\def\dijk_nodestoexplore}{\dijk_gobarg##1,##2}}%
- \expandafter\dijk_removenode_i\expandafter,\dijk_nodestoexplore\_nil}
- {}%
+ {%
+ \def\dijk_removenode_i##1,#1,##2\_nil{\skv_exparg{\def\dijk_nodestoexplore}{\dijk_gobarg##1,##2}}%
+ \expandafter\dijk_removenode_i\expandafter,\dijk_nodestoexplore\_nil
+ }
+ {%
+ }%
}
\def\dijkstra
@@ -213,70 +233,68 @@
\let\dijk_listofnodes\dijk_initlistofnodes
\let\dijk_nodestoexplore\dijk_initlistofnodes
\dijk_cnt0
- \skv_eearg{\def\dijk_currentnode}{\skv_removeextremespaces{#2}}%
- \skv_eearg{\def\dijk_endnode}{\skv_removeextremespaces{#3}}%
- \edef\dijk_tab{%
- \unexpanded\expandafter\expandafter\expandafter{\useKV[\dijkname]{pre-tab}}%
- \noexpand
- \begin{tabular}[\useKV[\dijkname]{v-position}]{%
- *{\dijk_numberofnodes}{|c}|%
+ \skv_eearg{\def\dijk_currentnode}{\dijk_stripsp{#2}}%
+ \skv_eearg{\def\dijk_endnode}{\dijk_stripsp{#3}}%
+ \edef\dijk_tab
+ {%
+ \noexpand\dijk_pre_tab
+ \noexpand\begin{tabular}[\dijk_v_position]{%
+ *{\dijk_numberofnodes}{|\dijk_col_type}|%
\ifboolKV[\dijkname]{show-lastcol}
- {\unexpanded\expandafter\expandafter\expandafter{\useKV[\dijkname]{lastcol-type}}}
+ {\noexpand\dijk_last_col_type}
{}%
}%
\noexpand\hline
- }%
+ }%
\def\dijk_autoamp{\def\dijk_autoamp{\dijk_addtomacro\dijk_tab&}}%
\skv_exparg{\dijk_foreach\dijk_tempnodename\in}\dijk_listofnodes
- {% pour tous le sommets du graphe
- \dijk_autoamp% ajouter "&", sauf la première fois
- \dijk_cscmd\let{dist_\dijk_tempnodename}\dijk_maxint% toutes les distances à +inf
- \dijk_cscmd\let{prev_\dijk_tempnodename}\dijk_quark% tous les prédecesseurs à <quark>
- \dijk_eaddtomacro\dijk_tab{\dijk_tempnodename}% peupler 1re ligne du tableau
- }%
+ {% pour tous le sommets du graphe
+ \dijk_autoamp% ajouter "&", sauf la première fois
+ \dijk_cscmd\let{dist_\dijk_tempnodename}\dijk_maxint% toutes les distances à +inf
+ \dijk_cscmd\let{prev_\dijk_tempnodename}\dijk_quark% tous les prédecesseurs à <quark>
+ \dijk_eaddtomacro\dijk_tab{\dijk_tempnodename}% peupler 1re ligne du tableau
+ }%
\ifboolKV[\dijkname]{show-lastcol}
- {\dijk_eaddtomacro\dijk_tab{\expandafter&\unexpanded\expandafter\expandafter\expandafter{\useKV[\dijkname]{lastcol-label}}}}
+ {\dijk_eaddtomacro\dijk_tab{\expandafter&\dijk_lastcol_label}}
{}%
\dijk_addtomacro\dijk_tab{\\\hline}%
\dijk_cscmd\def{dist_\dijk_currentnode}{0}% distance sommet de départ = 0
\dijk_whilenotempty\dijk_nodestoexplore
+ {%
+ \dijk_findmindist\dijk_currentnode% retourne \dijk_currentnode : le sommet enfant ayant la distance la plus faible
+ \skv_ifx{\dijk_quark\dijk_currentnode}
+ {% si le sommet n'est pas trouvé (graphe non connexe)
+ \global\let\dijkdist\dijk_infinity_code
+ \let\dijk_nodestoexplore\empty% sortir de la boucle
+ }
{%
- \dijk_findmindist\dijk_currentnode% retourne \dijk_currentnode : le sommet enfant ayant la distance la plus faible
- \skv_ifx{\dijk_quark\dijk_currentnode}
- {% si le sommet n'est pas trouvé (graphe non connexe)
- \skv_eearg{\gdef\dijkdist}{\useKV[\dijkname]{infinity-code}}%
- \let\dijk_nodestoexplore\empty% sortir de la boucle
- }
+ \xdef\dijkdist{\csname dist_\dijk_currentnode\endcsname}%
+ \unless\ifx\dijk_nodestoexplore\empty
+ \dijk_addstep
+ \fi
+ \skv_ifx{\dijk_currentnode\dijk_endnode}
+ {% si le sommet de sortie est atteint
+ \let\dijk_nodestoexplore\empty% sortir de la boucle
+ }
+ {% sinon
+ \skv_exparg\dijk_removenode\dijk_currentnode% enlever ce sommet du graphe à explorer
+ \skv_eearg{\dijk_foreach\dijk_temp\in}{\csname listofchilds_\dijk_currentnode\endcsname}
{%
- \xdef\dijkdist{\csname dist_\dijk_currentnode\endcsname}%
- \unless\ifx\dijk_nodestoexplore\empty
- \dijk_addstep
- \fi
- \skv_ifx{\dijk_currentnode\dijk_endnode}
- {% si le sommet de sortie est atteint
- \let\dijk_nodestoexplore\empty% sortir de la boucle
- }
- {% sinon
- \skv_exparg\dijk_removenode\dijk_currentnode% enlever ce sommet du graphe à explorer
- \skv_eearg{\dijk_foreach\dijk_temp\in}{\csname listofchilds_\dijk_currentnode\endcsname}
- {%
- \dijk_exptwoargs\dijk_ifinst\dijk_nodestoexplore{\dijk_temp,}
- {%
- \dijk_exptwoargs\dijk_updatedist\dijk_currentnode\dijk_temp
- }%
- {}%
- }%
- \advance\dijk_cnt1
- }%
+ \dijk_exptwoargs\dijk_ifinst\dijk_nodestoexplore{\dijk_temp,}
+ {\dijk_exptwoargs\dijk_updatedist\dijk_currentnode\dijk_temp}%
+ {}%
}%
+ \advance\dijk_cnt1
+ }%
}%
+ }%
\ifboolKV[\dijkname]{h-rules}
{}
{\dijk_addtomacro\dijk_tab\hline}%
\dijk_addtomacro\dijk_tab{\end{tabular}}%
- \dijk_eeaddtomacro\dijk_tab{\useKV[\dijkname]{post-tab}}%
+ \dijk_eaddtomacro\dijk_tab{\dijk_post_tab}%
\skv_ifx{\dijk_quark\dijk_currentnode}
- {\skv_eearg{\gdef\dijkpath}{\useKV[\dijkname]{nopath-string}}}
+ {\global\let\dijkpath\dijk_nopath_string}
{\skv_exparg\dijk_createpath\dijk_currentnode}% calculer le chemin sauf s'il est impossible à trouver
\ifboolKV[\dijkname]{show-tab}\dijk_tab{}% afficher le tableau
\endgroup
@@ -291,10 +309,12 @@
{% #1=sommet en cours
\skv_eearg{\def\dijk_temp}{\csname prev_#1\endcsname}%
\skv_ifx{\dijk_quark\dijk_temp}
- {}
- {\xdef\dijkpath{\dijk_temp\useKV[\dijkname]{path-sep}\dijkpath}%
+ {%
+ }
+ {%
+ \xdef\dijkpath{\dijk_temp\dijk_path_sep\dijkpath}%
\skv_exparg\dijk_createpathi\dijk_temp
- }%
+ }%
}
\def\dijk_findmindist#1%
@@ -302,12 +322,12 @@
\let\dijk_mindist\dijk_maxint
\let#1\dijk_quark
\skv_exparg{\dijk_foreach\dijk_currentnodechildname\in}\dijk_nodestoexplore
- {%
- \ifnum\csname dist_\dijk_currentnodechildname\endcsname<\dijk_mindist\relax
- \expandafter\let\expandafter\dijk_mindist\csname dist_\dijk_currentnodechildname\endcsname
- \let#1\dijk_currentnodechildname
- \fi
- }%
+ {%
+ \ifnum\csname dist_\dijk_currentnodechildname\endcsname<\dijk_mindist\relax
+ \expandafter\let\expandafter\dijk_mindist\csname dist_\dijk_currentnodechildname\endcsname
+ \let#1\dijk_currentnodechildname
+ \fi
+ }%
}
\def\dijk_whilenotempty#1#2%
@@ -329,35 +349,35 @@
{%
\def\dijk_autoamp{\def\dijk_autoamp{\dijk_addtomacro\dijk_tab&}}%
\skv_exparg{\dijk_foreach\dijk_temp\in}\dijk_listofnodes
+ {%
+ \dijk_autoamp
+ \dijk_exptwoargs\dijk_ifinst\dijk_nodestoexplore\dijk_temp
{%
- \dijk_autoamp
- \dijk_exptwoargs\dijk_ifinst\dijk_nodestoexplore\dijk_temp
- {%
- \ifnum\csname dist_\dijk_temp\endcsname=\dijk_maxint\relax
- \dijk_eeaddtomacro\dijk_tab{\useKV[\dijkname]{infinity-code}}%
- \else
- \skv_ifx{\dijk_temp\dijk_currentnode}% si c'est le sommet fixé, le mettre en valeur
- {%
- \skv_ifcsname{distwithprev_\dijk_temp}
- {%
- \dijk_eeaddtomacro\dijk_tab{\expandafter\expandafter\expandafter\dijk_highlightnode
- \csname distwithprev_\dijk_temp\endcsname}% forme \dijk_highlightnode\formatnodewithprev{<dist>}{<sommet>}
- }
- {%
- \dijk_eeaddtomacro\dijk_tab{\expandafter\expandafter\expandafter
- \highlightfirstnode\expandafter\expandafter\expandafter
- {\csname dist_\dijk_temp\endcsname}}% forme \highlightfirstnode{0}
- }%
- }
- {% sinon, afficher normalement (forme \formatnodewithprev{<dist>}{<sommet>})
- \dijk_eeaddtomacro\dijk_tab{\csname dist\ifcsname distwithprev_\dijk_temp\endcsname withprev\fi _\dijk_temp\endcsname}%
- }%
- \fi
- }%
+ \ifnum\csname dist_\dijk_temp\endcsname=\dijk_maxint\relax
+ \dijk_eaddtomacro\dijk_tab{\dijk_infinity_code}%
+ \else
+ \skv_ifx{\dijk_temp\dijk_currentnode}% si c'est le sommet fixé, le mettre en valeur
{%
- \dijk_eeaddtomacro\dijk_tab{\useKV[\dijkname]{norevisit-code}}% sommet déjà fixé
+ \skv_ifcsname{distwithprev_\dijk_temp}
+ {%
+ \dijk_eeaddtomacro\dijk_tab{\expandafter\expandafter\expandafter\dijk_highlightnode
+ \csname distwithprev_\dijk_temp\endcsname}% forme \dijk_highlightnode\formatnodewithprev{<dist>}{<sommet>}
+ }
+ {%
+ \dijk_eeaddtomacro\dijk_tab{\expandafter\expandafter\expandafter
+ \highlightfirstnode\expandafter\expandafter\expandafter
+ {\csname dist_\dijk_temp\endcsname}}% forme \highlightfirstnode{0}
+ }%
+ }
+ {% sinon, afficher normalement (forme \formatnodewithprev{<dist>}{<sommet>})
+ \dijk_eeaddtomacro\dijk_tab{\csname dist\ifcsname distwithprev_\dijk_temp\endcsname withprev\fi _\dijk_temp\endcsname}%
}%
+ \fi
+ }%
+ {%
+ \dijk_eaddtomacro\dijk_tab{\dijk_no_revisit_code}% sommet déjà fixé
}%
+ }%
\ifboolKV[\dijkname]{show-lastcol}
{\dijk_eaddtomacro\dijk_tab{\expandafter&\detokenize\expandafter{\dijk_currentnode}}}% ajout du sommet fixé
{}%
@@ -369,9 +389,22 @@
\def\dijk_highlightnode\formatnodewithprev{\highlightnode}
+\defKV[\dijkname]{%
+ v-position = \def\dijk_v_position {#1},
+ pre-tab = \def\dijk_pre_tab {#1},
+ post-tab = \def\dijk_post_tab {#1},
+ col-type = \def\dijk_col_type {#1},
+ infinity-code = \def\dijk_infinity_code {#1},
+ norevisit-code = \def\dijk_no_revisit_code{#1},
+ lastcol-type = \def\dijk_last_col_type {#1},
+ lastcol-label = \def\dijk_lastcol_label {#1},
+ nopath-string = \def\dijk_nopath_string {#1},
+ path-sep = \def\dijk_path_sep {#1}
+}
+
\dijk_restorecatcode
-\expandafter\let\expandafter\initdijk\csname skv_[\dijkname]\endcsname
+\def\initdijk{\restoreKV[\dijkname]}
% Macros permettant de modifier les <valeurs> des <clés>
\def\setdijk#{\setKV[\dijkname]}
@@ -421,4 +454,9 @@ Versions :
| 0.11 | 09/09/2017 | - retrait d'un \show, laissé par oubli après les |
| | | phases de débogage |
| | | - petit nettoyage du code |
+|---------+------------+------------------------------------------------------|
+| 0.12 | 25/06/2020 | - bugfix : le package est rendu compatible avec la |
+| | | version 0.2 de simplekv |
+| | | - bugfix : mauvaise gestion est espaces dans la macro|
+| | | \dijk_sanitizegraph |
|---------+------------+------------------------------------------------------| \ No newline at end of file