Reordered blocks in graph view to avoid edge crossing.

6 files changed, 576 insertions, 156 deletions

diff --git a/src/gtkext/graph/cluster-int.h b/src/gtkext/graph/cluster-int.h
index 881a60a..3121d64 100644
--- a/src/gtkext/graph/cluster-int.h
+++ b/src/gtkext/graph/cluster-int.h
@@ -49,21 +49,27 @@ void g_graph_cluster_setup_links(GGraphCluster *);
 /* Organise la disposition d'un ensemble de blocs basiques. */
 void g_graph_cluster_dispatch_x(GGraphCluster *);
 
+/* Détermine une direction préférée pour la suite du bloc. */
+bool g_graph_cluster_get_exit_direction(const GGraphCluster *, const GGraphCluster *, LeavingLinkDir *);
+
+/* Réorganise au besoin les liens sortants d'un bloc. */
+void g_graph_cluster_sort_leaving_links(GGraphCluster *);
+
+/* Calcule les ordonnées extrèmes atteintes via liens sortants. */
+bool g_graph_cluster_compute_min_max_bottom(const GGraphCluster *cluster, gint [2]);
+
+/* Retrouve s'il existe un lien entrant vers un bloc d'origine. */
+const leaving_link_t *g_graph_cluster_has_origin(const GGraphCluster *, const GGraphCluster *);
+
+/* Compare deux clusters selon un de leurs liens d'origine. */
+int g_graph_cluster_compare_by_origin(const GGraphCluster **, const GGraphCluster **, const GGraphCluster *);
+
 /* Réorganise au besoin les liens entrants d'un bloc. */
 void g_graph_cluster_sort_incoming_links(GGraphCluster *);
 
 /* Retrouve l'indice d'un lien entrant donné pour un bloc. */
 size_t g_graph_cluster_find_incoming_link(const GGraphCluster *, const leaving_link_t *);
 
-/* Détermine si un cluster possède un lien sortant. */
-bool g_graph_cluster_has_exit_link(GGraphCluster *, bool *);
-
-/* Compare deux clusters avec lien sortant. */
-int g_graph_cluster_compare_by_exit(const GGraphCluster **, const GGraphCluster **, const bool *);
-
-/* Réordonne les blocs sortant du cluster au mieux. */
-void g_graph_cluster_reorder_exit_blocks(GGraphCluster *);
-
 /* Réordonne les blocs de départ de boucle au mieux. */
 void g_graph_cluster_reorder_loop_blocks(GGraphCluster *);
 
diff --git a/src/gtkext/graph/cluster.c b/src/gtkext/graph/cluster.c
index 5785251..801929e 100644
--- a/src/gtkext/graph/cluster.c
+++ b/src/gtkext/graph/cluster.c
@@ -701,7 +701,6 @@ void g_graph_cluster_setup_links(GGraphCluster *cluster)
         {
             leaving->straight = true;
             leaving->straight_level = target_level;
-            continue;
         }
 
         /* Est-ce une sortie de cluster ? */
@@ -715,10 +714,7 @@ void g_graph_cluster_setup_links(GGraphCluster *cluster)
                     break;
 
             if (k == container->ranks_count)
-            {
                 leaving->cluster_exit = true;
-                continue;
-            }
 
         }
 
@@ -741,7 +737,6 @@ void g_graph_cluster_setup_links(GGraphCluster *cluster)
             {
                 leaving->forced_straight = true;
                 leaving->straight_level = target_level;
-                continue;
             }
 
         }
@@ -911,102 +906,267 @@ void g_graph_cluster_dispatch_x(GGraphCluster *cluster)
 
 /******************************************************************************
 *                                                                             *
-*  Paramètres  : cluster = graphique de blocs à manipuler.                    *
+*  Paramètres  : cluster = graphique de blocs à analyser.                     *
+*                root    = élément à ne jamais croiser dans la paternité.     *
+*                dir     = préférence à actualiser si possible. [OUT]         *
 *                                                                             *
-*  Description : Réorganise au besoin les liens entrants d'un bloc.           *
+*  Description : Détermine une direction préférée pour la suite du bloc.      *
 *                                                                             *
-*  Retour      : -                                                            *
+*  Retour      : false si une incapacité de détermination a été rencontrée.   *
 *                                                                             *
 *  Remarques   : -                                                            *
 *                                                                             *
 ******************************************************************************/
 
