Graph.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
using System.Windows.Media;
using System.Windows;

namespace EdgeClustering
{
    /// \author Manuel Keglevic
    /// \author Thomas Schulz
    /// <summary>
    /// This class provides all the functionality to compute the edge bundled graph. All computationals
    /// functions are bundled here.
    /// </summary>
    class Graph
    {
        
        /// <summary>
        /// Structur with global computation settings.
        /// </summary>
        public struct Settings{
            private static int gridSize = 5;
            public static int GridSize
            {
                get { return Settings.gridSize; }
                set { Settings.gridSize = value; }
            }

            private static double kdeRadius = 30;
            public static double KdeRadius
            {
                get { return Settings.kdeRadius; }
                set { Settings.kdeRadius = value; }
            }
            
            private static int kdeHistogramSize = 360;
            public static int KdeHistogramSize
            {
                get { return Settings.kdeHistogramSize; }
                set { Settings.kdeHistogramSize = value; }
            }
            
            private static double kdeThreshold = 0.01;
            public static double KdeThreshold
            {
                get { return Settings.kdeThreshold; }
                set { Settings.kdeThreshold = value; }
            }

            private static double border = 0.01;

            public static double Border
            {
                get { return Settings.border; }
                set { Settings.border = value; }
            }
        }

        private  static double randomWidth = 100;
        private  static double randomHeight = 100;

        private int stage = 0;
        public int ComputingStage
        {
            get { return stage; }
        }

        #region DataStructures
        private List<SimpleEdge> simpleEdges;
        public List<SimpleEdge> SimpleEdges
        {
            get { return simpleEdges; }
        }

        private PointCollection points;
        public PointCollection Points
        {
            get { return points; }
        }

        private ArrayList[,] grid;
        public ArrayList[,] Grid
        {
            get { return grid; }
        }

        private double[,] kernelPeaks;
        public double[,] KernelPeaks
        {
            get { return kernelPeaks; }
        }

        private List<MergedSegment> mergedSegments;
        public List<MergedSegment> MergedSegments
        {
            get { return mergedSegments; }
        }

        private List<SimpleEdge> meshEdges;
        public List<SimpleEdge> MeshEdges
        {
            get { return meshEdges; }
        }

        private ControlMesh controlMesh = new ControlMesh();

        private List<EnhancedEdge> enhancedEdges;
        public List<EnhancedEdge> EnhancedEdges
        {
            get { return enhancedEdges; }
        }
        #endregion

        public static double gridScale;

        private double maxPointValue;
        public double MaxPointValue
        {
            get { return maxPointValue; }
        }

        public ControlMesh ControlMesh { get { return controlMesh; } }

        /// <summary>
        /// Initializes a new random Graph
        /// </summary>
        /// <param name="points">number of points</param>
        /// <param name="edges">number of edges per point</param>
        public Graph(int points, int edges)
        {
            RandomInit(points, edges);
            //TestInit(points);
            CalcGridScale();    //done in compute too - might not be necessary
        }

        /// <summary>
        /// Loads a graph from a xml data file
        /// </summary>
        /// <param name="filename">filename of the datafile</param>
        public Graph(string filename)
        {
            ReadXMLInit(filename);
            CalcGridScale();    //done in compute too - might not be necessary
        }

        /// <summary>
        /// Saves the graph to an XML file.
        /// </summary>
        /// <param name="filename"></param>
        public void WriteXMLGraph(String filename)
        {
            XMLData.WriteLinkedNodes(simpleEdges,filename);
        }

        /// <summary>
        /// Reads a graph out of an XML file. 
        /// </summary>
        /// <param name="filename"></param>
        public void ReadXMLInit(String filename)
        {
            simpleEdges = XMLData.ReadLinkedNodes(filename);
            points = new PointCollection();

            foreach (SimpleEdge s in simpleEdges)
            {
                if (!points.Contains(s.A))
                    points.Add(s.A);
                if (!points.Contains(s.B))
                    points.Add(s.B);
            }
        }

