/// <summary>
 /// Computes the "stress" of the current layout of the given graph:
 /// 
 ///   stress = sum_{(u,v) in V} D(u,v)^(-2) (d(u,v) - D(u,v))^2
 /// 
 /// where:
 ///   V is the set of nodes
 ///   d(u,v) is the euclidean distance between the centers of nodes u and v
 ///   D(u,v) is the graph-theoretic path length between u and v - scaled by average edge length.
 ///   
 /// The idea of “stress” in graph layout is that nodes that are immediate neighbors should be closer 
 /// together than nodes that are a few hops apart (i.e. that have path length>1).  More generally 
 /// the distance between nodes in the drawing should be proportional to the path length between them.  
 /// The lower the “stress” score of a particular graph layout the better it conforms to this ideal.
 /// 
 /// </summary>
 /// <param name="graph"></param>
 /// <returns></returns>
 public static double Stress(GeometryGraph graph)
 {
     ValidateArg.IsNotNull(graph, "graph");
     double stress = 0;
     if (graph.Edges.Count == 0)
     {
         return stress;
     }
     var apd = new AllPairsDistances(graph, false);
     apd.Run();
     var D = apd.Result;
     double l = graph.Edges.Average(e => e.Length);
     int i = 0;
     foreach (var u in graph.Nodes)
     {
         int j = 0;
         foreach (var v in graph.Nodes)
         {
             if (i != j)
             {
                 double duv = (u.Center - v.Center).Length;
                 double Duv = l * D[i][j];
                 double d = Duv - duv;
                 stress += d * d / (Duv * Duv);
             }
             ++j;
         }
         ++i;
     }
     return stress;
 }

        internal static void RankGraph(LgData lgData, GeometryGraph mainGeometryGraph) {
//fromDrawingToEdgeInfo = new Dictionary<ICurve, LgEdgeInfo>();
            foreach (var connectedGraph in lgData.ConnectedGeometryGraphs)
                RankTheGraph(lgData, mainGeometryGraph, connectedGraph);

            UpdateRanksOfClusters(lgData);
        }

        /// <summary>
        /// create a geometry edge, the geometry source and target have to be set already
        /// </summary>
        /// <param name="drawingEdge"></param>
        /// <param name="msaglGraph"></param>
        /// <returns></returns>
        static Core.Layout.Edge CreateGeometryEdgeAndAddItToGeometryGraph(Edge drawingEdge, GeometryGraph msaglGraph) {
            var msaglEdge = CreateGeometryEdgeFromDrawingEdge(drawingEdge);

            msaglGraph.Edges.Add(msaglEdge);
            
            return msaglEdge;
        }

        /// <summary>
        /// Computes the standard deviation of the edge length change for a set of given edges.
        /// </summary>
        /// <param name="graphOld"></param>
        /// <param name="graphNew"></param>
        /// <param name="proximityEdges"></param>
        /// <returns></returns>
        public static Tuple<String, double> EdgeLengthDeviation(GeometryGraph graphOld, GeometryGraph graphNew,
                                                 HashSet<Tuple<int, int>> proximityEdges)
        {
            if (proximityEdges.Count == 0) return Tuple.Create("EdgeLengthDeviation", -1.0);
            double meanRatio = 0;
            foreach (Tuple<int, int> p in proximityEdges) {
                double oldDist=(graphOld.Nodes[p.Item1].Center - graphOld.Nodes[p.Item2].Center).Length;
                double newDist = (graphNew.Nodes[p.Item1].Center - graphNew.Nodes[p.Item2].Center).Length;

                double ratio = newDist/oldDist;
                meanRatio += ratio;

            }
            meanRatio /= proximityEdges.Count;

            double standardDeviation = 0;
            foreach (Tuple<int, int> p in proximityEdges) {
                double oldDist = (graphOld.Nodes[p.Item1].Center - graphOld.Nodes[p.Item2].Center).Length;
                double newDist = (graphNew.Nodes[p.Item1].Center - graphNew.Nodes[p.Item2].Center).Length;

                double deviation = (newDist / oldDist)-meanRatio;
                deviation = deviation * deviation;

                standardDeviation += deviation;

            }
            standardDeviation = Math.Sqrt(standardDeviation/proximityEdges.Count)/meanRatio;

            return Tuple.Create("ProximityEdgeLengthDeviation",standardDeviation);
        }

        internal ConstrainedOrdering(
            GeometryGraph geomGraph,
            BasicGraph<Node, IntEdge> basicIntGraph,
            int[] layering,
            Dictionary<Node, int> nodeIdToIndex,
            Database database,
            SugiyamaLayoutSettings settings) {

            this.settings = settings;
            horizontalConstraints = settings.HorizontalConstraints;

            horizontalConstraints.PrepareForOrdering(nodeIdToIndex, layering);

            geometryGraph = geomGraph;
            this.database = database;
            intGraph = basicIntGraph;
            initialLayering = layering;
            //this has to be changed only to insert layers that are needed
            if (NeedToInsertLayers(layering)) {
                for (int i = 0; i < layering.Length; i++)
                    layering[i] *= 2;
                LayersAreDoubled = true;
                numberOfLayers = -1;
            }

            PrepareProperLayeredGraphAndFillLayerInfos();

            adjSwapper = new AdjacentSwapsWithConstraints(
                LayerArrays,
                HasCrossWeights(),
                ProperLayeredGraph,
                layerInfos);
        }

        public static GeometryGraph CopyGraph(GeometryGraph graph)
        {
            if (graph == null) return null;
            var copy = new GeometryGraph();

            Dictionary<Node,Node> nodeCopy=new Dictionary<Node, Node>(graph.Nodes.Count);

            foreach (Node node in graph.Nodes) {
                var c = new Node();
                copy.Nodes.Add(c);
                nodeCopy[node] = c;
                c.BoundaryCurve = node.BoundaryCurve.Clone();
            }

            foreach (Edge edge in graph.Edges) {
                var source = edge.Source;
                var target = edge.Target;
                var copySource = nodeCopy[source];
                var copyTarget = nodeCopy[target];
                Edge edgeCopy=new Edge(copySource,copyTarget);
                copy.Edges.Add(edgeCopy);
                StraightLineEdges.RouteEdge(edgeCopy,0);
            }

            return copy;
        }

        internal static GeometryGraph CreateAndLayoutGraph()
        {
            double w = 30;
            double h = 20;
            GeometryGraph graph = new GeometryGraph();
            Node a = new Node( new Ellipse(w, h, new P()),"a");
            Node b = new Node( CurveFactory.CreateRectangle(w, h, new P()),"b");
            Node c = new Node( CurveFactory.CreateRectangle(w, h, new P()),"c");
            Node d = new Node(CurveFactory.CreateRectangle(w, h, new P()), "d");

            graph.Nodes.Add(a);
            graph.Nodes.Add(b);
            graph.Nodes.Add(c);
            graph.Nodes.Add(d);
            Edge e = new Edge(a, b) { Length = 10 };
            graph.Edges.Add(e);
            graph.Edges.Add(new Edge(b, c) { Length = 3 });
            graph.Edges.Add(new Edge(b, d) { Length = 4 });

            //graph.Save("c:\\tmp\\saved.msagl");
            var settings = new Microsoft.Msagl.Layout.MDS.MdsLayoutSettings();
            LayoutHelpers.CalculateLayout(graph, settings, null);

            return graph;
        }

        /// <summary>
        /// Generate lattice graph with given number of nodes
        /// </summary>
        /// <returns>A graph with lattice pattern</returns>
        public static GeometryGraph GenerateSquareLattice(int nodeCount) {
            GeometryGraph graph = new GeometryGraph();

            int nodesOnOneEdge = (int)Math.Ceiling(Math.Sqrt(nodeCount));

            for (int i = 0; i < nodesOnOneEdge; i++) {
                for (int j = 0; j < nodesOnOneEdge; j++) {
                    Node node = CreateNode(graph.Nodes.Count.ToString(CultureInfo.InvariantCulture));

                    graph.Nodes.Add(node);

                    if (i > 0) {
                        List<Node> allNodes = graph.Nodes.ToList();
                        Node sourceNode = allNodes[(graph.Nodes.Count - 1) - nodesOnOneEdge];
                        Node targetNode = allNodes[graph.Nodes.Count - 1];
                        Edge edge = CreateEdge(sourceNode, targetNode);
                        graph.Edges.Add(edge);
                    }

                    if (j > 0) {
                        List<Node> allNodes = graph.Nodes.ToList();
                        Node sourceNode = allNodes[graph.Nodes.Count - 2];
                        Node targetNode = allNodes[graph.Nodes.Count - 1];
                        Edge edge = CreateEdge(sourceNode, targetNode);
                        graph.Edges.Add(edge);
                    }
                }
            }

            return graph;
        }

        public void SimpleDeepTranslationTest()
        {
            var graph = new GeometryGraph();
            var a = new Node(CurveFactory.CreateRectangle(30, 20, new Point()));
            var b = new Node(CurveFactory.CreateRectangle(30, 20, new Point(100, 0)));
            var e = new Edge(a, b);
            graph.Nodes.Add(a);
            graph.Nodes.Add(b);
            graph.Edges.Add(e);
            var c = CreateCluster(new Node[] { a, b }, 10);
            c.CalculateBoundsFromChildren(0);
            var originalClusterBounds = c.BoundingBox;
            RouteEdges(graph, 10);
            var edgeBounds = e.BoundingBox;

            Assert.AreEqual(c.BoundingBox.Width, 150, "Cluster has incorrect width");
            Assert.AreEqual(c.BoundingBox.Height, 40, "Cluster has incorrect width");

            var delta = new Point(10, 20);
            c.DeepTranslation(delta, true);
            Rectangle translatedClusterBounds = c.BoundingBox;

            Assert.IsTrue(ApproximateComparer.Close((translatedClusterBounds.LeftBottom - originalClusterBounds.LeftBottom), delta), "edge was not translated");

            c.CalculateBoundsFromChildren(0);

            Assert.IsTrue(ApproximateComparer.Close(translatedClusterBounds, c.BoundingBox), "translated bounds do not equal computed bounds of translated cluster");
            Assert.IsTrue(ApproximateComparer.Close((e.BoundingBox.LeftBottom - edgeBounds.LeftBottom), delta), "edge was not translated");
        }

        static void PostRunTransform(GeometryGraph geometryGraph, PlaneTransformation transformation)
        {
            bool transform = !transformation.IsIdentity;
            if (transform)
            {
                foreach (Node n in geometryGraph.Nodes)
                {
                    n.Transform(transformation);
                }

                //restore labels widths and heights
                foreach (Edge e in geometryGraph.Edges)
                {
                    if (e.Label != null)
                    {
                        e.Label.Width = e.OriginalLabelWidth;
                        e.Label.Height = e.OriginalLabelHeight;
                    }
                }

                TransformCurves(geometryGraph, transformation);
            }

            geometryGraph.UpdateBoundingBox();
        }

        /// <summary>
        /// Calculates the graph layout
        /// </summary>
        /// <exception cref="CancelException">Thrown when the layout is canceled.</exception>