-void g_graph_cluster_sort_incoming_links(GGraphCluster *cluster)
+bool g_graph_cluster_get_exit_direction(const GGraphCluster *cluster, const GGraphCluster *root, LeavingLinkDir *dir)
 {
-    size_t i;                               /* Boucle de parcours          */
+    bool result;                            /* Bilan à renvoyer            */
+    size_t i;                               /* Boucle de parcours #1       */
+    const leaving_link_t *leaving;          /* Lien sortant à traiter      */
+    GGraphCluster *iter;                    /* Boucle de parcours #2       */
+    LeavingLinkDir pref;                    /* Préférence du lien courant  */
 
-    qsort(cluster->top_anchors, cluster->ta_count, sizeof(incoming_link_t *), (__compar_fn_t)cmp_incoming_links);
+    result = true;
 
-    for (i = 0; i < cluster->ranks_count; i++)
-        sort_graph_rank_incoming_links(&cluster->ranks[i]);
+    for (i = 0; i < cluster->ba_count && result; i++)
+    {
+        leaving = cluster->bottom_anchors[i];
 
-    sort_incoming_links_for_vspace_manager(&cluster->self);
+        if (!leaving->cluster_exit)
+            continue;
+
+        /* Validation d'une sortie du cluster d'origine */
+
+        for (iter = leaving->other->owner; iter != NULL; iter = iter->owner)
+            if (iter == root)
+                break;
+
+        if (iter != NULL)
+            continue;
+
+        pref = get_leaving_link_direction(leaving);
+
+        /* Si la direction est claire... */
+        if (*dir == LLD_NO_PREF)
+            *dir = pref;
+
+        /* Multiples directions, on ne sait pas trancher ! */
+        else if (*dir != pref)
+            result = false;
+
+    }
+
+    for (i = 0; i < cluster->ranks_count && result; i++)
+        result = get_graph_rank_exit_direction(&cluster->ranks[i], root, dir);
+
+    return result;
 
 }
 
 
 /******************************************************************************
 *                                                                             *
-*  Paramètres  : cluster  = graphique de blocs à consulter.                   *
-*                incoming = adresse de l'autre bout du lien concerné.         *
+*  Paramètres  : cluster = graphique de blocs à manipuler.                    *
 *                                                                             *
-*  Description : Retrouve l'indice d'un lien entrant donné pour un bloc.      *
+*  Description : Réorganise au besoin les liens sortants d'un bloc.           *
 *                                                                             *
-*  Retour      : Indice à priori toujours valide.                             *
+*  Retour      : -                                                            *
 *                                                                             *
 *  Remarques   : -                                                            *
 *                                                                             *
 ******************************************************************************/
 
-size_t g_graph_cluster_find_incoming_link(const GGraphCluster *cluster, const leaving_link_t *leaving)
+void g_graph_cluster_sort_leaving_links(GGraphCluster *cluster)
 {
-    size_t result;                          /* Indice à retourner          */
+    size_t i;                               /* Boucle de parcours          */
+    leaving_link_t **left;                  /* Liens à placer à gauche     */
+    leaving_link_t **center;                /* Liens à placer au milieu    */
+    leaving_link_t **right;                 /* Liens à placer à droite     */
+    size_t left_count;                      /* Quantité de liens à gauche  */
+    size_t center_count;                    /* Quantité de liens au milieu */
+    size_t right_count;                     /* Quantité de liens à droite  */
+    leaving_link_t *leaving;                /* Lien sortant à traiter      */
+    LeavingLinkDir pref;                    /* Préférence du lien courant  */
 
-    for (result = 0; result < cluster->ta_count; result++)
-        if (cluster->top_anchors[result]->other == leaving)
-            break;
+    /**
+     * On n'intervient que s'il y a lieu de le faire, notamment si les sorties
+     * du groupe de blocs ont une direction claire.
+     */
 
-    assert(cluster->ta_count);
+    pref = LLD_NO_PREF;
 
-    return result;
+    if (!g_graph_cluster_get_exit_direction(cluster, cluster, &pref))
+        goto done;
+
+    if (cluster->ba_count < 2 || pref == LLD_NO_PREF)
+        goto done;
+
+    left = NULL;
+    center = NULL;
+    right = NULL;
+
+    left_count = 0;
+    center_count = 0;
+    right_count = 0;
+
+    /* Réorganisation des liens */
+
+    for (i = 0; i < cluster->ba_count; i++)
+    {
+        leaving = cluster->bottom_anchors[i];
+
+        if (SHOULD_BE_VERTICAL(leaving))
+        {
+            if (leaving->cluster_exit)
+                pref = get_leaving_link_direction(leaving);
+
+            else
+                pref = LLD_NO_PREF;
+
+        }
+        else
+        {
+            pref = LLD_NO_PREF;
+
+            if (!g_graph_cluster_get_exit_direction(leaving->other->owner, leaving->other->owner, &pref))
+                pref = LLD_NO_PREF;
+
+        }
+
+        switch (pref)
+        {
+            case LLD_TO_LEFT:
+                left = realloc(left, ++left_count * sizeof(leaving_link_t *));
+                left[left_count - 1] = leaving;
+                break;
+
+            case LLD_NO_PREF:
+                center = realloc(center, ++center_count * sizeof(leaving_link_t *));
+                center[center_count - 1] = leaving;
+                break;
+
+            case LLD_TO_RIGHT:
+                right = realloc(right, ++right_count * sizeof(leaving_link_t *));
+                right[right_count - 1] = leaving;
+                break;
+
+        }
+
+    }
+
+    /* Sauvegarde du nouvel arrangement */
+
+    assert((left_count + center_count + right_count) == cluster->ba_count);
+
+    cluster->ba_count = 0;
+
+    if (left != NULL)
+    {
+        qsort_r(left, left_count, sizeof(leaving_link_t *),
+                (__compar_d_fn_t)cmp_leaving_links,
+                (LeavingLinkDir []) { LLD_TO_LEFT });
+
+        for (i = 0; i < left_count; i++)
+            cluster->bottom_anchors[cluster->ba_count++] = left[i];
+
+        free(left);
+
+    }
+
+    if (center != NULL)
+    {
+        for (i = 0; i < center_count; i++)
+            cluster->bottom_anchors[cluster->ba_count++] = center[i];
+
+        free(center);
+
+    }
+
+    if (right != NULL)
+    {
+        qsort_r(right, right_count, sizeof(leaving_link_t *),
+                (__compar_d_fn_t)cmp_leaving_links,
+                (LeavingLinkDir []) { LLD_TO_RIGHT });
+
+        for (i = 0; i < right_count; i++)
+            cluster->bottom_anchors[cluster->ba_count++] = right[i];
+
+        free(right);
+
+    }
+
+    assert((left_count + center_count + right_count) == cluster->ba_count);
+
+    for (i = 0; i < cluster->ba_count; i++)
+        cluster->bottom_anchors[i]->index = i;
+
+    /* Application de la nouvelle disposition */
+
+    for (i = 0; i < cluster->ranks_count; i++)
+        reorder_graph_rank_clusters(&cluster->ranks[i], cluster);
+
+    for (i = 0; i < cluster->ranks_count; i++)
+        reset_graph_rank_allocation(&cluster->ranks[i]);
+
+    for (i = 0; i < cluster->ranks_count; i++)
+        offset_x_graph_rank(&cluster->ranks[i], cluster->alloc.x);
+
+    g_graph_cluster_dispatch_x(cluster);
+
+    g_graph_cluster_set_y(cluster, cluster->alloc.y);
+
+ done:
+
+    for (i = 0; i < cluster->ranks_count; i++)
+        visit_graph_rank(&cluster->ranks[i], g_graph_cluster_sort_leaving_links);
 
 }
 
 
 /******************************************************************************
 *                                                                             *
-*  Paramètres  : cluster = graphique de blocs à analyser.                     *
-*                l2r     = indique si le lien trouvé part vers à droite. [OUT]*
+*  Paramètres  : cluster = graphique de blocs à consulter.                    *
+*                pos     = ordonnées minimale et maximale en bout. [OUT]      *
 *                                                                             *
-*  Description : Détermine si un cluster possède un lien sortant.             *
+*  Description : Calcule les ordonnées extrèmes atteintes via liens sortants. *
 *                                                                             *
-*  Retour      : true si le chef de file à un lien qui sort de l'ensemble.    *
+*  Retour      : true si un lien sortant a été trouvé, false sinon.           *
 *                                                                             *
 *  Remarques   : -                                                            *
 *                                                                             *
 ******************************************************************************/
 
-bool g_graph_cluster_has_exit_link(GGraphCluster *cluster, bool *l2r)
+bool g_graph_cluster_compute_min_max_bottom(const GGraphCluster *cluster, gint pos[2])
 {
     bool result;                            /* Bilan à retourner           */
     size_t i;                               /* Boucle de parcours          */
-    leaving_link_t *leaving;                /* Lien manipulé               */
-    gint x1;                                /* Abscisse de départ de lien  */
-    size_t idx;                             /* Indice du lien entrant      */
-    gint x2;                                /* Abscisse d'arrivée de lien  */
+    const leaving_link_t *leaving;          /* Lien sortant à traiter      */
+    gint y;                                 /* Ordonnée rencontrée         */
 
     result = false;
 
-    for (i = 0; i < cluster->ba_count && !result; i++)
+    for (i = 0; i < cluster->ba_count; i++)
     {
         leaving = cluster->bottom_anchors[i];
 
-        if (leaving->cluster_exit)
-        {
-            result = true;
-
-            x1 = compute_leaving_link_position(leaving);
+        if (!leaving->cluster_exit)
+            continue;
 
-            idx = g_graph_cluster_find_incoming_link(leaving->other->owner, leaving);
+        result = true;
 
-            x2 = g_graph_cluster_compute_incoming_link_position(leaving->other->owner, idx);
+        y = leaving->other->owner->alloc.y;
 
-            *l2r = (x1 < x2);
+        if (y < pos[0])
+            pos[0] = y;
 
-        }
+        if (pos[1] < y)
+            pos[1] = y;
 
     }
 
+    for (i = 0; i < cluster->ranks_count; i++)
+        result |= compute_graph_rank_min_max_bottom(&cluster->ranks[i], pos);
+
     return result;
 
 }