        /// <summary>
        /// Initializes the graph datastructures with test data.
        /// </summary>
        /// <param name="size">The size of the PointCollection</param>
        private void TestInit(int size)
        {
            points = new PointCollection(size);
            //points.Add(new Point(21.5, 1));
            //points.Add(new Point(7, 18.5));
            //points.Add(new Point(10.9, 5.8));
            //points.Add(new Point(10.7, 18.9));
            //points.Add(new Point(24.3, 16.4));

            //points.Add(new Point(4.3, 4.15));
            //points.Add(new Point(19.8, 18.75));
            //points.Add(new Point(16.6, 3.35));
            //points.Add(new Point(4.8, 29.1));
            //points.Add(new Point(31.3, 16.4));
            //points.Add(new Point(20.9, 31.8));

            points.Add(new Point(4.3, 4.15));
            points.Add(new Point(19.8, 4.15));
            points.Add(new Point(16.6, 3.35));
            points.Add(new Point(20.8, 3.35));
            points.Add(new Point(1.3, 5));
            points.Add(new Point(10.9, 5));

            //paper1
            //points.Add(new Point(1, 1));
            //points.Add(new Point(1, 2));
            //points.Add(new Point(1, 3));
            //points.Add(new Point(1, 4));
            //points.Add(new Point(1, 5));
            //points.Add(new Point(21, 1));
            //points.Add(new Point(21, 2));
            //points.Add(new Point(21, 3));
            //points.Add(new Point(21, 4));
            //points.Add(new Point(21, 5));

            //paper2
            //Points.Add(new Point(2, 1));
            //points.Add(new Point(1, 2));
            //points.Add(new Point(20, 0.5));
            //points.Add(new Point(21, 1.5));
            //points.Add(new Point(7, 13));
            //points.Add(new Point(8, 13.3));
            //points.Add(new Point(20, 14));

            //points.Add(new Point(3, 1));
            //points.Add(new Point(3, 11));

            simpleEdges = new List<SimpleEdge>(size);

            simpleEdges.Add(new SimpleEdge(points[0], points[1]));
            simpleEdges.Add(new SimpleEdge(points[2], points[3]));
            simpleEdges.Add(new SimpleEdge(points[4], points[5]));
            //simpleEdges.Add(new SimpleEdge(points[1], points[0]));

            //paper1
            //simpleEdges.Add(new SimpleEdge(points[0], points[1]));
            //simpleEdges.Add(new SimpleEdge(points[0], points[5]));
            //simpleEdges.Add(new SimpleEdge(points[0], points[6]));

            //simpleEdges.Add(new SimpleEdge(points[1], points[7]));
            //simpleEdges.Add(new SimpleEdge(points[1], points[6]));
            //simpleEdges.Add(new SimpleEdge(points[1], points[5]));
            //simpleEdges.Add(new SimpleEdge(points[1], points[2]));

            //simpleEdges.Add(new SimpleEdge(points[2], points[7]));
            //simpleEdges.Add(new SimpleEdge(points[2], points[6]));
            //simpleEdges.Add(new SimpleEdge(points[2], points[8]));
            //simpleEdges.Add(new SimpleEdge(points[2], points[3]));

            //simpleEdges.Add(new SimpleEdge(points[3], points[7]));
            //simpleEdges.Add(new SimpleEdge(points[3], points[8]));
            //simpleEdges.Add(new SimpleEdge(points[3], points[9]));
            //simpleEdges.Add(new SimpleEdge(points[3], points[4]));

            //simpleEdges.Add(new SimpleEdge(points[4], points[8]));
            //simpleEdges.Add(new SimpleEdge(points[4], points[9]));

            //simpleEdges.Add(new SimpleEdge(points[5], points[6]));
            //simpleEdges.Add(new SimpleEdge(points[6], points[7]));
            //simpleEdges.Add(new SimpleEdge(points[7], points[8]));
            //simpleEdges.Add(new SimpleEdge(points[8], points[9]));

            //paper2
            //simpleEdges.Add(new SimpleEdge(points[0], points[2]));
            //simpleEdges.Add(new SimpleEdge(points[0], points[4]));
            //simpleEdges.Add(new SimpleEdge(points[0], points[6]));

            //simpleEdges.Add(new SimpleEdge(points[1], points[2]));
            //simpleEdges.Add(new SimpleEdge(points[1], points[6]));
            //simpleEdges.Add(new SimpleEdge(points[1], points[5]));
            //simpleEdges.Add(new SimpleEdge(points[1], points[4]));

            //simpleEdges.Add(new SimpleEdge(points[2], points[4]));
            //simpleEdges.Add(new SimpleEdge(points[2], points[5]));
            //simpleEdges.Add(new SimpleEdge(points[2], points[6]));
            //simpleEdges.Add(new SimpleEdge(points[2], points[3]));

            //simpleEdges.Add(new SimpleEdge(points[3], points[4]));
            //simpleEdges.Add(new SimpleEdge(points[3], points[5]));
            //simpleEdges.Add(new SimpleEdge(points[3], points[6]));

            //simpleEdges.Add(new SimpleEdge(points[5], points[6]));
        }

