From 7effd978acf9bc18bab84dc4e449205e2157195c Mon Sep 17 00:00:00 2001 From: Karl Berry Date: Sat, 9 Sep 2017 22:35:13 +0000 Subject: dijkstra (9sep17) git-svn-id: svn://tug.org/texlive/trunk@45256 c570f23f-e606-0410-a88d-b1316a301751 --- Master/texmf-dist/tex/latex/dijkstra/dijkstra.sty | 128 +++++++++++----------- 1 file changed, 62 insertions(+), 66 deletions(-) (limited to 'Master/texmf-dist/tex/latex/dijkstra') diff --git a/Master/texmf-dist/tex/latex/dijkstra/dijkstra.sty b/Master/texmf-dist/tex/latex/dijkstra/dijkstra.sty index 94ee77e7126..a1e88728047 100644 --- a/Master/texmf-dist/tex/latex/dijkstra/dijkstra.sty +++ b/Master/texmf-dist/tex/latex/dijkstra/dijkstra.sty @@ -4,9 +4,9 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % \def\dijkname {dijkstra} % -\def\dijkver {0.1} % +\def\dijkver {0.11} % % % -\def\dijkdate {2017/09/06} % +\def\dijkdate {2017/09/09} % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % @@ -36,63 +36,56 @@ % - fichier lisezmoi : README % -------------------------------------------------------------------- % -\ProvidesPackage{dijkstra}[\dijkdate\space v\dijkver\space Dijkstra Algorithm (CT)] \NeedsTeXFormat{LaTeX2e} +\ProvidesPackage{dijkstra}[\dijkdate\space v\dijkver\space Dijkstra Algorithm (CT)] \RequirePackage{simplekv} \expandafter\edef\csname dijk_restorecatcode\endcsname{\expandafter\catcode\number`\_=\number\catcode`\_\relax} -\catcode`\_11 -\chardef\dijk_stop0 +\catcode`\_=11 + +\newcount\dijk_nest +\newcount\dijk_cnt +\newif\ifdijk_oriented + \def\dijk_maxint{1073741823} \def\dijk_quark{\dijk_quark} -\def\dijk_relax{\relax} \def\dijk_cscmd#1#2{\expandafter#1\csname#2\endcsname} \def\dijk_gobarg#1{} \def\dijk_addtomacro#1#2{\expandafter\def\expandafter#1\expandafter{#1#2}} -\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_first#1#2{#1} -\long\def\dijk_second#1#2{#2} -\long\def\dijk_exparg#1#2{\expandafter\dijk_exparg_i\expandafter{#2}{#1}}% -\long\def\dijk_exparg_i#1#2{#2{#1}} -\long\def\dijk_eearg#1#2{\expandafter\expandafter\expandafter\dijk_exparg_i\expandafter\expandafter\expandafter{#2}{#1}}% -\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_ifcsname#1{\ifcsname#1\endcsname\expandafter\dijk_first\else\expandafter\dijk_second\fi} -\long\def\dijk_ifempty#1{\dijk_exparg\dijk_ifx{\expandafter\relax\detokenize{#1}\relax}} -\long\def\dijk_ifx#1{\ifx#1\expandafter\dijk_first\else\expandafter\dijk_second\fi} +\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_swapargs#1#2#3{#1{#3}{#2}} -\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_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} -\newcount\cnt_nest \def\dijk_foreach#1\in#2#3% {% - \global\advance\cnt_nest1 - \dijk_cscmd\def{dijk_loopcode_\number\cnt_nest}{#3}% + \global\advance\dijk_nest1 + \dijk_cscmd\def{dijk_loopcode_\number\dijk_nest}{#3}% \dijk_foreach_i#1#2,\dijk_quark,% - \dijk_cscmd\let{dijk_loopcode_\number\cnt_nest}\empty - \global\advance\cnt_nest-1 + \dijk_cscmd\let{dijk_loopcode_\number\dijk_nest}\empty + \global\advance\dijk_nest-1 }% \def\dijk_foreach_i#1#2,% {% \def#1{#2}% - \dijk_ifx{\dijk_quark#1} + \skv_ifx{\dijk_quark#1} {} {% - \dijk_ifx{#1\empty}{}{\csname dijk_loopcode_\number\cnt_nest\endcsname}% + \skv_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{\dijk_ifempty{##2}}}% + \def\dijk_ifinst_i##1#2##2\_nil{\dijk_swapargs{\skv_ifempty{##2}}}% \dijk_ifinst_i#1#2\_nil } -\newif\ifdijk_oriented \def\readgraph {% \dijk_ifstar{\dijk_orientedtrue\readgraph_a}{\dijk_orientedfalse\readgraph_a}% @@ -108,12 +101,12 @@ \def\dijk_sanitizegraph#1[#2],% {% - \dijk_ifx{\dijk_quark#1} + \skv_ifx{\dijk_quark#1} {% \dijk_removelastcommainmacro\dijk_graph } {% - \dijk_eearg{\def\dijk_childnodes}{\skv_removeextremespaces{#1}[}% + \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],}% @@ -139,11 +132,11 @@ \def\readgraph_b#1#2[#3]#4,% {% - \dijk_ifx{\dijk_quark#1} + \skv_ifx{\dijk_quark#1} {% - \dijk_exparg{\dijk_foreach\dijk_tempnodename\in}{\dijk_initlistofnodes} + \skv_exparg{\dijk_foreach\dijk_tempnodename\in}{\dijk_initlistofnodes} {% pour chaque sommet - \dijk_eearg{\dijk_foreach\dijk_tempnodechild\in}{\csname dijknode\dijk_tempnodename\endcsname} + \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 @@ -153,7 +146,7 @@ \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 - \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 + \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 @@ -170,11 +163,11 @@ }% }% \dijk_cnt0 - \dijk_exparg{\dijk_foreach\dijk_tempnodename\in}{\dijk_initlistofnodes} + \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 - \dijk_eearg{\dijk_foreach\dijk_tempnodechild\in}{\csname dijknode\dijk_tempnodename\endcsname} + \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,}% @@ -201,15 +194,14 @@ \expandafter\expandafter\expandafter\dijk_nodedist_i\csname dijknode#1\endcsname,#2=1073741823,\_nil% } -\def\removenode#1% +\def\dijk_removenode#1% {% enlève le sommet #1 de la liste des sommets non vus - \dijk_exparg{\dijk_ifinst}{\expandafter,\dijk_nodestoexplore}{,#1,} - {\def\removenode_i##1,#1,##2\_nil{\dijk_exparg{\def\dijk_nodestoexplore}{\dijk_gobarg##1,##2}}% - \expandafter\removenode_i\expandafter,\dijk_nodestoexplore\_nil} + \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} {}% } -\newcount\dijk_cnt \def\dijkstra {% \dijk_ifopt{\dijkstra_i}{\dijkstra_i[]}% @@ -217,12 +209,12 @@ \def\dijkstra_i[#1]#2#3% {% #1=sommet départ #2=sommet arrivée \begingroup - \dijk_ifempty{#1}{}{\setdijk{#1}}% - \let\listofnodes\dijk_initlistofnodes + \skv_ifempty{#1}{}{\setdijk{#1}}% + \let\dijk_listofnodes\dijk_initlistofnodes \let\dijk_nodestoexplore\dijk_initlistofnodes \dijk_cnt0 - \dijk_eearg{\def\dijk_currentnode}{\skv_removeextremespaces{#2}}% - \dijk_eearg{\def\dijk_endnode}{\skv_removeextremespaces{#3}}% + \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 @@ -235,11 +227,11 @@ \noexpand\hline }% \def\dijk_autoamp{\def\dijk_autoamp{\dijk_addtomacro\dijk_tab&}}% - \dijk_exparg{\dijk_foreach\dijk_tempnodename\in}\listofnodes + \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\def{prev_\dijk_tempnodename}{\relax}% les prédecesseurs à \relax + \dijk_cscmd\let{prev_\dijk_tempnodename}\dijk_quark% tous les prédecesseurs à \dijk_eaddtomacro\dijk_tab{\dijk_tempnodename}% peupler 1re ligne du tableau }% \ifboolKV[\dijkname]{show-lastcol} @@ -250,9 +242,9 @@ \dijk_whilenotempty\dijk_nodestoexplore {% \dijk_findmindist\dijk_currentnode% retourne \dijk_currentnode : le sommet enfant ayant la distance la plus faible - \dijk_ifx{\dijk_relax\dijk_currentnode} + \skv_ifx{\dijk_quark\dijk_currentnode} {% si le sommet n'est pas trouvé (graphe non connexe) - \dijk_eearg{\gdef\dijkdist}{\useKV[\dijkname]{infinity-code}}% + \skv_eearg{\gdef\dijkdist}{\useKV[\dijkname]{infinity-code}}% \let\dijk_nodestoexplore\empty% sortir de la boucle } {% @@ -260,13 +252,13 @@ \unless\ifx\dijk_nodestoexplore\empty \dijk_addstep \fi - \dijk_ifx{\dijk_currentnode\dijk_endnode} + \skv_ifx{\dijk_currentnode\dijk_endnode} {% si le sommet de sortie est atteint \let\dijk_nodestoexplore\empty% sortir de la boucle } {% sinon - \dijk_exparg\removenode\dijk_currentnode% enlever ce sommet du graphe à explorer - \dijk_eearg{\dijk_foreach\dijk_temp\in}{\csname listofchilds_\dijk_currentnode\endcsname} + \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,} {% @@ -283,10 +275,9 @@ {\dijk_addtomacro\dijk_tab\hline}% \dijk_addtomacro\dijk_tab{\end{tabular}}% \dijk_eeaddtomacro\dijk_tab{\useKV[\dijkname]{post-tab}}% - \dijk_ifx{\dijk_relax\dijk_currentnode} - {\dijk_eearg{\gdef\dijkpath}{\useKV[\dijkname]{nopath-string}}} - {\dijk_exparg\dijk_createpath\dijk_currentnode}% calculer le chemin sauf s'il est impossible à trouver - \show\dijk_tab + \skv_ifx{\dijk_quark\dijk_currentnode} + {\skv_eearg{\gdef\dijkpath}{\useKV[\dijkname]{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 } @@ -298,18 +289,19 @@ } \def\dijk_createpathi#1% {% #1=sommet en cours - \dijk_eearg{\def\dijk_temp}{\csname prev_#1\endcsname}% - \dijk_ifx{\dijk_relax\dijk_temp} + \skv_eearg{\def\dijk_temp}{\csname prev_#1\endcsname}% + \skv_ifx{\dijk_quark\dijk_temp} {} {\xdef\dijkpath{\dijk_temp\useKV[\dijkname]{path-sep}\dijkpath}% - \dijk_exparg\dijk_createpathi\dijk_temp + \skv_exparg\dijk_createpathi\dijk_temp }% } \def\dijk_findmindist#1% {% trouve dans "sommets à explorer" celui ayant la distance mini - \let\dijk_mindist\dijk_maxint \def#1{\relax}% - \dijk_exparg{\dijk_foreach\dijk_currentnodechildname\in}\dijk_nodestoexplore + \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 @@ -320,7 +312,7 @@ \def\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}}% + \skv_ifx{#1\empty}{}{#2\dijk_whilenotempty#1{#2}}% } \def\dijk_updatedist#1#2% @@ -336,7 +328,7 @@ \def\dijk_addstep {% \def\dijk_autoamp{\def\dijk_autoamp{\dijk_addtomacro\dijk_tab&}}% - \dijk_exparg{\dijk_foreach\dijk_temp\in}\listofnodes + \skv_exparg{\dijk_foreach\dijk_temp\in}\dijk_listofnodes {% \dijk_autoamp \dijk_exptwoargs\dijk_ifinst\dijk_nodestoexplore\dijk_temp @@ -344,9 +336,9 @@ \ifnum\csname dist_\dijk_temp\endcsname=\dijk_maxint\relax \dijk_eeaddtomacro\dijk_tab{\useKV[\dijkname]{infinity-code}}% \else - \dijk_ifx{\dijk_temp\dijk_currentnode}% si c'est le sommet fixé, le mettre en valeur + \skv_ifx{\dijk_temp\dijk_currentnode}% si c'est le sommet fixé, le mettre en valeur {% - \dijk_ifcsname{distwithprev_\dijk_temp} + \skv_ifcsname{distwithprev_\dijk_temp} {% \dijk_eeaddtomacro\dijk_tab{\expandafter\expandafter\expandafter\dijk_highlightnode \csname distwithprev_\dijk_temp\endcsname}% forme \dijk_highlightnode\formatnodewithprev{}{} @@ -425,4 +417,8 @@ Versions : | Version | Date | Changements | |---------+------------+------------------------------------------------------| | 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 | +| | | - petit nettoyage du code | |---------+------------+------------------------------------------------------| \ No newline at end of file -- cgit v1.2.3