@@ -1014,69 +1174,75 @@ bool g_graph_cluster_has_exit_link(GGraphCluster *cluster, bool *l2r)
 
 /******************************************************************************
 *                                                                             *
-*  Paramètres  : cluster = premier graphique de blocs à analyser.             *
-*                other   = second graphique de blocs à analyser.              *
-*                l2r     = indique si le lien trouvé part vers à droite.      *
+*  Paramètres  : cluster = graphique de blocs à analyser.                     *
+*                origin  = cluster d'origine à considérer.                    *
 *                                                                             *
-*  Description : Compare deux clusters avec lien sortant.                     *
+*  Description : Retrouve s'il existe un lien entrant vers un bloc d'origine. *
 *                                                                             *
-*  Retour      : Bilan de la comparaison.                                     *
+*  Retour      : Lien vers le bloc d'origine trouvé ou NULL.                  *
 *                                                                             *
 *  Remarques   : -                                                            *
 *                                                                             *
 ******************************************************************************/
 
-int g_graph_cluster_compare_by_exit(const GGraphCluster **cluster, const GGraphCluster **other, const bool *l2r)
+const leaving_link_t *g_graph_cluster_has_origin(const GGraphCluster *cluster, const GGraphCluster *origin)
 {
-    int result;                             /* Bilan à renvoyer            */
+    const leaving_link_t *result;           /* Lien trouvé à renvoyer      */
     size_t i;                               /* Boucle de parcours          */
-    gint cluster_y;                         /* Position de la sortie #0    */
-    gint other_y;                           /* Position de la sortie #1    */
-    leaving_link_t *leaving;                /* Lien manipulé               */
 
-    cluster_y = 0;
-    other_y = 0;
+    result = NULL;
 
-    for (i = 0; i < (*cluster)->ba_count; i++)
-    {
-        leaving = (*cluster)->bottom_anchors[i];
+    for (i = 0; i < cluster->ta_count && result == NULL; i++)
+        if (cluster->top_anchors[i]->other->owner == origin)
+            result = cluster->top_anchors[i]->other;
 
-        if (leaving->cluster_exit)
-        {
-            cluster_y = leaving->other->owner->alloc.y;
-            break;
-        }
+    return result;
 
-    }
+}
 
-    assert(i < (*cluster)->ba_count);
 
-    for (i = 0; i < (*other)->ba_count; i++)
-    {
-        leaving = (*other)->bottom_anchors[i];
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : cluster = premier graphique de blocs à analyser.             *
+*                other   = second graphique de blocs à analyser.              *
+*                origin  = cluster d'origine à considérer.                    *
+*                                                                             *
+*  Description : Compare deux clusters selon un de leurs liens d'origine.     *
+*                                                                             *
+*  Retour      : Bilan de la comparaison.                                     *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
 
-        if (leaving->cluster_exit)
-        {
-            other_y = leaving->other->owner->alloc.y;
-            break;
-        }
+int g_graph_cluster_compare_by_origin(const GGraphCluster **cluster, const GGraphCluster **other, const GGraphCluster *origin)
+{
+    int result;                             /* Bilan à renvoyer            */
+    const leaving_link_t *leaving;          /* Accès au lien manipulé      */
+    gint x0;                                /* Première abscisse à traiter */
+    gint x1;                                /* Seconde abscisse à traiter  */
 
-    }
+    leaving = g_graph_cluster_has_origin(*cluster, origin);
+
+    assert(leaving != NULL);
+
+    x0 = compute_leaving_link_position(leaving);
+
+    leaving = g_graph_cluster_has_origin(*other, origin);
+
+    assert(leaving != NULL);
 
-    assert(i < (*other)->ba_count);
+    x1 = compute_leaving_link_position(leaving);
 
-    if (cluster_y < other_y)
+    if (x0 < x1)
         result = -1;
 
-    else if (cluster_y > other_y)
+    else if (x0 > x1)
         result = 1;
 
     else
         result = 0;
 
-    if (*l2r)
-        result *= -1;
-
     return result;
 
 }
