% !TeX encoding = UTF-8
% Ce fichier contient le code de l'extension "dijkstra"
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                                                    %
\def\dijkname                   {dijkstra}                           %
\def\dijkver                      {0.13}                             %
%                                                                    %
\def\dijkdate                  {2022/10/01}                          %
%                                                                    %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% --------------------------------------------------------------------
% This work may be distributed and/or modified under the
% 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
%
% %     http://www.latex-project.org/lppl.txt
%
% and version 1.3 or later is part of all distributions of LaTeX
% version 2005/12/01 or later.
% --------------------------------------------------------------------
% This work has the LPPL maintenance status `maintained'.
%
% The Current Maintainer of this work is Christian Tellechea
% 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 :
%   - code               : dijkstra.sty
%   - manuel en français : dijkstra-fr.tex & dijkstra-fr.pdf
%   - fichier lisezmoi   : README
% --------------------------------------------------------------------
%
\csname dijkloadonce\endcsname
\let\dijkloadonce\endinput
\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

\newcount\dijk_nest
\newcount\dijk_cnt
\newif\ifdijk_oriented

\def\dijk_maxint{1073741823}
\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{\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{\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}}%
	\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%
{%
	\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\dijk_nest}\empty
	\global\advance\dijk_nest-1
}%

\def\dijk_foreach_i#1#2,%
{%
	\def#1{#2}%
	\dijk_ifx{\dijk_quark#1}
	{%
	}
	{%
		\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{\dijk_ifempty{##2}}}%
	\dijk_ifinst_i#1#2\_nil
}

\def\readgraph
{%
	\dijk_ifstar{\dijk_orientedtrue\readgraph_a}{\dijk_orientedfalse\readgraph_a}%
}

\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
	\expandafter\readgraph_b\dijk_graph,\dijk_quark[],%
}

\def\dijk_sanitizegraph#1,%
{%
	\expandafter\expandafter\expandafter\dijk_sanitizegraph_i\dijk_stripsp{#1},% bugfix 0.12
}

\def\dijk_sanitizegraph_i#1[#2],%
{%
	\dijk_ifx{\dijk_quark#1}
	{%
		\dijk_removelastcommainmacro\dijk_graph
	}
	{%
		\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],}%
		\dijk_sanitizegraph
	}%
}

\def\dijk_sanitizegraph_ii#1=#2\_nil
{%
	\dijk_eeaddtomacro\dijk_childnodes{\dijk_stripsp{#1}=}%
	\dijk_eaddtomacro\dijk_childnodes{\the\numexpr#2\relax,}%
}

\def\dijk_removelastcommainmacro#1%
{%
	\expandafter\dijk_removelastcommainmacro_i#1\_nil#1%
}

\def\dijk_removelastcommainmacro_i#1,\_nil#2%
{%
	\def#2{#1}%
}

\def\readgraph_b#1#2[#3]#4,%
{%
	\dijk_ifx{\dijk_quark#1}
	{%
		\dijk_exparg{\dijk_foreach\dijk_tempnodename\in}{\dijk_initlistofnodes}
		{% pour chaque sommet
			\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
				{%
				}%
				{%
					\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
					\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
								\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
			}%
		}%
		\dijk_cnt0
		\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
			\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,}%
			}%
		}%
		\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%
{%
	\def#3{#1}\edef#4{\number\numexpr#2\relax}%
}

\def\dijk_nodedist#1#2#3%
{% renvoit la distance du sommet #1 vers #2 dans la macro #3
	\def\dijk_nodedist_i##1#2=##2,##3\_nil{\def#3{##2}}%
	\expandafter\expandafter\expandafter\dijk_nodedist_i\csname dijknode#1\endcsname,#2=1073741823,\_nil%
}

\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\dijk_removenode_i##1,#1,##2\_nil{\dijk_exparg{\def\dijk_nodestoexplore}{\dijk_gobarg##1,##2}}%
		\expandafter\dijk_removenode_i\expandafter,\dijk_nodestoexplore\_nil
	}
	{%
	}%
}

\def\dijkstra
{%
	\dijk_ifopt{\dijkstra_i}{\dijkstra_i[]}%
}
\def\dijkstra_i[#1]#2#3%
{% #1=sommet départ   #2=sommet arrivée
	\begingroup
		\dijk_ifempty{#1}{}{\setdijk{#1}}%
		\let\dijk_listofnodes\dijk_initlistofnodes
		\let\dijk_nodestoexplore\dijk_initlistofnodes
		\dijk_cnt0
		\dijk_eearg{\def\dijk_currentnode}{\dijk_stripsp{#2}}%
		\dijk_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}
							{\noexpand\dijk_last_col_type}
							{}%
						}%
					\noexpand\hline
		}%
		\def\dijk_autoamp{\def\dijk_autoamp{\dijk_addtomacro\dijk_tab&}}%
		\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_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_whilenotempty\dijk_nodestoexplore
		{%
			\dijk_findmindist\dijk_currentnode% retourne \dijk_currentnode : le sommet enfant ayant la distance la plus faible
			\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
			}
			{%
				\xdef\dijkdist{\csname dist_\dijk_currentnode\endcsname}%
				\unless\ifx\dijk_nodestoexplore\empty
					\dijk_addstep
				\fi
				\dijk_ifx{\dijk_currentnode\dijk_endnode}
				{% si le sommet de sortie est atteint
					\let\dijk_nodestoexplore\empty% sortir de la boucle
				}
				{% sinon
					\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}%
							{}%
					}%
					\advance\dijk_cnt1
				}%
			}%
		}%
		\ifboolKV[\dijkname]{h-rules}
			{}
			{\dijk_addtomacro\dijk_tab\hline}%
		\dijk_addtomacro\dijk_tab{\end{tabular}}%
		\dijk_eaddtomacro\dijk_tab{\dijk_post_tab}%
		\dijk_ifx{\dijk_quark\dijk_currentnode}
			{\global\let\dijkpath\dijk_nopath_string}
			{\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
}

\def\dijk_createpath
{%
	\global\let\dijkpath\dijk_currentnode
	\dijk_createpathi
}
\def\dijk_createpathi#1%
{% #1=sommet en cours
	\dijk_eearg{\def\dijk_temp}{\csname prev_#1\endcsname}%
	\dijk_ifx{\dijk_quark\dijk_temp}
	{%
	}
	{%
		\xdef\dijkpath{\dijk_temp\dijk_path_sep\dijkpath}%
		\dijk_exparg\dijk_createpathi\dijk_temp
	}%
}

\def\dijk_findmindist#1%
{% trouve dans "sommets à explorer" celui ayant la distance mini
	\let\dijk_mindist\dijk_maxint
	\let#1\dijk_quark
	\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
			\let#1\dijk_currentnodechildname
		\fi
	}%
}

\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}}%
}

\def\dijk_updatedist#1#2%
{%
	\dijk_nodedist{#1}{#2}\tempdist
	\ifnum\numexpr\csname dist_#1\endcsname+\tempdist\relax<\csname dist_#2\endcsname\relax
		\dijk_cscmd\edef{dist_#2}{\the\numexpr\csname dist_#1\endcsname+\tempdist\relax}%
		\dijk_cscmd\edef{distwithprev_#2}{\noexpand\formatnodewithprev{\the\numexpr\csname dist_#1\endcsname+\tempdist\relax}{\unexpanded{#1}}}%
		\dijk_cscmd\def{prev_#2}{#1}%
	\fi
}

\def\dijk_addstep
{%
	\def\dijk_autoamp{\def\dijk_autoamp{\dijk_addtomacro\dijk_tab&}}%
	\dijk_exparg{\dijk_foreach\dijk_temp\in}\dijk_listofnodes
	{%
		\dijk_autoamp
		\dijk_exptwoargs\dijk_ifinst\dijk_nodestoexplore\dijk_temp
		{%
			\ifnum\csname dist_\dijk_temp\endcsname=\dijk_maxint\relax
				\dijk_eaddtomacro\dijk_tab{\dijk_infinity_code}%
			\else
				\dijk_ifx{\dijk_temp\dijk_currentnode}% si c'est le sommet fixé, le mettre en valeur
				{%
					\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>}
					}
					{%
						\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é
		{}%
	\dijk_addtomacro\dijk_tab{\\}%
	\ifboolKV[\dijkname]{h-rules}
		{\dijk_addtomacro\dijk_tab\hline}
		{}%
}

\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

\def\initdijk{\restoreKV[\dijkname]}

% Macros permettant de modifier les <valeurs> des <clés>
\def\setdijk#{\setKV[\dijkname]}

% ... ainsi que les <valeurs> par défaut
\def\setdijkdefault#{\setKVdefault[\dijkname]}

\newcommand*\formatnodewithprev[2]%
{% #1=distance, #2=nom du noeud de provenance
	$#1_{\mathrm{#2}}$%
}

\newcommand*\highlightnode[2]%
{% #1=distance, #2=nom du noeud de provenance
	$\mathbf{#1}_{\mathrm{\mathbf{#2}}}$%
}

\newcommand*\highlightfirstnode[1]%
{%
	$\mathbf{#1}$%
}

\setdijkdefault{
	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}
	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
	lastcol-label  = sommet fix\'e,
	nopath-string  = Pas de chemin possible,% si chemin impossible
	path-sep       = -,% séparateur entre sommets dans le chemin
}

\endinput

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                            |
|---------+------------+------------------------------------------------------|
|   0.12  | 25/06/2020 | - bugfix : le package est rendu compatible avec la   |
|         |            |   version 0.2 de simplekv                            |
|         |            | - 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                                       |
|---------+------------+------------------------------------------------------|