        /// <summary>
        /// Computes random points and edges.
        /// </summary>
        /// <param name="numofPoints">number of random points</param>
        /// <param name="numofEdges">number of random edges per point</param>
        private void RandomInit(int numofPoints, int numofEdges)
        {
            points = new PointCollection(numofPoints);
            Random r = new Random();

            for (int i = 0; i < numofPoints; i++)
            {
                double x = r.NextDouble()*randomWidth;
                double y = r.NextDouble()*randomHeight;

                points.Add(new Point(x, y));
            }



            simpleEdges = new List<SimpleEdge>(numofPoints * numofEdges);

            int n;
            foreach (Point p in points)
            {
                for (int i = 0; i < numofEdges; i++)
                {
                    do
                    {
                        n = r.Next(points.Count);
                    } while (points[n] == p);

                    simpleEdges.Add(new SimpleEdge(p, points[n]));
                }
            }
        }

        /// <summary>
        /// Computes the GridScale Value for the points in points
        /// </summary>
        private void CalcGridScale()
        {
            if (points == null)
                return;

            double yMax=0, xMax = 0;

            //Compute max x, y value - x,y may not be negative!
            foreach (Point p in points)
            {
                xMax = (p.X > xMax) ? p.X : xMax;
                yMax = (p.Y > yMax) ? p.Y : yMax;
            }

            maxPointValue = Math.Max(xMax, yMax) * (1 + Settings.Border);
            gridScale = maxPointValue / Settings.GridSize;
        }

        /// <summary>
        /// Generates the edge-bundled graph by calling all necessary functions 
        /// depending on the global  graph settings.
        /// </summary>
        public void Compute()
        {
            stage = 0;

            CalcGridScale();            //Caluclate new gridScale if gridSize changed
            CalculateGridElements();    //Calculate gridSegments - stage 1
            stage++;

            CalculateKDEPeaks();        //Calculate KDE peaks - stage 2     
            stage++;

            MergeSegments();            //Merge Segments - stage 3
            stage++;

            ComputeMeshEdges();         //Control mesh Edges - stage 4
            stage++;

            //controlMesh.GenerateTestControlMesh(meshEdges);
            controlMesh.CalculateControlMesh(meshEdges);
            stage++;                    //TestControlMesh - stage 5

            enhancedEdges = controlMesh.Intersect(simpleEdges);
            stage++;                    //Intersect with control mesh - stage 6
        }

        public void MoveControlMeshVertex(Point position,Vector move)
        {
            position.X /= gridScale;
            position.Y /= gridScale;

           
        }

        /// <summary>
        /// Calculates the grid segments
        /// </summary>
        public void CalculateGridElements()
        {
            grid = new ArrayList[Settings.GridSize, Settings.GridSize];

            foreach (SimpleEdge edge in simpleEdges)
            {
                double deltaX = edge.B.X - edge.A.X;    //X Abstand zwischen den Punkten
                double deltaY = edge.B.Y - edge.A.Y;

                double d = deltaY / deltaX;         //Steigung

                FillGrid(d, edge.Alpha, edge.A.X / gridScale, edge.B.X / gridScale,
                    edge.A.Y / gridScale, edge.B.Y / gridScale);
            }
        }