#else
        /// <summary>
        /// Calculates the graph layout
        /// </summary>
        /// <exception cref="System.OperationCanceledException">Thrown when the layout is canceled.</exception>
#endif
        public static void CalculateLayout(GeometryGraph geometryGraph, LayoutAlgorithmSettings settings, CancelToken cancelToken) {
            Console.WriteLine("starting CalculateLayout");
            if (settings is RankingLayoutSettings) {
                var rankingLayoutSettings = settings as RankingLayoutSettings;
                var rankingLayout = new RankingLayout(rankingLayoutSettings, geometryGraph);
                rankingLayout.Run(cancelToken);
                RouteAndLabelEdges(geometryGraph, settings, geometryGraph.Edges);
            }
            else if (settings is MdsLayoutSettings) {
                var mdsLayoutSettings = settings as MdsLayoutSettings;
                var mdsLayout = new MdsGraphLayout(mdsLayoutSettings, geometryGraph);
                mdsLayout.Run(cancelToken);
                if (settings.EdgeRoutingSettings.EdgeRoutingMode != EdgeRoutingMode.None)
                    RouteAndLabelEdges(geometryGraph, settings, geometryGraph.Edges);
            }
            else if (settings is FastIncrementalLayoutSettings) {
                var incrementalSettings = settings as FastIncrementalLayoutSettings;
                incrementalSettings.AvoidOverlaps = true;
                var initialLayout = new InitialLayout(geometryGraph, incrementalSettings);
                initialLayout.Run(cancelToken);
                if (settings.EdgeRoutingSettings.EdgeRoutingMode != EdgeRoutingMode.None)
                    RouteAndLabelEdges(geometryGraph, settings, geometryGraph.Edges);
                //incrementalSettings.IncrementalRun(geometryGraph);
            }
            else {
                var sugiyamaLayoutSettings = settings as SugiyamaLayoutSettings;
                if (sugiyamaLayoutSettings != null)
                    ProcessSugiamaLayout(geometryGraph, sugiyamaLayoutSettings, cancelToken);
                else {
                    Debug.Assert(settings is LgLayoutSettings);
                    LayoutLargeGraphWithLayers(geometryGraph, settings, cancelToken);
                }
            }
        }

 private void ChangeShapes(GeometryGraph g)
 {
     foreach(var n in g.Nodes){
         var box=n.BoundaryCurve.BoundingBox;
         n.BoundaryCurve = new Ellipse(20, 20, n.Center);
     }
 }

 /// <summary>
 /// Constructor
 /// </summary>
 /// <param name="streamPar">the stream to write the graph into</param>
 /// <param name="graphP">the graph</param>
 /// <param name="settings">The settings to be written.</param>
 public GeometryGraphWriter(Stream streamPar, GeometryGraph graphP, LayoutAlgorithmSettings settings) {
     stream = streamPar;
     Graph = graphP;
     Settings = settings;
     var xmlWriterSettings = new XmlWriterSettings {Indent = true};
     XmlWriter = XmlWriter.Create(stream, xmlWriterSettings);
     EdgeEnumeration = graphP.Edges;
 }

 /// <summary>
 /// Gives each label a size.
 /// By default they don't have a size so we must fill it in.
 /// </summary>
 private static void AddLabelSizes(GeometryGraph graph)
 {
     foreach (Label label in graph.CollectAllLabels())
     {
         label.Width = 30;
         label.Height = 15;
     }
 }

        internal static void FixBoundingBox(GeometryGraph component, LayoutAlgorithmSettings settings)
        {
            // Pad the graph with margins so the packing will be spaced out.
            component.Margins = settings.ClusterMargin;
            component.UpdateBoundingBox();

            // Zero the graph
            component.Translate(-component.BoundingBox.LeftBottom);
        }

 ///<summary>
 ///</summary>
 ///<param name="geomGraph"></param>
 static public void ShowGraph(GeometryGraph geomGraph) {
     var graph = new Graph();
     geomGraph.UpdateBoundingBox();
     var bb = geomGraph.BoundingBox;
     bb.Pad(geomGraph.Margins);
     geomGraph.BoundingBox = bb;
     BindGeomGraphToDrawingGraph(graph, geomGraph);
     DisplayGraph(graph, new Form());
 }

        ///<summary>
        ///</summary>
        ///<param name="graph"></param>
        ///<param name="geomGraph"></param>
        static public void BindGeomGraphToDrawingGraph(Graph graph, GeometryGraph geomGraph) {
            graph.GeometryGraph = geomGraph;
            var nodeIds = new Dictionary<GeomNode, string>();
            BindNodes(graph, geomGraph, nodeIds);

            BindClusters(graph, geomGraph, nodeIds);

            BindEdges(graph, geomGraph, nodeIds);
        }

 internal DeviceIndependendZoomCalculatorForNodes(
     Func<Node, LgNodeInfo> nodeToLgNodeInfo, GeometryGraph graph, LgLayoutSettings settings, int maxAmountPerTile)
 {
     NodeToLgNodeInfo = nodeToLgNodeInfo;
     this.maxAmountPerTile = maxAmountPerTile;
     Graph = graph;
     Settings = settings;
     unassigned = graph.Nodes.Count;
 }

 GeometryGraph FillGraph(GeometryGraph geometryGraph) {
     ProcessNodes(geometryGraph);
     if (drawingGraph.RootSubgraph != null) {
         geometryGraph.RootCluster = ProcessSubGraphs(drawingGraph.RootSubgraph);
         geometryGraph.RootCluster.GeometryParent = geometryGraph;
     }
     ProcessEdges(geometryGraph);
     ProcessGraphAttrs(drawingGraph, geometryGraph, drawingGraph.LayoutAlgorithmSettings);
     return geometryGraph;
 }

 /// <summary>
 /// 
 /// </summary>
 /// <param name="pushingNodes">the nodes are already at the correct positions</param>
 /// <param name="graph"></param>
 /// <param name="layoutSettings"></param>
 public IncrementalDragger(IEnumerable<GeomNode> pushingNodes, GeometryGraph graph, LayoutAlgorithmSettings layoutSettings) {
     this.graph = graph;
     this.nodeSeparation = layoutSettings.NodeSeparation;
     this.layoutSettings = layoutSettings;
     pushingNodesArray = pushingNodes as GeomNode[] ?? pushingNodes.ToArray();
     Debug.Assert(pushingNodesArray.All(n => DefaultClusterParent(n) == null) ||
                   (new Set<GeomNode>(pushingNodesArray.Select(n => n.ClusterParents.First()))).Count == 1,
                             "dragged nodes have to belong to the same cluster");
     InitBumperPushers();
 }