Визуализация графов. Метод связывания ребер

    Иногда полезно представить граф в графической форме, так чтобы была видна структура. Можно привести десятки примеров, где это может пригодиться: визуализация иерархии классов и пакетов исходного кода какой-нибудь программы, визуализация социального графа (тот же Twitter или Facebook) или графа цитирования (какие публикации на кого ссылаются) и т.д. Но вот незадача: количество ребер в графе зачастую настолько велико, что нарисованный граф просто невозможно разобрать. Взгляните на эту картинку:



    Это граф зависимостей некой программной системы. Он представляет собой дерево разбиения на пакеты (серые шарики — пакеты, белые — классы), на которое поверх наложены ребра зависимости одних классов от других. Чтобы не рисовать стрелки направления, ребра нарисованы в виде градиентных линий, где зеленый — это начало, а красный — конец ребра. Как видите, граф настолько визуально перегружен, что архитектуру программы невозможно проследить.
    Под катом описание метода, решающего эту проблему.


    Описание метода


    Идея метода гениально проста — почему бы не использовать тот же принцип, что и в кабельных сетях? Многие из нас знают, какой бардак начинается, когда проводов становится слишком много. Для того, чтобы это бардак предотвратить, провода объединяют в жгуты.
    Как эту идею применить к графам и реализовать алгоритмически?

    Рассмотрим пример рисования одного ребра на примере. Необходимо провести ребро из вершины P0 в вершину P4:



    Найдем путь между этими вершинами:



    Теперь проведем кривую через полигон, образованный точками P0, P1, P2, P3, P4:



    Собственно, а как это сделать? Авторы этого метода проанализировали, что лучше всего для целей визуализации в качестве кривых подходят кусочно-заданные кубические B-сплайны. Задача нахождения таких B-сплайнов является классической и давным давно решена другими. Вкратце лишь скажу, что кубический B-сплайн — это просто набор кривых третьего порядка в двухмерном пространстве, для которых выполняется условия сшивки первых и вторых производных на краях. Если кому-то захочется реализовать этот метод, не изобретайте велосипед — в конце я выложил работающий код отрисовки ребер на C#.
    Для того, чтобы управлять степенью связанности ребер, вводится параметр β, который принимает значения от 0 до 1 (0 — ребра не связаны в жгут и представляют собой независимые прямые линии, 1 — ребра максимально связаны друг с другом). Математически это выглядит так:




    S(t) — это точки сплайна, S'(t) — это результирующая кривая, которая и отрисовывается на экран в виде ребра.
    Ну и вот результат того, во что вся эта математика выливается:



    Здесь β = 0.85. Теперь архитектрура программы представляется значительно яснее. Видны отдельные связки ребер, проглядываются зависимости между пакетами.
    Тот же граф, только используется радиальный способ визуализации архитектуры (без применения метода, эквивалентно β = 0):



    С применением метода (β = 0.85):



    Как видно, метод связывания ребер можно сочитать с различными методами рисования деревьев: в этом его большое преимущество.

    Другие примеры


    Граф цитирования публикаций. Зеленый круг — это публикации 2008 года, которые ссылаются на публикации предыдущих годов (2007, 2006 и т.д.). Отмечаются только ссылки публикаций 2008 года. Без применения метода это выглядит так:


    С применением метода (β = 0.99):



    Замечания


    1. Чтобы не было вот такого:



    можно использовать альфа-канал:



    2. Если из контрольного полигона удалить вершину LCA (least common ancestor, наименьший общий предок между соединяемыми вершинами), то граф будет выглядеть значительно лучше. Взгляните на разницу:

     

    Во втором случае вершина LCA исключается из набора вершин, и граф выглядит намного красивее.

    Реализация на C#


    Ниже выложена реализация класса-расширения System.Drawing.Graphics, который умеет рисовать кубический Б-сплайн через набор вершин.

    using System;
    using System.Text;
    using System.Drawing;

    static class GraphicsExtension
    {
      private static void DrawCubicCurve(this Graphics graphics, Pen pen, float beta, float step, PointF start, PointF end, float a3, float a2, float a1, float a0, float b3, float b2, float b1, float b0)
      {
        float xPrev, yPrev;
        float xNext, yNext;
        bool stop = false;

        xPrev = beta * a0 + (1 - beta) * start.X;
        yPrev = beta * b0 + (1 - beta) * start.Y;

        for (float t = step; ; t += step)
        {
          if (stop)
            break;

          if (t >= 1)
          {
            stop = true;
            t = 1;
          }

          xNext = beta * (a3 * t * t * t + a2 * t * t + a1 * t + a0) + (1 - beta) * (start.X + (end.X - start.X) * t);
          yNext = beta * (b3 * t * t * t + b2 * t * t + b1 * t + b0) + (1 - beta) * (start.Y + (end.Y - start.Y) * t);

          graphics.DrawLine(pen, xPrev, yPrev, xNext, yNext);

          xPrev = xNext;
          yPrev = yNext;
        }
      }

      /// <summary>
      /// Draws a B-spline curve through a specified array of Point structures.
      /// </summary>
      /// <param name="pen">Pen for line drawing.</param>
      /// <param name="points">Array of control points that define the spline.</param>
      /// <param name="beta">Bundling strength, 0 <= beta <= 1.</param>
      /// <param name="step">Step of drawing curve, defines the quality of drawing, 0 < step <= 1</param>
      internal static void DrawBSpline(this Graphics graphics, Pen pen, PointF[] points, float beta, float step)
      {
        if (points == null)
          throw new ArgumentNullException("The point array must not be null.");

        if (beta < 0 || beta > 1)
          throw new ArgumentException("The bundling strength must be >= 0 and <= 1.");

        if (step <= 0 || step > 1)
          throw new ArgumentException("The step must be > 0 and <= 1.");

        if (points.Length <= 1)
          return;

        if (points.Length == 2)
        {
          graphics.DrawLine(pen, points[0], points[1]);
          return;
        }

        float a3, a2, a1, a0, b3, b2, b1, b0;
        float deltaX = (points[points.Length - 1].X - points[0].X) / (points.Length - 1);
        float deltaY = (points[points.Length - 1].Y - points[0].Y) / (points.Length - 1);
        PointF start, end;

        {
          a0 = points[0].X;
          b0 = points[0].Y;

          a1 = points[1].X - points[0].X;
          b1 = points[1].Y - points[0].Y;

          a2 = 0;
          b2 = 0;

          a3 = (points[0].X - 2 * points[1].X + points[2].X) / 6;
          b3 = (points[0].Y - 2 * points[1].Y + points[2].Y) / 6;

          start = points[0];
          end = new PointF
          (
            points[0].X + deltaX,
            points[0].Y + deltaY
          );

          graphics.DrawCubicCurve(pen, beta, step, start, end, a3, a2, a1, a0, b3, b2, b1, b0);
        }

        for (int i = 1; i < points.Length - 2; i++)
        {
          a0 = (points[i - 1].X + 4 * points[i].X + points[i + 1].X) / 6;
          b0 = (points[i - 1].Y + 4 * points[i].Y + points[i + 1].Y) / 6;

          a1 = (points[i + 1].X - points[i - 1].X) / 2;
          b1 = (points[i + 1].Y - points[i - 1].Y) / 2;

          a2 = (points[i - 1].X - 2 * points[i].X + points[i + 1].X) / 2;
          b2 = (points[i - 1].Y - 2 * points[i].Y + points[i + 1].Y) / 2;

          a3 = (-points[i - 1].X + 3 * points[i].X - 3 * points[i + 1].X + points[i + 2].X) / 6;
          b3 = (-points[i - 1].Y + 3 * points[i].Y - 3 * points[i + 1].Y + points[i + 2].Y) / 6;

          start = new PointF
          (
            points[0].X + deltaX * i,
            points[0].Y + deltaY * i
          );

          end = new PointF
          (
            points[0].X + deltaX * (i + 1),
            points[0].Y + deltaY * (i + 1)
          );

          graphics.DrawCubicCurve(pen, beta, step, start, end, a3, a2, a1, a0, b3, b2, b1, b0);
        }

        {
          a0 = points[points.Length - 1].X;
          b0 = points[points.Length - 1].Y;

          a1 = points[points.Length - 2].X - points[points.Length - 1].X;
          b1 = points[points.Length - 2].Y - points[points.Length - 1].Y;

          a2 = 0;
          b2 = 0;

          a3 = (points[points.Length - 1].X - 2 * points[points.Length - 2].X + points[points.Length - 3].X) / 6;
          b3 = (points[points.Length - 1].Y - 2 * points[points.Length - 2].Y + points[points.Length - 3].Y) / 6;

          start = points[points.Length - 1];

          end = new PointF
          (
            points[0].X + deltaX * (points.Length - 2),
            points[0].Y + deltaY * (points.Length - 2)
          );

          graphics.DrawCubicCurve(pen, beta, step, start, end, a3, a2, a1, a0, b3, b2, b1, b0);
        }
      }
    }

    * This source code was highlighted with Source Code Highlighter.


    Литература


    Описанный метод связывания ребер и почти все картинки взяты из статьи «Hierarchical Edge Bundles:
    Visualization of Adjacency Relations in Hierarchical Data». Автор — Danny Holten.
    Поделиться публикацией

    Комментарии 67

      0
      Хороший и простой метод, несколько раз видел в иллюстрациях, но руки не доходили разобраться как это все реализовано. Спасибо.
        0
        Спасибо за статью. Как раз думал, как сделать красивую визуализацию.
          +4
          Красота!
            +3
            Почему бы не реализовать это в 3D? У плоских графов есть известная проблема планарности — если у графа есть подграф K33 или K35, то его дуги будут неизбежно пересекаться на плоскости. Эта непланарность ухудшает наглядность картинки. Графы в трёхмерном пространстве, напротив, не имеют такой проблемы: в 3D надо постараться, чтобы дуги пересекались. Спроецировать кривую Безье на экран — элементарная задача. Осталось написать написать простую рисовалку и картинки как в этой статье станут трёхмерными.
              +1
              Я не уверен, но вроде как 3D, спроецированный на экран, станет 2D, и ребра все равно будут пересекаться. Или вы имеете в виду, что можно будет этот граф повертеть?
              Кстати, кривые Безье и B-сплайны — разные вещи.
                +1
                Да, я имею ввиду, что можно будет повертеть. Различия между кривыми Безье и B-сплайнами, имхо, несущественны: и то и то кусочно полиномиальные кривые с дополнительными условиями гладкости в местах стыков. Одни условия дают сплайны, другие — кривые Безье.
                  +1
                  Ну, в принципе, отличная идея. Может быть даже и возьмусь на досуге за такой проект. Только не вижу смысла ничего проецировать, по-моему лучше реализовать это все на OpenGL.
                    0
                    они не существенны с точки зрения наблюдателя, но с математической, на мой взгляд значительная. Безье это аппроксимизация 1го порядка, а Би-сплайны второго. Что на самом деле дает значительные отличия при визуализации. Безье проходит через начальную и конечную точку изгибаясь от опорной (не помню как точно называется). В то время как Би-сплайн не проходит через начальную и конечную точку, она как бы не дотягивается до них. Для того чтобы Би-сплайны проходили через конечную и начальную необходимо добавить пару фиктивных точек с координатами идентичными реальным начальным и конечным.

                    Извините за зануда-режим, но для меня эта разница является существенной.
                0
                Никогда не понимал, зачем же это вообще нужно-то? На стену повесить в рамочку?
                  +2
                  Проанализировать связи в системе.
                    +8
                    Просмотрите изображения еще раз. Вы уверены, что они как-то приспособлены для анализа?

                    Трудно представить себе такую реплику:
                    — Вот тут посмотрите, у вас связи вокруг класса идут в форме ласточки, перепишите класс, чтобы в этом месте образовался зайчик.
                      +3
                      Зато легко представить себе такую:
                      — Почему здесь имеется связь напрямую к подсистеме БД из клиентского приложения? Необходимо убрать эту связку.
                      Очень легко отслеживать нарушение уровняй абстракции на таких диаграмах.
                        +2
                        На каких диаграммах? image
                          +6
                          Неудачно подобранные примеры нисколько не нивелируют полезность метода в общем.
                            –2
                            Мы про топик с вами говорим, или что?
                              +2
                              В топике говорится про алгоритм. По сути примеров применения в топике 2 (последние картинки описывают отдельных технический аспект алгоритма). Первая картинка достаточно показательна — по ней можно предоположить что у системы (возможно) достаточно посредственная архитектура, исходя из анализа связности и связанности пакетов. Хотя для того, чтобы сказать что-то предметное кроме графика нужно иметь представление и о самой системе изнутри.
                              Второй пример просто не совсем показателен, т.к. в нем уже заданы декртовы координаты вершин графа, но вот если бы они небыли так красиво заданы — то просто так граф было бы не разобрать.
                              Ну а коли в топике говорится про алгоритм, а не про включенные в него картинки — я привел более наглядный пример.
                                –1
                                Давайте сойдемся на том, что такие графы сделаны для того, чтобы отдел программистов отдохнул, ползая по простыне графа и красиво расставляя узлы.
                                  +2
                                  Абсолютно не понял к чему камент.
                                  Такие графы сделаны для упрощения анализа системы, чтобы как раз людям не пришлось вручную приводить граф к удобоваримому виду (ну или чтобы значительно упростить им эту задачу). Без подобных утилит мы получим графы подобные тому, что я привел парой каментов выше — абсолютно нечитаемые.
                                    0
                                    Вы его привели, как пример полезного графа, а теперь он нечитаем. Давайте не будем дальше продолжать эту дискуссию.
                                      +4
                                      В ответ на Ваш комментарий с неудачным графом-кандидатом на обработку я привел граф, на котором данный алгоритм полезен. А раз этот граф претендует на обработку подобными алгоритмами — значит он изначально нечитаем — все вполне очевидно, следите за комментариями, на которые получаете ответ, во избежание путаницы.
                          +1
                          Теоретически, если на всех уровнях соблюдается инкапсуляция, подобных «нежелательных связей» возникнуть не может. Но в реальных приложениях да, согласен.

                          Визуализацию можно сделать динамической и выводить на монитор РМа. Чуть где «проросло» лишнее — сирены, мигалки, алярм! Зондер-команда выдвигается в отдел разработки
                            0
                            Все сводится к тому, что если команда настолько профессиональна, что способна создавать качественные продукты без помощи визуализации графов системы — то она не нуждается в средствах визуализации.
                            0
                            Для анализа полезней будет распечатать схему зависимостей модулей в виде таблички…
                            0
                            Вы пробовали?
                              0
                              Не поймите меня неправильно, графы для анализа системы могут быть полезны во многих задачах.
                              Но представленные в посте — только для красоты, функциональная нагрузка практически нулевая.
                              Такая же польза, как от генерации фракталов.
                                +5
                                А вот насчет фракталов вы ой как сильно ошибаетесь )))
                              +4
                              О, внезапно адекватный комментатор.
                              Я сейчас весьма серьёзно исследую тему использования различных графов для визуализации дизассемблированного кода при реверс инженеринге — вы всё совершенно правильно говорите. Продемонстрированные в данном топике графы годятся максимум в качестве крассивых картинок для того, что бы разбавить скучную презентацию или научную работу.
                                +1
                                Дизассемблированный код != архитектура программной системы. Во втором случае, если у архитектора руки не кривые, картинки вполне могут быть красивыми и полезными.
                            +4
                            А вот пример задачи. Пощёлкайте.
                              –4
                              Очень красиво, прямо как windows seven mobile.
                              –1
                              Нужно для того, чтобы дать визуальное представление и возможность грубо оценить те или иные аспекты визуализируемых данных.
                                +2
                                Оцените какой-нибудь из представленных посте графиков и я с вами сразу же соглашусь.
                                0
                                Вас интересует зачем нужны графы?
                                  0
                                  Нет, в этом случае я бы так и спросил. Меня интересует полезность алгоритма, представленного в топике.
                                    +2
                                    В одном из постов на хабре я видел такую картинку:
                                    image
                                    Метод немного похож на то, что описано мною. Согласитесь, было бы намного уродливее, если бы все ребра были прямыми?
                                  +3
                                  да ладно Вам, прикольно же :)
                                    0
                                    Для проектирования правильной обвязки поводов за системником, у меня сейчас первый вариант, завтра будет второй.
                                      0
                                      ох, неблагодарное это дело. сколько красоту ни наводил — через пару недель снова все разбираешь и в клубок
                                    +1
                                    Не знаю почему, но у меня первая ассоциация с СКС :-)
                                      0
                                      Несмотря на просьбу автора не изобретать велосипед, все же спрошу: где можно прочитать о алгоритме вывода B-сплайнов?
                                        0
                                        Собственно, главный вопрос — почему расчет значений, кроме основного цикла, имеет еще два случая — для 3 начальных точек и 2 конечных, и откуда взяты формулы для них (с формулами в цикле ясно, в вики они описаны в «Uniform cubic B-splines» в самом конце страницы http://en.wikipedia.org/wiki/B-spline)
                                          0
                                          Не для 2 конечных, а для 3 конечных: в начале для построения кривой используются точки P0, P1, P2 и в конце PN-1, PN-2, PN-3.

                                          Почему эти случаи рассматриваются отдельно? Потому что на краях условия сшивки другие. Ведь точек с индексами P-1 и PN нету, следовательно нужно придумывать что-то другое. Я взял следующие условия:
                                          — Первая производная совпадает с направление вектора P1 — P0 (коэффициенты a1 и b1)
                                          — Вторая производная равна нулю (чтобы кривизна была нулевой, т.е. a2 = b2 = 0)
                                          — Остальные коэффициенты a0, b0, a3, b3 определяется из условия равенства на краях.
                                            0
                                            Простите, PN-1 не заметил. Теперь стало яснее, но вот еще такой момент: комментарием ниже вы говорите, что выводили формулы сами, однако какими-то материалами вы ведь все равно пользовались для этого, что, думаю, логично? Возможно, расскажете о том, как пришли к описаным вами выше условиям на краях?
                                              0
                                              Материалами не пользовался. Я просто обобщил свои знания по сплайнам на двумерное пространттво. Условия на краях вывел из общих соображений:
                                              1. Кривая должна выходить из точки P0
                                              2. Кривая должна касаться отрезка, соединяющей P1-P0
                                              3. Кривая должна иметь нулевую кривизну: это стандартное условие для любых сплайнов (необязательно двумерных).

                                              Аналогично для другого края.
                                                0
                                                Да, увы, русскоязычный интернет весьма беден сведениями о сплайнах («Кривая должна иметь нулевую кривизну: это стандартное условие для любых сплайнов»). Что поделать, буду искать на этот счет материалы на английском.
                                          0
                                          Я, ради спортивного интереса, выводил все формулы сам, поэтому книжку наподобие «B-сплайны для чайников» вряд ли смогу посоветовать. Скорее всего, такое есть в каких-нибудь книжках по выч.методам.
                                          0
                                          Удобно. Для наглядности можно ещё ползунок сделать, который будет значение β изменять с одновременным динамическим изменением картинки.
                                            0
                                            Собственно, так и было сделано. Вот только когда графы большие, все начинает жутко тормозить, поэтому этот ползунок был впоследствии ликвидирован.
                                              0
                                              Готовый проект выложите?
                                                0
                                                Писал не я. Если уговорю, то может и выложим. Но сначала там нужно говнокод исправить, так что в любом случае это будет нескоро.
                                            –1
                                            Спасибо за хорошую и объемную статью c примером на внятном языке.
                                              0
                                              Рад стараться)
                                              +2
                                              Суперкруто.

                                              У меня кстати была идея чтобы в операционных системах сделать также наглядно список всех исполняемых процессов и их связи. И соединять или разрывать связи между этими шариками (процессами). Вроде такого интерфейса.
                                                +2
                                                А что такое связи между процессами?
                                                  0
                                                  pstree
                                                    0
                                                    pstree — это ведь просто дерево, нет? А в статье речь идет о графах.
                                                0
                                                Подскажите какие инструменты для визуализации в NET вы используете в своей работе?
                                                  0
                                                  Я? Никакие. Это не я картинки рисовал.
                                                  0
                                                  Возможно, я что-то упустил, но каким образом выбираются опорные точки для прорисовки сплайнов? То есть, с конечными точками всё понятно, а вот с промежуточными не всё ясно. Используется какая-то сетка?
                                                    +1
                                                    Опорные точки считаются по формуле Ci = (Pi-1 + 4 Pi + Pi+1) / 6
                                                    Крайние точки считаются отдельно и равны соответствующим крайним контрольным точкам.

                                                    Это выглядит вот так:
                                                    image
                                                      +1
                                                      (Коэффициенты 1/6, 4/6 и 1/6 вытекают из равенста первых и вторых производных при сшивке, можете проверить)
                                                        0
                                                        Нет-нет, с самим построением сплайна всё понятно. Тут интересней другое — как выбираются точки P1 и P2, в частности?
                                                          0
                                                          Точки P1, P2 и т.д. — это вершины дерева, через которые проходит путь между соединяемыми вершинами.
                                                            0
                                                            А построение дерева — это, видимо, отдельная задача, имеющая множество вариантов решения и не связанная непосредственно с данным алгоритмом визуализации. Спасибо за пояснения и саму статью.
                                                              0
                                                              >> А построение дерева — это, видимо, отдельная задача, имеющая множество вариантов решения

                                                              Да, вы совершенно правы. Вы строите дерево любым удобным для вас способом, а потом накладываете на него ребра описанным методом.
                                                      0
                                                      Интересная статья, спасибо. Еще бы с Graph# это соединить.
                                                        0
                                                        Если Вы дополнительно к этому алгоритму прикрутите интерактивность, например, возможность выделить все линии пучка другим цветом ивозможность оставить только часть графа, то подобный софт будет очень и очень востребован :-) Респект!

                                                        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                        Самое читаемое