documentation.tex

\documentclass[a4paper,english,french]{article}

\usepackage[utf8]{inputenc}

\usepackage{amsmath}

\usepackage[T1]{fontenc}
\usepackage{lmodern}

\usepackage{algorithmic}
\usepackage{babel}
\usepackage{graphicx}

\usepackage[np]{numprint}

\usepackage{hyperref}

\hypersetup{pdftitle={Trajectoires}, pdfauthor={Lionel Guez},
  hypertexnames=false}

\newcommand{\Eng}[1]{\textit{\foreignlanguage{english}{#1}}}

% ---------------

\title{Documentation des scripts d'identification de trajectoires}
\author{Lionel GUEZ}

                                %---------------

\begin{document}

\maketitle
\tableofcontents

\section{Divers}

Lorsque plusieurs tourbillons fusionnent ou lorsqu'un tourbillon se
divise, il peut être utile de suivre dans le futur un des tourbillons
issus de la division, ou de suivre dans le passé un des tourbillons
fusionnant, jugé comme tourbillon principal dans l'événement de fusion
ou division. Le graphe des recouvrements est complètement neutre et
objectif sur cette question : il représente toutes les divisions et
fusions par des arcs. On peut donc traiter ce graphe pour
produire des chemins préférentiels dans le graphe, correspondant à des
tourbillons dont on considère qu'ils conservent leur identité à
travers des événements de fusion ou division. On peut aussi décomposer
le graphe en composantes connexes, ou chercher le graphe amont ou aval
à partir d'un noeud du graphe.

Il y a en théorie des graphes ce qu'on appelle une géodésique d'un
graphe : c'est un chemin le plus court sur le graphe, en tenant compte
des poids des arêtes. On peut définir aussi une géodésique maximale :
qui ne peut pas être étendue ni à son origine ni à sa fin. Et il y a
un problème connu en théorie des graphes : celui de la décomposition
d'un graphe en un nombre minimal de géodésiques. Si j'ai bien compris,
c'est un problème difficile et je n'ai pas trouvé d'algorithme tout
prêt.

Des bibliothèques Python de traitement de graphe semblent bien
adaptées pour ces traitements. Les scripts dans le répertoire
\verb+Trajectoires+ créent des trajectoires. Ces trajectoires forment
une liste de chemins qui recouvrent tout le graphe.

Vocabulaire : fusion pour \Eng{merging} et division pour
\Eng{splitting}.

Idée d'une naissance et d'une mort d'un tourbillon, avec une source
(si c'est un défluent), une embouchure (si c'est un affluent). Pour
chaque tourbillon, on peut lister ses défluents non afluents, ses
affluents non défluents et ses défluents-affluents.

Pour lire dans Networkx un graphe de Graph-tool créé par
\verb+segments.py+ ou \verb+cost_function.py+, le passage par le
format GraphML ne marche pas à cause des attributs vecteurs. Passer
par le format GML :
\begin{verbatim}
g_graph_tool.save("my_graph.gml")
g_networkx = nx.read_gml("my_graph.gml", label = "name")
\end{verbatim}

Pour visualiser un graphe de Graph-tool créé par
\verb+segments.py+ ou \verb+cost_function.py+ :
\begin{verbatim}
from graph_tool import draw
draw.graphviz_draw(g, output = "my_graph.gv", layout = "dot",
                   vprops = {"label": g.vp["name"]})
\end{verbatim}
Je n'ai pas réussi à faire marcher \verb+graphviz_draw+ sans
l'argument output. Ou :
\begin{verbatim}
draw.graph_draw(g, vertex_text = g.vp.name,
                vertex_text_position = - 2,
                vertex_text_color = "black")
\end{verbatim}
Ou :
\begin{verbatim}
g.save("my_graph.dot")
\end{verbatim}
et remplacer name par label dans le fichier dot.

Idée : transformer les shapefiles en fichiers Apache Parquet et
Feather. Utiliser Geopandas ? Regarder le format des fichiers dans la
base de données \href{https://www.ncdc.noaa.gov/ibtracs}{IBTracs}.

Mémoire vive nécessaire pour charger le graphe global sur 28 ans, sans
attributs, avec Graph-tool : environ \np{6.1} GiB. Il faut au moins 11
GiB avec Networkx.

\section{Script \texttt{segments.py}}

Définition d'un segment : si un tourbillon se divise, c'est-à-dire si
le degré sortant du noeud correspondant est supérieur à 2, alors le
segment s'arrête à ce noeud inclus ; si un tourbillon est une fusion,
degré entrant du noeud correspondant supérieur à deux, alors un
segment commence à ce noeud. Il n'y a donc ni division ni fusion dans
un segment. Un segment est un chemin maximal dont le premier noeud a
un degré sortant inférieur à 1, les noeuds intérieur sont de degré 2
et le dernier noeud a un degré entrant inférieur à 1. Le degré entrant
du premier noeud d'un segment et le degré sortant du dernier noeud
peuvent être quelconques.

Le graphe des segments est-il un lissage du graphe des tourbillons
instantanés ?

\begin{figure}[htbp]
  \centering
  \includegraphics[height=3cm]{impossible_segment}
  \caption{Graphe de segment impossible.}
  \label{fig:impossible_segment}
\end{figure}
Le graphe sur la figure \ref{fig:impossible_segment} ne peut pas faire
partie d'un graphe des
segments. Cf. \href{../../Overlap/Documentation_texfol/documentation.pdf}{Documentation
  du programme de recherche de recouvrements entre tourbillons
  instantanés}.

La mémoire vive nécessaire augmente à peu près
linéairement avec la taille du graphe lu. La taille du graphe global
sur 28 ans, pour une orientation donnée est de \np{3e7} arêtes. Le
temps d'exécution augmente à peu près linéairement avec le nombre de
noeuds du graphe lu (différent du nombre d'arêtes). Sur Ciclad, comme
d'habitude, les variations de temps sont grandes d'une exécution à
l'autre, d'un noeud d'exécution à
l'autre. Cf. \href{../experiences.ods}{expériences}.

Dans la boucle sur v qui lisse le graphe, le degré de v3 n'est pas
modifié. Le degré sortant de v2 peut être diminué (à 0) si et
seulement si v n'a pas de successeur.

Pour qu'un noeud soit isolé avant son tour dans la boucle, il faut que
dans le graphe initial son degré entrant soit nul. Il faut donc un
segment isolé.

La révision 6f5bb0c1 donne exactement le même résultat que la 787726e0
sur le graphe global 1993-2020.

A segment may be identified by a vertex index in the abstract graph of
segments. The vertex index is defined and used by the graph software,
graph-tool. Is is between 0 and $N - 1$ where $N$ is the number of
vertices in the graph. It appears in the file
\verb+traj_vert_ind.json+ created by script \verb+trajectories.py+.

\section{Script \texttt{cost\_function.py}}

\`A une jonction entre segments (division ou fusion), calcul sur sept
jours avant et après la jonction, pour chaque segment, de moyennes sur
le segment : $\overline{\Delta N_\mathrm{Ro}}$,
$\overline{\Delta N_\mathrm{Bu}}$, $\bar d$ et d'écarts-types sur le
segment : $\sigma_{\Delta N_\mathrm{Ro}}$,
$\sigma_{\Delta N_\mathrm{Bu}}$, $\sigma_d$. Le nombre de Rossby
$N_\mathrm{Ro}$ :
\begin{equation*}
  N_\mathrm{Ro} = \frac{|v|}{R |f|}
\end{equation*}
est calculé sur le contour de vitesse maximale, et le nombre de Burger
$N_\mathrm{Bu}$ :
\begin{equation*}
  N_\mathrm{Bu} = \frac{g A}{R^2 f^2}
\end{equation*}
où $A$ est l'amplitude, est calculé sur le contour extérieur. $d$ est
la distance entre les extremums. Calcul d'une fonction de coût à
partir des grandeurs ci-dessus, analogue à celle de Pegliasco (2015
k0998, équation (1)) qui permet de faire un choix à travers la
jonction. Ou bien utilisation de la fonction de coût de Le Vu (2018
k1000).

En extrayant les $10^6$ premières arêtes dans le graphe des
tourbillons instantanés du domaine global Aviso 1993-2023, les
tourbillons sont étalés sur un an environ. Le graphe des segments
contient environ \np{8e4}
noeuds. Cf. \href{../experiences.ods}{expériences}.

Dans le calcul de \verb+ip_beg+ et \verb+ip_end+, il y a
potentiellement des répétitions de calcul de date pour les mêmes
tourbillons instantanés. Nous aurions pu l'éviter en définissant un
tableau de dates pour le début de segment, que nous aurions ré-utilisé
en partie pour la fin de segment, de la même façon que nous
ré-utilisons le tableau properties. Cela aurait dégradé la lisibilité
de l'algorithme et la différence de performance doit être faible dans
la mesure où le coût de calcul d'une date est faible.

\section{Script \texttt{trajectory.py}}

Les trajectoires sont presque toujours, mais pas toujours, des
géodésiques du graphe. Cf. test Geodesic pour un contre-exemple.

Cf. tableau \ref{tab:trajectory}.
\begin{table}[htbp]
  \centering
  \begin{tabular}{llll}
    Cas & v0.28 & v0.29 & v0.30 \\
    \hline
    Greece\_trajectories & OK & KO & OK \\
    Division\_fusion & KO & OK & OK \\
    Test\_order\_edges & OK & KO & OK \\
    Traj\_component & KO & KO & OK \\
  \end{tabular}
  \caption{Tests du script \texttt{trajectory.py}. KO signifie que les
    trajectoires obtenues par le script ne sont pas satisfaisantes.}
  \label{tab:trajectory}
\end{table}

On peut en principe construire \verb+traj_vert_ind+ à partir de
\verb+traj_prop+ après la boucle sur les noeuds du graphe :
\begin{algorithmic}
  \STATE traj\_vert\_ind = \{\}
  \FOR{n in topology.topological\_sort(g)}
  \IF{traj\_prop[n] in traj\_vert\_ind}
  \STATE traj\_vert\_ind[traj\_prop[n]].append(n)
  \ELSE
  \STATE traj\_vert\_ind[traj\_prop[n]] = [n]
  \ENDIF
  \ENDFOR

  \STATE traj\_vert\_ind = [traj\_vert\_ind[t] for t in
  range(len(traj\_vert\_ind))]
\end{algorithmic}
L'avantage serait de clarifier la première boucle sur les noeuds du
graphe, qui aurait pour seule mission de définir
\verb+traj_prop+. Mais ce serait probablement plus long.

\end{document}