Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Карта связей

341
20 мая 2008 года
Der Meister
874 / / 21.12.2007
Всем привет.
Было, но не раскрыто: есть граф - набор узлов и связей между ними. Связи играют ключевую роль, являются направленными и бывают двух видов, к примеру, положительные и отрицательные. Необходимо расположить узлы так, чтобы в центре графа оказались узлы с наибольшим количеством входящих/исходящих связей, по краям - узлы с наименьшим количеством положительных связей, либо узлы с максимальным количеством отрицательных связей. Ну, и вся картинка должна, в конце концов, быть удобочитаемой и наглядной. Критерием качества тут будет являться возможность легкого разбиения графа на группы по связям.
Есть идея располагать узлы по концентрическим окружностям, учитывая количество положительных связей. Но, как видно на картинке, такой алгоритм не всегда приведёт к получению наглядной карты взаимосвязей узлов.
Так вот, как лучше построить такой граф, а точнее карту взаимосвязей?
341
28 мая 2008 года
Der Meister
874 / / 21.12.2007
Всё, и без вас разобрался.
Код:
class Node
{
    public Point Position;
    public Point Disp;
}

public class Edge
{
    public Node From;
    public Node To;
}

public class App
{
    double fr(double z, double k) { return k * k / z; }
    double fa(double z, double k) { return z * z / k; }

    void Spread()
    {
        int maxwidth = m_Nodes.Count * 30;
        int maxheight = maxwidth;

        double temperature = maxwidth / 10.0;
        double t = temperature;

        double area = (double)maxwidth * maxheight;
        double k = Math.Sqrt(area / m_Nodes.Count);

        int itercount = 30;

        Random rnd = new Random(0);
        foreach (Node v in m_Nodes)
        {
            v.Position.X = rnd.Next(maxwidth);
            v.Position.Y = rnd.Next(maxheight);
        }

        for (int i = 0; i < itercount; i++)
        {
            Invalidate();
            Application.DoEvents();
            System.Threading.Thread.Sleep(1000);

            foreach (Node v in m_Nodes)
            {
                v.Disp = Point.Empty;
                foreach (Node u in m_Nodes)
                {
                    if (v != u)
                    {
                        Point delta = new Point();
                        delta.X = v.Position.X - u.Position.X;
                        delta.Y = v.Position.Y - u.Position.Y;

                        double l = Math.Sqrt(
                            Math.Pow(delta.X, 2.0) + Math.Pow(delta.Y, 2.0)
                        );

                        double d = fr(l, k) / l;

                        v.Disp.X += (int)(delta.X * d);
                        v.Disp.Y += (int)(delta.Y * d);
                    }
                }
            }

            foreach (Edge r in m_Edges)
            {
                Point delta = new Point();
                delta.X = r.From.Position.X - r.To.Position.X;
                delta.Y = r.From.Position.Y - r.To.Position.Y;

                double l = Math.Sqrt(
                    Math.Pow(delta.X, 2) + Math.Pow(delta.Y, 2)
                );

                double d = fa(l, k) / l;

                r.From.Disp.X -= (int)(delta.X * d);
                r.From.Disp.Y -= (int)(delta.Y * d);

                r.To.Disp.X += (int)(delta.X * d);
                r.To.Disp.Y += (int)(delta.Y * d);
            }

            foreach (Node v in m_Nodes)
            {
                double l = Math.Sqrt(
                    Math.Pow(v.Disp.X, 2.0) + Math.Pow(v.Disp.Y, 2.0)
                );

                double d = Math.Min(l, temperature) / l;
                v.Position.X += (int)(v.Disp.X * d);
                v.Position.Y += (int)(v.Disp.Y * d);

                v.Position.X = Math.Min(
                    maxwidth,
                    (Math.Max(1, v.Position.X))
                );
                v.Position.Y = Math.Min(
                    maxheight,
                    (Math.Max(1, v.Position.Y))
                );
            }
            t -= temperature / itercount;
        }
    }
}
39K
25 мая 2008 года
lovebeijso
1 / / 23.05.2008
it is better to fight for good than to fail at the ill.-------------------------Our wow power leveling website offer Fast and Secure wow powerleveling service. WoW Power Leveling 60-70, Cheap wow power leveling 1-70. The Professional WoW Power Leveling! Powerlevel WoW Power Leveling now. WOrld of warcraft Power Leveling bloom of true love associated with this time of year!
341
28 мая 2008 года
Der Meister
874 / / 21.12.2007
Набрёл вот на это, затем на это. Однако, результат не впечатляет: симуляция происходит неверно (узлы выстраиваются в одну линию и гоняют вдоль неё), несмотря на то, что суть алгоритма была вкурена и реализована с точностью до. Реализовывал ли кто-нибудь подобное? В книге очепяток куча, и мож я просто ошибочные формулы использую?
341
28 мая 2008 года
Der Meister
874 / / 21.12.2007
И, кстати, оттопырил вот такую хрень для коннекторов между узлами
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог