Layout.cs

Go to the documentation of this file.

#region License
/*This file is part of Satsuma Graph Library
Copyright © 2013 Balázs Szalkai

This software is provided 'as-is', without any express or implied
warranty. In no event will the authors be held liable for any damages
arising from the use of this software.

Permission is granted to anyone to use this software for any purpose,
including commercial applications, and to alter it and redistribute it
freely, subject to the following restrictions:

   1. The origin of this software must not be misrepresented; you must not
   claim that you wrote the original software. If you use this software
   in a product, an acknowledgment in the product documentation would be
   appreciated but is not required.

   2. Altered source versions must be plainly marked as such, and must not be
   misrepresented as being the original software.

   3. This notice may not be removed or altered from any source
   distribution.*/
#endregion

using System;
using System.Collections.Generic;
using System.Linq;
using System.Xml.Linq;
using System.Drawing;
using System.Globalization;

namespace Satsuma.Drawing
{
    public struct PointD : IEquatable<PointD>
    {
        public double X { get; private set; }
        public double Y { get; private set; }

        public PointD(double x, double y)
            : this()
        {
            X = x;
            Y = y;
        }

        public bool Equals(PointD other)
        {
            return X == other.X && Y == other.Y;
        }

        public override bool Equals(object obj)
        {
            if (!(obj is PointD)) return false;
            return Equals((PointD)obj);
        }

        public static bool operator ==(PointD a, PointD b)
        {
            return a.Equals(b);
        }

        public static bool operator !=(PointD a, PointD b)
        {
            return !(a == b);
        }

        public override int GetHashCode()
        {
            return (X.GetHashCode() * 17) + Y.GetHashCode();
        }

        public string ToString(IFormatProvider provider)
        {
            return string.Format(provider, "({0} {1})", X, Y);
        }

        public override string ToString()
        {
            return ToString(CultureInfo.CurrentCulture);
        }

        public static PointD operator +(PointD a, PointD b)
        {
            return new PointD(a.X + b.X, a.Y + b.Y);
        }

        public static PointD Add(PointD a, PointD b)
        {
            return a + b;
        }

        public static explicit operator PointF(PointD self)
        {
            return new PointF((float)self.X, (float)self.Y);
        }

        public static PointF ToPointF(PointD self)
        {
            return (PointF)self;
        }

        public double Distance(PointD other)
        {
            return Math.Sqrt((X - other.X) * (X - other.X) + (Y - other.Y) * (Y - other.Y));
        }
    }

    public sealed class ForceDirectedLayout
    {
        public const double DefaultStartingTemperature = 0.2;
        public const double DefaultMinimumTemperature = 0.01;
        public const double DefaultTemperatureAttenuation = 0.95;

        public IGraph Graph { get; private set; }
        public Dictionary<Node, PointD> NodePositions { get; private set; }
        public Func<double, double> SpringForce { get; set; }
        public Func<double, double> ElectricForce { get; set; }
        public double Temperature { get; set; }
        public double TemperatureAttenuation { get; set; }
        
        public ForceDirectedLayout(IGraph graph, Func<Node, PointD> initialPositions = null)
        {
            Graph = graph;
            NodePositions = new Dictionary<Node, PointD>();
            SpringForce = (d => 2 * Math.Log(d));
            ElectricForce = (d => 1 / (d * d));
            TemperatureAttenuation = DefaultTemperatureAttenuation;
        
            Initialize(initialPositions);
        }

        public void Initialize(Func<Node, PointD> initialPositions = null)
        {
            if (initialPositions == null)
            {
                // make a random layout
                Random r = new Random();
                initialPositions = (node => new PointD(r.NextDouble(), r.NextDouble()));
            }

            foreach (var node in Graph.Nodes())
                NodePositions[node] = initialPositions(node);

            // reset the temperature
            Temperature = DefaultStartingTemperature;
        }

        public void Step()
        {
            Dictionary<Node, PointD> forces = new Dictionary<Node, PointD>();

            foreach (var u in Graph.Nodes())
            {
                PointD uPos = NodePositions[u];
                double xForce = 0, yForce = 0;
                // attraction forces
                foreach (var arc in Graph.Arcs(u))
                {
                    PointD vPos = NodePositions[Graph.Other(arc, u)];
                    double d = uPos.Distance(vPos);
                    double force = Temperature * SpringForce(d);
                    xForce += (vPos.X - uPos.X) / d * force;
                    yForce += (vPos.Y - uPos.Y) / d * force;
                }
                // repulsion forces
                foreach (var v in Graph.Nodes())
                {
                    if (v == u) continue;
                    PointD vPos = NodePositions[v];
                    double d = uPos.Distance(vPos);
                    double force = Temperature * ElectricForce(d);
                    xForce += (uPos.X - vPos.X) / d * force;
                    yForce += (uPos.Y - vPos.Y) / d * force;
                }
                forces[u] = new PointD(xForce, yForce);
            }

            foreach (var node in Graph.Nodes())
                NodePositions[node] += forces[node];
            Temperature *= TemperatureAttenuation;
        }

        public void Run(double minimumTemperature = DefaultMinimumTemperature)
        {
            while (Temperature > minimumTemperature) Step();
        }
    }
}