summaryrefslogtreecommitdiff
path: root/Master
diff options
context:
space:
mode:
authorKarl Berry <karl@freefriends.org>2017-09-06 22:09:19 +0000
committerKarl Berry <karl@freefriends.org>2017-09-06 22:09:19 +0000
commit7db74766d509bc4d3983e90a8a713e72fc2b35ea (patch)
treea6a1a1d818a59a670f5ca38e59b4b6295aa90af8 /Master
parent6587e7ce1fe72e0bb5e1e366de980cd60b259621 (diff)
dijkstra (6sep17)
git-svn-id: svn://tug.org/texlive/trunk@45232 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Master')
-rw-r--r--Master/texmf-dist/doc/latex/dijkstra/README21
-rw-r--r--Master/texmf-dist/doc/latex/dijkstra/dijkstra-fr.pdfbin0 -> 370350 bytes
-rw-r--r--Master/texmf-dist/doc/latex/dijkstra/dijkstra-fr.tex434
-rw-r--r--Master/texmf-dist/tex/latex/dijkstra/dijkstra.sty428
-rwxr-xr-xMaster/tlpkg/bin/tlpkg-ctan-check2
-rw-r--r--Master/tlpkg/tlpsrc/collection-mathscience.tlpsrc1
-rw-r--r--Master/tlpkg/tlpsrc/dijkstra.tlpsrc0
7 files changed, 885 insertions, 1 deletions
diff --git a/Master/texmf-dist/doc/latex/dijkstra/README b/Master/texmf-dist/doc/latex/dijkstra/README
new file mode 100644
index 00000000000..cfc74a840b7
--- /dev/null
+++ b/Master/texmf-dist/doc/latex/dijkstra/README
@@ -0,0 +1,21 @@
+___________________________________
+
+ L'extension
+ dijkstra
+
+ v0.1
+
+ 6 sptembre 2017
+___________________________________
+
+Authors : Christian Tellechea
+Maintainer: Christian Tellechea
+E-mail : unbonpetit@netc.fr (CT)
+ Commentaires, signalements de bugs et
+ suggestions bienvenus
+Licence : Released under the LaTeX Project Public License v1.3c or
+ later, see http://www.latex-project.org/lppl.txt
+
+----------------------------------------------------------------------
+
+Dijkstra algorithm for LaTeX
diff --git a/Master/texmf-dist/doc/latex/dijkstra/dijkstra-fr.pdf b/Master/texmf-dist/doc/latex/dijkstra/dijkstra-fr.pdf
new file mode 100644
index 00000000000..6d8eaaa3fb7
--- /dev/null
+++ b/Master/texmf-dist/doc/latex/dijkstra/dijkstra-fr.pdf
Binary files differ
diff --git a/Master/texmf-dist/doc/latex/dijkstra/dijkstra-fr.tex b/Master/texmf-dist/doc/latex/dijkstra/dijkstra-fr.tex
new file mode 100644
index 00000000000..8fab6de12e0
--- /dev/null
+++ b/Master/texmf-dist/doc/latex/dijkstra/dijkstra-fr.tex
@@ -0,0 +1,434 @@
+% !TeX encoding = ISO-8859-1
+% Ceci est la documentation du package "dijkstra"
+%
+% Fichier compilé avec pdflatex
+\documentclass[french,a4paper,10pt]{article}
+\usepackage[latin1]{inputenc}
+\usepackage[T1]{fontenc}
+\usepackage[margin=2cm]{geometry}
+\usepackage[bottom]{footmisc}
+\usepackage{libertine,boites,tikz,enumitem,MnSymbol,babel,xspace,listings,dijkstra}
+\usetikzlibrary{arrows.meta}
+\usepackage[scaled=0.85]{luximono}
+\frenchbsetup{og=«,fg=»}
+\def\eTeX{\hbox{$\varepsilon$-\TeX}}
+\def\DIJK{\texttt{\dijkname}\xspace}
+\makeatletter
+\def\code{\expandafter\code@i\string}
+\def\code@i#1{%
+ \begingroup
+ \par\nobreak\medskip\parindent0pt
+ \leftskip.1\linewidth
+ \catcode`\^^I 13 \begingroup\lccode`\~`\^^I \lowercase{\endgroup\def~{\leavevmode\space\space\space\space}}%
+ \let\do\@makeother \dospecials
+ \ttfamily\small\@noligs
+ \make@car@active\,{\string,{}}%
+ \obeylines\obeyspaces
+ \def\code@ii##1#1{##1\par\medbreak\endgroup}%
+ \code@ii
+}
+\long\def\grab@toks#1\relax{\gdef\right@content{#1}}
+
+\newcommand\disable@lig[1]{%
+ \catcode`#1\active
+ \begingroup
+ \lccode`\~`#1\relax
+ \lowercase{\endgroup\def~{\leavevmode\kern\z@\string#1}}%
+}
+
+\newcommand\make@car@active[1]{%
+ \catcode`#1\active
+ \begingroup
+ \lccode`\~`#1\relax
+ \lowercase{\endgroup\def~}%
+}
+
+\newcommand\exemple{%
+ \begingroup
+ \parskip\z@
+ \exemple@}
+
+\newcommand\exemple@{%
+ \medbreak\noindent
+ \begingroup
+ \let\do\@makeother\dospecials
+ \make@car@active\ { {}}%
+ \make@car@active\^^M{\par\leavevmode}%
+ \make@car@active\^^I{\space\space}%
+ \make@car@active\,{\leavevmode\kern\z@\string,}%
+ \make@car@active\-{\leavevmode\kern\z@\string-}%
+ \make@car@active\>{\leavevmode\kern\z@\string>}%
+ \make@car@active\<{\leavevmode\kern\z@\string<}%
+ \@makeother\;\@makeother\!\@makeother\?\@makeother\:% neutralise frenchb
+ \exemple@@
+}
+
+\newcommand\exemple@@[2][35]{%
+ \xdef\@hparta{0.#1\linewidth}\xdef\@hpartb{0.\number\numexpr95-#1\relax\linewidth}%
+ \def\@tempa##1#2{\exemple@@@{##1}}%
+ \@tempa
+}
+
+\newcommand\exemple@@@[1]{%
+ \xdef\the@code{#1}%
+ \endgroup
+ \begingroup
+ \fboxrule0.4pt \fboxsep=5pt
+ \let\breakboxparindent\z@
+ \def\bkvz@top{\hrule\@height\fboxrule}%
+ \def\bkvz@bottom{\hrule\@height\fboxrule}%
+ \let\bkvz@before@breakbox\relax
+ \def\bkvz@set@linewidth{\advance\linewidth\dimexpr-2\fboxrule-2\fboxsep\relax}%
+ \def\bkvz@left{\vrule\@width\fboxrule\kern\fboxsep}%
+ \def\bkvz@right{\kern\fboxsep\vrule\@width\fboxrule}%
+ \breakbox
+ \kern.5ex\relax
+ \leavevmode$\vcenter{\hsize=\@hparta\relax
+ \ttfamily\small\the@code\par}$%
+ \hfill%\vrule\hfill
+ $\vcenter{\hsize=\@hpartb\relax
+ \newlinechar`\^^M\everyeof{\noexpand}\scantokens{#1}\par}$%
+ \endbreakbox
+ \endgroup
+ \medbreak
+ \endgroup
+}
+\begingroup
+ \catcode`\<13 \catcode`\>13
+ \gdef\verb{\relax\ifmmode\hbox\else\leavevmode\null\fi
+ \bgroup
+ \verb@eol@error \let\do\@makeother \dospecials
+ \verbatim@font\@noligs
+ \catcode`\<13 \catcode`\>13 \def<{\begingroup$\langle$\itshape}\def>{$\rangle$\endgroup}%
+ \@ifstar\@sverb\@verb}
+\endgroup
+\def\longfrdijkdate@i#1/#2/#3\@nil{\number#3\relax\space \ifcase#2 \or janvier\or février\or mars\or avril\or mai\or juin\or juillet\or aout\or septembre\or octobre\or novembre\or décembre\fi\space#1}
+\edef\longfrdijkdate{\expandafter\longfrdijkdate@i\dijkdate\@nil}
+\makeatother
+\begingroup
+ \catcode`\_11
+ \gdef\cleval#1#2{%
+ \bigbreak\noindent
+ \hbox to .25\linewidth{%
+ \color{teal}\bfseries\ttfamily
+ \detokenize{#1}=$\langle$\detokenize{#2}$\rangle$\hss}\kern2.5em
+ (\textit{Défaut} : {\color{teal}\ttfamily
+ \skv_eearg\skv_ifempty{\useKV[\dijkname]{#1}}
+ {$\langle$vide$\rangle$}
+ {"\detokenize\expandafter\expandafter\expandafter{\useKV[\dijkname]{#1}}"}})%
+ \par\nobreak
+ }
+\endgroup
+\begin{document}
+\parindent=0pt
+\thispagestyle{empty}
+\begin{titlepage}
+ \begingroup
+ \centering
+ \null\vskip.25\vsize
+ {\large\bfseries L'extension pour \LaTeX\par \Huge \dijkname\par}%
+ \bigbreak
+ v \dijkver
+ \smallbreak
+ \longfrdijkdate
+ \vskip1.5cm
+ Christian \bsc{Tellechea}\par
+ \texttt{unbonpetit@netc.fr}\par
+ \endgroup
+ \vskip2cm
+ \leftskip=.2\linewidth \rightskip=.2\linewidth \small
+ Cette petite extension met en \oe uvre l'algorithme de Dijkstra pour des graphes pondérés, orientés ou non : le tableau de recherche du plus court chemin peut être affiché, la distance minimale entre deux sommets et le chemin correspondant sont stockés dans des macros.
+\end{titlepage}
+\parindent0pt
+
+\section{Un exemple}
+Dans le graphe \emph{non orienté} suivant, quel est le plus court chemin pour aller de A à F ?
+
+\begin{center}
+ \begin{tikzpicture}[scale=1.75]
+ \begin{scope}[every node/.style={inner sep=1pt,outer sep=0pt,circle,draw}]
+ \node(A) at(0,0) {A}
+ node(B) at(1,1) {B}
+ node(C) at(3,1) {C}
+ node(D) at(1,-1) {D}
+ node(E) at(3,-1) {E}
+ node(F) at(4,0) {F};
+ \end{scope}
+ \begin{scope}[every node/.style={inner sep=0pt,outer sep=2pt,midway,sloped,above}]
+ \footnotesize\bfseries
+ \draw(A)--(B) node{7}
+ (B)--(C) node{12}
+ (C)--(D) node[pos=0.35]{5}
+ (A)--(D) node{15}
+ (D)--(E) node{2}
+ (E)--(F) node{14}
+ (B)--(E) node[pos=0.65]{4}
+ (C)--(F) node{3}
+ (B)--(F) node[pos=.65]{16};
+ \end{scope}
+ \end{tikzpicture}
+\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 :
+
+\code/\readgraph{
+ A [B=7, D=15],
+ B [C=12, E=4, F=16],
+ C [D=5, F=3],
+ D [E=2],
+ 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|».
+
+\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 programmation implémenté dans cette extension exige de plus que ces distances soient des nombres \emph{entiers}.\medbreak
+Une fois que le graphe a été lu, celui-ci est rendu \emph{non orienté} en interne et donc en coulisses, la liste d'adjacence devient
+
+\code/A [B=7, D=15],
+B [A=7, C=12, E=4, F=16],
+C [B=12, D=5, E=3],
+D [A=15, C=5, E=2],
+E [D=2, B=4, F=14],
+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|.
+
+\exemple|\readgraph{
+ A [B=7, D=15],
+ B [C=12, E=4, F=16],
+ C [D=5, F=3],
+ D [E=2],
+ E [F=14]}
+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|.
+
+\section{Graphe non 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}
+ \begin{tikzpicture}[scale=1.75]
+ \begin{scope}[every node/.style={inner sep=1pt,outer sep=0pt,circle,draw}]
+ \node(A) at(0,0) {A}
+ node(B) at(1,1) {B}
+ node(C) at(1,0) {C}
+ node(D) at(1,-1) {D}
+ node(E) at(2,0) {E}
+ node(F) at(3,1) {F}
+ node(G) at(3,-1) {G}
+ node(H) at(4,0) {H};
+ \end{scope}
+ \begin{scope}[-{Stealth[length=7pt,width=5pt,inset=3pt]},every node/.style={inner sep=0pt,outer sep=2pt,midway,sloped,above}]
+ \footnotesize\bfseries
+ \draw(A)--(B) node{5};
+ \draw(A)--(C) node{3};
+ \draw(A)--(D) node{2};
+ \draw(C)--(B)node{1};
+ \draw(D)--(C) node{1};
+ \draw(B)--(F) node {2};
+ \draw(B)--(E) node {2};
+ \draw(D)--(E) node {3};
+ \draw(D)--(G) node{2};
+ \draw(F)--(E) node{4};
+ \draw(E)--(G)node{4};
+ \draw(G)--(F)node{1};
+ \draw(G)--(H)node{8};
+ \draw(F)--(H)node{5};
+
+ \end{scope}
+\end{tikzpicture}
+\end{center}
+
+Cela donne
+\exemple|\readgraph*{
+ A[B=5, C=3, D=2],
+ B[E=2, F=2],
+ C[B=1],
+ D[C=1, E=3, G=2],
+ E[G=4],
+ F[E=4, H=5],
+ G[F=1, H=8]}
+Tableau : \dijkstra{A}{H}\par
+Distance A-H = \dijkdist\par
+Chemin = \dijkpath|
+
+\section{Paramètres}
+\paragraph{Paramètres de \texttt{\char`\\ dijkstra}}
+Des \verb|<paramètres>| peuvent être passés à la macro \verb|\dijkstra| dans son argument optionnel qui prend la forme d'une liste de \verb|<clé>=<valeur>|.
+
+On peut également régler des \verb|<paramètres>| pour toutes les exécutions de la macro \verb|\dijkstra| à venir avec
+\begin{center}
+ \verb|\setdijk{<paramètres>}|
+\end{center}
+mais aussi modifier des \verb|<paramètres>| \emph{par défaut} avec
+\begin{center}
+ \verb|\setdijkdefault{<paramètres>}|
+\end{center}
+
+Voici toutes les \verb|<clés>|, leur \verb|<valeur>| par défaut et leur description.
+
+\cleval{show-tab}{booléen}
+Lorsque cette \verb|<clé>| est \verb|true|, le tableau est affiché par la macro \verb|\dijkstra|. Il ne l'est pas dans le cas contraire.
+
+\cleval{v-position}{texte}
+Ce paramètre est placé dans l'argument optionnel de \verb|\begin{tabular}[<v-position>]| pour spécifier la position que doit avoir le tableau par rapport à la ligne de base.
+
+\cleval{pre-tab}{code}
+Ce \verb|<code>| arbitraire est exécuté juste avant le \verb|\begin{tabular}|.
+
+\cleval{post-tab}{code}
+Ce \verb|<code>| arbitraire est exécuté juste après le \verb|\end{tabular}|.
+
+\cleval{col-type}{code}
+Ce \verb|<code>| est le descripteur des colonnes contenant les sommets.
+
+\cleval{infinity-code}{code}
+Ce \verb|<code>| est exécuté pour exprimer une distance infinie dans le tableau et dans la macro \verb|\dijkdist|.
+
+\cleval{norevisit-code}{code}
+Ce \verb|<code>| est exécuté dans le tableau pour exprimer qu'un sommet a déjà été fixé.
+
+\cleval{h-rules}{booléen}
+Lorsque ce booléen est \verb|true|, les réglures horizontales entre les étapes sont tracées dans le tableau.
+
+\exemple|\readgraph{
+ A [B=7, D=15],
+ B [C=12, E=4, F=16],
+ C [D=5, F=3],
+ D [E=2],
+ E [F=14]}
+Tableau :
+\dijkstra[h-rules=true,
+ v-position=b]{A}{F}|
+
+\cleval{show-lastcol}{booléen}
+Lorsque ce booléen est \verb|true|, une colonne supplémentaire est affichée dans le tableau; cette colonne correspond au sommet fixé.
+
+\cleval{lastcol-type}{code}
+Ce \verb|<code>| est le descripteur de la colonne correspondant au sommets fixés.
+
+\cleval{lastcol-label}{code}
+Ce \verb|<code>| contient le nom de la colonne correspondant aux sommets fixés.
+
+\exemple|\readgraph{
+ A [B=7, D=15],
+ B [C=12, E=4, F=16],
+ C [D=5, F=3],
+ D [E=2],
+ E [F=14]}
+Tableau : \dijkstra[show-lastcol]{A}{F}|
+
+\cleval{nopath-string}{code}
+Ce \verb|<code>| est placé dans la macro \verb|\dijkpath| dans le cas où aucun chemin n'a pu être trouvé, comme cela peut être le cas si le graphe est non connexe.
+
+\exemple|\readgraph{
+ A [B=2],
+ B [C=3],
+ D [E=5]}
+\dijkstra[show-tab=false]{A}{E}% pas d'affichage
+Chemin = \dijkpath\par
+Distance A-E= \dijkdist|
+
+\cleval{path-sep}{code}
+Ce \verb|<code>| est inséré entre chaque sommet dans la macro \verb|\dijkpath|.
+
+\paragraph{Formatage distance/sommet}
+Lorsqu'un sommet a un prédécesseur, la macro \verb|\formatnodewithprev| se charge d'afficher la distance et le sommet. Cette macro prend deux arguments (la \verb|<distance>| et le \verb|<sommet>|) et sa définition par défaut est
+
+\code|\newcommand*\formatnodewithprev[2]%
+{% #1=distance, #2=nom du noeud de provenance
+ $#1_{\mathrm{#2}}$%
+}|
+
+ce qui a pour effet de mettre le sommet de provenance en indice de la distance. On peut redéfinir cette macro pour choisir une autre mise en forme comme ci-dessous où le sommet est placé entre parenthèses.
+
+\exemple|\renewcommand*\formatnodewithprev[2]%
+{%
+ #1 (#2)%
+}
+\readgraph{
+ A [B=7, D=15],
+ B [C=12, E=4, F=16],
+ C [D=5, F=3],
+ D [E=2],
+ E [F=14]}
+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 :
+
+\code|\newcommand*\highlightfirstnode[1]{$\mathbf{#1}$}|
+
+Les autres sommets, lorsqu'ils sont fixés, apparaissent dans le tableau avec leur distance et leur nom et sont traités par la macro \verb|\highlightnode| qui rend deux arguments. Sa définition permet une mise en forme similaire à ce que fait \verb|\formatnodewithprev|, sauf que la distance et le sommet sont en gras:
+
+\code|\newcommand*\highlightnode[2]%
+{% #1=distance, #2=nom du noeud de provenance
+ $\mathbf{#1}_{\mathrm{\mathbf{#2}}}$%
+}|
+
+Pour obtenir d'autre effets, on peut redéfinir ces macros. L'exemple donné n'est pas réaliste tant les effets sont incohérents, c'est simplement un aperçu de ce qu'il est possible de faire :
+
+\exemple|\renewcommand*\highlightfirstnode[1]%
+{%
+ \fboxsep=1pt
+ \fbox{\color{blue}$\mathbf{#1}$}%
+}%
+\renewcommand*\highlightnode[2]%
+{% #1=distance, #2=nom du noeud de provenance
+ \color{red}$#1_\mathrm{#2}$%
+}
+\readgraph{
+ A [B=7, D=15],
+ B [C=12, E=4, F=16],
+ C [D=5, F=3],
+ D [E=2],
+ 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.
+
+\section{Code}
+Le code ci-dessous est l'exact verbatim du fichier \verb|dijkstra.sty| :
+
+\lstinputlisting[
+ language=TeX,
+ moretexcs={unless,ifcsname,ifdefined,detokenize,numexpr,dimexpr,glueexpr,unexpanded},
+ basicstyle=\small\ttfamily\color{black!25},
+ identifierstyle=\bfseries\color{white},%
+ backgroundcolor=\color{black!85},
+ keywordstyle=\bfseries\color{orange},
+ commentstyle=\color{cyan!66},
+ columns=fixed,
+ alsoletter={\_},
+ tabsize=2,
+ extendedchars=true,
+ showspaces=false,
+ showstringspaces=false,
+ numbers=left,
+ numberstyle=\tiny\ttfamily\color{black},
+ breaklines=true,
+ prebreak={\hbox{$\rhookswarrow$}},
+ breakindent=3em,
+ breakautoindent=true,
+ xleftmargin=1em,
+ xrightmargin=0pt,
+ lineskip=0pt,
+ numbersep=1em,
+ classoffset=1,
+ alsoletter={\_},
+ morekeywords={dijkstra,dijkdist,dijkpath,initdijk,setdijk,setdijkdefault,formatnodewithprev,highlightnode,highlightfirstnode},
+ keywordstyle=\bfseries\color{red!85!black},
+ classoffset=0,
+]{dijkstra.sty}
+
+\end{document} \ No newline at end of file
diff --git a/Master/texmf-dist/tex/latex/dijkstra/dijkstra.sty b/Master/texmf-dist/tex/latex/dijkstra/dijkstra.sty
new file mode 100644
index 00000000000..94ee77e7126
--- /dev/null
+++ b/Master/texmf-dist/tex/latex/dijkstra/dijkstra.sty
@@ -0,0 +1,428 @@
+% !TeX encoding = ISO-8859-1
+% Ce fichier contient le code de l'extension "dijkstra"
+%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+% %
+\def\dijkname {dijkstra} %
+\def\dijkver {0.1} %
+% %
+\def\dijkdate {2017/09/06} %
+% %
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%
+% --------------------------------------------------------------------
+% This work may be distributed and/or modified under the
+% conditions of the LaTeX Project Public License, either version 1.3
+% 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
+% 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
+% - manuel en français : dijkstra-fr.tex & dijkstra-fr.pdf
+% - fichier lisezmoi : README
+% --------------------------------------------------------------------
+%
+\ProvidesPackage{dijkstra}[\dijkdate\space v\dijkver\space Dijkstra Algorithm (CT)]
+\NeedsTeXFormat{LaTeX2e}
+\RequirePackage{simplekv}
+
+\expandafter\edef\csname dijk_restorecatcode\endcsname{\expandafter\catcode\number`\_=\number\catcode`\_\relax}
+\catcode`\_11
+\chardef\dijk_stop0
+\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_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}
+
+\newcount\cnt_nest
+\def\dijk_foreach#1\in#2#3%
+{%
+ \global\advance\cnt_nest1
+ \dijk_cscmd\def{dijk_loopcode_\number\cnt_nest}{#3}%
+ \dijk_foreach_i#1#2,\dijk_quark,%
+ \dijk_cscmd\let{dijk_loopcode_\number\cnt_nest}\empty
+ \global\advance\cnt_nest-1
+}%
+
+\def\dijk_foreach_i#1#2,%
+{%
+ \def#1{#2}%
+ \dijk_ifx{\dijk_quark#1}
+ {}
+ {%
+ \dijk_ifx{#1\empty}{}{\csname dijk_loopcode_\number\cnt_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
+}
+
+\newif\ifdijk_oriented
+\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[#2],%
+{%
+ \dijk_ifx{\dijk_quark#1}
+ {%
+ \dijk_removelastcommainmacro\dijk_graph
+ }
+ {%
+ \dijk_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
+ }%
+}
+
+\def\dijk_sanitizegraph_i#1=#2\_nil
+{%
+ \dijk_eeaddtomacro\dijk_childnodes{\skv_removeextremespaces{#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\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}
+ {}%
+}
+
+\newcount\dijk_cnt
+\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\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}}%
+ \edef\dijk_tab{%
+ \unexpanded\expandafter\expandafter\expandafter{\useKV[\dijkname]{pre-tab}}%
+ \noexpand
+ \begin{tabular}[\useKV[\dijkname]{v-position}]{%
+ *{\dijk_numberofnodes}{|c}|%
+ \ifboolKV[\dijkname]{show-lastcol}
+ {\unexpanded\expandafter\expandafter\expandafter{\useKV[\dijkname]{lastcol-type}}}
+ {}%
+ }%
+ \noexpand\hline
+ }%
+ \def\dijk_autoamp{\def\dijk_autoamp{\dijk_addtomacro\dijk_tab&}}%
+ \dijk_exparg{\dijk_foreach\dijk_tempnodename\in}\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_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_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_relax\dijk_currentnode}
+ {% si le sommet n'est pas trouvé (graphe non connexe)
+ \dijk_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
+ \dijk_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}
+ {%
+ \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_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
+ \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_relax\dijk_temp}
+ {}
+ {\xdef\dijkpath{\dijk_temp\useKV[\dijkname]{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 \def#1{\relax}%
+ \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}\listofnodes
+ {%
+ \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
+ \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_eeaddtomacro\dijk_tab{\useKV[\dijkname]{norevisit-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}
+
+\dijk_restorecatcode
+
+\expandafter\let\expandafter\initdijk\csname skv_[\dijkname]\endcsname
+
+% 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 |
+|---------+------------+------------------------------------------------------| \ No newline at end of file
diff --git a/Master/tlpkg/bin/tlpkg-ctan-check b/Master/tlpkg/bin/tlpkg-ctan-check
index 46106b33c96..c269eb85797 100755
--- a/Master/tlpkg/bin/tlpkg-ctan-check
+++ b/Master/tlpkg/bin/tlpkg-ctan-check
@@ -209,7 +209,7 @@ my @TLP_working = qw(
dejavu
delim delimseasy delimset delimtxt denisbdoc dhua
diadia diagbox diagmac2 dialogl diagnose dice dichokey
- dickimaw dictsym diffcoeff digiconfigs din1505
+ dickimaw dictsym diffcoeff digiconfigs dijkstra din1505
dinat dinbrief dingbat directory dirtree dirtytalk disser dithesis
dk-bib dlfltxb
dnaseq dnp doc-pictex docbytex doclicense
diff --git a/Master/tlpkg/tlpsrc/collection-mathscience.tlpsrc b/Master/tlpkg/tlpsrc/collection-mathscience.tlpsrc
index 8f3a9409aca..a2750246675 100644
--- a/Master/tlpkg/tlpsrc/collection-mathscience.tlpsrc
+++ b/Master/tlpkg/tlpsrc/collection-mathscience.tlpsrc
@@ -54,6 +54,7 @@ depend delimset
depend delimseasy
depend diffcoeff
depend digiconfigs
+depend dijkstra
depend drawmatrix
depend drawstack
depend dyntree
diff --git a/Master/tlpkg/tlpsrc/dijkstra.tlpsrc b/Master/tlpkg/tlpsrc/dijkstra.tlpsrc
new file mode 100644
index 00000000000..e69de29bb2d
--- /dev/null
+++ b/Master/tlpkg/tlpsrc/dijkstra.tlpsrc