@@ -1084,9 +1250,9 @@ int g_graph_cluster_compare_by_exit(const GGraphCluster **cluster, const GGraphC
 
 /******************************************************************************
 *                                                                             *
-*  Paramètres  : cluster = graphique de blocs à actualiser.                   *
+*  Paramètres  : cluster = graphique de blocs à manipuler.                    *
 *                                                                             *
-*  Description : Réordonne les blocs sortant du cluster au mieux.             *
+*  Description : Réorganise au besoin les liens entrants d'un bloc.           *
 *                                                                             *
 *  Retour      : -                                                            *
 *                                                                             *
@@ -1094,12 +1260,44 @@ int g_graph_cluster_compare_by_exit(const GGraphCluster **cluster, const GGraphC
 *                                                                             *
 ******************************************************************************/
 
-void g_graph_cluster_reorder_exit_blocks(GGraphCluster *cluster)
+void g_graph_cluster_sort_incoming_links(GGraphCluster *cluster)
 {
     size_t i;                               /* Boucle de parcours          */
 
+    qsort(cluster->top_anchors, cluster->ta_count, sizeof(incoming_link_t *), (__compar_fn_t)cmp_incoming_links);
+
     for (i = 0; i < cluster->ranks_count; i++)
-        reorder_graph_rank_exit_blocks(&cluster->ranks[i]);
+        sort_graph_rank_incoming_links(&cluster->ranks[i]);
+
+    sort_incoming_links_for_vspace_manager(&cluster->self);
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : cluster  = graphique de blocs à consulter.                   *
+*                incoming = adresse de l'autre bout du lien concerné.         *
+*                                                                             *
+*  Description : Retrouve l'indice d'un lien entrant donné pour un bloc.      *
+*                                                                             *
+*  Retour      : Indice à priori toujours valide.                             *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+size_t g_graph_cluster_find_incoming_link(const GGraphCluster *cluster, const leaving_link_t *leaving)
+{
+    size_t result;                          /* Indice à retourner          */
+
+    for (result = 0; result < cluster->ta_count; result++)
+        if (cluster->top_anchors[result]->other == leaving)
+            break;
+
+    assert(result < cluster->ta_count);
+
+    return result;
 
 }
 
@@ -2256,6 +2454,25 @@ GGraphCluster *bootstrap_graph_cluster(GLoadedBinary *binary, const GBlockList *
     g_graph_cluster_dispatch_x(result);
 
     /**
+     * Une première passe d'organisation horizontale est réalisée.
+     *
+     * A ce point, en proposant des emplacements verticaux en complément,
+     * on est en mesure de déterminer si les liens qui sortent de leur
+     * conteneur vont en croiser d'autres.
+     *
+     * On réorganise ainsi au besoin les différents blocs pour éviter ce cas
+     * de figure. Les blocs sont replacés à une nouvelle position horizontale
+     * au besoin.
+     *
+     * Une illustration concrête de la nécessité de cette opération est la
+     * fonction test_ite_2() de la suite de tests.
+     */
+
+    g_graph_cluster_set_y(result, 0);
+
+    g_graph_cluster_sort_leaving_links(result);
+
+    /**
      * A ce point, tous les blocs sont placés.
      * On est donc en mesure de réorganiser les points d'arrivée
      * des liens afin d'éviter les croisements : un lien qui vient
@@ -2272,21 +2489,6 @@ GGraphCluster *bootstrap_graph_cluster(GLoadedBinary *binary, const GBlockList *
     g_graph_cluster_sort_incoming_links(result);
 
     /**
-     * Comme des profondeurs de rang identiques peuvent renvoyer à des
-     * positions verticales différentes selon les chemins présents,
-     * on lance ici une réorganisation des blocs qui ont une sortie fuyante
-     * de leur ensemble parent en plaçant, même de façon parcellaire, l'ensemble
-     * des blocs.
-     *
-     * Une illustration concrête de cette nécessité est la fonction test_ite_2()
-     * de la suite de tests.
-     */
-
-    g_graph_cluster_set_y(result, 0);
-
-    g_graph_cluster_reorder_exit_blocks(result);
-
-    /**
      * Même s'ils ne sont pas encore entièrement tracés, les liens de boucle
      * voient désormais leurs positions d'arrivée et de départ définies.
      *
diff --git a/src/gtkext/graph/leaving.c b/src/gtkext/graph/leaving.c
index ad07f04..3147784 100644
--- a/src/gtkext/graph/leaving.c
+++ b/src/gtkext/graph/leaving.c
@@ -24,6 +24,7 @@
 #include "leaving.h"
 
 
+#include <assert.h>
 #include <malloc.h>
 
 
@@ -105,3 +106,126 @@ gint compute_leaving_link_position(const leaving_link_t *link)
     return result;
 
 }
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : link = information sur un lien à consulter.                  *
+*                                                                             *
+*  Description : Détermine une direction prise par un lien à son départ.      *
+*                                                                             *
+*  Retour      : Direction prise à l'écran.                                   *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+LeavingLinkDir get_leaving_link_direction(const leaving_link_t *link)
+{
+    LeavingLinkDir result;                  /* Préférence à retourner      */
+    gint x1;                                /* Abscisse de départ de lien  */
+    GGraphCluster *owner;                   /* Raccourci vers le proprio   */
+    size_t idx;                             /* Indice du lien entrant      */
+    gint x2;                                /* Abscisse d'arrivée de lien  */
+
+    x1 = compute_leaving_link_position(link);
+
+    owner = link->other->owner;
+
+    idx = g_graph_cluster_find_incoming_link(owner, link);
+
+    x2 = g_graph_cluster_compute_incoming_link_position(owner, idx);
+
+    if (x1 < x2)
+        result = LLD_TO_RIGHT;
+
+    else if (x1 > x2)
+        result = LLD_TO_LEFT;
+
+    else
+        result = LLD_NO_PREF;
+
+    return result;
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : a   = premier lien entrant à comparer.                       *
+*                b   = second lien entrant à comparer.                        *
+*                dir = complément d'information quant à la direction traitée. *
+*                                                                             *
+*  Description : Compare deux liens sortants.                                 *
+*                                                                             *
+*  Retour      : Bilan de comparaison.                                        *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+int cmp_leaving_links(const leaving_link_t **a, const leaving_link_t **b, const LeavingLinkDir *dir)
+{
+    int result;                             /* Bilan à retourner           */
+    GGraphCluster *owner;                   /* Raccourci vers le proprio   */
+    gint pos_a[2];                          /* Points de départ pour A     */
+    GtkAllocation alloc;                    /* Emplacement de cluster      */
+    gint pos_b[2];                          /* Points de départ pour B     */
+
+    /* Calcul des ordonnées des points de chute */
+
+    owner = (*a)->other->owner;
+
+    pos_a[0] = G_MAXINT;
+    pos_a[1] = 0;
+
+    if (!g_graph_cluster_compute_min_max_bottom(owner, pos_a))
+    {
+        g_graph_cluster_get_allocation(owner, &alloc);
+
+        pos_a[0] = alloc.y;
+        pos_a[1] = alloc.y;
+
+    }
+
+    owner = (*b)->other->owner;
+
+    pos_b[0] = G_MAXINT;
+    pos_b[1] = 0;
+
+    if (!g_graph_cluster_compute_min_max_bottom(owner, pos_b))
+    {
+        g_graph_cluster_get_allocation(owner, &alloc);
+
+        pos_b[0] = alloc.y;
+        pos_b[1] = alloc.y;
+
+    }
+
+    /* Comparaison */
+
+    if (pos_a[1] < pos_b[1])
+        result = -1;
+
+    else if (pos_a[1] > pos_b[1])
+        result = 1;
+
+    else
+    {
+        if (pos_a[0] < pos_b[0])
+            result = -1;
+
+        else if (pos_a[0] > pos_b[0])
+            result = 1;
+
+        else
+            result = 0;
+
+    }
+
+    if (*dir == LLD_TO_RIGHT)
+        result *= -1;
+
+    return result;
+
+}
diff --git a/src/gtkext/graph/leaving.h b/src/gtkext/graph/leaving.h
index c91f232..b81e1ca 100644
--- a/src/gtkext/graph/leaving.h
+++ b/src/gtkext/graph/leaving.h
@@ -61,6 +61,21 @@ void delete_leaving_link(leaving_link_t *);
 /* Calcule l'abscisse d'un lien à son départ d'un bloc. */
 gint compute_leaving_link_position(const leaving_link_t *);
 
+/* Direction prise par le lien */
+typedef enum _LeavingLinkDir
+{
+    LLD_NO_PREF,                            /* Direction variable          */
+    LLD_TO_LEFT,                            /* Vers la gauche              */
+    LLD_TO_RIGHT,                           /* Vers la droite              */
+
+} LeavingLinkDir;
+
+/* Détermine une direction prise par un lien à son départ. */
+LeavingLinkDir get_leaving_link_direction(const leaving_link_t *);
+
+/* Compare deux liens sortants. */
+int cmp_leaving_links(const leaving_link_t **, const leaving_link_t **, const LeavingLinkDir *);
+
 
 
 #endif  /* _GTKEXT_GRAPH_LEAVING_H */
diff --git a/src/gtkext/graph/rank.c b/src/gtkext/graph/rank.c
index 0fadb27..bffefe9 100644
--- a/src/gtkext/graph/rank.c
+++ b/src/gtkext/graph/rank.c
@@ -104,6 +104,28 @@ void exit_graph_rank(graph_rank_t *grank)
 *                                                                             *
 *  Paramètres  : grank = ensemble de même rang à consulter.                   *
 *                                                                             *
+*  Description : Parcours l'ensemble des blocs du rang avec un visiteur.      *
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+void visit_graph_rank(const graph_rank_t *grank, graph_rank_cb cb)
+{
+    size_t i;                               /* Boucle de parcours          */
+
+    for (i = 0; i < grank->count; i++)
+        cb(grank->clusters[i]);
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : grank = ensemble de même rang à consulter.                   *
+*                                                                             *
 *  Description : Assigne à un ensemble de blocs un emplacement initial.       *
 *                                                                             *
 *  Retour      : -                                                            *
@@ -494,24 +516,29 @@ void dispatch_x_graph_rank(const graph_rank_t *grank)
 
 /******************************************************************************
 *                                                                             *
-*  Paramètres  : grank  = ensemble de blocs de même rang à actualiser.        *
+*  Paramètres  : grank = ensemble de blocs de même rang à actualiser.         *
+*                root  = élément à ne jamais croiser dans la paternité.       *
+*                dir   = préférence à actualiser si possible. [OUT]           *
 *                                                                             *
 *  Description : Réorganise au besoin les liens entrants un ensemble de blocs.*
 *                                                                             *
-*  Retour      : -                                                            *
+*  Retour      : false si une incapacité de détermination a été rencontrée.   *
 *                                                                             *
 *  Remarques   : -                                                            *
 *                                                                             *
 ******************************************************************************/
 
-void sort_graph_rank_incoming_links(graph_rank_t *grank)
+bool get_graph_rank_exit_direction(graph_rank_t *grank, const GGraphCluster *root, LeavingLinkDir *dir)
 {
+    bool result;                            /* Bilan à renvoyer            */
     size_t i;                               /* Boucle de parcours          */
 
-    for (i = 0; i < grank->count; i++)
-        g_graph_cluster_sort_incoming_links(grank->clusters[i]);
+    result = true;
 
-    sort_incoming_links_for_vspace_manager(&grank->vspaces);
+    for (i = 0; i < grank->count && result; i++)
+        result = g_graph_cluster_get_exit_direction(grank->clusters[i], root, dir);
+
+    return result;
 
 }
 
@@ -519,8 +546,37 @@ void sort_graph_rank_incoming_links(graph_rank_t *grank)
 /******************************************************************************
 *                                                                             *
 *  Paramètres  : grank = ensemble de blocs de même rang à actualiser.         *
+*                pos   = ordonnées minimale et maximale en bout. [OUT]        *
+*                                                                             *
+*  Description : Calcule les ordonnées extrèmes atteintes via liens sortants. *
 *                                                                             *
-*  Description : Réordonne les blocs sortant d'un ensemble.                   *
+*  Retour      : true si un lien sortant a été trouvé, false sinon.           *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+bool compute_graph_rank_min_max_bottom(const graph_rank_t *grank, gint pos[2])
+{
+    bool result;                            /* Bilan à renvoyer            */
+    size_t i;                               /* Boucle de parcours          */
+
+    result = false;
+
+    for (i = 0; i < grank->count; i++)
+        result |= g_graph_cluster_compute_min_max_bottom(grank->clusters[i], pos);
+
+    return result;
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : grank  = ensemble de blocs de même rang à actualiser.        *
+*                origin = cluster d'origine à considérer.                     *
+*                                                                             *
+*  Description : Réorganise au besoin les blocs selon les liens d'origine.    *
 *                                                                             *
 *  Retour      : -                                                            *
 *                                                                             *
@@ -528,64 +584,69 @@ void sort_graph_rank_incoming_links(graph_rank_t *grank)
 *                                                                             *
 ******************************************************************************/
 
-void reorder_graph_rank_exit_blocks(graph_rank_t *grank)
+void reorder_graph_rank_clusters(graph_rank_t *grank, const GGraphCluster *origin)
 {
-    GGraphCluster **exit_2_left;            /* Liste avec sortie à gauche  */
-    GGraphCluster **exit_2_right;           /* Liste avec sortie à droite  */
-    GGraphCluster **no_exit;                /* Liste sans sortie           */
-    size_t count_2_left;                    /* Quantité de présents        */
-    size_t count_2_right;                   /* Quantité de présents        */
-    size_t count_no;                        /* Quantité de présents        */
     size_t i;                               /* Boucle de parcours          */
-    bool l2r;                               /* Détermination de catégorie  */
+    GGraphCluster **filtered;               /* Blocs à réorganiser         */
+    size_t fcount;                          /* Nombre de ces blocs         */
+    size_t next;                            /* Prochain indice à réinsérer */
 
     if (grank->count > 1)
     {
-        exit_2_left = malloc(grank->count * sizeof(GGraphCluster *));
-        exit_2_right = malloc(grank->count * sizeof(GGraphCluster *));
-        no_exit = malloc(grank->count * sizeof(GGraphCluster *));
+        /**
+         * On prend garde de ne déplacer que les blocs avec un lien concernant
+         * un bloc d'origine, dont les liens au départ ont été réorganisés.
+         */
 
-        count_2_left = 0;
-        count_2_right = 0;
-        count_no = 0;
+        filtered = malloc(grank->count * sizeof(GGraphCluster *));
+        fcount = 0;
 
         for (i = 0; i < grank->count; i++)
-        {
-            if (g_graph_cluster_has_exit_link(grank->clusters[i], &l2r))
+            if (g_graph_cluster_has_origin(grank->clusters[i], origin) != NULL)
             {
-                if (l2r)
-                    exit_2_right[count_2_right++] = grank->clusters[i];
-                else
-                    exit_2_left[count_2_left++] = grank->clusters[i];
+                filtered[fcount++] = grank->clusters[i];
+                grank->clusters[i] = NULL;
             }
-            else
-                no_exit[count_no++] = grank->clusters[i];
 
-        }
+        qsort_r(filtered, fcount, sizeof(GGraphCluster *),
+                (__compar_d_fn_t)g_graph_cluster_compare_by_origin, (void *)origin);
 
-        assert((count_2_left + count_2_right + count_no) == grank->count);
+        next = 0;
 
-        qsort_r(exit_2_left, count_2_left, sizeof(GGraphCluster *),
-                (__compar_d_fn_t)g_graph_cluster_compare_by_exit, (bool []){ false });
+        for (i = 0; i < grank->count; i++)
+            if (grank->clusters[i] == NULL)
+            {
+                assert(next < fcount);
+                grank->clusters[i] = filtered[next++];
+            }
 
-        qsort_r(exit_2_right, count_2_right, sizeof(GGraphCluster *),
-                (__compar_d_fn_t)g_graph_cluster_compare_by_exit, (bool []){ true });
+        free(filtered);
 
-        grank->count = 0;
+    }
 
-        for (i = 0; i < count_2_left; i++)
-            grank->clusters[grank->count++] = exit_2_left[i];
+}
 
-        for (i = 0; i < count_no; i++)
-            grank->clusters[grank->count++] = no_exit[i];
 
-        for (i = 0; i < count_2_right; i++)
-            grank->clusters[grank->count++] = exit_2_right[i];
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : grank = ensemble de blocs de même rang à actualiser.         *
+*                                                                             *
+*  Description : Réorganise au besoin les liens entrants un ensemble de blocs.*
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
 
-    }
+void sort_graph_rank_incoming_links(graph_rank_t *grank)
+{
+    size_t i;                               /* Boucle de parcours          */
 
     for (i = 0; i < grank->count; i++)
-        g_graph_cluster_reorder_exit_blocks(grank->clusters[i]);
+        g_graph_cluster_sort_incoming_links(grank->clusters[i]);
+
+    sort_incoming_links_for_vspace_manager(&grank->vspaces);
 
 }
 
diff --git a/src/gtkext/graph/rank.h b/src/gtkext/graph/rank.h
index 1a149fc..e28b1f0 100644
--- a/src/gtkext/graph/rank.h
+++ b/src/gtkext/graph/rank.h
@@ -55,6 +55,12 @@ void init_graph_rank(graph_rank_t *, GGraphCluster *);
 /* Termine la gestion d'un ensemble de blocs de même rang. */
 void exit_graph_rank(graph_rank_t *);
 
+/* Visiteur pour blocs */
+typedef void (* graph_rank_cb) (GGraphCluster *);
+
+/* Parcours l'ensemble des blocs du rang avec un visiteur. */
+void visit_graph_rank(const graph_rank_t *grank, graph_rank_cb);
+
 /* Assigne à un ensemble de blocs un emplacement initial. */
 void reset_graph_rank_allocation(const graph_rank_t *);
 
@@ -89,10 +95,16 @@ void _place_graph_rank_clusters(GGraphCluster **, size_t, gint, int);
 void dispatch_x_graph_rank(const graph_rank_t *);
 
 /* Réorganise au besoin les liens entrants un ensemble de blocs. */
-void sort_graph_rank_incoming_links(graph_rank_t *);
+bool get_graph_rank_exit_direction(graph_rank_t *, const GGraphCluster *, LeavingLinkDir *);
+
+/* Calcule les ordonnées extrèmes atteintes via liens sortants. */
+bool compute_graph_rank_min_max_bottom(const graph_rank_t *, gint [2]);
 
-/* Réordonne les blocs sortant d'un ensemble. */
-void reorder_graph_rank_exit_blocks(graph_rank_t *);
+/* Réorganise au besoin les blocs selon les liens d'origine. */
+void reorder_graph_rank_clusters(graph_rank_t *, const GGraphCluster *);
+
+/* Réorganise au besoin les liens entrants un ensemble de blocs. */
+void sort_graph_rank_incoming_links(graph_rank_t *);
 
 /* Réordonne les blocs de départ de boucle d'un ensemble. */
 void reorder_graph_rank_loop_blocks(graph_rank_t *);