Extended the number of cases where beautiful graphs are produced.

4 files changed, 631 insertions, 114 deletions

diff --git a/ChangeLog b/ChangeLog
index 1f6cfbf..62a1bc6 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,10 @@
+16-10-21  Cyrille Bagard <nocbos@gmail.com>
+
+	* src/gtkext/graph/cluster.c:
+	* src/gtkext/graph/edge.c:
+	* src/gtkext/graph/edge.h:
+	Extend the number of cases where beautiful graphs are produced.
+
 16-10-18  Cyrille Bagard <nocbos@gmail.com>
 
 	* src/gtkext/gtkgraphview.c:
diff --git a/src/gtkext/graph/cluster.c b/src/gtkext/graph/cluster.c
index 4c92718..3e18f5f 100644
--- a/src/gtkext/graph/cluster.c
+++ b/src/gtkext/graph/cluster.c
@@ -26,6 +26,7 @@
 
 #include <assert.h>
 #include <malloc.h>
+#include <stdlib.h>
 #include <string.h>
 
 
@@ -37,23 +38,49 @@
 
 
 /* Définition du tracé d'un lien */
-typedef struct _link_def
+typedef struct _incoming_edge
 {
     InstructionLinkType type;               /* Complexité du tracé         */
 
+    const size_t *hslot;                    /* Couche horizontale réservée */
     GdkPoint y;                             /* Position des décrochages    */
-
     GdkPoint end;                           /* Point d'arrivée final       */
 
     GGraphEdge *edge;                       /* Lien complet en préparation */
 
-} link_def;
+    GGraphCluster *origin;                  /* Bloc de départ du lien      */
+    const size_t *leaving_index;            /* Indice du point de départ   */
+
+} incoming_edge;
+
+
+/* Détails sur le départ d'un lien */
+typedef struct _leaving_edge
+{
+    GdkPoint start;                         /* Point de départ d'un lien   */
+    size_t index;                           /* Indice sur ligne de départ  */
+
+} leaving_edge;
+
+/* Réservation pour les lignes horizontales */
+typedef struct _hspace_booking
+{
+    gint start;                             /* Abscisse de départ de ligne */
+    size_t index;                           /* Indice de rangée verticale  */
+
+} hspace_booking;
 
 /* Découpage vertical */
 typedef struct _graph_rank
 {
     unsigned int level;                     /* Niveau des blocs            */
 
+    hspace_booking **right2left;            /* Réservations de D -> G      */
+    size_t r2l_count;                       /* Quantité de ces réservations*/
+
+    hspace_booking **left2right;            /* Réservations de G -> D      */
+    size_t l2r_count;                       /* Quantité de ces réservations*/
+
     GGraphCluster **clusters;               /* Ensembles de blocs          */
     size_t count;                           /* Nombre de ces ensembles     */
 
@@ -64,6 +91,7 @@ struct _GGraphCluster
 {
     GObject parent;                         /* A laisser en premier        */
 
+    size_t *parent_index;                   /* Indice du lien au départ    */
 
     ////////////////////////////////////////
     gint top_margin[2];                     /* Espaces gauches et droites  */
@@ -72,16 +100,20 @@ struct _GGraphCluster
     ////////////////////////////////////////
 
 
-    link_def **top_anchors;                 /* Accroches supérieures       */
+    incoming_edge **top_anchors;            /* Accroches supérieures       */
     size_t ta_count;                        /* Quantité de ces accroches   */
 
     GBasicBlock *block;                     /* Bloc d'origine représenté   */
     GtkWidget *view;                        /* Vue graphique associée      */
     GtkAllocation alloc;                    /* Emplacement final du bloc   */
 
-    GdkPoint **bottom_anchors;              /* Accroches inférieures       */
+    leaving_edge **bottom_anchors;          /* Accroches inférieures       */
     size_t ba_count;                        /* Quantité de ces accroches   */
 
+    bool has_straight;                      /* Présence d'une ligne droite */
+    unsigned int straight_level;            /* Rang atteint en ligne droite*/
+    size_t straight_index;                  /* Indice du lien vertical     */
+
     graph_rank *ranks;                      /* Répartition verticale       */
     size_t ranks_count;                     /* Nombre de divisions         */
 
@@ -99,7 +131,7 @@ struct _GGraphClusterClass
 #define HORIZONTAL_MARGIN 20
 
 /* Espace minimal vertical entre les blocs */
-#define VERTICAL_MARGIN 30
+#define VERTICAL_MARGIN 15
 
 /* Espace minimal entre les liens */
 #define LINK_MARGIN 10
@@ -142,8 +174,17 @@ static void g_graph_cluster_set_y(GGraphCluster *, gint);
 /* Met en place les embryons de liens nécessaires. */
 static void g_graph_cluster_define_links(GGraphCluster *, GHashTable *);
 
-/* Détermine les positions de tous les liens en place. */
-static void g_graph_cluster_compute_link_positions(GGraphCluster *);
+/* Calcule l'abscisse d'un lien à son départ d'un bloc. */
+static gint g_graph_cluster_compute_leaving_link_position(const GGraphCluster *, size_t);
+
+/* Détermine les abscisses de tous les liens en place. */
+static void g_graph_cluster_compute_link_x_positions(GGraphCluster *);
+
+/* Réserve de l'espace vertical pour les lignes horizontales. */
+static void g_graph_cluster_book_hspace_for_links(GGraphCluster *);
+
+/* Détermine les ordonnées de tous les liens en place. */
+static void g_graph_cluster_compute_link_y_positions(GGraphCluster *);
 
 /* Applique les positions calculées pour chaque lien graphique. */
 static void g_graph_cluster_resolve_links(const GGraphCluster *);
@@ -324,7 +365,7 @@ static void g_graph_cluster_add_sub(GGraphCluster *cluster, GGraphCluster *sub,
     unsigned int level;                     /* Niveau du nouvel ensemble   */
     size_t i;                               /* Boucle de parcours          */
     graph_rank new;                         /* Nouvel étage à insérer      */
-    graph_rank *rank;                        /* Nouvel étage à compléter     */
+    graph_rank *rank;                       /* Nouvel étage à compléter    */
 
     level = g_basic_block_get_rank(block);
 
@@ -336,6 +377,12 @@ static void g_graph_cluster_add_sub(GGraphCluster *cluster, GGraphCluster *sub,
     {
         new.level = level;
 
+        new.right2left = NULL;
+        new.r2l_count = 0;
+
+        new.left2right = NULL;
+        new.l2r_count = 0;
+
         new.clusters = (GGraphCluster **)calloc(1, sizeof(GGraphCluster *));
         new.count = 1;
 
@@ -389,9 +436,47 @@ static void g_graph_cluster_add_sub(GGraphCluster *cluster, GGraphCluster *sub,
 static void g_graph_cluster_dispatch_x(GGraphCluster *cluster)
 {
     size_t k;                               /* Boucle de parcours #1       */
+    const graph_rank *rank;                 /* Accès confortable au rang   */
+    size_t j;                               /* Boucle de parcours #2       */
+    gint start;                             /* Position initiale de départ */
     size_t rcount;                          /* Nombre d'ensembles présents */
     size_t mid;                             /* Position centrale de départ */
-    gint start;                             /* Position initiale de départ */
+
+    /**
+     * A ce point, tous les blocs parents 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
+     * de la gauche ne doit pas arriver tout à droite !
+     */
+
+    int compare_incoming_edges(const incoming_edge **a, const incoming_edge **b)
+    {
+        int result;                         /* Bilan à retourner           */
+        gint pos_a;                         /* Point de départ pour A      */
+        gint pos_b;                         /* Point de départ pour B      */
+
+        pos_a = g_graph_cluster_compute_leaving_link_position((*a)->origin, *(*a)->leaving_index);
+
+        pos_b = g_graph_cluster_compute_leaving_link_position((*b)->origin, *(*b)->leaving_index);
+
+        if (pos_a < pos_b)
+            result = -1;
+
+        else if (pos_a > pos_b)
+            result = 1;
+
+        else
+            result = 0;
+
+        return result;
+
+    }
+
+    qsort(cluster->top_anchors, cluster->ta_count, sizeof(incoming_edge *), (__compar_fn_t)compare_incoming_edges);
+
+    /**
+     * Il est désormais temps de placer tous les blocs de code inférieurs.
+     */
 
     void place_sub(GGraphCluster **iter, size_t loop, gint base, int dir)
     {
@@ -418,41 +503,80 @@ static void g_graph_cluster_dispatch_x(GGraphCluster *cluster)
     }
 
 
-
-
     for (k = 0; k < cluster->ranks_count; k++)
     {
-        rcount = cluster->ranks[k].count;
+        rank = &cluster->ranks[k];
 
-        if (rcount % 2 == 1)
+        /* Répartition autour d'une ligne verticale */
+        if (cluster->has_straight)
         {
-            if (rcount > 1)
+            start = g_graph_cluster_compute_leaving_link_position(cluster, cluster->straight_index);
+
+            if (rank->level < cluster->straight_level)
             {
-                mid = rcount / 2;
+                /* Répartition à gauche du lien */
 
-                start = cluster->ranks[k].clusters[mid]->alloc.x - HORIZONTAL_MARGIN;
+                for (j = rank->count; j > 0; j--)
+                    if (*rank->clusters[j - 1]->parent_index < cluster->straight_index)
+                        break;
 
-                place_sub(cluster->ranks[k].clusters + mid - 1, mid, start, -1);
+                start -= HORIZONTAL_MARGIN / 2;
 
-                start *= -1;
+                place_sub(rank->clusters, j, start, -1);
+
+                /* Répartition à droite du lien */
+
+                for (j = 0; j < rank->count; j++)
+                    if (*rank->clusters[j]->parent_index > cluster->straight_index)
+                        break;
 
-                place_sub(cluster->ranks[k].clusters + mid + 1, mid, start, 1);
+                start += HORIZONTAL_MARGIN;
+
+                place_sub(rank->clusters + j, rank->count - j, start, 1);
 
             }
 
         }
 
+        /* Répartition homogène */
         else
         {
-            mid = rcount / 2 - 1;
+            rcount = rank->count;
+
+            if (rcount % 2 == 1)
+            {
+                if (rcount > 1)
+                {
+                    mid = rcount / 2;
+
+                    start = rank->clusters[mid]->alloc.x - HORIZONTAL_MARGIN;
+
+                    place_sub(rank->clusters + mid - 1, mid, start, -1);
+
+                    start *= -1;
+
+                    place_sub(rank->clusters + mid + 1, mid, start, 1);
+
+                }
 
-            start = - HORIZONTAL_MARGIN / 2;
+                else
+                    g_graph_cluster_dispatch_x(rank->clusters[0]);
+
+            }
+
+            else
+            {
+                mid = rcount / 2 - 1;
+
+                start = - HORIZONTAL_MARGIN / 2;
 
-            place_sub(cluster->ranks[k].clusters + mid, mid + 1, start, -1);
+                place_sub(rank->clusters + mid, mid + 1, start, -1);
 
-            start *= -1;
+                start *= -1;
 
-            place_sub(cluster->ranks[k].clusters + mid + 1, mid + 1, start, 1);
+                place_sub(rank->clusters + mid + 1, mid + 1, start, 1);
+
+            }
 
         }
 
@@ -527,6 +651,7 @@ static void g_graph_cluster_offset_x(GGraphCluster *cluster, gint offset)
 static void g_graph_cluster_set_y(GGraphCluster *cluster, gint base)
 {
     size_t i;                               /* Boucle de parcours #1       */
+    const graph_rank *rank;                 /* Accès simplifié à la rangée */
     gint max;                               /* Hauteur maximale rencontrée */
     size_t j;                               /* Boucle de parcours #2       */
     GGraphCluster *sub;                     /* Sous-ensemble traité        */
@@ -538,13 +663,34 @@ static void g_graph_cluster_set_y(GGraphCluster *cluster, gint base)
 
     for (i = 0; i < cluster->ranks_count; i++)
     {
+        rank = &cluster->ranks[i];
+
+        /* On ajoute l'espace vertical pour les lignes horizontales */
+
+        if (rank->r2l_count > rank->l2r_count)
+            max = rank->r2l_count;
+        else
+            max = rank->l2r_count;
+
+        base += VERTICAL_MARGIN;
+
+        /**
+         * Comme les liens purement verticaux n'entrainent pas de réservation,
+         * il n'y a potentiellement pas toujours d'espace à ajouter.
+         */
+
+        if (max > 0)
+            base += ((max - 1) * LINK_MARGIN);
+
+        /* On ajoute l'espace requis pour l'affichage des blocs */
+
         base += VERTICAL_MARGIN;
 
         max = 0;
 
-        for (j = 0; j < cluster->ranks[i].count; j++)
+        for (j = 0; j < rank->count; j++)
         {
-            sub = cluster->ranks[i].clusters[j];
+            sub = rank->clusters[j];
 
             g_graph_cluster_set_y(sub, base);
 
@@ -756,18 +902,23 @@ static GGraphCluster *g_graph_cluster_find_lower_dest_cluster(const GGraphCluste
 
 static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all)
 {
+    unsigned int level;                     /* Niveau du nouvel ensemble   */
     GArchInstruction *last;                 /* Dernière instruction du bloc*/
     GArchInstruction **dests;               /* Instr. visée par une autre  */
     InstructionLinkType *types;             /* Type de lien entre lignes   */
     size_t dcount;                          /* Nombre de liens de dest.    */
     size_t i;                               /* Boucle de parcours #1       */
     GGraphCluster *target;                  /* Bloc ciblé par un lien      */
-    GdkPoint *start;                        /* Point de départ d'un lien   */
-    link_def *end;                          /* Définitions d'arrivée       */
+    leaving_edge *leaving;                  /* Point de départ d'un lien   */
+    unsigned int target_level;              /* Rang du bloc ciblé          */
     size_t j;                               /* Boucle de parcours #2       */
+    size_t k;                               /* Boucle de parcours #3       */
+    incoming_edge *incoming;                /* Définitions d'arrivée       */
 
     /* Au niveau du bloc courant */
 
+    level = g_basic_block_get_rank(cluster->block);
+
     g_basic_block_get_boundary(cluster->block, NULL, &last);
 
     g_arch_instruction_rlock_dest(last);
@@ -787,32 +938,80 @@ static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all
 
                 /* Point de départ */
 
-                start = (GdkPoint *)calloc(1, sizeof(GdkPoint));
+                leaving = (leaving_edge *)calloc(1, sizeof(leaving_edge));
+
+                cluster->bottom_anchors = (leaving_edge **)realloc(cluster->bottom_anchors,
+                                                                   ++cluster->ba_count * sizeof(leaving_edge *));
+                cluster->bottom_anchors[cluster->ba_count - 1] = leaving;
+
+                /* Est-ce un lien qui doit être vertical ? */
+
+
+                /* FIXME : trop de boucles ! */
+
+                target_level = -1;
+
+                for (j = 0; j < cluster->ranks_count && target_level == -1; j++)
+                    for (k = 0; k < cluster->ranks[j].count && target_level == -1; k++)
+                        if (cluster->ranks[j].clusters[k] == target)
+                        {
+                            target_level = cluster->ranks[j].level;
+
+                            if (target_level > (level + 1) && target_level > cluster->straight_level)
+                            {
+                                cluster->has_straight = true;
+                                cluster->straight_level = target_level;
+                                cluster->straight_index = cluster->ba_count - 1;
+                            }
+
+                        }
+
+
+
+
 
-                cluster->bottom_anchors = (GdkPoint **)realloc(cluster->bottom_anchors,
-                                                               ++cluster->ba_count * sizeof(GdkPoint *));
-                cluster->bottom_anchors[cluster->ba_count - 1] = start;
 
                 /* Point d'arrivée */
 
-                end = (link_def *)calloc(1, sizeof(link_def));
+                incoming = (incoming_edge *)calloc(1, sizeof(incoming_edge));
 
-                target->top_anchors = (link_def **)realloc(target->top_anchors,
-                                                           ++target->ta_count * sizeof(link_def *));
-                target->top_anchors[target->ta_count - 1] = end;
+                target->top_anchors = (incoming_edge **)realloc(target->top_anchors,
+                                                                ++target->ta_count * sizeof(incoming_edge *));
+                target->top_anchors[target->ta_count - 1] = incoming;
 
                 /* Etablissement d'un embryon de lien */
 
-                end->type = types[i];
+                leaving->index = cluster->ba_count - 1;
+
+                incoming->type = types[i];
 
                 if (types[i] == ILT_JUMP_IF_TRUE)
-                    end->edge = g_graph_edge_new_true(start, &end->y, &end->end);
+                    incoming->edge = g_graph_edge_new_true(&leaving->start, &incoming->y, &incoming->end);
 
                 else if (types[i] == ILT_JUMP_IF_FALSE)
-                    end->edge = g_graph_edge_new_false(start, &end->y, &end->end);
+                    incoming->edge = g_graph_edge_new_false(&leaving->start, &incoming->y, &incoming->end);
 
                 else
-                    end->edge = g_graph_edge_new(start, &end->y, &end->end);
+                    incoming->edge = g_graph_edge_new(&leaving->start, &incoming->y, &incoming->end);
+
+                incoming->origin = cluster;
+                incoming->leaving_index = &leaving->index;
+
+
+                /* FIXME : trop de boucles ! */
+
+                target_level = -1;
+
+                for (j = 0; j < cluster->ranks_count && target_level == -1; j++)
+                    for (k = 0; k < cluster->ranks[j].count && target_level == -1; k++)
+                        if (cluster->ranks[j].clusters[k] == target)
+                        {
+                            target_level = 0;
+                            target->parent_index = &leaving->index;
+                        }
+
+
+
 
                 break;
 
@@ -820,7 +1019,7 @@ static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all
             case ILT_LOOP:
 
                 /* TODO */
-                assert(false);
+                //assert(false);
 
                 break;
 
@@ -831,6 +1030,57 @@ static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all
 
     g_arch_instruction_runlock_dest(last);
 
+
+
+
+    /* Déplacement d'un éventuel lien central */
+
+    if (cluster->has_straight)
+    {
+        size_t center;
+        leaving_edge *tmp;
+
+        if (cluster->ba_count % 2 == 0)
+            center = cluster->ba_count / 2 - 1;
+        else
+            center = cluster->ba_count / 2;
+
+        if (cluster->straight_index < center)
+        {
+            tmp = cluster->bottom_anchors[cluster->straight_index];
+
+            memmove(cluster->bottom_anchors + cluster->straight_index,
+                    cluster->bottom_anchors + cluster->straight_index + 1,
+                    (center - cluster->straight_index) * sizeof(leaving_edge *));
+
+            cluster->bottom_anchors[center] = tmp;
+
+            for (i = cluster->straight_index; i <= center; i++)
+                cluster->bottom_anchors[i]->index = i;
+
+            cluster->straight_index = center;
+
+        }
+
+        else if (cluster->straight_index > center)
+        {
+            tmp = cluster->bottom_anchors[cluster->straight_index];
+
+            memmove(cluster->bottom_anchors + center + 1,
+                    cluster->bottom_anchors + center,
+                    (cluster->straight_index - center) * sizeof(leaving_edge *));
+
+            cluster->bottom_anchors[center] = tmp;
+
+            for (i = center; i <= cluster->straight_index ; i++)
+                cluster->bottom_anchors[i]->index = i;
+
+            cluster->straight_index = center;
+
+        }
+
+    }
+
     /* Propagation de la mise en place */
 
     for (i = 0; i < cluster->ranks_count; i++)
@@ -842,60 +1092,113 @@ static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all
 
 /******************************************************************************
 *                                                                             *
-*  Paramètres  : cluster = graphique de blocs à actualiser.                   *
+*  Paramètres  : cluster = graphique de blocs à consulter.                    *
+*                index   = indice du lien à considérer.                       *
 *                                                                             *
-*  Description : Détermine les positions de tous les liens en place.          *
+*  Description : Calcule l'abscisse d'un lien à son départ d'un bloc.         *
 *                                                                             *
-*  Retour      : -                                                            *
+*  Retour      : Abscisse à attribuer à un départ de lien.                    *
 *                                                                             *
 *  Remarques   : -                                                            *
 *                                                                             *
 ******************************************************************************/
 
-static void g_graph_cluster_compute_link_positions(GGraphCluster *cluster)
+static gint g_graph_cluster_compute_leaving_link_position(const GGraphCluster *cluster, size_t index)
 {
+    gint result;                            /* Position à retourner        */
     gint mid_x;                             /* Abscisse centrale           */
     size_t half;                            /* Indice de répartition égale */
-    gint y;                                 /* Ordonnée d'application      */
 
+    assert(index < cluster->ba_count);
+
+    mid_x = cluster->alloc.x + (cluster->alloc.width / 2);
+
+    half = cluster->ba_count / 2;
+
+    if (cluster->ba_count % 2 == 1)
+    {
+        if (index < half)
+            result = mid_x - (half - index) * LINK_MARGIN;
+
+        else if (index == half)
+            result = mid_x;
+
+        else
+            result = mid_x + (index - half) * LINK_MARGIN;
+
+    }
+
+    else
+    {
+        if (index < half)
+            result = mid_x - LINK_MARGIN / 2 - (half - index - 1) * LINK_MARGIN;
+
+        else
+            result = mid_x + LINK_MARGIN / 2 + (index - half) * LINK_MARGIN;
+
+    }
+
+    return result;
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : cluster = graphique de blocs à actualiser.                   *
+*                                                                             *
+*  Description : Détermine les abscisses de tous les liens en place.          *
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+static void g_graph_cluster_compute_link_x_positions(GGraphCluster *cluster)
+{
+    gint mid_x;                             /* Abscisse centrale           */
     size_t i;                               /* Boucle de parcours #1       */
+    size_t half;                            /* Indice de répartition égale */
     GdkPoint *pt;                           /* Point à actualiser          */
     size_t j;                               /* Boucle de parcours #2       */
 
-
-
     mid_x = cluster->alloc.x + (cluster->alloc.width / 2);
 
     /* Du côté des départs... */
 
     if (cluster->ba_count > 0)
-    {
-        half = cluster->ba_count / 2;
+        for (i = 0; i < cluster->ba_count; i++)
+        {
+            pt = &cluster->bottom_anchors[i]->start;
 
-        y = cluster->alloc.y + cluster->alloc.height;
+            pt->x = g_graph_cluster_compute_leaving_link_position(cluster, i);
+
+        }
+
+    /* Du côté des arrivées... */
+
+    if (cluster->ta_count > 0)
+    {
+        half = cluster->ta_count / 2;
 
-        if (cluster->ba_count % 2 == 1)
+        if (cluster->ta_count % 2 == 1)
         {
             for (i = half; i > 0; i--)
             {
-                pt = cluster->bottom_anchors[i - 1];
+                pt = &cluster->top_anchors[i - 1]->end;
 
                 pt->x = mid_x - (half - i + 1) * LINK_MARGIN;
-                pt->y = y;
 
             }
 
-            pt = cluster->bottom_anchors[half];
-
-            pt->x = mid_x;
-            pt->y = y;
+            cluster->top_anchors[half]->end.x = mid_x;
 
-            for (i = half + 1; i < cluster->ba_count; i++)
+            for (i = half + 1; i < cluster->ta_count; i++)
             {
-                pt = cluster->bottom_anchors[i];
+                pt = &cluster->top_anchors[i]->end;
 
                 pt->x = mid_x + (i - half) * LINK_MARGIN;
-                pt->y = y;
 
             }
 
@@ -905,19 +1208,17 @@ static void g_graph_cluster_compute_link_positions(GGraphCluster *cluster)
         {
             for (i = half; i > 0; i--)
             {
-                pt = cluster->bottom_anchors[i - 1];
+                pt = &cluster->top_anchors[i - 1]->end;
 
                 pt->x = mid_x - LINK_MARGIN / 2 - (half - i) * LINK_MARGIN;
-                pt->y = y;
 
             }
 
-            for (i = half; i < cluster->ba_count; i++)
+            for (i = half; i < cluster->ta_count; i++)
             {
-                pt = cluster->bottom_anchors[i];
+                pt = &cluster->top_anchors[i]->end;
 
                 pt->x = mid_x + LINK_MARGIN / 2 + (half - i) * LINK_MARGIN;
-                pt->y = y;
 
             }
 
@@ -925,78 +1226,191 @@ static void g_graph_cluster_compute_link_positions(GGraphCluster *cluster)
 
     }
 
-    /* Du côté des arrivées... */
+    /* Propagation des déterminations */
 
-    if (cluster->ta_count > 0)
+    for (i = 0; i < cluster->ranks_count; i++)
+        for (j = 0; j < cluster->ranks[i].count; j++)
+            g_graph_cluster_compute_link_x_positions(cluster->ranks[i].clusters[j]);
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : cluster = graphique de blocs à traiter.                      *
+*                                                                             *
+*  Description : Réserve de l'espace vertical pour les lignes horizontales.   *
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+static void g_graph_cluster_book_hspace_for_links(GGraphCluster *cluster)
+{
+    size_t i;                               /* Boucle de parcours #1       */
+    graph_rank *rank;                       /* Rangée à manipuler          */
+    size_t j;                               /* Boucle de parcours #2       */
+    GGraphCluster *sub;                     /* Bloc inférieur à manipuler  */
+    size_t k;                               /* Boucle de parcours #3       */
+    gint x1;                                /* Abscisse de départ de lien  */
+    gint x2;                                /* Abscisse d'arrivée de lien  */
+    hspace_booking *new;                    /* Nouvelle réservation        */
+
+    for (i = 0; i < cluster->ranks_count; i++)
     {
-        half = cluster->ta_count / 2;
+        rank = &cluster->ranks[i];
 
-        y = cluster->alloc.y;
+        /* Enregistrement des besoins */
 
-        if (cluster->ta_count % 2 == 1)
+        for (j = 0; j < rank->count; j++)
         {
-            for (i = half; i > 0; i--)
+            sub = rank->clusters[j];
+
+            for (k = 0; k < sub->ta_count; k++)
             {
-                pt = &cluster->top_anchors[i - 1]->end;
+                g_graph_edge_get_x_borders(sub->top_anchors[k]->edge, &x1, &x2);
 
-                pt->x = mid_x - (half - i + 1) * LINK_MARGIN;
-                pt->y = y;
+                if (x1 > x2)
+                {
+                    new = (hspace_booking *)calloc(1, sizeof(hspace_booking));
 
-            }
+                    new->start = x1;
+                    sub->top_anchors[k]->hslot = &new->index;
 
-            pt = &cluster->top_anchors[half]->end;
+                    int compare_right_to_left(const hspace_booking **a, const hspace_booking **b)
+                    {
+                        int result;         /* Bilan à retourner           */
 
-            pt->x = mid_x;
-            pt->y = y;
+                        if ((*a)->start > (*b)->start)
+                            result = -1;
 
-            for (i = half + 1; i < cluster->ta_count; i++)
-            {
-                pt = &cluster->top_anchors[i]->end;
+                        else if ((*a)->start < (*b)->start)
+                            result = 1;
 
-                pt->x = mid_x + (i - half) * LINK_MARGIN;
-                pt->y = y;
+                        else
+                        {
+                            assert(false);
+                            result = 0;
+                        }
 
-            }
+                        return result;
 
-        }
+                    }
 
-        else
-        {
-            for (i = half; i > 0; i--)
-            {
-                pt = &cluster->top_anchors[i - 1]->end;
+                    rank->right2left = qinsert(rank->right2left, &rank->r2l_count,
+                                               sizeof(hspace_booking *),
+                                               (__compar_fn_t)compare_right_to_left, &new);
 
-                pt->x = mid_x - LINK_MARGIN / 2 - (half - i) * LINK_MARGIN;
-                pt->y = y;
+                }
 
-            }
+                else if (x1 < x2)
+                {
+                    new = (hspace_booking *)calloc(1, sizeof(hspace_booking));
 
-            for (i = half; i < cluster->ta_count; i++)
-            {
-                pt = &cluster->top_anchors[i]->end;
+                    new->start = x1;
+                    sub->top_anchors[k]->hslot = &new->index;
 
-                pt->x = mid_x + LINK_MARGIN / 2 + (half - i) * LINK_MARGIN;
-                pt->y = y;
+                    int compare_left_to_right(const hspace_booking **a, const hspace_booking **b)
+                    {
+                        int result;         /* Bilan à retourner           */
+
+                        if ((*a)->start < (*b)->start)
+                            result = -1;
+
+                        else if ((*a)->start > (*b)->start)
+                            result = 1;
+
+                        else
+                        {
+                            assert(false);
+                            result = 0;
+                        }
+
+                        return result;
+
+                    }
+
+                    rank->left2right = qinsert(rank->left2right, &rank->l2r_count,
+                                               sizeof(hspace_booking *),
+                                               (__compar_fn_t)compare_left_to_right, &new);
+
+                }
+
+                else
+                    sub->top_anchors[k]->hslot = NULL;
 
             }
 
         }
 
+        /* Définition des couches */
 
+        for (j = 0; j < rank->r2l_count; j++)
+            rank->right2left[j]->index = j;
 
+        for (j = 0; j < rank->l2r_count; j++)
+            rank->left2right[j]->index = j;
 
+        /* Propagation des déterminations */
 
+        for (j = 0; j < rank->count; j++)
+            g_graph_cluster_book_hspace_for_links(rank->clusters[j]);
 
+    }
 
+}
 
-        for (i = 0; i < cluster->ta_count; i++)
-            cluster->top_anchors[i]->y.y = cluster->top_anchors[i]->end.y - 18;
 
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : cluster = graphique de blocs à actualiser.                   *
+*                                                                             *
+*  Description : Détermine les ordonnées de tous les liens en place.          *
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+static void g_graph_cluster_compute_link_y_positions(GGraphCluster *cluster)
+{
+    gint y;                                 /* Ordonnée d'application      */
+    size_t i;                               /* Boucle de parcours #1       */
+    incoming_edge *incoming;                /* Raccourci pour le confort   */
+    size_t j;                               /* Boucle de parcours #2       */
+
+    /* Du côté des départs... */
 
+    if (cluster->ba_count > 0)
+    {
+        y = cluster->alloc.y + cluster->alloc.height;
 
+        for (i = 0; i < cluster->ba_count; i++)
+            cluster->bottom_anchors[i]->start.y = y;
 
+    }
 
+    /* Du côté des arrivées... */
 
+    if (cluster->ta_count > 0)
+    {
+        y = cluster->alloc.y;
+
+        for (i = 0; i < cluster->ta_count; i++)
+        {
+            incoming = cluster->top_anchors[i];
+
+            incoming->end.y = y;
+
+            incoming->y.y = incoming->end.y - VERTICAL_MARGIN;
+
+            if (incoming->hslot != NULL)
+                incoming->y.y -= *incoming->hslot * LINK_MARGIN;
+
+        }
 
     }
 
@@ -1004,7 +1418,7 @@ static void g_graph_cluster_compute_link_positions(GGraphCluster *cluster)
 
     for (i = 0; i < cluster->ranks_count; i++)
         for (j = 0; j < cluster->ranks[i].count; j++)
-            g_graph_cluster_compute_link_positions(cluster->ranks[i].clusters[j]);
+            g_graph_cluster_compute_link_y_positions(cluster->ranks[i].clusters[j]);
 
 }
 
@@ -1124,8 +1538,6 @@ static GGraphCluster *setup_graph_clusters(GLoadedBinary *binary, const GBlockLi
     g_arch_instruction_rlock_dest(last);
     dcount = g_arch_instruction_get_destinations(last, &dests, &types, NULL);
 
-    printf(" ... block=%p dest=%zu\n", block, dcount);
-
     for (i = 0; i < dcount; i++)
         switch (types[i])
         {
@@ -1158,9 +1570,33 @@ static GGraphCluster *setup_graph_clusters(GLoadedBinary *binary, const GBlockLi
 
                     if (j == pending->count)
                     {
-                        assert((pending->count + 1) < g_block_list_count_blocks(list));
-                        pending->list[pending->count++] = target;
-                        printf(" --push-- %d -> %p\n", types[i], target);
+                        /**
+                         * Il faut vérifier ici si la destination n'a pas déjà été
+                         * empruntée, sauf peine de faire réagir l'assertion plus
+                         * haut au moment de l'insertion.
+                         *
+                         * Le type de code à problème est le suivant :
+                         *
+                         *    ...
+                         *    if (...)
+                         *        ...
+                         *    ...
+                         *
+                         * Le code suivant le bloc conditionnel a deux origines,
+                         * qui vont chacune poursuivre le traitement vers ce code
+                         * commun.
+                         *
+                         * Et comme les origines ne sont pas dominantes, on utilise
+                         * la table globale.
+                         */
+
+                        if (!g_hash_table_contains(all, dests[i]))
+                        {
+                            assert((pending->count + 1) < g_block_list_count_blocks(list));
+                            pending->list[pending->count++] = target;
+                            printf(" --push-- %d -> %p\n", types[i], target);
+                        }
+
                     }
 
                     do
@@ -1266,12 +1702,15 @@ GGraphCluster *bootstrap_graph_cluster(GLoadedBinary *binary, const GBlockList *
 
 
 
-
+#if 0
     do
     {
         size_t i;
         GBasicBlock *block;
         const bitfield_t *domination;
+        GArchInstruction *first;                /* Première instruction du bloc*/
+        GArchInstruction *last;                 /* Dernière instruction du bloc*/
+
 
         printf("DBG // count : %zu\n", count);
 
@@ -1280,8 +1719,12 @@ GGraphCluster *bootstrap_graph_cluster(GLoadedBinary *binary, const GBlockList *
             block = g_block_list_get_block(list, i);
             domination = g_basic_block_get_domination(block);
 
-            printf("DBG // block [%zu] : 0x%08lx  --  rank = %u\n",
-                   i, gfw(domination), g_basic_block_get_rank(block));
+            g_basic_block_get_boundary(block, &first, &last);
+
+            printf("DBG // block [%zu] @ 0x%08x : 0x%08lx  --  rank = %u\n",
+                   i,
+                   (unsigned int)first->range.addr.virtual,
+                   gfw(domination), g_basic_block_get_rank(block));
 
         }
 
@@ -1292,6 +1735,39 @@ GGraphCluster *bootstrap_graph_cluster(GLoadedBinary *binary, const GBlockList *
 
 
 
+    void show_tree(GGraphCluster *cluster, int depth)
+    {
+        int i;
+        GArchInstruction *first;
+        size_t j;
+        size_t k;
+
+        printf("TREE |  ");
+
+        for (i = 0; i < depth; i++)
+            printf("    ");
+
+        g_basic_block_get_boundary(cluster->block, &first, NULL);
+
+        printf("cluster @ 0x%08x\n", (unsigned int)first->range.addr.virtual);
+
+        for (j = 0; j < cluster->ranks_count; j++)
+        {
+            printf("TREE |  ");
+
+            for (i = 0; i < depth; i++)
+                printf("    ");
+
+            printf(" + rank %u +\n", cluster->ranks[j].level);
+
+            for (k = 0; k < cluster->ranks[j].count; k++)
+                show_tree(cluster->ranks[j].clusters[k], depth + 1);
+
+        }
+
+
+    }
+#endif
 
 
     result = setup_graph_clusters(binary, list, 0, highlighted, pending, all);
@@ -1300,12 +1776,16 @@ GGraphCluster *bootstrap_graph_cluster(GLoadedBinary *binary, const GBlockList *
 
     g_graph_cluster_define_links(result, all);
 
+
+    //show_tree(result, 0);
+    //printf("--------------\n");
+
+
+
     /* Positionnements dans l'espace */
 
     g_graph_cluster_dispatch_x(result);
 
-    g_graph_cluster_set_y(result, 0);
-
     /* Réajustement vers la droite */
 
     g_graph_cluster_compute_needed_alloc(result, &needed);
@@ -1314,7 +1794,13 @@ GGraphCluster *bootstrap_graph_cluster(GLoadedBinary *binary, const GBlockList *
 
     /* Application finale sur les liens */
 
-    g_graph_cluster_compute_link_positions(result);
+    g_graph_cluster_compute_link_x_positions(result);
+
+    g_graph_cluster_book_hspace_for_links(result);
+
+    g_graph_cluster_set_y(result, 0);
+
+    g_graph_cluster_compute_link_y_positions(result);
 
     g_graph_cluster_resolve_links(result);
 
diff --git a/src/gtkext/graph/edge.c b/src/gtkext/graph/edge.c
index a917cc3..ab3a666 100644
--- a/src/gtkext/graph/edge.c
+++ b/src/gtkext/graph/edge.c
@@ -205,6 +205,27 @@ GGraphEdge *_g_graph_edge_new(const GdkPoint *start, const GdkPoint **mid, size_
 
 /******************************************************************************
 *                                                                             *
+*  Paramètres  : edge = ligne de rendu à consulter.                           *
+*                x1   = abscisse du point de départ de la ligne. [OUT]        *
+*                x2   = abscisse du point d'arrivée de la ligne. [OUT]        *
+*                                                                             *
+*  Description : Fournit les abscisses des points extrèmes de la ligne.       *
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+void g_graph_edge_get_x_borders(const GGraphEdge *edge, gint *x1, gint *x2)
+{
+    *x1 = edge->start->x;
+    *x2 = edge->end->x;
+}
+
+
+/******************************************************************************
+*                                                                             *
 *  Paramètres  : edge = ligne de rendu à définir dans les détails.            *
 *                                                                             *
 *  Description : Détermine les positions finales d'un lien graphique.         *
diff --git a/src/gtkext/graph/edge.h b/src/gtkext/graph/edge.h
index 602c559..e2237c3 100644
--- a/src/gtkext/graph/edge.h
+++ b/src/gtkext/graph/edge.h
@@ -75,6 +75,9 @@ GGraphEdge *_g_graph_edge_new(const GdkPoint *, const GdkPoint **, size_t, const
 #define g_graph_edge_new_false(start, y, end) \
     _g_graph_edge_new(start, (const GdkPoint *[]) { y }, 1, end, EGC_RED)
 
+/* Fournit les abscisses des points extrèmes de la ligne. */
+void g_graph_edge_get_x_borders(const GGraphEdge *, gint *, gint *);
+
 /* Détermine les positions finales d'un lien graphique. */
 void g_graph_edge_resolve(GGraphEdge *);