        /// <summary>
        /// Fills each grid cell that is intersected by the passed line with 
        /// the angle <code>angle</code>.
        /// </summary>
        /// <param name="deltavalue">The gradient of the line</param>
        /// <param name="angle">The angle of the line</param>
        /// <param name="Ax">The X-coordinate of the first point</param>
        /// <param name="Bx">The X-coordinate of the second point</param>
        /// <param name="Ay">The Y-coordinate of the first point</param>
        /// <param name="By">The Y-coordinate of the second point</param>
        public void FillGrid(double deltavalue, double angle, double Ax, double Bx, double Ay, double By)
        {
            if ((Ax == Bx && Ay == By) || deltavalue == double.NaN)
                return;
            int x = (int)Ax; //start
            double d = deltavalue;
            Console.WriteLine("(" + Ax + ", " + Ay + ") - (" + Bx + ", " + By + ")");
            int xmin = (int)(Math.Min(Ax, Bx)), xmax = (int)Math.Max(Ax, Bx), ymin = (int)(Math.Min(Ay, By)), ymax = (int)Math.Max(Ay, By);

            // set start point
            if (grid[x, (int)Ay] == null)
                grid[x, (int)Ay] = new ArrayList();
            grid[x, (int)Ay].Add(angle);

            if (Ax < Bx)
            {
                x++;
                while (x < Bx)
                {
                    //cakculate y
                    int ypos = (int)(Ay + ((double)x - Ax) * d);

                    //check if y is out of grid
                    if (ypos < 0 || ypos >= grid.GetLength(1) || ypos > ymax || ypos < ymin)
                    {
                        x++;
                        continue;
                    }

                    if (grid[x, ypos] == null)
                        grid[x, ypos] = new ArrayList();
                    grid[x, ypos].Add(angle);

                    x++;
                }
            }
            else
            {
                while (x > Bx)
                {
                    //cakculate y
                    int ypos = (int)(Ay + ((double)x - Ax) * d);

                    //check if y is out of grid
                    if (ypos < 0 || ypos >= grid.GetLength(1) || ypos > ymax || ypos < ymin || x < 1)
                    {
                        x--;
                        continue;
                    }

                    if (grid[x - 1, ypos] == null)
                        grid[x - 1, ypos] = new ArrayList();
                    grid[x - 1, ypos].Add(angle);

                    x--;
                }
            }

            int y = (int)Ay; //start

            if (Ay < By)
            {
                y++;
                while (y < By)
                {
                    //cakculate x
                    int xpos = (int)(((double)(y - Ay) / d) + Ax);

                    //check if x is out of grid
                    if (xpos < 0 || xpos >= grid.GetLength(0) || xpos > xmax || xpos < xmin)
                    {
                        y++;
                        continue;
                    }

                    if (grid[xpos, y] == null)
                        grid[xpos, y] = new ArrayList();
                    grid[xpos, y].Add(angle);

                    y++;
                }
            }
            else
            {
                while (y > By)
                {
                    //cakculate x
                    int xpos = (int)(((double)(y - Ay) / d) + Ax);

                    //check if x is out of grid
                    if (xpos < 0 || xpos >= grid.GetLength(0) || xpos > xmax || xpos < xmin || y < 1)
                    {
                        y--;
                        continue;
                    }

                    if (grid[xpos, y - 1] == null)
                        grid[xpos, y - 1] = new ArrayList();
                    grid[xpos, y - 1].Add(angle);

                    y--;
                }
            }
        }

        /// <summary>
        /// Calculates the kde peaks for the segments with the threshold and kde settings 
        /// defined by the static kde values.
        /// </summary>
        public void CalculateKDEPeaks()
        {
            //Set KDE Settings
            KernelDensityEstimator.HistogramSize = Settings.KdeHistogramSize;
            KernelDensityEstimator.GenerateKernel(Settings.KdeRadius);

            //Array for peaks
            kernelPeaks = new double[Settings.GridSize, Settings.GridSize];


            //Calculate KernelDensityEstimator peaks
            for (int x = 0; x < Settings.GridSize; x++)
            {
                for (int y = 0; y < Settings.GridSize; y++)
                {
                    if (grid[x, y] != null)
                        kernelPeaks[x, y] = KernelDensityEstimator.CalculateMaximum((double[])grid[x, y].ToArray(typeof(double)), Settings.KdeThreshold);
                    else
                        kernelPeaks[x, y] = -1;     //Set -1 if no data for this segment
                }
            }
        }

        /// <summary>
        /// Merges the segments based on the kde peaks.
        /// </summary>
        public void MergeSegments()
        {
            
            mergedSegments = new List<MergedSegment>();

            //Parse elements and calculate segments
            for (int x = 0; x < Settings.GridSize; x++)
            {
                for (int y = 0; y < Settings.GridSize; y++)
                {
                    if (kernelPeaks[x, y] != -1)
                    {
                        MergedSegment s = new MergedSegment(new MergedSegment.Segment(x, y, kernelPeaks[x, y], grid[x, y].Count));
                        int i = mergedSegments.IndexOf(s);

                        while (i != -1)
                        {
                            s.AddMergedSegment(mergedSegments[i]);
                            mergedSegments.RemoveAt(i);

                            i = mergedSegments.IndexOf(s);
                        }

                        mergedSegments.Add(s);

                    }
                }
            }

        }

        /// <summary>
        /// Compute control mesh edges for each merged segment
        /// </summary>
        private void ComputeMeshEdges()
        {
            meshEdges = new List<SimpleEdge>();

            SimpleEdge tmp;
            foreach (MergedSegment ms in mergedSegments) if ((tmp = ms.CalculateMeshEdge()) != null) meshEdges.Add(tmp);
        }
    }
}

---