summaryrefslogtreecommitdiff
path: root/macros/latex/contrib/dijkstra/dijkstra.sty
diff options
context:
space:
mode:
Diffstat (limited to 'macros/latex/contrib/dijkstra/dijkstra.sty')
-rw-r--r--macros/latex/contrib/dijkstra/dijkstra.sty154
1 files changed, 83 insertions, 71 deletions
diff --git a/macros/latex/contrib/dijkstra/dijkstra.sty b/macros/latex/contrib/dijkstra/dijkstra.sty
index b8c673449e..92252c6b81 100644
--- a/macros/latex/contrib/dijkstra/dijkstra.sty
+++ b/macros/latex/contrib/dijkstra/dijkstra.sty
@@ -1,12 +1,12 @@
-% !TeX encoding = ISO-8859-1
+% !TeX encoding = UTF-8
% Ce fichier contient le code de l'extension "dijkstra"
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% %
\def\dijkname {dijkstra} %
-\def\dijkver {0.12} %
+\def\dijkver {0.13} %
% %
-\def\dijkdate {2020/06/25} %
+\def\dijkdate {2022/10/01} %
% %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
@@ -24,14 +24,14 @@
% This work has the LPPL maintenance status `maintained'.
%
% The Current Maintainer of this work is Christian Tellechea
-% Copyright : Christian Tellechea 2017-2020
+% Copyright : Christian Tellechea 2017-2022
% email: unbonpetit@netc.fr
% Commentaires, suggestions et signalement de bugs bienvenus !
% Comments, bug reports and suggestions are welcome.
% --------------------------------------------------------------------
-% L'extension dijkstra est composée des 4 fichiers suivants :
+% L'extension dijkstra est composée des 4 fichiers suivants :
% - code : dijkstra.sty
-% - manuel en français : dijkstra-fr.tex & dijkstra-fr.pdf
+% - manuel en français : dijkstra-fr.tex & dijkstra-fr.pdf
% - fichier lisezmoi : README
% --------------------------------------------------------------------
%
@@ -52,14 +52,23 @@
\def\dijk_quark{\dijk_quark}
\def\dijk_cscmd#1#2{\expandafter#1\csname#2\endcsname}
\def\dijk_gobarg#1{}
+\long\def\dijk_first#1#2{#1}
+\long\def\dijk_second#1#2{#2}
+\long\def\dijk_earg#1#2{\expandafter\dijk_earg_i\expandafter{#2}{#1}}\let\dijk_exparg\dijk_earg
+\long\def\dijk_eearg#1#2{\expandafter\expandafter\expandafter\dijk_earg_i\expandafter\expandafter\expandafter{#2}{#1}}
+\long\def\dijk_earg_i#1#2{#2{#1}}
+\long\def\dijk_ifx#1{\ifx#1\expandafter\dijk_first\else\expandafter\dijk_second\fi}
+\long\def\dijk_ifempty#1{\dijk_ifempty_i#1\_nil\_nil\dijk_second\dijk_first\__nil}%
+\long\def\dijk_ifempty_i#1#2\_nil#3#4#5\__nil{#4}
+\def\dijk_ifcsname#1{\ifcsname#1\endcsname\expandafter\skv_first\else\expandafter\skv_second\fi}
\def\dijk_addtomacro#1#2{\expandafter\def\expandafter#1\expandafter{#1#2}}
-\def\dijk_eaddtomacro#1#2{\skv_exparg{\dijk_addtomacro#1}{#2}}
-\def\dijk_eeaddtomacro#1#2{\skv_eearg{\dijk_addtomacro#1}{#2}}
-\long\def\dijk_exptwoargs#1#2#3{\skv_exparg{\skv_exparg{#1}{#2}}{#3}}
-\def\dijk_ifnum#1{\ifnum#1\expandafter\skv_first\else\expandafter\skv_second\fi}
+\def\dijk_eaddtomacro#1#2{\dijk_exparg{\dijk_addtomacro#1}{#2}}
+\def\dijk_eeaddtomacro#1#2{\dijk_eearg{\dijk_addtomacro#1}{#2}}
+\long\def\dijk_exptwoargs#1#2#3{\dijk_exparg{\dijk_exparg{#1}{#2}}{#3}}
+\def\dijk_ifnum#1{\ifnum#1\expandafter\dijk_first\else\expandafter\dijk_second\fi}
\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_ifstar#1#2{\def\dijk_ifstar_i{\dijk_ifx{*\dijk_nxttok}{\dijk_first{#1}}{#2}}\futurelet\dijk_nxttok\dijk_ifstar_i}
+\def\dijk_ifopt#1#2{\def\dijk_ifopt_i{\dijk_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}}%
@@ -69,7 +78,6 @@
}
\dijk_stripsp{ }
-
\def\dijk_foreach#1\in#2#3%
{%
\global\advance\dijk_nest1
@@ -82,18 +90,18 @@
\def\dijk_foreach_i#1#2,%
{%
\def#1{#2}%
- \skv_ifx{\dijk_quark#1}
+ \dijk_ifx{\dijk_quark#1}
{%
}
{%
- \skv_ifx{#1\empty}{}{\csname dijk_loopcode_\number\dijk_nest\endcsname}%
+ \dijk_ifx{#1\empty}{}{\csname dijk_loopcode_\number\dijk_nest\endcsname}%
\dijk_foreach_i#1%
}%
}%
\def\dijk_ifinst#1#2%
{% #2 est-il dans #1 ?
- \def\dijk_ifinst_i##1#2##2\_nil{\dijk_swapargs{\skv_ifempty{##2}}}%
+ \def\dijk_ifinst_i##1#2##2\_nil{\dijk_swapargs{\dijk_ifempty{##2}}}%
\dijk_ifinst_i#1#2\_nil
}
@@ -105,8 +113,8 @@
\def\readgraph_a#1%
{%
\let\dijk_initlistofnodes\empty% liste des sommets
- \let\dijk_graph\empty% argument #1 où l'on va enlever les espaces
- \dijk_sanitizegraph#1,\dijk_quark[],% enlever tous les espaces indésirables et évaluer les nombres dans l'argument #1
+ \let\dijk_graph\empty% argument #1 où l'on va enlever les espaces
+ \dijk_sanitizegraph#1,\dijk_quark[],% enlever tous les espaces indésirables et évaluer les nombres dans l'argument #1
\expandafter\readgraph_b\dijk_graph,\dijk_quark[],%
}
@@ -117,12 +125,12 @@
\def\dijk_sanitizegraph_i#1[#2],%
{%
- \skv_ifx{\dijk_quark#1}
+ \dijk_ifx{\dijk_quark#1}
{%
\dijk_removelastcommainmacro\dijk_graph
}
{%
- \skv_eearg{\def\dijk_childnodes}{\dijk_stripsp{#1}[}%
+ \dijk_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],}%
@@ -148,11 +156,11 @@
\def\readgraph_b#1#2[#3]#4,%
{%
- \skv_ifx{\dijk_quark#1}
+ \dijk_ifx{\dijk_quark#1}
{%
- \skv_exparg{\dijk_foreach\dijk_tempnodename\in}{\dijk_initlistofnodes}
+ \dijk_exparg{\dijk_foreach\dijk_tempnodename\in}{\dijk_initlistofnodes}
{% pour chaque sommet
- \skv_eearg{\dijk_foreach\dijk_tempnodechild\in}{\csname dijknode\dijk_tempnodename\endcsname}
+ \dijk_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
@@ -162,11 +170,11 @@
\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
+ \unless\ifdijk_oriented% si graphe non orienté, ajouter les distances inverses
+ \dijk_exparg{\dijk_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
+ \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
@@ -180,11 +188,11 @@
}%
}%
\dijk_cnt0
- \skv_exparg{\dijk_foreach\dijk_tempnodename\in}{\dijk_initlistofnodes}
+ \dijk_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}
+ \dijk_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,}%
@@ -212,10 +220,10 @@
}
\def\dijk_removenode#1%
-{% enlève le sommet #1 de la liste des sommets non vus
- \skv_exparg{\dijk_ifinst}{\expandafter,\dijk_nodestoexplore}{,#1,}
+{% enlève le sommet #1 de la liste des sommets non vus
+ \dijk_exparg{\dijk_ifinst}{\expandafter,\dijk_nodestoexplore}{,#1,}
{%
- \def\dijk_removenode_i##1,#1,##2\_nil{\skv_exparg{\def\dijk_nodestoexplore}{\dijk_gobarg##1,##2}}%
+ \def\dijk_removenode_i##1,#1,##2\_nil{\dijk_exparg{\def\dijk_nodestoexplore}{\dijk_gobarg##1,##2}}%
\expandafter\dijk_removenode_i\expandafter,\dijk_nodestoexplore\_nil
}
{%
@@ -227,14 +235,14 @@
\dijk_ifopt{\dijkstra_i}{\dijkstra_i[]}%
}
\def\dijkstra_i[#1]#2#3%
-{% #1=sommet départ #2=sommet arrivée
+{% #1=sommet départ #2=sommet arrivée
\begingroup
- \skv_ifempty{#1}{}{\setdijk{#1}}%
+ \dijk_ifempty{#1}{}{\setdijk{#1}}%
\let\dijk_listofnodes\dijk_initlistofnodes
\let\dijk_nodestoexplore\dijk_initlistofnodes
\dijk_cnt0
- \skv_eearg{\def\dijk_currentnode}{\dijk_stripsp{#2}}%
- \skv_eearg{\def\dijk_endnode}{\dijk_stripsp{#3}}%
+ \dijk_eearg{\def\dijk_currentnode}{\dijk_stripsp{#2}}%
+ \dijk_eearg{\def\dijk_endnode}{\dijk_stripsp{#3}}%
\edef\dijk_tab
{%
\noexpand\dijk_pre_tab
@@ -247,23 +255,23 @@
\noexpand\hline
}%
\def\dijk_autoamp{\def\dijk_autoamp{\dijk_addtomacro\dijk_tab&}}%
- \skv_exparg{\dijk_foreach\dijk_tempnodename\in}\dijk_listofnodes
+ \dijk_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_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&\dijk_lastcol_label}}
{}%
\dijk_addtomacro\dijk_tab{\\\hline}%
- \dijk_cscmd\def{dist_\dijk_currentnode}{0}% distance sommet de départ = 0
+ \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)
+ \dijk_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
}
@@ -272,13 +280,13 @@
\unless\ifx\dijk_nodestoexplore\empty
\dijk_addstep
\fi
- \skv_ifx{\dijk_currentnode\dijk_endnode}
+ \dijk_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_exparg\dijk_removenode\dijk_currentnode% enlever ce sommet du graphe à explorer
+ \dijk_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}%
@@ -293,9 +301,9 @@
{\dijk_addtomacro\dijk_tab\hline}%
\dijk_addtomacro\dijk_tab{\end{tabular}}%
\dijk_eaddtomacro\dijk_tab{\dijk_post_tab}%
- \skv_ifx{\dijk_quark\dijk_currentnode}
+ \dijk_ifx{\dijk_quark\dijk_currentnode}
{\global\let\dijkpath\dijk_nopath_string}
- {\skv_exparg\dijk_createpath\dijk_currentnode}% calculer le chemin sauf s'il est impossible à trouver
+ {\dijk_exparg\dijk_createpath\dijk_currentnode}% calculer le chemin sauf s'il est impossible à trouver
\ifboolKV[\dijkname]{show-tab}\dijk_tab{}% afficher le tableau
\endgroup
}
@@ -307,21 +315,21 @@
}
\def\dijk_createpathi#1%
{% #1=sommet en cours
- \skv_eearg{\def\dijk_temp}{\csname prev_#1\endcsname}%
- \skv_ifx{\dijk_quark\dijk_temp}
+ \dijk_eearg{\def\dijk_temp}{\csname prev_#1\endcsname}%
+ \dijk_ifx{\dijk_quark\dijk_temp}
{%
}
{%
\xdef\dijkpath{\dijk_temp\dijk_path_sep\dijkpath}%
- \skv_exparg\dijk_createpathi\dijk_temp
+ \dijk_exparg\dijk_createpathi\dijk_temp
}%
}
\def\dijk_findmindist#1%
-{% trouve dans "sommets à explorer" celui ayant la distance mini
+{% trouve dans "sommets à explorer" celui ayant la distance mini
\let\dijk_mindist\dijk_maxint
\let#1\dijk_quark
- \skv_exparg{\dijk_foreach\dijk_currentnodechildname\in}\dijk_nodestoexplore
+ \dijk_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
@@ -331,8 +339,8 @@
}
\def\dijk_whilenotempty#1#2%
-{% tant que la macro #1 n'est pas \ifx-vide, exécuter #2
- \skv_ifx{#1\empty}{}{#2\dijk_whilenotempty#1{#2}}%
+{% tant que la macro #1 n'est pas \ifx-vide, exécuter #2
+ \dijk_ifx{#1\empty}{}{#2\dijk_whilenotempty#1{#2}}%
}
\def\dijk_updatedist#1#2%
@@ -348,7 +356,7 @@
\def\dijk_addstep
{%
\def\dijk_autoamp{\def\dijk_autoamp{\dijk_addtomacro\dijk_tab&}}%
- \skv_exparg{\dijk_foreach\dijk_temp\in}\dijk_listofnodes
+ \dijk_exparg{\dijk_foreach\dijk_temp\in}\dijk_listofnodes
{%
\dijk_autoamp
\dijk_exptwoargs\dijk_ifinst\dijk_nodestoexplore\dijk_temp
@@ -356,9 +364,9 @@
\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_ifx{\dijk_temp\dijk_currentnode}% si c'est le sommet fixé, le mettre en valeur
{%
- \skv_ifcsname{distwithprev_\dijk_temp}
+ \dijk_ifcsname{distwithprev_\dijk_temp}
{%
\dijk_eeaddtomacro\dijk_tab{\expandafter\expandafter\expandafter\dijk_highlightnode
\csname distwithprev_\dijk_temp\endcsname}% forme \dijk_highlightnode\formatnodewithprev{<dist>}{<sommet>}
@@ -375,11 +383,11 @@
\fi
}%
{%
- \dijk_eaddtomacro\dijk_tab{\dijk_no_revisit_code}% sommet déjà fixé
+ \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é
+ {\dijk_eaddtomacro\dijk_tab{\expandafter&\detokenize\expandafter{\dijk_currentnode}}}% ajout du sommet fixé
{}%
\dijk_addtomacro\dijk_tab{\\}%
\ifboolKV[\dijkname]{h-rules}
@@ -406,10 +414,10 @@
\def\initdijk{\restoreKV[\dijkname]}
-% Macros permettant de modifier les <valeurs> des <clés>
+% Macros permettant de modifier les <valeurs> des <clés>
\def\setdijk#{\setKV[\dijkname]}
-% ... ainsi que les <valeurs> par défaut
+% ... ainsi que les <valeurs> par défaut
\def\setdijkdefault#{\setKVdefault[\dijkname]}
\newcommand*\formatnodewithprev[2]%
@@ -431,16 +439,16 @@
show-tab = true,% afficher le tableau
v-position = c,% argument optionnel de \begin{tabular}[<arg>]
pre-tab = {},% juste avant le \begin{tabular}
- post-tab = {},% juste après le \end{tabular}
+ post-tab = {},% juste après le \end{tabular}
col-type = c,% colonnes de type "c" pour les colonnes de distances
infinity-code = $\infty$,% pour distance infinie
- norevisit-code = ---,% pour les sommets préalablement fixés
- h-rules = false,% pas de filets entre les lignes des étapes
- show-lastcol = false,% si vrai : mettre en plus la colonne "sommet fixé"
- lastcol-type = c|,% dernière colonne
+ norevisit-code = ---,% pour les sommets préalablement fixés
+ h-rules = false,% pas de filets entre les lignes des étapes
+ show-lastcol = false,% si vrai : mettre en plus la colonne "sommet fixé"
+ lastcol-type = c|,% dernière colonne
lastcol-label = sommet fix\'e,
nopath-string = Pas de chemin possible,% si chemin impossible
- path-sep = -,% séparateur entre sommets dans le chemin
+ path-sep = -,% séparateur entre sommets dans le chemin
}
\endinput
@@ -449,14 +457,18 @@ Versions :
_____________________________________________________________________________
| Version | Date | Changements |
|---------+------------+------------------------------------------------------|
-| 0.1 | 06/09/2017 | Première version |
+| 0.1 | 06/09/2017 | Première version |
|---------+------------+------------------------------------------------------|
-| 0.11 | 09/09/2017 | - retrait d'un \show, laissé par oubli après les |
-| | | phases de débogage |
+| 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|
+| | | - bugfix : mauvaise gestion des espaces dans la macro|
| | | \dijk_sanitizegraph |
+|---------+------------+------------------------------------------------------|
+| 0.13 | 01/10/2022 | - le package est rendu compatible avec la version |
+| | | 0.2a de simplekv |
+| | | - code en UFT8 |
|---------+------------+------------------------------------------------------| \ No newline at end of file